The methods of logic circuit simplifications are equally applicable to
Boolean expression minimization.
Classification 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
Graphical methods Graphical methods represent the required logical function by a diagram representing the logic variables and value of the function. By manipulating or inspecting a diagram, much tedious calculation may be eliminated. Graphical minimization methods for two-level logic include: •
Euler diagram (aka
Eulerian circle) (1768) by
Leonhard P. Euler (1707–1783) •
Venn diagram (1880) by
John Venn (1834–1923) •
Karnaugh map (1953) by
Maurice Karnaugh Boolean expression minimization The same methods of Boolean 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
\Sigma_2^P-complete in
time complexity, a result finally proved in 2008, This allows finding optimal circuit representations using a
SAT solver.
Heuristic methods A
heuristic method uses established rules that solve a practical useful subset of the much larger possible set of problems. The heuristic method may not produce the theoretically optimum solution, but if useful, will provide most of the optimization desired with a minimum of effort. An example of a computer system that uses heuristic methods for logic optimization is the
Espresso heuristic logic minimizer.
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) — 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 representation (
binary decision diagrams,
algebraic decision diagrams) 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
F1 and
F2: : F_1 = AB + AC + AD,\, : F_2 = A'B + A'C + A'E.\, 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. :
F1 =
AP +
AD. :
F2 = ''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
combinational circuits and
sequential circuits. Combinational circuits produce their outputs based only on the current inputs. They can be represented by Boolean
relations. Some examples are
priority encoders,
binary decoders,
multiplexers,
demultiplexers. 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-flops and
counters. ==Example==