Abstract
This paper presents a new and efficient heuristic procedure for determining whether or not a given Boolean function is a threshold function, when the Boolean function is given in the form of a decision diagram. The decision diagram based method is significantly different from earlier methods that are based on solving linear inequalities in Boolean variables that derived from truth tables. This method's success depends on the ordering of the variables in the binary decision diagram (BDD). An alternative data structure, and one that is more compact than a BDD, called a max literal factor tree (MLFT) is introduced. An MLFT is a particular type of factoring tree and was found to be more efficient than a BDD for identifying threshold functions. The threshold identification procedure is applied to the MCNC benchmark circuits to synthesize threshold gate networks.
Original language | English (US) |
---|---|
Article number | 5752412 |
Pages (from-to) | 665-677 |
Number of pages | 13 |
Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Volume | 30 |
Issue number | 5 |
DOIs | |
State | Published - May 2011 |
Keywords
- Binary decision diagrams
- Boolean algebra
- Boolean function
- logic design
- logic optimization
- logic synthesis
- threshold function
- threshold logic
ASJC Scopus subject areas
- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering