Logic optimization: Difference between revisions

Revision as of 17:53, 19 April 2023

Latest revision as of 13:37, 23 April 2025

(17 intermediate revisions by 11 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"/> TheUsually, the smaller circuit with the same function is cheaper,<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018"/> takes less space, [[Power efficiency|consumes less power]], havehas 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==

The problem with having a complicated [[Electronic circuit|circuit]] (i.e. one with many elements, such as [[logic gate]]s) 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 circuit]]s.

With the advent of [[logic synthesis]], one of the biggest challenges faced by the [[electronic design automation]] (EDA) industry was to find the most simple circuit representation of the given design description.<ref group="nb" name="NB_Netlist"/> 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 [[Hardware description language]]s for circuit description, formalized the logic optimization ___domain as it exists today, including [[Logic Friday]] (graphical interface), Minilog, and ESPRESSO-IISOJS (many-valued logic).<ref>{{Cite journal |last=Theobald |first=M. |last2=Nowick |first2=S. M. |date=November 1998 |title=Fast heuristic and exact algorithms for two-level hazard-free logic minimization |url=https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download |journal=IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |volume=17 |issue=11 |pages=1130–1147 |doi=10.1109/43.736186}}</ref>

== Methods ==

The methods of logic circuit simplifications are equally applicable to the [[#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 [[SequentialCombinational logic|sequentialcombinational circuits]] and [[CombinationalSequential logic|combinationalsequential circuits]],. Combinational circuits produce their outputs based only on the current whoseinputs. behaviorThey can be describedrepresented inby terms ofBoolean [[finite-stateRelation machine(mathematics)|relations]]. stateSome tables/diagramsexamples orare by[[priority Booleanencoder]]s, functions[[binary anddecoder]]s, relations[[multiplexer]]s, respectively[[demultiplexer]]s.

Combinational circuits are defined as the time independent circuits which do not depends upon previous inputs to generate any output are termed as combinational circuits. Examples – [[Priority encoder]], [[Binary decoder]], [[Multiplexer]], [[Demultiplexer]].

Sequential circuits areproduce thosetheir whichoutput are dependentbased on clockboth cyclescurrent and dependspast inputs, depending on presenta asclock wellsignal asto pastdistinguish the previous inputs tofrom generatethe anycurrent outputinputs. ExamplesThey –can be represented by finite state machines. Some examples are [[Flip-flop (electronics)|flip-flops]], and [[Counter (digital)|Counterscounters]].

==Example==

Line 122:

== References ==

{{reflist|refs=

<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 |url-status=live |archive-url= |archive-date=}}</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>