Logic optimization: Difference between revisions

Content deleted Content added
m caps
Line 8:
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:
 
== Methods ==
The methods of logic circuit simplifications are equally applicable to [[#Boolean expression minimization|booleanBoolean expression minimization]].
 
=== Classification ===
Line 43:
=== {{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 79:
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]].