Generalized Tree Circuit—The Basic Building Block of an Extended Decomposition Theory
Generalized Tree Circuit—The Basic Building Block of an Extended Decomposition Theory
复制标题
广义树电路——扩展分解理论的基本构件
DOI：
10.1145/321186.321202
复制
发表时间：
1963
期刊：
影响因子：
--
通讯作者：
H. Allen Curtis
中科院分区：
文献类型：
--
作者：
H. Allen Curtis
在[1]和[2]中，该作者开发了一种算法，用于以树状CH的形式合成形式的切换电路：〜ra仪 - 差异化的树回路。交换功能对应于此类树电路，以F（x L，x：,。。。。，x，〜）的形式= f [（zt（xl，x：,,： 。 <k，所有后续的亚功能都采用类似的形式。阈值和阈值的特性。 [1]的定理2说明了整个纸张的存在所需的条件。该定理中现在被重新列为定理0，给出了：定理。 ），b] i f a n d o n l y i f i t s 2 tm x 2 e〜i i m a t r i x h a s s最多2〜d i s t i s t i n c t c t c o l u m n载体。对于k = 0或1的[1]，定理在简单分解分解，切换函数分解的瓷砖基本定理上，定理将其简化为R. L. Ashenhurst的第一个定理[4]。在这种情况下，复合函数是切换函数f（a，b）的简单分析性分解。 Ashenhurst [4]使用简单的分解分解作为基本的构建块，制定了他重要的复杂分解分解理论。该理论的自然产物是一种系统的程序，用于检测和构建任何开关函数的复杂分解分解术。 Ashenhurst在制定他的理论时建立了五个基本定理。这样做的自然猜想是：如果普遍的树回路形式是简单的不重分解的概括，那么是否可以用广义的树回路来开发复杂分解的扩展理论，因为基本 *接收到了。 1962年8月。562分解理论中的基因脉电路563构建基块？此外，是否可以从Ashenhurst的五个基本定理的直接扩展中发展出这种理论似乎是不合理的吗？现在，基于上述猜想进行了复杂分解的扩展理论的发展。 KARP对[1]的算法的建设性批评引起了这种发展的动机。扩展的分解理论应提供对算法进行所需改进的手段。如此精制的算法应该具有某种实际意义，罪过，广义的树回路形式包含一类宽类的分解（如KARP [3]指出）；而分离分解类相对较小。此外，它希望这种分离分解理论的概括的表述将为该领域的其他人提供更多的见解，从而使他们能够开发新的理论和方法。 2。尝试扩展Ashenhurst的基本定理之前的基本定理，很方便地注意分解图的一些有用的属性。 [1]表明，分解图是开关函数矩阵表示的实际形式。此后，图表和矩阵将互换使用。同样[1]显示开关函数的部分扩展与其矩阵表示之间的对应关系。交换函数F（a，b，c）的部分扩展围绕变量B为2 [b] _l f（a，b，c）= 〜f（a，j，c）pi（b），其中功能F（A，J，C）对应于具有2个EEL行和2个LA]列的2个EZJ图。这些图表由m/在下面的内容中给出。如果这些图表并排放置，它们会形成c i ba分解图ba c mol v，i ... ira's-，1。同样，如果它们放在另一个上方，则它们形成BC我的图表
In [1] and [2] this author developed an algorithm for the synthesis of switching circuits in forms with tree-like ch:~raeteristies--generalized tree circuits. Switching functions corresponding to such tree circuits take the form f ( x l , x : , . . . , x,~) = F[(zt(xl , x: , . . . , x j ) , 42(:cl , x~, . . . , x j ) , . . . , ~ ( x ~ , x2 , . . , x j ) , x~+~ , . . . , z,], where the subfunctions 4,~, 1 -< i -< k, and all succeeding subfunctions assume similar forms. R. Karp [3] refined the algorithm by developing methods for choosing the "best" set of subfunctions ~ from a large possible set on the basis of their disjoint decomposition, symmetric, unate, and threshold strueturM properties. The primary objective of the present paper is to improve further the algorithm. Another objective, a by-product of the first, but possibly a more important one, is to extend the theory of functional decomposition. 1. I n t r o d u c t i o n Theorem 2 of [1] states the conditions required for the existence of a generalized tree circuit. I t is assumed throughout the present paper tha t the reader has a full knowledge of [1] and its notation. However, for handy reference the statement of this theorem, now renumbered to Theorem 0, is given: THEOREM O. A s w i t c h i n g f u n c t i o n f ( A , B ) i s e x p r e s s i b l e as a c o m p o s i t e func t ion F[ol(A) , 4~2(A), --" , dpk(A), B] i f a n d o n l y i f i t s 2 TM X 2 E~I m a t r i x h a s at most 2 ~ d i s t i n c t c o l u m n vectors. I t was noted in [1] tha t for k = 0 or 1 the theorem reduces to R. L. Ashenhurst 's first theorem [4] on simple disjunctive decompositions, tile fundamental theorem of the decomposition of switching functions. In such a case the composite function is a simple disjunctive decomposition of the switching function f(A, B). Ashenhurst [4] using the simple disjunctive decomposition as the basic building block, formulated his impor tant theory of complex disjunctive decompositions. A natural outgrowth of this theory was a systematic procedure for the detection and construction of the complex disjunctive decomposition s tructure of any switching function. Ashenhurst established five fundamental theorems on complex disjunctive decompositions in formulating his theory. A natural conjecture to make then is the following: if the generalized tree circuit form is a generalization of the simple disiunctive decomposition, is it not reasonable tha t an extended theory of complex decompositions could be developed with the generalized tree circuit as the basic * Received August, 1962. 562 GENEIIALIZED TREE CIRCUIT IN DECOMPOSITION THEORY 563 building block? Moreover, does it not appear plausible that such a theory could be developed from straightforward extensions of Ashenhurst's five fundamental theorems? The development of an extended theory of complex decompositions is now undertaken based on the above conjecture. The motivation for this development was prompted by Karp's [3] constructive criticisms of the algorithm of [1]. The extended decomposition theory should provide the means of making needed refinements to the algorithm. The thus-refined algorithm should be of some practical significance, sines the generalized tree circuit form encompasses a wide class of decompositions (as noted by Karp [3]); whereas the class of disjunctive decompositions is relatively small. It is, furthermore, hoped that the formulation of this generalization of the disjunctive decomposition theory will provide others in this field with added insight, enabling them to develop new theories and methods of approach. 2. Fundamental Theorems Before an attempt is made to extend Ashenhurst's fundamental theorems, it is convenient to note some useful properties of decomposition charts. It was shown [1] that a decomposition chart was a practical form of a matrix representation of a switching function. Henceforth charts and matrices will be used interchangeably. Also [1] the correspondence between a partial expansion of a switching function and its matrix representation was shown. The partial expansion of a switching function f(A, B, C) about the variables B is 2[B]_l f(A, B, C) = ~ f(A, j, C)pi(B), where the functions f(A, j, C) correspond to 2 Ezj charts having 2 Eel rows and 2 LA] columns. These charts are given by M/ in what follows. If these charts are placed side by side, they form the C I BA decomposition chart BA c Mol V,I... Ira'"s-,1. Similarly, if they are placed one on top of the other, they form the BC I A chart