Logic optimization


Logic optimization

Logic optimization a part of logic synthesis, 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 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 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 two-level circuit representation of circuits strictly refers to the flattened view of the circuit in terms of sum-of-products (SOPs)- more applicable to PLA implementation of design—multi-level representation is a more generic view of the circuit in terms of arbitrarily connected SOPs, POSs (product-of-sum), 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:

: 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".

: "F"1 = "AP" + "AD".

: "F"2 = "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 and combinational circuits, whose behavior can be described in terms of finite-state machine(FSM) state tables/diagrams or by Boolean functions and relations respectively.

See also

*Logic minimization
*Logic synthesis
*Electronic design automation
*Binary decision diagram

References

*"Synthesis and Optimization of Digital Circuits", by Giovanni De Micheli, ISBN 0-07-016333-2.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Logic synthesis — is a process by which an abstract form of desired circuit behavior (typically register transfer level (RTL) or behavioral) is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDLs,… …   Wikipedia

  • Optimization (mathematics) — In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an… …   Wikipedia

  • 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.[1] Espresso was developed at IBM by Robert Brayton. Rudell later published the …   Wikipedia

  • Tautology (logic) — In propositional logic, a tautology (from the Greek word ταυτολογία) is a propositional formula that is true under any possible valuation (also called a truth assignment or an interpretation) of its propositional variables. For example, the… …   Wikipedia

  • Power optimization (EDA) — Power optimization refers to the use of electronic design automation tools to optimize (reduce) the power consumption of a digital design, while preserving the functionality.Introduction and historyThe increasing speed and complexity of today’s… …   Wikipedia

  • Mathematical optimization — For other uses, see Optimization (disambiguation). The maximum of a paraboloid (red dot) In mathematics, computational science, or management science, mathematical optimization (alternatively, optimization or mathematical programming) refers to… …   Wikipedia

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

  • Interprocedural optimization — (IPO) is a compiler technique used in computer programming to improve performance in programs containing many frequently used functions of small or medium length. IPO differs from other compiler optimization because it analyzes the entire… …   Wikipedia

  • fuzzy logic — ☆ fuzzy logic n. 〚< fuzzy (set), coined (1965) by L. A. Zadeh, U.S. computer scientist〛 a type of logic used in computers and other electronic devices for processing imprecise or variable data: in place of the traditional binary values, fuzzy… …   Universalium

  • Cross-layer optimization — is an escape from the pure waterfall like concept of the OSI communications model with virtually strict boundaries between layers. The cross layer approach transports feedback dynamically via the layer boundaries to enable the compensation for… …   Wikipedia