Logic optimization

Logic optimization, a part of logic synthesis in electronics, is the process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. Generally the circuit is constrained to minimum chip area meeting a prespecified delay.

Introduction[]

With the advent of logic synthesis, one of the biggest challenges faced by the electronic design automation (EDA) industry was to find the best netlist representation of the given design description. While two-level logic optimization had long existed in the form of the Quine–McCluskey algorithm, later followed by the Espresso heuristic logic minimizer, the rapidly improving chip densities, and the wide adoption of HDLs for circuit description, formalized the logic optimization domain as it exists today.

Today, logic optimization is divided into various categories:

Based on circuit representation

• Two-level logic optimization
• Multi-level logic optimization

Based on circuit characteristics

• Sequential logic optimization
• Combinational logic optimization

Based on type of execution

• Graphical optimization methods
• Tabular optimization methods
• Algebraic optimization methods

While a of circuits strictly refers to the flattened view of the circuit in terms of SOPs (sum-of-products) — which is more applicable to a PLA implementation of the design^{[clarification needed]} — a is a more generic view of the circuit in terms of arbitrarily connected SOPs, POSs (product-of-sums), factored form etc. Logic optimization algorithms generally work either on the structural (SOPs, factored form) or functional (BDDs, ADDs) representation of the circuit.^{[clarification needed]}

Two-level versus multi-level representations[]

If we have two functions F₁ and F₂:

${\displaystyle F_{1}=AB+AC+AD,\,}$

${\displaystyle F_{2}=A'B+A'C+A'E.\,}$

The above 2-level representation takes six product terms and 24 transistors in CMOS Rep.^[why?]

A functionally equivalent representation in multilevel can be:

P = B + C.

F₁ = AP + AD.

F₂ = A'P + A'E.

While the number of levels here is 3, the total number of product terms and literals reduce^[quantify] because of the sharing of the term B + C.

Similarly, we distinguish between sequential and combinational circuits, whose behavior can be described in terms of finite-state machine state tables/diagrams or by Boolean functions and relations respectively.^{[clarification needed]}

Circuit minimization in Boolean algebra[]

In Boolean algebra, circuit minimization is the problem of obtaining the smallest logic circuit (Boolean formula) that represents a given Boolean function or truth table. For the case when the Boolean function is specified by a circuit (that is, we want to find an equivalent circuit of minimum size possible), the unbounded circuit minimization problem was long-conjectured to be ${\displaystyle \Sigma _{2}^{P}}$-complete, a result finally proved in 2008,^[1] but there are effective heuristics such as Karnaugh maps and the Quine–McCluskey algorithm that facilitate the process.

Boolean function minimizing methods include:

• –Poretsky method
• ^{[2][3][4][5][6]}
• Quine–McCluskey algorithm
• method of algebraic transformations
• Petrick's method
• Roth method^[7][8][9]
• Kudielka method^[10][11][12]
• Wells method^[13]
• Scheinman's binary method^[14][15]
• a method of minimizing functions in bases YES-NO and OR-NOT (Schaeffer and Pierce basis)
• method of undetermined coefficients
• hypercube method
• functional decomposition method
• Espresso heuristic logic minimizer

Purpose[]

The problem with having a complicated circuit (i.e. one with many elements, such as logic gates) is that each element takes up physical space in its implementation and costs time and money to produce in itself. Circuit minimization may be one form of logic optimization used to reduce the area of complex logic in integrated circuits.

Example[]

While there are many ways to minimize a circuit, this is an example that minimizes (or simplifies) a Boolean function. Note that the Boolean function carried out by the circuit is directly related to the algebraic expression from which the function is implemented.^[16] Consider the circuit used to represent ${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}$. It is evident that two negations, two conjunctions, and a disjunction are used in this statement. This means that to build the circuit one would need two inverters, two AND gates, and an OR gate.

We can simplify (minimize) the circuit by applying logical identities or using intuition. Since the example states that A is true when B is false or the other way around, we can conclude that this simply means ${\displaystyle A\neq B}$. In terms of logical gates, inequality simply means an XOR gate (exclusive or). Therefore, ${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}$. Then the two circuits shown below are equivalent:

You can additionally check the correctness of the result using a truth table.

Graphical logic minimization methods[]

Graphical minimization methods for two-level logic include:

• Euler diagram (aka Eulerian circle) (1768) by Leonhard P. Euler (1707–1783)
• Venn diagram (1880) by John Venn (1834–1923)^[17][18]
• Marquand diagram (1881) by Allan Marquand (1853–1924)^[19][20]
• Harvard minimizing chart (aka Harvard chart) (1951) by Howard H. Aiken (1900–1973) and Martha L. Whitehouse^{[21][22][23][24][15]} of the Harvard Computation Laboratory
• Decomposition chart (1952) by Robert L. Ashenhurst (1929–2009) and Theodore Singer (1916–1991)^{[25][26][27][24]} of the Harvard Computation Laboratory
• Veitch chart (1952) by Edward W. Veitch (1924–2013)^[28][20]
• Karnaugh map (1953) by Maurice Karnaugh (1924–)^[22][24]
• Contact bones, contact grids (1955), and the triadic map by Antonín Svoboda (1907–1980)^{[29][30][31][32][33][34][35][36][37][38][39][40][41][42]}
• Graphical method (1957) by Vadim Nikolaevich Roginskij^[43] [Вадим Николаевич Рогинский] (1913–1983)^{[44][45][46][36]}
• Händler diagram (aka Händler circle graph, Händler'scher Kreisgraph, Kreisgraph nach Händler, Händler-Kreisgraph, Händler-Diagramm, Minimisierungsgraph, Mⁿ graph) (1958) by Wolfgang Händler (1920–1998)^{[47][48][49][41][50][51][52][53][54][55][56][57][58]}
• Mahoney map aka M-map or designation numbers (1963) by Matthew V. Mahoney^{[59][60][61][62][63][64][65][66][67][68][69][70][71]}
• Graph method (1965) by  [de] (1907–1979)^{[72][73][74][75][76][77][78][79][80][81]}
• Reduced Karnaugh map (RKM)^[82][83][84] techniques aka infrequent variables (1969) by G. W. Schultz,^[85][86][87] map-entered variables (MEV, 1969) by ^[86] and Christopher R. Clare,^{[88][89][90][91][92][93][94][95][83][84]} Karnaugh map with letter-name variables (1972) by J. Robert Burgoon^[82][96] and Larry L. Dornhoff (1942–2017),^[90] variable-entered Karnaugh map (VEKM, 1983) by Ali M. Rushdi (1951–),^{[97][98][99][100][101][102][96]} variable-entered map (VEM) by William I. Fletcher (1938–2020)^[91][103] or variable entrant map (VEM)^[104]
• Hypercube method (1982) by Stamatios V. Kartalopoulos^[105]
• Minterm-ring map (MRM) or Minterm-ring algorithm (1990) by Thomas R. McCalla^{[106][95][107][103]}
• V diagram (2001) by Jonathan Westphal (1951–)^[108][109]
• Paraboomig (2003) by Shrish Verma and Kiran D. Permar^[110][111]
• Majority-inverter graph (MIG) (2014) by Luca Amarú, Pierre-Emmanuel Gaillardon and Giovanni De Micheli^[112][113]
• Pandit plot (2017) by Vedhas Pandit and Björn W. Schuller (1975–)^[114]
• Truth graph (2020) by Eisa Alharbi^[115][116]

See also[]

• Binary decision diagram (BDD)
• Don't care condition
• Prime implicant
• Circuit complexity
• Function composition
• Function decomposition
• Gate underutilization
• Harvard minimizing chart (Wikiversity) (Wikibooks)

References[]

Further reading[]

• Hwa, "Sherman" Hsuen Ren (June 1974). "A Method of Generating Prime Implicants of a Boolean Expression". IEEE Transactions on Computers. IEEE. C-23 (6): 637–641. doi:10.1109/T-C.1974.224003. eISSN 1557-9956. ISSN 0018-9340. S2CID 10646917. CD-ISSN 2326-3814. 1F09. Retrieved 2020-05-12; Hwa, "Sherman" Hsuen Ren (April 1973). A Method of Generating Prime Implicants of a Boolean Expression. Basser Department of Computer Science, University of Sydney. Technical Report 82.
• Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). Analysis and Design of Sequential Digital Systems. Macmillan Press. ISBN 0-33319266-4. [49] (146 pages)
• Ghosh, Debidas (June 1977) [1977-01-21]. "A method of generating prime factors of a Boolean Expression in a conjunctive normal form with the possibility of inclusion of Don't care combination" (PDF). Journal of Technology. Department of Mathematics, Bengal Engineering College, Howrah, India. XXII (1). Archived (PDF) from the original on 2020-05-12. Retrieved 2020-05-12.
• De Micheli, Giovanni (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill. ISBN 0-07-016333-2. (NB. Chapters 7–9 cover combinatorial two-level, combinatorial multi-level, and respectively sequential circuit optimization.)
• Hachtel, Gary D.; Somenzi, Fabio (2006) [1996]. Logic Synthesis and Verification Algorithms. Springer Science & Business Media. ISBN 978-0-387-31005-3.
• Kohavi, Zvi; Jha, Niraj K. (2009). "4–6". Switching and Finite Automata Theory (3rd ed.). Cambridge University Press. ISBN 978-0-521-85748-2.
• Knuth, Donald Ervin (2010). "7.1.2: Boolean Evaluation". The Art of Computer Programming. 4A. Addison-Wesley. pp. 96–133. ISBN 978-0-201-03804-0.
• Rutenbar, Rob A. Multi-level minimization, Part I: Models & Methods (PDF) (lecture slides). Carnegie Mellon University (CMU). Lecture 7. Archived (PDF) from the original on 2018-01-15. Retrieved 2018-01-15; Rutenbar, Rob A. Multi-level minimization, Part II: Cube/Cokernel Extract (PDF) (lecture slides). Carnegie Mellon University (CMU). Lecture 8. Archived (PDF) from the original on 2018-01-15. Retrieved 2018-01-15.
• Tomaszewski, Sebastian P.; Celik, Ilgaz U.; Antoniou, George E. (December 2003) [2003-03-05, 2002-04-09]. "WWW-based Boolean function minimization" (PDF). International Journal of Applied Mathematics and Computer Science. 13 (4): 577–584. Archived (PDF) from the original on 2020-05-10. Retrieved 2020-05-10. [50][51] (7 pages)
• Wilhelmy, Alexander; Kudielka, Viktor; Deussen, Peter; Böhling, Karl Heinz; Händler, Wolfgang; Neander, Joachim (January 1963) [1961-10-18]. Dörr, Johannes; Peschl, Ernst Ferdinand; Unger, Heinz (eds.). 2. Colloquium über Schaltkreis- und Schaltwerk-Theorie - Vortragsauszüge vom 18. bis 20. Oktober 1961 in Saarbrücken. Internationale Schriftenreihe zur Numerischen Mathematik [International Series of Numerical Mathematics] (ISNM) (in German). 4 (2013-12-20 reprint of 1st ed.). Institut für Angewandte Mathematik, Universität Saarbrücken, Rheinisch-Westfälisches Institut für Instrumentelle Mathematik: Springer Basel AG / Birkhäuser Verlag Basel. doi:10.1007/978-3-0348-4156-6. ISBN 978-3-0348-4081-1. Retrieved 2020-04-15. (152 pages)
• Brayton, Robert King; Rudell, Richard L.; Sangiovanni-Vincentelli, Alberto Luigi; Wang, Albert R. (December 1987). "MIS: A Multiple-Level Logic Optimization System". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 6 (6): 1062–1081. doi:10.1109/TCAD.1987.1270347. (MIS) (20 pages)
• De Geus, Aart J.; Cohen, William W. (July–August 1985). "A Rule-Based System for Optimizing Combinational Logic". IEEE Design & Test of Computers. 2 (4): 22–32. doi:10.1109/MDT.1985.294719. eISSN 1558-1918. ISSN 0740-7475. S2CID 46651690. Archived from the original on 2021-02-19. Retrieved 2021-02-19. (11 pages) [52] (SOCRATES)
• Khatri, Sunil P.; Gulati, Kanupriya, eds. (2011). Advanced Techniques in Logic Synthesis, Optimizations and Applications (1 ed.). New York / Dordrecht / Heidelberg / London: Springer Science+Business Media, LLC. ISBN 978-1-4419-7517-1. (xxii+423+1 pages)
• Jesse, Jobst E. (February 1972). Written at Sunnyvale, California, USA. "A More Efficient Use of Karnaugh Maps". Computer Design. Vol. 11 no. 2. Concord, Massachusetts, USA: Computer Design Publishing Corporation. pp. 80–82. ISSN 0010-4566. OCLC 828863003. CODEN CMPDA. (3 pages)
• Reusch, Bernd (September 1975). "Generation of Prime Implicants from Subfunctions and a Unifying Approach to the Covering Problem". IEEE Transactions on Computers. IEEE. C-24 (9): 924–930. doi:10.1109/T-C.1975.224338. eISSN 1557-9956. ISSN 0018-9340. S2CID 32090834. CD-ISSN 2326-3814. Retrieved 2021-02-19. (7 pages)
• Dineley, R. L. (April 1969). "To the Editor". Letters to the editor. Computer Design. Vol. 8 no. 4. Concord, Massachusetts, USA: Computer Design Publishing Corporation. p. 16. ISSN 0010-4566. OCLC 828863003. CODEN CMPDA. p. 16: […] I would like to offer a method for the simplification of maxterm type Boolean expression by use of the Veitch diagram. To the best of my knowledge, I am the originator of the method, having derived it in 1960 while attending the Digital Computer Fundamentals course at Redstone Arsenal. Most texts simplify the maxterm (product of sums) type expression by plotting the individual terms on separate Veitch diagrams and then overlaying the diagrams to discover the intersects, or "anded," function. […] The method offered here permits the plotting of all terms on one diagram with the "anded" relationship easily discernible. […] Each sum term of the expression is assigned a symbol. This symbol is plotted on the Veitch for each of the or'd factors of the term. The "and" function occurs whenever any square or combination of 2ⁿ adjacent squares contain all of the assigned symbols. A simple example will illustrate. […] (A + BC)^[1] (A + C)^[2] = A + BC […] Yours truly, R. L. Dineley, Sperry Rand Corp. (1 page) (NB. Referred to in Schultz's letter above.)
• Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). "6. Historical Overview of the Research on Decomposition". A Survey of Literature on Function Decomposition (PDF). Version IV. Functional Decomposition Group, Department of Electrical Engineering, Portland University, Portland, Oregon, USA. CiteSeerX 10.1.1.64.1129. Archived (PDF) from the original on 2021-03-28. Retrieved 2021-03-28. (188 pages)
• Stanković, Radomir S.; Sasao, Tsutomu; Astola, Jaakko T. (August 2001). "Publications in the First Twenty Years of Switching Theory and Logic Design" (PDF). Tampere International Center for Signal Processing (TICSP) Series. Tampere University of Technology / TTKK, Monistamo, Finland. ISSN 1456-2774. S2CID 62319288. #14. Archived (PDF) from the original on 2017-08-09. Retrieved 2021-03-28. (4+60 pages)