A Novel Graphical Technique for Combinational Logic Representation and Optimization
Authors: 
Vedhas Pandit, Björn Schuller Academic Editor: Michele ScarpinitiAuthors Info & Claims
Abstract
We present a new technique for defining, analysing, and simplifying digital functions, through hand-calculations, easily demonstrable therefore in the classrooms. It can be extended to represent discrete systems beyond the Boolean logic. The method is graphical in nature and provides complete ‘‘implementation-free” description of the logical functions, similar to binary decision diagrams (BDDs) and Karnaugh-maps (K-maps). Transforming a function into the proposed representations (also the inverse) is a very intuitive process, easy enough that a person can hand-calculate these transformations. The algorithmic nature allows for its computing-based implementations. Because the proposed technique effectively transforms a function into a scatter plot, it is possible to represent multiple functions simultaneously. Usability of the method, therefore, is constrained neither by the number of inputs of the function nor by its outputs in theory. This, being a new paradigm, offers a lot of scope for further research. Here, we put forward a few of the strategies invented so far for using the proposed representation for simplifying the logic functions. Finally, we present extensions of the method: one that extends its applicability to multivalued discrete systems beyond Boolean functions and the other that represents the variants in terms of the coordinate system in use.
References
[1]
R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. R. Wang, “MIS: A Multiple-Level Logic Optimization System,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 6, no. 6, pp. 1062–1081, 1987.
[2]
A. J. De Geus and W. Cohen, “A Rule-Based System for Optimizing Combinational Logic,” IEEE Design Test of Computers, vol. 2, no. 4, pp. 22–32, 1985.
[3]
M. Karnaugh, “The map method for synthesis of combinational logic circuits,” Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, vol. 72, no. 5, pp. 593–599, 1953.
[4]
M. E. Holder, “A modified karnaugh map technique,” IEEE Transactions on Education, vol. 48, no. 1, pp. 206–207, 2005.
[5]
J. Cavanagh, Computer Arithmetic and Verilog HDL Fundamentals, CRC Press, 2009.
[6]
Z. Kohavi and N. K. Jha, Switching and finite automata theory, Cambridge University Press, 2009.
[7]
C. Y. Lee, “Representation of switching circuits by binary-decision programs,” Bell Labs Technical Journal, vol. 38, pp. 985–999, 1959.
[8]
S. B. Akers, “Binary decision diagrams,” IEEE Transactions on Computers, vol. 27, no. 6, pp. 509–516, 1978.
[9]
B. Lin and S. Devadas, “Synthesis of Hazard-Free Multilevel Logic Under Multiple-Input Changes from Binary Decision Diagrams,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 8, pp. 974–985, 1995.
[10]
C. Yang and M. Ciesielski, “BDS: A BDD-based logic optimization system,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 7, pp. 866–876, 2002.
[11]
R. E. Bryant, “Graph-based algorithms for boolean function manipulation,” IEEE Transactions on Computers, vol. C-35, no. 8, pp. 677–691, 1986.
[12]
L. Mauborgne, “Abstract interpretation using typed decision graphs,” Science of Computer Programming, vol. 31, no. 1, pp. 91–112, 1998.
[13]
O. Coudert and J. C. Madre, “A new implicit graph-based prime and essential prime computation technique,” in Proceedings of the Proc. International Symp. Information Sciences, Fukuoka, Japan, 1992.
[14]
O. Coudert and J. C. Madre, “A New Graph Based Prime Computation Technique,” in Logic Synthesis and Optimization, pp. 33–57, Springer, Boston, MA, USA, 1993.
[15]
O. Coudert, J. C. Madre, H. Fraisse, and H. Touati, “Implicit prime cover computation: An overview,” in Proceedings of the in Proc. Synthesis and Simulation Meeting and International Interchange (SASIMI), Nara, Japan, 1993.
[16]
J. Gu and R. Puri, “Asynchronous circuit synthesis with Boolean satisfiability,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 8, pp. 961–973, 1995.
[17]
W. V. Quine, “The problem of simplifying truth functions,” The American Mathematical Monthly, vol. 59, pp. 521–531, 1952.
[18]
W. V. Quine, “A way to simplify truth functions,” The American Mathematical Monthly, vol. 62, pp. 627–631, 1955.
[19]
J. McCluskey, “Minimization of Boolean functions,” Bell Labs Technical Journal, vol. 35, pp. 1417–1444, 1956.
[20]
S. Petrick, “A direct determination of the irredundant forms of a boolean function from the set of prime implicants,” Air Force Cambridge Research Center, 1956.
[21]
R. L. Rudell, “Multiple-Valued Logic Minimization for PLA Synthesis,” Defense Technical Information Center, 1986.
[22]
L. Amaru, P.-E. Gaillardon, and G. De Micheli, “Majority-Inverter Graph: A New Paradigm for Logic Optimization,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 5, pp. 806–819, 2016.
[23]
D. C. Fielder, “Classroom Reduction of Boolean Functions,” IEEE Transactions on Education, vol. 9, no. 4, pp. 202–205, 1966.
[24]
B. C. H. Turton, “Extending Quine-McCluskey for exclusive-or logic synthesis,” IEEE Transactions on Education, vol. 39, no. 1, pp. 81–85, 1996.
[25]
R. Benzer and V. Rozga, “The Design and Application of a Minority Logic Gate-A Senior Project,” IEEE Transactions on Education, vol. 10, no. 3, pp. 141–146, 1967.
[26]
N. R. Bell, “A Map Method for the Teaching of the Fundamental Concepts of Compound-Input Logic Circuits,” IEEE Transactions on Education, vol. 11, no. 3, pp. 173–177, 1968.
[27]
R. F. Tinder, “Multilevel Logic Minimization Using K-map XOR Patterns,” IEEE Transactions on Education, vol. 38, no. 4, pp. 370–375, 1995.
[28]
B. D. Carroll and I. Chen, “ABAL—A Language for Boolean Function Representation and Manipulation,” IEEE Transactions on Education, vol. 20, no. 1, pp. 70–72, 1977.
[29]
C. E. Klock, F. R. Schneider, M. V. N. Gomes, D. S. Moura, R. P. Ribas, and A. I. Reis, “KARMA: A didactic tool for two-level logic synthesis,” in Proceedings of the MSE 2007: 2007 IEEE International Conference on Microelectronic Systems Education: Educating Systems Designers for the Global Economy and a Secure World, pp. 59–60, San Diego, CA, USA, June 2007.
[30]
V. P. Correia and A. I. Reis, “A tutorial tool for switch logic,” in Proceedings of the International Conference on Microelectronic Systems Education, MSE 2001, pp. 28–29, Las Vegas, NV, USA, June 2001.
[31]
Z. Stanisavljevic, V. Pavlovic, B. Nikolic, and J. Djordjevic, “SDLDS-system for digital logic design and simulation,” IEEE Transactions on Education, vol. 56, no. 2, pp. 235–245, 2013.
[32]
P. Corsini and L. Rizzo, “SSCSSC: A Tool for the Teaching of Digital Circuits,” IEEE Transactions on Education, vol. 34, no. 1, pp. 70–75, 1991.
[33]
G. J. Klir and M. A. Marin, “New considerations in teaching switching theory,” IEEE Transactions on Education, vol. 12, no. 4, pp. 257–261, 1969.
[34]
M. Gardner, “Mathematical games: The fantastic combinations of John Conway's new solitaire game "life",” Scientific American, vol. 223, no. 4, pp. 120–123, 1970.
[35]
S. Wolfram, “Cellular automata as models of complexity,” Nature, vol. 311, no. 5985, pp. 419–424, 1984.
[36]
M. Sierpinski, “Sur une courbe dont tout point est un point de ramification,” Compte Rendus hebdomadaires des séance de lÁcadémie des Science de Paris, vol. 160, pp. 302–305, 1915.
[37]
J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.
[38]
K. A. Bartlett, R. K. Brayton, G. D. Hachtel, R. M. Jacoby, C. R. Morrison, R. L. Rudell, A. SangiovannI-Vincentelli, and A. R. Wang, “Multilevel Logic Minimization Using Implicit Don't Cares,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 7, no. 6, pp. 723–740, 1988.
[39]
P. Niemann, R. Wille, D. M. Miller, M. A. Thornton, and R. Drechsler, “QMDDs: Efficient Quantum Function Representation and Manipulation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 1, pp. 86–99, 2016.
[40]
D. Searls and M. Noordewier, “Pattern-matching search of DNA sequences using logic grammars,” in Proceedings of the Seventh IEEE Conference on Artificial Intelligence Application, pp. 3–9, Miami Beach, FL, USA, 1991.
[41]
C. R. Woese, “Order in the genetic code.” Proceedings of the National Acadamy of Sciences of the United States of America, vol. 54, no. 1, pp. 71–75, 1965.
[42]
M. A. Marchisio and J. Stelling, “Automatic design of digital synthetic gene circuits,” PLoS Computational Biology, vol. 7, no. 2, 2011.
[43]
N. Gershenfeld, D. Dalrymple, K. Chen, A. Knaian, F. Green, E. D. Demaine, S. Greenwald, and P. Schmidt-Nielsen, “Reconfigurable asynchronous logic automata: (RALA),” in Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'10, vol. 45, pp. 1–6, Madrid, Spain, January 2010.
[44]
V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, “Synthesis of reversible logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 6, pp. 710–722, 2003.
[45]
P. Gupta, A. Agrawal, and N. K. Jha, “An algorithm for synthesis of reversible logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 11, pp. 2317–2329, 2006.
Index Terms
- A Novel Graphical Technique for Combinational Logic Representation and Optimization
Index terms have been assigned to the content through auto-classification.
Recommendations
Quaternary CMOS Combinational Logic Circuits
ICIMT '09: Proceedings of the 2009 International Conference on Information and Multimedia TechnologyGood Characteristics and advantages of multi-valued logic (MVL) electronic systems and circuits are created great interest for its practical implementation. This paper presents voltage mode quaternary CMOS circuit design using 90nm technology. Basic ...
A novel compact piecewise-linear representation: Research Articles
A new compact MAX representation for 2-D continuous piecewise-linear (PWL) functions is developed in this paper. The representation is promising since it can be easily generalized into higher dimensions. We also establish the explicit functional form of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2017 Vedhas Pandit and Björn Schuller.
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Publisher
John Wiley & Sons, Inc.
United States
Publication History
Published: 01 January 2017
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in