Abstract:
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 th...Show MoreMetadata
Abstract:
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 2ni-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 + ½) 2n; for a PLA with two-bit decoders, 4(n + 4) 2n; for a three-level PLA, 2n+ (3n + l)√2n+ 2n2Especially 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 + ½) √3n; and for a parity function, (n + ½)√ 2n.
Published in: IEEE Transactions on Computers ( Volume: C-30, Issue: 9, September 1981)