Publication:
On the size of PLA's required to realize binary and multiple-valued functions

Loading...
Thumbnail Image
Authors
Bender, Edward A.
Butler, Jon T.
Subjects
complexity of logic circuits
enumerative analysis
logic design
multiple-valued logic
PLA
programmable logic arrays
Advisors
Date of Issue
1989-01
Date
Jan. 1989
Publisher
Language
Abstract
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.
Type
Article
Description
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
Series/Report No
Department
Department of Electrical and Computer Engineering
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
On the size of PLA's required to realize binary and multiple-valued functions," IEEE Transactions on Computers, C-38, Jan. 1989, pp. 82-98 1988
Distribution Statement
Rights
Collections