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

Two-level versus multi-level representations

If we have two functions F₁ and F₂:

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.

Graphical two-level logic minimization methods

Graphical minimization methods for two-level logic include:

• Marquand diagram (1881) by Allan Marquand (1853–1924)^[1][2]
• Harvard minimizing chart (1951) by Howard H. Aiken and Martha L. Whitehouse of the Harvard Computation Laboratory^[3][4][5][6]
• Veitch chart (1952) by Edward Veitch (1924–2013)^[7][2]
• Karnaugh map (1953) by Maurice Karnaugh (1924–)
• Svoboda's graphical aids (1956) and triadic map by Antonín Svoboda (1907–1980)^{[8][9][10][11]}
• Händler circle graph (aka Händler'scher Kreisgraph, Kreisgraph nach Händler, Händler-Kreisgraph, Händler-Diagramm, Minimisierungsgraph [sic]) (1958) by Wolfgang Händler (1920–1998)^{[12][13][14][10][15][16][17][18][19]}
• Graph method (1965) by Herbert Kortum (1907–1979)^{[20][21][22][23][24][25]}

See also

• Binary decision diagram
• Circuit minimization

References

Further reading

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