On Tree Circuits

This article is primarily concerned with means for finding economical tree circuit realizations¿iterative applications of decompositions f(xn, xn-1,..., x1) = Fi(Gi(xn, xn-1,..., x¿i,..., x1), Hi,(xn, xn-1,..., x¿i,..., x1), xi) and their associated circuitry¿for Boolean functions f(xn, xn-1,..., x1). A uniform estimate or inequality shows that when synthesis is effected with two-input-per-gate circuitry, tree circuits are preferable to those which result from conventional sum of products techniques. The practical significance of the estimate is illustrated by its application to the tree circuit synthesis problem. The relationship of tree circuit theory to decomposition theory is established and the extension of the present theory to the corresponding multiple-output and incompletely-specified problems is indicated.