Optimal synthesis of arbitrary switching functions with regular arrays of 2-input, 1-output switching elements

Not all switching functions are realizable by a single cascade of 2- input, 1-output switching elements, even if repeated inputs are allowed. However, arrays of such cascades feeding a single collector cascade of AND or OR cells can be used to synthesize any function. This paper is concerned with optimal array realizations of this form. A procedure is given which allows one to generate rather efficiently all prime cascade realizable functions which imply a given switching function. These prime functions may be restricted to those realizable by a single cascade either with or without repeated inputs. To solve problems of optimal single output array synthesis, allowing incompletely specified functions, it is necessary only to select a minimum cost cover from the set of prime cascade realizable functions. Each function used in the cover may be realized very easily, and the resulting cascades supply the inputs to the collector cascade. Extensions are made to the simultaneous realization of several switching functions, each the output of a separate collector cascade fed from the same array.