Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexity of Programmable Logic Arrays

Generalized Boolean functions are shown to be useful for the design of programmable logic arrays (PLA´s), and the complexity of three types of PLA´s is obtained by the theory of multiple- valued decomposition. A two-level PLA consists of an AND array and an OR array, and they are cascaded to perform a two-level AND-OR circuit. A PLA with decoders consists of decoders, an AND array, and an OR array. A three-level PLA consists of a D array, an AND array, and an OR array, and they are cascaded to perform a three-level OR- AND-OR circuit. It is shown that a generalized Boolean function f(X1, X2,··, Xr):X Bni → B, where B = {0,1}, is represented by a generalized Boolean expression of 2ⁿⁱ-valued variables Xi; and f can be directly realized by a PLA with decoders or a three-level PLA. To realize a function of n-variables (n = 2r), the following sizes are shown to be sufficient: for a two-level PLA, (n + ½) 2ⁿ; for a PLA with two-bit decoders, 4(n + 4) 2ⁿ; for a three-level PLA, 2ⁿ+ (3n + l)√2ⁿ+ 2n²Especially in the case of PLA with two-bit decoders, the following sizes are shown to be necessary and sufficient: for an arbitrary symmetric function, 3/2(n + ½) √3ⁿ; and for a parity function, (n + ½)√ 2ⁿ.