A New Decomposition Algorithm for Threshold Synthesis and Generalization of Boolean Functions
- 18 April 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems I: Regular Papers
- Vol. 55 (10), 3188-3196
- https://doi.org/10.1109/tcsi.2008.923432
Abstract
A new algorithm for obtaining efficient architectures composed of threshold gates that implement arbitrary Boolean functions is introduced. The method reduces the complexity of a given target function by splitting the function according to the variable with the highest influence. The procedure is iteratively applied until a set of threshold functions is obtained, leading to reduced depth architectures, in which the obtained threshold functions form the nodes and a and or or function is the output of the architecture. The algorithm is tested on a large set of benchmark functions and the results compared to previous existing solutions, showing a considerable reduction on the number of gates and levels of the obtained architectures. An extension of the method for partially defined functions is also introduced and the generalization ability of the method is analyzed.Keywords
This publication has 31 references indexed in Scilit:
- Generalization ability of Boolean functions implemented in feedforward neural networksNeurocomputing, 2006
- The influence of oppositely classified examples on the generalization complexity of Boolean functionsIEEE Transactions on Neural Networks, 2006
- Generalization properties of modular networks: implementing the parity functionIEEE Transactions on Neural Networks, 2001
- Training digital circuits with Hamming clusteringIEEE Transactions on Circuits and Systems I: Regular Papers, 2000
- Programmable neural logicIEEE Transactions on Components, Packaging, and Manufacturing Technology: Part B, 1998
- R-MINI: An iterative approach for generating minimal rules from examplesIEEE Transactions on Knowledge and Data Engineering, 1997
- A Fast Partitioning Algorithm and a Comparison of Binary Feedforward Neural NetworksEurophysics Letters, 1992
- A training algorithm for binary feedforward neural networksIEEE Transactions on Neural Networks, 1992
- Depth-size tradeoffs for neural computationInternational Conference on Acoustics, Speech, and Signal Processing (ICASSP), 1991
- Learning in feedforward layered networks: the tiling algorithmJournal of Physics A: General Physics, 1989