Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Complexity of XOR/XNOR boolean functions: a model using binary decision diagrams and back propagation neural networks
Keywords:
Binary Decision Diagrams (BDDs), Reduced Ordered Binary Decision diagrams (ROBDDs), XOR/XNOR min-terms, Complexity, Boolean FunctionsAbstract
This paper proposes a model that predicts the complexity of Boolean functions with only XOR/XNOR min-terms using back propagation neural networks (BPNNs) applied to Binary Decision Diagrams (BDDs). The BPNN model (BPNNM) is developed through the training process of experimental data already obtained for XOR/XNOR-based Boolean functions. The outcome of this model is a unique matrix for the complexity estimation over a set of BDDs derived from Boolean expressions with a given number of variables and XOR/XNOR min-terms. The comparison results of the experimental and BPNNM underline the efficiency of this approach, which is capable of providing some useful clues about the complexity of the circuit to be implemented. It also proves the computational capabilities of NNs in providing reliable classification of the complexity of Boolean functions.
Downloads
Download data is not yet available.
References
[1] G. E. Moore, “ Progress in Digital Integrated Electronics,” IEEE IEDM, 1975, pp. 11-13.
[2] K.S. Brace, R.L. Rudell and R.E. Bryant, “Efficient implementation of a BDD package,” 27th ACM IEEE Design Automation Conference 1990. pp. 40-45.
[3] Wegener, The Complexity of Boolean Functions,. John Wiley and Sons Ltd, 1987
[4] C. Meinel and A. Slobodova, “On the Complexity ofconstructing Optimal Ordered Binary Decision diagrams,” Proc. of 19th Inter. Symposium on Mathematical Foundation of Computer Science, 1994, pp.515-524.
[5] F. Somenzi, “Efficient manipulation of decision diagrams,” Intl. J. Software Tools for Technology Transfer, (STTT), 2001, pp. 171-181.
[6] K. Priyank, “VLSI Logic Test, Validation and Verification, Properties & Applications of Binary Decision Diagrams,” Lecture Notes, Department of Electrical and Computer Engineering University of Utah, Salt Lake City, UT 84112.
[7] S. B. Akers, “Binary Decision Diagram,” IEEE Trans. Computers, Vol. 27, 1978, pp. 509-516.
[8] R.E. Bryant, “Graph-based algorithm for booleanfunction manipulation,” IEEE Transaction on Computers, 1986, pp. 677-691.
[9] S. Minato, Binary Decision diagrams and Applications for VLSICAD. Kluwer Academic Publishers, Dordrecht, 1995.
[10] J.E. Harlow, and F. Brglez, “Design of experimentsand evaluation on of BDD ordering heuristics,” Intl. J. Software Tools for Tech. Transfer., 3: 2001, pp.193-206.
[11] K. Priyank, “VLSI Logic Test, Validation and Verification, Properties & Applications of Binary Decision Diagrams,” Lecture Notes, Department of Electrical and Computer Engineering University of Utah, Salt Lake City, UT 84112.
[12] K. Y Siu, V. P. Roychowdhury, and T. Kailath, “ Discrete Neural Computation – A theoretical Foundation,” Prentice Hall, 1995.
[13] T. Masters, Signal and Image Processing with Neural Networks, John Wiley & Sons, Inc., 1994.
[14] M. Caudill, AI Expert: Neural Network Primer,Miller Freeman Publications, 1990.
[15] I. Parberry, Circuit Complexity and Neural Networks, MIT Press, 1994.
[16] M. Raseen, P.W.C. Prasad, S.M.N.A.Senanayake, “XOR/XNOR Functional Behaviour on ROBDD Representation,” Proc. of the 14th IASTED Conference on Applied simulation and Modelling (ASM), 2005, pp. 115-119
[17] R. E. Uhrig, “Introduction to Artificial Neural Networks,” Proceedings of the 1995 IEEE IECON 21st International Conference on Industrial Electronics, Control and Instrumentation, Vol. 1, 1995, pp. 33-37.
[18] K.Yale, “Preparing the right data for training neural networks,” IEEE Spectrum, Vol. 34, Issue 3, 1997, pp. 64-66.
[19]G. Stegmayer, and O. Chiotti, “The Volterra representation of an electronic device using the Netural Network parameters,” Latin American Conference on Informatics (CLEI’2004), 2004.
[20] http://www.eco.utexas.edu/faculty/Kendrick/frontpg /NeuralNets.htm
[21] M. Raseen, P.W.C.Prasad, and A.Assi, “ An Efficient Estimation of the ROBDD's Complexity,” Integration, the VLSI Journal, Volume 39, Issue 3, 2006, pp. 211-228.
[2] K.S. Brace, R.L. Rudell and R.E. Bryant, “Efficient implementation of a BDD package,” 27th ACM IEEE Design Automation Conference 1990. pp. 40-45.
[3] Wegener, The Complexity of Boolean Functions,. John Wiley and Sons Ltd, 1987
[4] C. Meinel and A. Slobodova, “On the Complexity ofconstructing Optimal Ordered Binary Decision diagrams,” Proc. of 19th Inter. Symposium on Mathematical Foundation of Computer Science, 1994, pp.515-524.
[5] F. Somenzi, “Efficient manipulation of decision diagrams,” Intl. J. Software Tools for Technology Transfer, (STTT), 2001, pp. 171-181.
[6] K. Priyank, “VLSI Logic Test, Validation and Verification, Properties & Applications of Binary Decision Diagrams,” Lecture Notes, Department of Electrical and Computer Engineering University of Utah, Salt Lake City, UT 84112.
[7] S. B. Akers, “Binary Decision Diagram,” IEEE Trans. Computers, Vol. 27, 1978, pp. 509-516.
[8] R.E. Bryant, “Graph-based algorithm for booleanfunction manipulation,” IEEE Transaction on Computers, 1986, pp. 677-691.
[9] S. Minato, Binary Decision diagrams and Applications for VLSICAD. Kluwer Academic Publishers, Dordrecht, 1995.
[10] J.E. Harlow, and F. Brglez, “Design of experimentsand evaluation on of BDD ordering heuristics,” Intl. J. Software Tools for Tech. Transfer., 3: 2001, pp.193-206.
[11] K. Priyank, “VLSI Logic Test, Validation and Verification, Properties & Applications of Binary Decision Diagrams,” Lecture Notes, Department of Electrical and Computer Engineering University of Utah, Salt Lake City, UT 84112.
[12] K. Y Siu, V. P. Roychowdhury, and T. Kailath, “ Discrete Neural Computation – A theoretical Foundation,” Prentice Hall, 1995.
[13] T. Masters, Signal and Image Processing with Neural Networks, John Wiley & Sons, Inc., 1994.
[14] M. Caudill, AI Expert: Neural Network Primer,Miller Freeman Publications, 1990.
[15] I. Parberry, Circuit Complexity and Neural Networks, MIT Press, 1994.
[16] M. Raseen, P.W.C. Prasad, S.M.N.A.Senanayake, “XOR/XNOR Functional Behaviour on ROBDD Representation,” Proc. of the 14th IASTED Conference on Applied simulation and Modelling (ASM), 2005, pp. 115-119
[17] R. E. Uhrig, “Introduction to Artificial Neural Networks,” Proceedings of the 1995 IEEE IECON 21st International Conference on Industrial Electronics, Control and Instrumentation, Vol. 1, 1995, pp. 33-37.
[18] K.Yale, “Preparing the right data for training neural networks,” IEEE Spectrum, Vol. 34, Issue 3, 1997, pp. 64-66.
[19]G. Stegmayer, and O. Chiotti, “The Volterra representation of an electronic device using the Netural Network parameters,” Latin American Conference on Informatics (CLEI’2004), 2004.
[20] http://www.eco.utexas.edu/faculty/Kendrick/frontpg /NeuralNets.htm
[21] M. Raseen, P.W.C.Prasad, and A.Assi, “ An Efficient Estimation of the ROBDD's Complexity,” Integration, the VLSI Journal, Volume 39, Issue 3, 2006, pp. 211-228.
Downloads
Published
2007-04-02
Issue
Section
Original Articles
License
How to Cite
[1]
“Complexity of XOR/XNOR boolean functions: a model using binary decision diagrams and back propagation neural networks”, JCS&T, vol. 7, no. 02, pp. p. 141–147, Apr. 2007, Accessed: Mar. 06, 2026. [Online]. Available: https://journal.info.unlp.edu.ar/JCST/article/view/784
