Generalized Tree Circuit—The Basic Building Block of an Extended Decomposition Theory

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(xl, x:, ... , x,~) = F[(zt(xl, x: , ... , xj), 42(:cl , x~, ... , xj), ... , ~(x~ , x2 , ..-, xj), 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.