On the size of PLA's required to realize binary and multiple-valued functions
Bender, Edward A.
Butler, Jon T.
MetadataShow full item record
While the use of programmable logic arrays in modern logic design is common, little is known about what PLA size provides reasonable coverage in typical applications. We address this question by showing upper and lower bounds on the average number of product terms required in the minimal realization of binary and multiple-valued functions as a function of the number of nonzero output values. When the number of such values is small, the bounds are nearly the same, and accurate values for the average are obtained. In addition, an upper bound is derived for the variance of the distribution of the number of product terms required in minimal realizations of binary functions. When the number of nonzero values is small, we find that the variance is small, and it follows that most functions require nearly the average number of product terms. The variance, in addition to the upper and lower bounds, allow conclusions to be made about how PLA size determines the set of realizable functions. Although the bounds are most accurate when there are few nonzero values, they are adequate for analyzing commercially available PLA’s, which we do in this paper. Most such PLA’s are small enough that our results can be applied. For example, when the number of nonzero values exceeds some threshold uT, determined by the PLA size, only a small fraction of the functions can be realized. Our analysis shows that for all but one commercially available PLA, the number of nonzero values is a statistically meaningful criteria for determining whether or not a given function is likely to be realized.
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.IEEE Transactions on Computers, C-38, Jan. 1989, pp. 82-98, 1988
Showing items related by title, author, creator and subject.
Sasao, Tsutomu; Matsuura, Munehiro; Butler, Jon T. (2005-09);The traditional problem in binary decision diagrams (BDDs) has been to minimize the number of nodes since this reduces the memory needed to store the BDD. Recently, a new problem has emerged: minimizing the average path ...
Tirumalai, Parthasarathy; Butler, Jon T. (1991-02);We analyze the performance of various heuristic algorithms for minimizing realizations of multiple-valued functions by the newly developed CCD 191 and CMOS [W] programmable logic arrays. The functions realized by ...
On the Properties of Multiple-Valued Functions that are Symmetric in Both Variable Values and Labels Butler, Jon T.; Sasao, Tsutomu (Monterey, California. Naval Postgraduate School, 1997-12); NPS-EC-97-015Functions that are symmetric in both variable labels and variable values are important for use as benchmarks. We present the properties of such functions, showing that they are isomorphic to partitions on r (the number ...