Integrating Fast Karnough Map and Modular Neural Networks for Simplification and Realization of Complex Boolean Functions
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:59132", author = "Hazem M. El-Bakry", title = "Integrating Fast Karnough Map and Modular Neural Networks for Simplification and Realization of Complex Boolean Functions", 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.", volume = "5", number = "3", pages = "303-9", }
