Programmable logic arrays (PLAs) have been popular in the current decade because of their applications in VLSI design. Although the design algorithms have not been developed as far as those using gates, the regularity of structure of PLAs and their ability to realize AND/OR type logic have made them highly useful in logic design. PLA size is very critical in VLSI design and is governed by the AND terms which the logic function contains after it is minimized. The function may be made of variables which are binary or multivalued. Therefore, it becomes important to know the relation between a PLA’s size and the number of functions it can realize.
In the paper under review, the authors address this issue in depth for binary as well as multi-valued functions. They derive lower and upper bounds on the average number of AND terms in the minimal realization of a function as a function of the number of nonzero output values. They also derive an upper bound on the distribution variance of the number of AND terms in a minimized function. They demonstrate how these bounds can relate PLA size to the set of realizable functions, which contain larger numbers of nonzero values. In fact, they suggest that this number is a statistically useful criterion to find whether the given function is realizable using commercial PLAs.
The paper can prove useful to VLSI designers who are looking for useful guidelines for PLA size. Although the paper is mathematical, it is very well written and contains several graphs and illustrative examples.