On the size of PLA's required to realize binary and multiple-valued functions
Loading...
Authors
Bender, Edward A.
Butler, Jon T.
Subjects
complexity of logic circuits
enumerative analysis
logic design
multiple-valued logic
PLA
programmable logic arrays
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
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