COATES GRAPH APPROACH FOR GENERATING SYMBOLIC NETWORK FUNCTION

In this paper, symbolic code matrix ,constant matrix and count matrix are defined .The first twomatrices are used to describe the elemental expression of augmented matrix and the nede admittance equa-tion is thus obtained. The third matrix is used to obtain the incoming degree matrix, and according to thematrix all the 1- factors of the Coates graph are given. By using the data code, the determinant is expandedand the same items in the expansion are merged. Thus the symbolic network function in which no term can-cellation occurs is generated.     

平面化图的哈密顿圈的产生

本文提出如何利用修正的王氏积产生平面化图的全部哈密顿圈。这种方法较以前的计算简单得多。它的计算步骤在文中以举例的方式作了说明。为了保证算法的正确,导出了一个2-树是2-顶点树的充要条件。     

AN ALGORITHM OF K-LINE LOCATION FOR BBL IN LSI/VLSI

In this paper,a K-line location algorithm for building block cells in LSI/VLSI ispresented.When the relative positions of rectangular cells are given,there are 2 states accordingto the two orientations of a cell.It is proved that to find the optimum solution from the 2~N statescan be reduced to calculate the N states in K-line algorithm.So the algorithm is shown veryeffective and can be used with association for cluster method in BBL placement.Under certainconditions,this method can also be used to pesudo BBL placement directly.     

关于产生哈密顿圈的定理及其应用

作者曾提出利用王氏代数产生图的全部哈密顿圈,本文继续研究了这种算法。为了简化计算,给出一个关于王积度数约束的定理,为了避免算法中的不必要的重复,提出一种改进的方法。 最后讨论了本算法在布线设计中的应用等。     

产生全符号网络函数的Coates流图法

本文引入符号码数组、常数数组和记数数组,前二数组用来描述增广矩阵的元素表达式,建立节点导纳方程,后一数组用来写出入度矩阵,然后根据入度矩阵产生Coates流图的全部1-因子增益。在展开行列式时利用符号代码合并同类项,消去相消项,从而得到无相消项的全符号网络函数。     

基于群法的BBL布局算法研究

本文对BBL结群及其在布局中的应用进行了研究。提出了表示群内单元位置关系的点结构模型、扩展的点结构模型、图模型及方位树模型;导出了计算单元数为n的群的全部点结构(或方位树)数及布局方式数的公式;证明了(扩展的)点结构模型与(扩展的)方位树模型的一一对应关系;提出了适用于Floor Plan及自顶向下布局法的限定高度的结群算法及适用于自底向上等布局法的最小冗余比结群法,并提出了递归结群法。本布局法可产生Slicing及Nonslicing二种布局结构。以上算法均已在UNIVAC 1100/10机上用Fortran 77实现,结果是令人满意的。     

关于Coates图的1-因子的算法

本文是作者1982年一文的继续,根据该文使用星积产生1-因子的定理,我们先讨论了一类特殊图,阐明星积和求排列的关系,然后推广到一般情况。最后,给出求Coates图的1-因子的算法。     

ON THE THEOREM OF GENERATING HAMILTON CIRCUITS AND ITS APPLICATIONS

The study of the algorithm by the author for generating all the Hamilton circuits in a graph bya method of Wang algebra is continued.In order to simplify the algorithm,a theorem of the constraintof degrees in the Wang's product is presented and for avoiding unnecessary repetitions in the algorithmsome modified procedures are given.Finally,the application of the algorithm in layout design is discussed.