Logical Design of n-bit Comparators: Pedagogical Insight from Eight-Variable Karnaugh Maps

Main Article Content

Ali Muhammad Ali Rushdi
Sultan Sameer Zagzoog

Abstract

An -bit comparator is a celebrated combinational circuit that compares two -bit inputs  and  and produces three orthonormal outputs: G (indicating that  is strictly greater than ), E (indicating that  and  are equal or equivalent), and L (indicating that  is strictly less than ). The symbols ‘G’, ‘E’, and ‘L’ are deliberately chosen to convey the notions of ‘Greater than,’ ‘Equal to,’ and ‘Less than,’ respectively. This paper analyzes an -bit comparator in the general case of arbitrary  and visualizes the analysis for  on a regular and modular version of the 8-variable Karnaugh-map. The cases  3, 2, and 1 appear as special cases on 6-variable, 4-variable, and 2-variable submaps of the original map. The analysis is a tutorial exposition of many important concepts in switching theory including those of implicants, prime implicants, essential prime implicants, minimal sum, complete sum and disjoint sum of products (or probability-ready expressions).

Keywords:
Comparator, Karnaugh map, prime implicant, minimal sum, complete sum, probability-ready expression.

Article Details

How to Cite
Rushdi, A., & Zagzoog, S. (2019). Logical Design of n-bit Comparators: Pedagogical Insight from Eight-Variable Karnaugh Maps. Journal of Advances in Mathematics and Computer Science, 32(3), 1-20. https://doi.org/10.9734/jamcs/2019/v32i330146
Section
Original Research Article

References

Karnaugh M. The map method for synthesis of combinational logic circuits. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics. 1953;72(5):593-599.

Hurley RB. Probability maps, IEEE Transactions on Reliability. 1963;12(3):39-44.

Lee SC. Modern switching theory and digital design, prentice-Hall, Englewood Cliffs, New Jersey, NJ, USA; 1978.

Muroga S. Logic design and switching theory, John Wiley, New York, NY, USA; 1979.

Rushdi AM. Symbolic reliability analysis with the aid of variable-entered Karnaugh maps, IEEE Transactions on Reliability. 1983;32(2):134-139.

Rushdi AM. Map differentiation of switching functions. Microelectronics and Reliability. 1986;26(5): 891-907.

Rushdi AM. Improved variable-entered Karnaugh map procedures. Computers & Electrical Engineering. 1987;13(1):41-52.

Hill FJ, Peterson GR. Computer aided logical design with emphasis on VLSI, 4th Edition, Wiley, New York, NY, USA; 1993.

Rushdi AMA. Karnaugh map, encyclopedia of mathematics. M. Hazewinkel (Editor), Boston, Kluwer Academic Publishers. 1997;I(Supplement):327-328.
Available:http://eom.springer.de/K/k110040.html

Rushdi AM, Al-Yahya HA. A Boolean minimization procedure using the variable-Entered Karnaugh map and the generalized consensus concept. International Journal of Electronics. 2000;87(7):769-794.

Rushdi AM, Al-Yahya HA. Further improved variable-entered Karnaugh map procedures for obtaining the irredundant forms of an incompletely-specified switching function. Journal of King Abdulaziz University: Engineering Sciences. 2001;13(1):111-152.

Rushdi AM, Al-Yahya HA. Derivation of the complete sum of a switching function with the aid of the variable-entered Karnaugh map. Journal of King Saud University-Engineering Sciences. 2001;13(2):239-268.

Rushdi AM, Al-Yahya HA. Variable-entered Karnaugh map procedures for obtaining the irredundant disjunctive forms of a switching function from its complete sum. Journal of King Saud University-Engineering Sciences. 2002;14(1):13-26.

Roth C, Kinney L. Fundamentals of Logic Design,7th Edition, Cengage Learning, Stamford, CT, USA; 2014.

Rushdi AMA, Ghaleb FAM. The Walsh spectrum and the real transform of a switching function: A review with a Karnaugh-map perspective. Journal of Engineering and Computer Sciences, Qassim University. 2014;7(2):73-112.

Fabricius ED. Modern Digital Design and Switching Theory. CRC Press; 2017.

Cavanagh J. Digital Design and Verilog HDL Fundamentals. CRC Press; 2017.

Rushdi AMA, Badawi RMS. Karnaugh-map utilization in Boolean analysis: The case of war termination. Journal of Qassim University: Engineering and Computer Sciences. 2017;10(1):53-88.

Deschamps JP, Valderrama E, Terés L. Digital systems: From logic gates to processors. Springer; 2017.

Rushdi AMA, Badawi RMS. Karnaugh map utilization in coincidence analysis. Journal of King Abdulaziz University: Faculty of Computers and Information Technology. 2017;6(1-2):37-44.

Rushdi AMA. Utilization of Karnaugh maps in multi-value qualitative comparative analysis, International Journal of Mathematical, Engineering and Management Sciences (IJMEMS). 2018;3(1): 28-46.

Rushdi, R. A., & Rushdi, A. M. (2018). Karnaugh-map utility in medical studies: The case of Fetal Malnutrition. International Journal of Mathematical, Engineering and Management Sciences (IJMEMS), 3(3), 220-244.

Rushdi AMA, Badawi RMS. Computer engineers look at qualitative comparative analysis. International Journal of Mathematical, Engineering and Management Sciences (IJMEMS). 2019;4(3).

Roth CH. Computer aids for teaching logic design. In Proceedings of IEEE Frontiers in Education Conference-FIE'93. IEEE. 1993;188-191.

Hacker C, Sitte R. Interactive teaching of elementary digital logic design with Win Logi Lab. IEEE Transactions on Education. 2004;47(2):196-203.

Solairaju A, Periyasamy R. Optimal Boolean function simplification through K-map using object-oriented algorithm. International Journal of Computer Applications. 2011;15(7):28-32.

Baneres D, Clarisó R, Jorba J, Serra M. Experiences in digital circuit design courses: A self-study platform for learning support. IEEE Transactions on Learning Technologies. 2014;7(4):360-374.

Battistella P, von Wangenheim CG. Games for teaching computing in higher education–A systematic review. IEEE Technology and Engineering Education. 2016;9(1):8-30.

Rushdi AM, Zagzoog SS. Derivation of all particular solutions of a ‘big’ Boolean equation with applications in digital design. . Current Journal of Applied Science and Technology. 2018;27(3):1-16.

Salhi Y. Approaches for enumerating all the essential prime implicants. In International Conference on Artificial Intelligence: Methodology, Systems, and Applications. Springer, Cham. 2018;228-239.

Halder AK. Karnaugh map extended to six or more variables. Electronics Letters. 1982;18(20):868-870.‏

Motil JM. Views of digital logic & probability via sets, numberings; 2017.
Available:http://www.csun.edu/~jmotil/ccSetNums2.pdf

Rushdi AM, Zagzoog SS, Balamesh AS. Derivation of a scalable solution for the problem of factoring an n-bit integer. Journal of Advances in Mathematics and Computer Science. 2019;30(1):1-22.

Rushdi AMA, Alsayegh AB. Reliability analysis of a commodity-supply multi-state system using the map method. Journal of Advances in Mathematics and Computer Science. 2019;31(2):1-17.

Fantauzzi G. Application of Karnaugh maps to Maitra cascades. In Proceedings of the April 30--May 2, 1968, spring joint computer conference. ACM. 1968;291-296.

Edwards CR, Hurst SL. A digital synthesis procedure under function symmetries and mapping methods. IEEE Transactions on Computers. 1978;27(11):985-997.

Heiss M. Error-detecting unit-distance code. IEEE Transactions on Instrumentation and Measurement. 1990;39(5):730-734.

Pomeranz I, Reddy SM. Pattern sensitivity: A property to guide test generation for combinational circuits. In Proceedings Eighth Asian Test Symposium (ATS'99). IEEE. 1999;75-80.

Tabandeh M. Application of Karnaugh map for easy generation of error correcting codes. Scientia Iranica. 2012;19(3):690-695.

El-Maleh AH, Oughali FC. A generalized modular redundancy scheme for enhancing fault tolerance of combinational circuits. Microelectronics Reliability. 2014;54(1):316-326.

Pezeshkpour P, Tabandeh M. Data bits in Karnaugh map and increasing map capability in error correcting. arXiv preprint arXiv:1502.02253. 2015;1-8.

Rushdi AMA, Ba-Rukab OM. Map calculation of the Shapley-Shubik voting powers: An example of the European Economic Community. International Journal of Mathematical, Engineering and Management Sciences (IJMEMS). 2017;2(1):17-29.

Rushdi AMA, Ba-Rukab OM. Calculation of Banzhaf voting indices utilizing variable-entered Karnaugh maps. British Journal Mathematics and Computer Science. 2017;20(4):1-17.

Rushdi AM, Al-Khateeb DL. A review of methods for system reliability analysis: A Karnaugh-map perspective, Proceedings of the First Saudi Engineering Conference, Jeddah, Saudi Arabia. 1983; 1:57-95.

Rushdi AM. Overall reliability analysis for computer-communication networks, Proceedings of the Seventh National Computer Conference, Riyadh, Saudi Arabia. 1984;23-38.

Rushdi AM. On reliability evaluation by network decomposition, IEEE Transactions on Reliability, 1984;33(5):379-384. Corrections: ibid. 1985;34(4):319.

Rushdi AMA, Zagzoog SS. Design of a digital circuit for integer factorization via solving the inverse problem of logic. Journal of Advances in Mathematics and Computer Science. 2018;26(3):1-14.

Rushdi AM, Zagzoog SS, Balamesh AS. Design of a hardware circuit for integer factorization using a big Boolean algebra. Journal of Advances in Mathematics and Computer Science. 2018;27(1):1-25.

Taylor FJ, Gill R, Joseph J, Radke J. A 20 bit logarithmic number system processor. IEEE Transactions on Computers. 1988;37(2):190-200.

Thapliyal H, Ranganathan N, Ferreira R. Design of a comparator tree based on reversible logic. In 10th IEEE International Conference on Nanotechnology. IEEE. 2010;1113-1116.

Morrison M, Lewandowski M, Ranganathan N. Design of a tree-based comparator and memory unit based on a novel reversible logic structure. In 2012 IEEE Computer Society Annual Symposium on VLSI. IEEE. 2012;231-236.

Rushdi AM. Logic design of NAND (NOR) circuits by the entered-map-factoring method. Microelectronics Reliability. 1987;27(4):693-701.

Rushdi AM, Ba-Rukab OM. A purely map procedure for two-level multiple-output logic minimization. International Journal of Computer Mathematics. 2007;84(1):1-10.

Rushdi AM, Ba-Rukab OM. A map procedure for two-level multiple-output logic minimization. In Proceedings of the Seventeenth National Computer Conference. 2004;521-532.

Rushdi AM, Goda AS. Symbolic reliability analysis via Shannon's expansion and statistical independence. Microelectronics and Reliability. 1985;25(6):1041-1053.

Rushdi AM, Abdul Ghani AA. A comparison between reliability analyses based primarily on disjointness or statistical independence. Microelectronics and Reliability. 1993;33:965-978.

Rushdi AMA, Hassan AK. Reliability of migration between habitat patches with heterogeneous ecological corridors. Ecological Modeling. 2015;304:1-10.

Rushdi, A. M. A., & Hassan A. K. (2016). An exposition of system reliability analysis with an ecological perspective, Ecological Indicators, 63, 282-295.

Rushdi AM, Rushdi MA. Switching-algebraic analysis of system reliability, Chapter 6 in M. Ram and P. Davim (Editors), Advances in Reliability and System Engineering, Management and Industrial Engineering Series, Springer International Publishing, Cham, Switzerland. 2017;139-161.

Rushdi AM, Alturki AM. Novel representations for a coherent threshold reliability system: A tale of eight signal flow graphs. Turkish Journal of Electrical Engineering & Computer Sciences. 2018;26(1): 257-269.

Parker KP, McCluskey EJ. Probabilistic treatment of general combinational networks, IEEE Transactions on Computers. 1975;24(6):668-670.

Ogus RC. The probability of a correct output from a combinational circuit. IEEE Transactions on Computers. 1975;24(5):534-544.

McCluskey EJ, Parker KP, Shedletsky JJ. Boolean network probabilities and network design. IEEE Transactions on Computers. 1978;27(2):187-189.

Krishnamurthy B, Tollis IG. Improved techniques for estimating signal probabilities. IEEE Transactions on Computers. 1989;38(7):1041-1045.

Ercolani S, Favalli M, Damiani M, Olivo P, Ricco B. Estimate of signal probability in combinational logic networks. Proceedings of the 1st IEEE European Test Conference. 1989;132-138.

Jiang Y, Tang Y, Wang Y, Savaria Y. Evaluating the output probability of Boolean functions without floating point operations, IEEE Canadian Conference on Electrical and Computer Engineering. 1999; 1:433-437.

Franco DT, Vasconcelos MC, Naviner L, Naviner JF. Signal probability for reliability evaluation of logic circuits. Microelectronics Reliability. 2008;48(8):1586-1591.

Han J, Chen H, Boykin E, Fortes J. Reliability evaluation of logic circuits using probabilistic gate models. Microelectronics Reliability. 2011;51(2):468-476.

Qian W, Riedel MD, Zhou H, Bruck J. Transforming probabilities with combinational logic. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2011;30(9):1279-1292.

Brown FM. Boolean reasoning: The logic of Boolean equations. Kluwer Academic Publishers, Boston, USA; 1990.

Rushdi AM, Ba-Rukab OM. Map derivation of the closures for dependency and attribute sets and all candidate keys for a relational database, Journal of King Abdulaziz University: Engineering Sciences. 2014;25(2):3-34.

Rushdi AMA, Albarakati HM. Construction of general subsumptive solutions of Boolean equations via complete-sum derivation. Journal of Mathematics and Statistics. 2014;10(2):155-168.

Rushdi AM, Alshehri TM, Zarouan M, Rushdi MA. Utilization of the modern syllogistic method in the exploration of hidden aspects in engineering ethical dilemmas. Journal of King Abdulaziz University: Computers and Information Technology. 2014;3(1):73-127.

Rushdi AM, Zarouan M, Alshehri TM, Rushdi MA. The incremental version of the Modern Syllogistic Method. Journal of King Abdulaziz University: Engineering Sciences. 2015;26(1):25-51.

Rushdi AM, Rushdi MA. Utilization of the modern syllogistic method in the service of academic advising. In Proceedings of KAU Conference on Academic Advising in Higher Education. 2015;228-241.

Rushdi AM, Rushdi MA. Switching-algebraic algorithmic derivation of candidate keys in relational databases. Proceedings of the IEEE International Conference on Emerging Trends in Communication Technologies (ICETCT-2016); 2016.

Rushdi AM, Rushdi MA. Mathematics and examples of the modern syllogistic method of propositional logic. In Ram, M. (Editor), Mathematics Applied in Information Systems, Bentham Science Publishers, Emirate of Sharjah, United Arab Emirates. 2018;Chapter 6:123-167.

Rushdi AMA, Ghaleb FAM. Novel characterizations of the JK Bistables (Flip Flops). Journal of Engineering Research and Reports. 2019;4(3):1-20.

Rushdi AMA, Ghaleb FAM. A tutorial exposition of semi-tensor products of matrices with a stress on their representation of Boolean functions. Journal of King Abdulaziz University: Faculty of Computers and Information Technology. 2016;5(1-2):3-41.

McNaughton R. Unate truth functions. IRE Transactions on Electronic Computers. 1961;1:1-6.

Choudhury A, Sarma D, Das SR. Minimal third-order expressions of Boolean Unate functions. International Journal of Control. 1967;6(5):447-459.

Fisher LT. Unateness properties of AND-EXCLUSIVE-OR logic circuits. IEEE Transactions on Computers. 1974;C-24(2):166-172.

Thayse A, Deschamps JP. Logic properties of unate discrete and switching functions. IEEE Transactions on Computers. 1977;C-26(12):1202-1212.

Srivatsa SK, Biswas NN. Karnaugh map analysis and synthesis of threshold functions. International Journal of Systems Science. 1977;8(12):1385-1399.

Hansen P, Simeone B. Unimodular functions. Discrete Applied Mathematics. 1986;14(3):269-281.

Feigelson A, Hellerstein L. The forbidden projections of unate functions. Discrete Applied Mathematics. 1997;77(3):221-236.

Muroga S, Tsuboi T, Baugh CR. Enumeration of threshold functions of eight variables. IEEE Transactions on Computers. 1970;C-19(9):818-825.

Rushdi AM. Threshold systems and their reliability. Microelectronics and Reliability. 1990;30(2): 299-312.

Zhang R, Gupta P, Zhong L, Jha NK. Threshold network synthesis and optimization and its application to nanotechnologies. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2005;24(1):107-118.

Subirats JL, Jerez JM, Franco L. A new decomposition algorithm for threshold synthesis and generalization of Boolean functions. IEEE Transactions on Circuits and Systems I: Regular Papers. 2008;55(10):3188-3196.

Rushdi AMA, Alturki AM. Reliability of coherent threshold systems. Journal of Applied Sciences. 2015;15(3):431-443.