HOME

TheInfoList



OR:

Logic optimization is a process of finding an equivalent representation of the specified
logic circuit A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
under one or more specified constraints. This process is a part of a
logic synthesis In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a compu ...
applied in
digital electronics Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals. Digital electronic circuits are usual ...
and
integrated circuit design Integrated circuit design, or IC design, is a sub-field of electronics engineering, encompassing the particular logic and circuit design techniques required to design integrated circuits, or ICs. ICs consist of miniaturized electronic component ...
. Generally, the circuit is constrained to a minimum chip area meeting a predefined response delay. The goal of logic optimization of a given circuit is to obtain the smallest
logic circuit A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
that evaluates to the same values as the original one. The smaller circuit with the same function is cheaper, takes less space, consumes less power, have 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 An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...
. In terms of
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
, the optimization of a complex
boolean expression In computer science, a Boolean expression is an expression used in programming languages that produces a Boolean value when evaluated. A Boolean value is either true or false. A Boolean expression may be composed of a combination of the Boolean con ...
is a process of finding a simpler one, which would upon evaluation ultimately produce the same results as the original one.


Motivation

The problem with having a complicated circuit (i.e. one with many elements, such as
logic gate A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
s) 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 circuit An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...
s. With the advent of
logic synthesis In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a compu ...
, one of the biggest challenges faced by the
electronic design automation Electronic design automation (EDA), also referred to as electronic computer-aided design (ECAD), is a category of software tools for designing Electronics, electronic systems such as integrated circuits and printed circuit boards. The tools wo ...
(EDA) industry was to find the most simple circuit representation of the given design description. While
two-level logic optimization Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit de ...
had long existed in the form of the
Quine–McCluskey algorithm The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a gener ...
, later followed by the
Espresso heuristic logic minimizer The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. ...
, the rapidly improving chip densities, and the wide adoption of
Hardware description language In computer engineering, a hardware description language (HDL) is a specialized computer language used to describe the structure and behavior of electronic circuits, and most commonly, digital logic circuits. A hardware description language e ...
s for circuit description, formalized the logic optimization domain as it exists today, including
Logic Friday The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. a ...
(graphical interface), Minilog, and ESPRESSO-IISOJS (many-valued logic).


Methods

The methods of logic circuit simplifications are equally applicable to the 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 An Euler diagram (, ) is a diagrammatic means of representing sets and their relationships. They are particularly useful for explaining complex hierarchies and overlapping definitions. They are similar to another set diagramming technique, Ven ...
'' (aka ''Eulerian circle'') (1768) by
Leonhard P. Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
(1707–1783) * ''
Venn diagram A Venn diagram is a widely used diagram style that shows the logical relation between set (mathematics), sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple ...
'' (1880) by
John Venn John Venn, Fellow of the Royal Society, FRS, Fellow of the Society of Antiquaries of London, FSA (4 August 1834 – 4 April 1923) was an English mathematician, logician and philosopher noted for introducing Venn diagrams, which are used in l ...
(1834–1923) * ''
Karnaugh map The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logica ...
'' (1953) by
Maurice Karnaugh Maurice Karnaugh (; October 4, 1924 – November 8, 2022) was an American physicist, mathematician, computer scientist, and inventor known for the Karnaugh map used in Boolean algebra. Career Karnaugh studied mathematics and physics at City Co ...


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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
(the complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time), a result finally proved in 2008, but there are effective heuristics such as
Karnaugh map The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logica ...
s and the
Quine–McCluskey algorithm The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a gener ...
that facilitate the process. Boolean function minimizing methods include: *
Quine–McCluskey algorithm The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a gener ...
*
Petrick's method In Boolean algebra, Petrick's method (also known as ''Petrick function'' or ''branch-and-bound'' method) is a technique described by Stanley R. Petrick (1931–2006) in 1956 for determining all minimum sum-of-products solutions from a prime impl ...


Optimal multi-level methods

Methods which find optimal circuit representations of Boolean functions are often referred as "exact synthesis" in the literature. Due to the computational complexity, exact synthesis is tractable only for small Boolean functions. Recent approaches map the optimization problem to a
Boolean satisfiability In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
problem. This allows finding optimal circuit representations using a
SAT solver The SAT ( ) is a standardized test widely used for college admissions in the United States. Since its debut in 1926, its name and scoring have changed several times; originally called the Scholastic Aptitude Test, it was later called the Schola ...
.


Heuristic methods

A
heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
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 The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. ...
.


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 In Boolean algebra (logic), Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form (Disjunctive normal form, CDNF) or minterm canonical form and its dual canonical conjunctive normal form (Conjunctive nor ...
) — which is more applicable to a
PLA PLA may refer to: Organizations Politics and military * People's Liberation Army, the armed forces of China and of the ruling Chinese Communist Party * People's Liberation Army (disambiguation) ** Irish National Liberation Army, formerly called ...
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 In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...
), factored form etc. Logic optimization algorithms generally work either on the structural (SOPs, factored form) or functional ( Binary decision diagrams, Algebraic Decision Diagrams (ADDs)) representation 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 ''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 In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called th ...
and combinational circuits, whose behavior can be described in terms of
finite-state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
state tables/diagrams or by Boolean functions and relations respectively. Combinational circuits are defined as the time independent circuits which do not depends upon previous inputs to generate any output are termed as combinational circuits. Examples –
Priority encoder A priority encoder is a circuit or algorithm that compresses multiple binary inputs into a smaller number of outputs. The output of a priority encoder is the binary representation of the index of the most significant activated line, starting from ...
,
Binary decoder In digital electronics, a binary decoder is a combinational logic circuit that converts binary information from the n coded inputs to a maximum of 2n unique outputs. They are used in a wide variety of applications, including instruction decoding, ...
,
Multiplexer In electronics, a multiplexer (or mux; spelled sometimes as multiplexor), also known as a data selector, is a device that selects between several analog or digital input signals and forwards the selected input to a single output line. The sel ...
,
Demultiplexer In electronics, a multiplexer (or mux; spelled sometimes as multiplexor), also known as a data selector, is a device that selects between several analog or digital input signals and forwards the selected input to a single output line. The sel ...
. Sequential circuits are those which are dependent on clock cycles and depends on present as well as past inputs to generate any output. Examples –
Flip-flops Flip-flops are a type of light sandal, typically worn as a form of casual footwear. They consist of a flat sole held loosely on the foot by a Y-shaped strap known as a toe thong that passes between the first and second toes and around both side ...
, Counters.


Example

While there are many ways to minimize a circuit, this is an example that minimizes (or simplifies) a Boolean function. 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 (A \wedge \bar) \vee (\bar \wedge B). 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 A power inverter, inverter or invertor is a power electronic device or circuitry that changes direct current (DC) to alternating current (AC). The resulting AC frequency obtained depends on the particular device employed. Inverters do the opp ...
, two
AND gate The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not all ...
s, and an
OR gate The OR gate is a digital logic gate that implements logical disjunction. The OR gate returns true if either or both of its inputs are true; otherwise it returns false. The input and output states are normally represented by different voltage le ...
. The circuit can simplified (minimized) by applying laws of
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
or using intuition. Since the example states that A is true when B is false and the other way around, one can conclude that this simply means A \neq B. In terms of logical gates,
inequality Inequality may refer to: Economics * Attention inequality, unequal distribution of attention across users, groups of people, issues in etc. in attention economy * Economic inequality, difference in economic well-being between population groups * ...
simply means an
XOR gate XOR gate (sometimes EOR, or EXOR and pronounced as Exclusive OR) is a digital logic gate that gives a true (1 or HIGH) output when the number of true inputs is odd. An XOR gate implements an exclusive or (\nleftrightarrow) from mathematical log ...
(exclusive or). Therefore, (A \wedge \bar) \vee (\bar \wedge B) \iff A \neq B. Then the two circuits shown below are equivalent, as can be checked using a
truth table A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
:


See also

*
Binary decision diagram In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Un ...
(BDD) * Don't care condition *
Prime implicant In Boolean logic, the term implicant has either a generic or a particular meaning. In the generic use, it refers to the hypothesis of an implication (implicant). In the particular use, a product term (i.e., a conjunction of literals) ''P'' is an ...
*
Circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
— on estimation of the circuit complexity *
Function composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
*
Function decomposition In mathematics, functional decomposition is the process of resolving a Function (mathematics), functional relationship into its constituent parts in such a way that the original function can be reconstructed (i.e., recomposed) from those parts by ...
* Gate underutilization *
Logic redundancy Logic redundancy occurs in a digital gate network containing circuitry that does not affect the static logic function. There are several reasons why logic redundancy may exist. One reason is that it may have been added deliberately to suppress tra ...
* Harvard minimizing chart (Wikiversity) (Wikibooks)


Notes


References


Further reading

* (146 pages) * (NB. Chapters 7–9 cover combinatorial two-level, combinatorial multi-level, and respectively sequential circuit optimization.) * * * {{digital electronics Electronic engineering Electronic design Digital electronics Electronic design automation Electronics optimization Boolean algebra Circuit complexity Logic in computer science