Content deleted Content added
Neutronstar2 (talk | contribs) |
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 [[
==Motivation==
Line 16:
== Methods ==
The methods of logic circuit simplifications are equally applicable to [[#Boolean 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
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
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]].
|