Logic optimization, a part of logic synthesis

Logic synthesis

In electronics, logic synthesis is a process by which an abstract form of desired circuit behavior, typically register transfer level , is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDLs, including VHDL and Verilog...

, 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

Logic synthesis

In electronics, logic synthesis is a process by which an abstract form of desired circuit behavior, typically register transfer level , is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDLs, including VHDL and Verilog...

, one of the biggest challenges faced by the EDA

Electronic design automation

Electronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...

 industry was to find the best netlist

Netlist

The word netlist can be used in several different contexts, but perhaps the most popular is in the field of electronic design. In this context, a "netlist" describes the connectivity of an electronic design....

 representation of the given design description. While two-level logic optimization had long existed in the form of the Quine–McCluskey algorithm

Quine–McCluskey algorithm

The Quine–McCluskey algorithm is a method used for minimization of boolean functions which was developed by W.V. Quine and Edward J. McCluskey...

, later followed by the Espresso heuristic logic minimizer

Espresso heuristic logic minimizer

The Espresso logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital electronic gate circuits. Espresso was developed at IBM by Robert Brayton. Rudell later published the variant Espresso-MV in 1986 under the title...

, the rapidly improving chip densities, and the wide adoption of HDLs

Hardware description language

In electronics, a hardware description language or HDL is any language from a class of computer languages, specification languages, or modeling languages for formal description and design of electronic circuits, and most-commonly, digital logic...

 for circuit description, formalized the logic optimization domain as it exists today.

Today, logic optimization is divided into various categories based on two criteria:

Based on circuit representation

• Two-level logic optimization
• Multi-level logic optimization

Based on circuit characteristics

• Sequential logic optimization
• Combinational logic optimization

While a two-level circuit representation of circuits strictly refers to the flattened view of the circuit in terms of SOPs (sum-of-products

Canonical form (Boolean algebra)

In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums because they are the logical OR of a set of variables In...

) — which is more applicable to a PLA

Programmable logic array

A programmable logic array is a kind of programmable logic device used to implement combinational logic circuits. The PLA has a set of programmable AND gate planes, which link to a set of programmable OR gate planes, which can then be conditionally complemented to produce an output...

 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

Canonical form (Boolean algebra)

In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums because they are the logical OR of a set of variables In...

), 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₁ and F₂:

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.

F₁ = AP + AD.

F₂ = 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 sequential

Sequential logic

In digital circuit theory, sequential logic is a type of logic circuit whose output depends not only on the present input but also on the history of the input. This is in contrast to combinational logic, whose output is a function of, and only of, the present input...

 and combinational circuits

Combinational logic

In digital circuit theory, combinational logic is a type of digital logic which is implemented by boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the...

, whose behavior can be described in terms of finite-state machine state tables/diagrams or by Boolean functions and relations respectively.

See also

• Logic minimization
• Logic synthesis
  Logic synthesis
  In electronics, logic synthesis is a process by which an abstract form of desired circuit behavior, typically register transfer level , is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDLs, including VHDL and Verilog...
  
  
• Electronic design automation
  Electronic design automation
  Electronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...
  
  
• Binary decision diagram
  Binary decision diagram
  In the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...