
Logic optimization

Logic optimization, a part of logic synthesis in electronics, is the process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. Generally the circuit is constrained to minimum chip area meeting a prespecified delay.
Introduction.
With the advent of logic synthesis, one of the biggest challenges faced by the electronic design automation (EDA) industry was to find the best netlist representation of the given design description. 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 HDLs for circuit description, formalized the logic optimization domain as it exists today.
Today, logic optimization is divided into various categories:
Based on circuit representation 
Based on circuit characteristics
Based on type of execution
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 (BDDs, ADDs) representation of the circuit.
Two-level versus multi-level representations.
If we have two functions "F"1 and "F"2:
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 because of the sharing of the term B + C.
Similarly, we distinguish between sequential and combinational circuits, whose behavior can be described in terms of finite-state machine state tables/diagrams or by Boolean functions and relations respectively.
Circuit minimization in Boolean algebra.
In Boolean algebra, circuit minimization is the problem of obtaining the smallest logic circuit (Boolean formula) that represents a given Boolean function or truth table. 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 formula_3-complete, a result finally proved in 2008, but there are effective heuristics such as Karnaugh maps and the Quine–McCluskey algorithm that facilitate the process.
Boolean function minimizing methods include:
Purpose.
The problem with having a complicated circuit (i.e. one with many elements, such as logic gates) 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 circuits.
Example.
While there are many ways to minimize a circuit, this is an example that minimizes (or simplifies) a Boolean function. Note that the Boolean function carried out by the circuit is directly related to the algebraic expression from which the function is implemented.
Consider the circuit used to represent formula_4. It is evident that two negations, two conjunctions, and a disjunction are used in this statement. This means that to build the circuit one would need two inverters, two AND gates, and an OR gate.
We can simplify (minimize) the circuit by applying logical identities or using intuition. Since the example states that A is true when B is false or the other way around, we can conclude that this simply means formula_5. In terms of logical gates, inequality simply means an XOR gate (exclusive or). Therefore, formula_6. Then the two circuits shown below are equivalent:
You can additionally check the correctness of the result using a truth table.
Graphical logic minimization methods.
Graphical minimization methods for two-level logic include: