Logic optimization: Difference between revisions

Revision as of 21:58, 29 September 2023

Latest revision as of 13:37, 23 April 2025

(11 intermediate revisions by 8 users not shown)

Line 1:

{{short description|Process in  digital electronics  and  integrated circuit design}}

{{other uses|Minimisation (disambiguation){{!}}Minimisation}}

{{bots|deny=Citation bot}}

{{Use dmy dates|date=May 2019|cs1-dates=y}}

{{Use list-defined references|date=January 2022}}

{{Use dmy dates|date=May 2019|cs1-dates=y}}

'''Logic optimization''' is a process of finding an equivalent representation of the specified [[logic circuit]] under one or more specified constraints. This process is a part of a [[logic synthesis]] applied in [[digital electronics]] and [[integrated circuit design]].

Generally, the circuit is constrained to a minimum chip area meeting a predefined response delay. The goal of logic optimization of a given circuit is to obtain the smallest [[logic circuit]] that evaluates to the same values as the original one.<ref name="Maxfield_2008"/> Usually, the smaller circuit with the same function is cheaper,<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018"/> takes less space, [[Power efficiency|consumes less power]], has shorter latency, and minimizes risks of unexpected [[Crosstalk|cross-talk]], [[Hazard (logic)|hazard of delayed signal processing]], and other issues present at the nano-scale level of metallic structures on an [[integrated circuit]].

In terms of [[Boolean algebra]], the optimization of a complex [[booleanBoolean expression]] is a process of finding a simpler one, which would upon evaluation ultimately produce the same results as the original one.

==Motivation==

Line 16 ⟶ 17:

== Methods ==

The methods of logic circuit simplifications are equally applicable to [[#Boolean expression minimization|booleanBoolean expression minimization]].

=== Classification ===

Line 43 ⟶ 44:

=== {{Anchor|Circuit minimization in Boolean algebra}}Boolean expression minimization ===

{{Cleanup|date=October 2021|reason=We need more consistent, simpler and prose-like summary on every method|section}}

The same methods of booleanBoolean expression minimization (simplification) listed below may be applied to the circuit optimization.

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 [[polynomial hierarchy|<math>\Sigma_2^P</math>-complete]] in [[time complexity]], a result finally proved in 2008,<ref name="Buchfuhrer_2011"/> but there are effective heuristics such as [[Karnaugh map]]s and the [[Quine–McCluskey algorithm]] that facilitate the process.

Line 53 ⟶ 54:

=== Optimal multi-level methods ===

Methods whichthat find optimal circuit representations of Boolean functions are often referred to as "''exact synthesis"'' in the literature. Due to the computational complexity, exact synthesis is tractable only for small Boolean functions. Recent approaches map the optimization problem to a [[Satisfiability|Boolean satisfiability]] problem.<ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism |url=https://si2.epfl.ch/~demichel/publications/archive/2020/winston-exact.pdf |website=EPFL |access-date=7 December 2022}}</ref><ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis for Multi-Level Logic Networks |url=https://si2.epfl.ch/~demichel/graduates/theses/winston.pdf |website=EPFL |access-date=7 December 2022}}</ref> This allows finding optimal circuit representations using a [[SAT solver]].

=== Heuristic methods ===

Line 60 ⟶ 61:

===Two-level versus multi-level representations===

While a two-level circuit representation of circuits strictly refers to the flattened view of the circuit in terms of SOPs ([[sum-of-products]]) &mdash; which is more applicable to a [[Programmable logic array|PLA]] implementation of the design{{Clarify|date=February 2010}} &mdash; 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 representation ([[Binarybinary decision diagramsdiagram]]s, Algebraic[[algebraic Decisiondecision Diagrams (ADDs)diagram]]s) representation of the circuit. In sum-of-products (SOP) form, AND gates form the smallest unit and are stitched together using ORs, whereas in product-of-sums (POS) form it is opposite. POS form requires parentheses to group the OR terms together under AND gates, because OR has lower precedence than AND. Both SOP and POS forms translate nicely into circuit logic.

If we have two functions ''F''₁ and ''F''₂:

Line 79 ⟶ 80:

While the number of levels here is 3, the total number of product terms and literals reduce {{Quantify|date=February 2010}} because of the sharing of the term B + C.

Similarly, we distinguish between [[Combinational logic|combinational circuits]] and [[Sequential logic|sequential circuits]]. Combinational circuits produce their outputs based only on the current inputs. They can be represented by booleanBoolean [[Relation (mathematics)|relations]]. Some examples are [[priority encoder]]s, [[binary decoder]]s, [[multiplexer]]s, [[demultiplexer]]s.

Sequential circuits produce their output based on both current and past inputs, depending on a clock signal to distinguish the previous inputs from the current inputs. They can be represented by finite state machines. Some examples are [[Flip-flop (electronics)|flip-flops]] and [[Counter (digital)|counters]].

Line 123 ⟶ 124:

<ref name="Maxfield_2008">{{cite book |title=FPGAs |chapter=Chapter 5: "Traditional" Design Flows |author-last=Maxfield |author-first=Clive "Max" |date=2008-01-01 |editor-last=Maxfield |editor-first=Clive "Max" |series=Instant Access |publication-place=Burlington |publisher=[[Newnes (publisher)|Newnes]] / [[Elsevier Inc.]] |isbn=978-0-7506-8974-8 |<!-- chapter- -->doi=10.1016/B978-0-7506-8974-8.00005-3 |pages=75–106 |chapter-url=https://www.sciencedirect.com/science/article/pii/B9780750689748000053 |access-date=2021-10-04 }}</ref>

<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018">{{cite web |title=Digital Electronics |author-last1=Balasanyan |author-first1=Seyran |author-last2=Aghagulyan |author-first2=Mane |author-last3=Wuttke |author-first3=Heinz-Dietrich |author-last4=Henke |author-first4=Karsten |date=2018-05-16 |id=DesIRE |series=Bachelor Embedded Systems - Year Group |publisher=Tempus |pages= |url=https://ec.europa.eu/programmes/erasmus-plus/project-result-content/120e4810-0d29-4397-9ad4-b4091c2e3d19/Digital%20Electronics.pdf |access-date=2021-10-04 |url-status=live |archive-url=https://web.archive.org/web/20211004200546/https://ec.europa.eu/programmes/erasmus-plus/project-result-content/120e4810-0d29-4397-9ad4-b4091c2e3d19/Digital%20Electronics.pdf |archive-date=2021-10-04}} (101 pages)</ref>

<ref name="Buchfuhrer_2011">{{cite journal |doi=10.1016/j.jcss.2010.06.011 |title=The complexity of Boolean formula minimization |journal=[[Journal of Computer and System Sciences]] (JCSS) |volume=77 |issue=1 |pages=142–153 |date=January 2011 |___location=Computer Science Department, [[California Institute of Technology]], Pasadena, California, USA |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans |publisher=[[Elsevier Inc.]] |url=http://users.cms.caltech.edu/~umans/papers/BU07.pdf}} This is an extended version of the conference paper: {{cite book |doi=10.1007/978-3-540-70575-8_3 |chapter=The Complexity of Boolean Formula Minimization |title=Proceedings of Automata, Languages and Programming, |work=35th International Colloquium (ICALP) |volume=5125 |pages=24–35 |publisher=[[Springer-Verlag]] |publication-place=Berlin / Heidelberg, Germany |series=[[Lecture Notes in Computer Science]] (LNCS) |date=2008 |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans |isbn=978-3-540-70574-1 |url=http://users.cms.caltech.edu/~umans/papers/BU07.pdf |access-date=2018-01-14 |url-status=live |archive-url=https://web.archive.org/web/20180114141842/http://users.cms.caltech.edu/~umans/papers/BU07.pdf |archive-date=2018-01-14}}</ref>

<ref name="Mano_2014">{{cite book |author-first1=M. Morris |author-last1=Mano |author-first2=Charles R. |author-last2=Kime |title=Logic and Computer Design Fundamentals |edition=4th new international |publisher=[[Pearson Education Limited]] |date=2014 |page=54 |isbn=978-1-292-02468-4}}</ref>