Logic optimization

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.

[1] Usually, the smaller circuit with the same function is cheaper,[2] takes less space, consumes less power, has shorter latency, and minimizes risks of unexpected cross-talk, hazard of delayed signal processing, and other issues present at the nano-scale level of metallic structures on an integrated circuit.

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

-complete in time complexity, a result finally proved in 2008,[4] but there are effective heuristics such as Karnaugh maps and the Quine–McCluskey algorithm that facilitate the process.

Due to the computational complexity, exact synthesis is tractable only for small Boolean functions.

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.

Logic optimization algorithms generally work either on the structural (SOPs, factored form) or functional representation (binary decision diagrams, algebraic decision diagrams) of the circuit.

Both SOP and POS forms translate nicely into circuit logic.

If we have two functions F1 and F2: The above 2-level representation takes six product terms and 24 transistors in CMOS Rep. A functionally equivalent representation in multilevel can be: While the number of levels here is 3, the total number of product terms and literals reduce [quantify] 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.

Some examples are priority encoders, binary decoders, multiplexers, demultiplexers.

The circuit can simplified (minimized) by applying laws of Boolean algebra or using intuition.