Integrating Fast Karnough Map and Modular Neural Networks for Simplification and Realization of Complex Boolean Functions

Authors: Hazem M. El-Bakry

Abstract:

In this paper a new fast simplification method is presented. Such method realizes Karnough map with large number of variables. In order to accelerate the operation of the proposed method, a new approach for fast detection of group of ones is presented. Such approach implemented in the frequency domain. The search operation relies on performing cross correlation in the frequency domain rather than time one. It is proved mathematically and practically that the number of computation steps required for the presented method is less than that needed by conventional cross correlation. Simulation results using MATLAB confirm the theoretical computations. Furthermore, a powerful solution for realization of complex functions is given. The simplified functions are implemented by using a new desigen for neural networks. Neural networks are used because they are fault tolerance and as a result they can recognize signals even with noise or distortion. This is very useful for logic functions used in data and computer communications. Moreover, the implemented functions are realized with minimum amount of components. This is done by using modular neural nets (MNNs) that divide the input space into several homogenous regions. Such approach is applied to implement XOR function, 16 logic functions on one bit level, and 2-bit digital multiplier. Compared to previous non- modular designs, a clear reduction in the order of computations and hardware requirements is achieved.

Keywords: Boolean functions, simplification, Karnough map, implementation of logic functions, modular neural networks.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1074547

References:

[1] O. Ledion Bitincka, George E. Antoniou, "PDA-based Boolean Function Simplification: A Useful Educational Tool," Informatika, 2004, Vol. 15, no. 3, pp. 329-336.
[2] Ledion Bitincka, George E. Antoniou, "Pocket-PC Boolean Function Simplification," Journal of Electrical Engineering, vol. 56, no. 7-8, 2005, pp. 209-212.
[3] TOMASZEWSKI, S. P.ÔÇöILGAZ, I. U.ÔÇöANTONIOU, G. E. :WWWBased Boolean Function Simplification, International Journal of Mathematics and Computer Science 13 No. 4 (2003), 577-583.
[4] WAKERLY, J. F. : Digital Design, Prentice-Hall, New York, 2000.
[5] NELSON, V. P.ÔÇöNAGLE, H. T.ÔÇöCARROLL, B. D.ÔÇöIRWIN, D. : Digital Logic Circuit Analysis and Design, Prentice-Hall, New Jersey, 1995.
[6] KATZ, R. : Contemporary Logic Design, Benjamin/Cummings Publ, Redwood City, CA, 1994.
[7] BROWN, S.ÔÇöVRANESIC, Z. : Fundamentals of Digital Logic with VHDL, McGraw-Hill, New York, 2003.
[8] HAYES, J. P. : Digital Logic Design, New York, 1993.
[9] KARNAUGH, M.: The Map Method for Synthesis of Com-binatorial Logic Circuits, Trans. AIEE, Communications and Electronics 72 (1953), 593-598.
[10] QUINE, W. V. : The Problem of Simplifying Truth Tables, Am. Math. Monthly 59 No. 8 (1952), 521-531.
[11] McCLUSKEY, E. J. : Minimization of Boolean functions, Bell System Tech. Journal 35 No. 5 (1956), 1417-1444.
[12] GAJSKI, D. D. : Principles of Digital Design, Prentice-Hall, 1997.
[13] CHIRLIAN, P. M. : Digital Circuits with Microprocessor Applications, Matrix Publishers, Oregon, 1982.
[14] HILL, F. J,ÔÇöPETERSON, G. R. : Computer Aided Logical Design with Emphasis on VLSI, Wiley, New York, 1993.
[15] Alan B. Marcovitz, "Introduction to Logic and Computer Design "Hardcover, 2007.
[16] Alan B. Marcovitz, "Introduction to Logic Design," (2nd Economy Edition), Paperback, 2005.
[17] Amy E. Arntson, "Digital Design Basics," Paperback, 2005.
[18] Frank Vahid, " Digital Design," Hardcover, 2006.
[19] Janaye M. Houghton and Robert S. Houghton, "Circuit Sense for Elementary Teachers and Students: Understanding and Building Simple Logic Circuits," Paperback, 1994.
[20] John F. Wakerly, "Digital Design: Principles and Practices Package (4th Edition), Hardcover, 2005.
[21] Mano, Charles Kime, "Logic and Computer Design Fundamentals" (Third Edition), Hardcover, 2003.
[22] Morris M. Mano, Michael D. Ciletti, "Digital Design (4th Edition), Hardcover, 2006.
[23] Morris M. Mano, "Digital Design," Hardcover, 1984.
[24] Morris M. Mano, "Computer System Architecture (3rd Edition)", Hardcover, 1992.
[25] Nripendra N. Biswas, "Computer aided minimization procedure for boolean functions," Proceedings of the 21st conference on Design automation," Albuquerque, New Mexico, United States, Pages: 699 - 702, 1984.
[26] Randal E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Computers, C-35-8, pp. 677-691, August, 1986.
[27] Robert Dueck, "Digital Design with CPLD Applications and VHDL(Digital Design: Principles and Practices Package (2nd Edition), Hardcover, 2004.
[28] Thomas L. Floyd ,"Electronics Fundamentals: Circuits, Devices and Applications" (7 th Edition), Hardcover, 2006.
[29] Thomas L. Floyd, Digital Fundamentals, Hardcover, 1994.
[30] Victor P. Nelson, H. Troy Nagle, Bill D. Carroll, and David Irwin, "Digital Logic Circuit Analysis and Design", Paperback, 1995
[31] William Kleitz, "Digital and Microprocessor Fundamentals: Theory and Application (4th Edition), Hardcover, 2002.
[32] Yves Crama and Peter L. Hammer, "Boolean Functions Theory, Algorithms and Applications", January 22, 2006.
[33] http://www.asic-world.com/digital/kmaps.html, "Simplification of Boolean Functions", 2006.
[34] Hazem M. El-Bakry, and Ahmed Atwan, "Simplification and Implementation of Boolean Functions," International Journal of Universal Computer Sciences, issue 1, vol. 1, 2010, pp. 19-33.
[35] Hazem M. El-bakry, Ahmed Atwan, and Nikos Mastorakis "Aِ New Technique for Realization of Boolean Functions, " Proc. of Recent Advances in Artificial Intelligence, Koweledge Engineering and Databases, Cambridge, UK, February 20-22, 2010, pp. 260-270.
[36] Hazem M. El-bakry, and Nikos Mastorakis "A Fast Computerized Method For Automatic Simplification of Boolean Functions," Proc. of 9th WSEAS International Conference on SYSTEMS THEORY AND SCIENTIFIC COMPUTATION (ISTASC '09), Moscow, Russia, August 26-28, 2009, pp. 99-107.
[37] Hazem M. El-bakry, "Fast Karnough Map for Simplification of Complex Boolean Functions," Proc. of 10th WSEAS International Conference on Applied Computer Science (ACS'10), Japan, October 4- 6, 2010, pp. 478-483.
[38] Hazem M. El-Bakry, "An Efficient Algorithm for Pattern Detection using Combined Classifiers and Data Fusion," Information Fusion Journal, vol. 11, 2010, pp. 133-148..
[39] Hazem M. El-Bakry, "A Novel High Speed Neural Model for Fast Pattern Recognition," Soft Computing Journal, vol. 14, no. 6, 2010, pp. 647-666.
[40] Hazem M. El-Bakry, "Fast Virus Detection by using High Speed Time Delay Neural Networks," Journal of Computer Virology, vol.6, no.2, 2010, pp.115-122.
[41] Hazem M. El-Bakry, "New Fast Principal Component Analysis For Real-Time Face Detection," MG&V Journal, vol. 18, no. 4, 2009, pp. 405-426.
[42] Hazem M. El-Bakry, "A New Neural Design for Faster Pattern Detection Using Cross Correlation and Matrix Decomposition," Neural World journal, 2009, vol. 19, no. 2, pp. 131-164.
[43] Hazem M. El-Bakry and M. Hamada, "A New Implementation for High Speed Neural Networks in Frequency Space," Lecture Notes in Computer Science, Springer, KES 2008, Part I, LNAI 5177, pp. 33-40.
[44] Hazem M. El-Bakry and Mohamed Hamada, " New Fast Decision Tree Classifier for Identifying Protein Coding Regions," Lecture Notes in Computer Science, Springer, ISICA 2008, LNCS 5370, 2008, pp. 489- 500.
[45] Hazem M. El-Bakry, and Nikos Mastorakis "New Fast Normalized Neural Networks for Pattern Detection," Image and Vision Computing Journal, vol. 25, issue 11, 2007, pp. 1767-1784.
[46] Hazem M. El-Bakry and Nikos Mastorakis, "Fast Code Detection Using High Speed Time Delay Neural Networks," Lecture Notes in Computer Science, Springer, vol. 4493, Part III, May 2007, pp. 764-773.
[47] Hazem M. El-Bakry, "New Fast Time Delay Neural Networks Using Cross Correlation Performed in the Frequency Domain," Neurocomputing Journal, vol. 69, October 2006, pp. 2360-2363.
[48] Hazem M. El-Bakry, "Face detection using fast neural networks and image decomposition," Neurocomputing Journal, vol. 48, 2002, pp. 1039-1046.
[49] Hazem M. El-Bakry, "Human Iris Detection Using Fast Cooperative Modular Neural Nets and Image Decomposition," Machine Graphics & Vision Journal (MG&V), vol. 11, no. 4, 2002, pp. 498-512.
[50] Hazem M. El-Bakry, "Automatic Human Face Recognition Using Modular Neural Networks," Machine Graphics & Vision Journal (MG&V), vol. 10, no. 1, 2001, pp. 47-73.
[51] Hazem M. El-Bakry, "New Faster Normalized Neural Networks for Sub- Matrix Detection using Cross Correlation in the Frequency Domain and Matrix Decomposition," Applied Soft Computing journal, vol. 8, issue 2, March 2008, pp. 1131-1149.
[52] Hazem M. El-Bakry, "Automatic Human Face Recognition Using Modular Neural Networks," Machine Graphics & Vision Journal (MG&V), vol. 10, no. 1, 2001, pp. 47-73.
[53] Hazem M. El-Bakry, "Human Iris Detection Using Fast Cooperative Modular Neural Nets and Image Decomposition," Machine Graphics & Vision Journal (MG&V), vol. 11, no. 4, 2002, pp. 498-512.
[54] Hazem M. El-Bakry "Fast Iris Detection for Personal Verification Using Modular Neural Networks," Lecture Notes in Computer Science, Springer, vol. 2206, October 2001, pp. 269-283.
[55] Hazem M. El-bakry, "Complexity Reduction Using Modular Neural Networks," Proc. of IEEE IJCNN-03, Portland, Oregon, pp. 2202-2207, July, 20-24, 2003.
[56] R. Klette, and Zamperon, "Handbook of image processing operators, " John Wiley & Sonsltd, 1996.
[57] J. Murre, Learning and Categorization in Modular Neural Networks, Harvester Wheatcheaf. 1992.
[58] R. Jacobs, M. Jordan, A. Barto, Task Decomposition Through Competition in a Modular Connectionist Architecture: The what and where vision tasks, Neural Computation 3, pp. 79-87, 1991.
[59] J. W. Cooley, and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Math. Comput. 19, 297-301, 1965.
[60] G. Auda, and M. Kamel, CMNN: Cooperative Modular Neural Networks for Pattern Recognition, Pattern Recognition Letters, Vol. 18, pp. 1391-1398, 1997.
[61] E. Alpaydin, , Multiple Networks for Function Learning, Int. Conf. on Neural Networks, Vol.1 CA, USA, pp. 9-14, 1993.
[62] A. Waibel, Modular Construction of Time Delay Neural Networks for Speach Recognition, Neural Computing 1, pp.39-46.
[63] D. E. Rumelhart, G. E. Hinton, and R. J. Williams, Learning representation by error backpropagation, Parallel distributed Processing: Explorations in the Microstructues of Cognition, Vol. 1, Cambridge, MA:MIT Press, pp. 318-362, 1986.
[64] K. Joe, Y. Mori, S. Miyake, Construction of a large scale neural network: Simulation of handwritten Japanese Character Recognition, on NCUBE Concurrency 2 (2), pp. 79-107.