Logic optimization

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 two-level circuit representation 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 — a multi-level representation 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.

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.

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 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.

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:

• Blake–Poretsky method
• Nelson method[2][3][4][5][6]
• Quine method
• Quine–McCluskey method
• method of algebraic transformations
• Petrick's method
• Roth method[7]
• Kudielka method[8][9][10]
• Wells method[11]
• Scheinman's binary method[12][13]
• 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

Graphical minimization methods for two-level logic include:

• Euler diagram
• Venn diagram
• Marquand diagram
• Harvard minimizing chart
• Veitch chart
• Karnaugh map
• Contact bones, contact grids (1955), and the triadic map by Antonín Svoboda
• Graphical method [15] [Вадим Николаевич Рогинский] (1913–1983)[16][17][18][19]
• Händler diagram
• Graph method (1965) by Herbert F. Kortum (1907–1979)[20][21][22][23][24][25][26][27][28][29]
• V diagram (2001) by Jonathan Westphal (1951–)[30][31]
• Majority-inverter graph
• Pandit plot

• Binary decision diagram (BDD)
• Prime implicant
• Circuit complexity
• Function composition
• Function decomposition
• Gate underutilization

• 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. 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. (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. (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)
• De Geus, Aart J.; Cohen, William W. (1985). "A Rule-Based System for Optimizing Combinational Logic". IEEE Design & Test of Computers. 2 (4): 22–32. doi:10.1109/MDT.1985.294719. S2CID 46651690. (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)