Misplaced Pages

Logic optimization: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 02:50, 31 May 2022 editWtshymanski (talk | contribs)Extended confirmed users76,106 edits {{Anchor|Circuit minimization in Boolean algebra}}Boolean expression minimization: get rid of references to primary sourcesTag: Reverted← Previous edit Revision as of 02:53, 31 May 2022 edit undoWtshymanski (talk | contribs)Extended confirmed users76,106 edits removing cites of primary sourcesTag: RevertedNext edit →
Line 38: Line 38:
Graphical minimization methods for two-level logic include: Graphical minimization methods for two-level logic include:
* '']'' (aka ''Eulerian circle'') (1768) by ] (1707–1783) * '']'' (aka ''Eulerian circle'') (1768) by ] (1707–1783)
* '']'' (1880) by ] (1834–1923)<ref name="Venn_1880_1" /><ref name="Venn_1880_2" /> * '']'' (1880) by ] (1834–1923)
* '']'' (1953) by ] (1924–)<ref name="Karnaugh_1953" /><ref name="Curtis_1962" /> * '']'' (1953) by ]
and many others have been developed.


=== {{Anchor|Circuit minimization in Boolean algebra}}Boolean expression minimization === === {{Anchor|Circuit minimization in Boolean algebra}}Boolean expression minimization ===

Revision as of 02:53, 31 May 2022

Process in digital electronics and integrated circuit design For other uses, see Minimisation.

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 design.

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 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 a integrated circuit.

In terms of Boolean algebra, the optimization of a complex boolean expression 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 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.

With the advent of logic synthesis, one of the biggest challenges faced by the electronic design automation (EDA) industry was to find the most simple circuit 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 Hardware description languages for circuit description, formalized the logic optimization domain as it exists today, including Logic Friday (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:

Boolean expression minimization

This section may require cleanup to meet Misplaced Pages's quality standards. The specific problem is: We need more consistent, simpler and prose-like summary on every method. Please help improve this section if you can. (October 2021) (Learn how and when to remove this message)

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 Σ 2 P {\displaystyle \Sigma _{2}^{P}} -complete in time complexity (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 maps and the Quine–McCluskey algorithm that facilitate the process.

Boolean function minimizing methods include:

Espresso heuristic logic minimizer

This section is an excerpt from Espresso heuristic logic minimizer § ESPRESSO algorithm.

A different approach to this issue is followed in the ESPRESSO algorithm, developed by Brayton et al. at the University of California, Berkeley. It is a resource and performance efficient algorithm aimed at solving the heuristic hazard-free two-level logic minimization problem.

Rather than expanding a logic function into minterms, the program manipulates "cubes", representing the product terms in the ON-, DC-, and OFF- covers iteratively. Although the minimization result is not guaranteed to be the global minimum, in practice this is very closely approximated, while the solution is always free from redundancy. Compared to the other methods, this one is essentially more efficient, reducing memory usage and computation time by several orders of magnitude. Its name reflects the way of instantly making a cup of fresh coffee. There is hardly any restriction to the number of variables, output functions and product terms of a combinational function block. In general, e.g. tens of variables with tens of output functions are readily dealt with.

The input for ESPRESSO is a function table of the desired functionality; the result is a minimized table, describing either the ON-cover or the OFF-cover of the function, depending on the selected options. By default, the product terms will be shared as much as possible by the several output functions, but the program can be instructed to handle each of the output functions separately. This allows for efficient implementation in two-level logic arrays such as a PLA (Programmable Logic Array) or a PAL (Programmable Array Logic).

The ESPRESSO algorithm proved so successful that it has been incorporated as a standard logic function minimization step into virtually any contemporary logic synthesis tool. For implementing a function in multi-level logic, the minimization result is optimized by factorization and mapped onto the available basic logic cells in the target technology, whether this concerns a field-programmable gate array (FPGA) or an application-specific integrated circuit (ASIC).

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) — 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 (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 F1 and F2:

F 1 = A B + A C + A D , {\displaystyle F_{1}=AB+AC+AD,\,}
F 2 = A B + A C + A E . {\displaystyle 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.
F1 = AP + AD.
F2 = 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 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 – Encoder, Decoder, Multiplexer, Demultiplexer.

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, Counters.

Example

Original and simplified example circuit

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 B ¯ ) ( A ¯ B ) {\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\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, two AND gates, and an OR gate.

The circuit can simplified (minimized) by applying laws of Boolean algebra or using intuition. Since the example states that A {\displaystyle A} is true when B {\displaystyle B} is false and the other way around, one can conclude that this simply means A B {\displaystyle A\neq B} . In terms of logical gates, inequality simply means an XOR gate (exclusive or). Therefore, ( A B ¯ ) ( A ¯ B ) A B {\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B} . Then the two circuits shown below are equivalent, as can be checked using a truth table:

A B (A B) (A B) A B
F F F F T F T F F F F F
F T F F F T T T T F T T
T F T T T T F F F T T F
T T T F F F F F T T F T

See also

Notes

  1. The netlist size can be used to measure simplicity.

References

  1. Maxfield, Clive "Max" (2008-01-01). "Chapter 5: "Traditional" Design Flows". In Maxfield, Clive "Max" (ed.). FPGAs. Instant Access. Burlington: Newnes / Elsevier Inc. pp. 75–106. doi:10.1016/B978-0-7506-8974-8.00005-3. ISBN 978-0-7506-8974-8. Retrieved 2021-10-04.{{cite book}}: CS1 maint: url-status (link)
  2. Balasanyan, Seyran; Aghagulyan, Mane; Wuttke, Heinz-Dietrich; Henke, Karsten (2018-05-16). "Digital Electronics" (PDF). Bachelor Embedded Systems - Year Group. Tempus. DesIRE. Archived (PDF) from the original on 2021-10-04. Retrieved 2021-10-04. (101 pages)
  3. https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download
  4. Buchfuhrer, David; Umans, Christopher (January 2011). "The complexity of Boolean formula minimization" (PDF). Journal of Computer and System Sciences (JCSS). 77 (1). Computer Science Department, California Institute of Technology, Pasadena, California, USA: Elsevier Inc.: 142–153. doi:10.1016/j.jcss.2010.06.011. This is an extended version of the conference paper: Buchfuhrer, David; Umans, Christopher (2008). "The Complexity of Boolean Formula Minimization". Proceedings of Automata, Languages and Programming (PDF). Lecture Notes in Computer Science (LNCS). Vol. 5125. Berlin / Heidelberg, Germany: Springer-Verlag. pp. 24–35. doi:10.1007/978-3-540-70575-8_3. ISBN 978-3-540-70574-1. Archived (PDF) from the original on 2018-01-14. Retrieved 2018-01-14. {{cite book}}: |work= ignored (help)
  5. Brayton, Robert King; Hachtel, Gary D.; McMullen, Curtis Tracy; Sangiovanni-Vincentelli, Alberto Luigi M. (1984). Logic Minimization Algorithms for VLSI Synthesis (9th printing 2000, 1st ed.). Boston, Massachusetts, USA: Kluwer Academic Publishers. ISBN 0-89838-164-9.
  6. "Robert K. Brayton; Professor Emeritus, Professor in the Graduate School". University of California, Berkeley. 2018-09-23. Archived from the original on 2018-09-23. Retrieved 2018-09-23.
  7. Theobald, Michael; Nowick, Steven M. (1998). Fast Heuristic and Exact Algorithms for Two-Level Hazard-Free Logic Minimization. Columbia University (Report). doi:10.7916/D8N58V58. Retrieved 2021-10-04.
  8. Mano, M. Morris; Kime, Charles R. (2014). Logic and Computer Design Fundamentals (4th new international ed.). Pearson Education Limited. p. 54. ISBN 978-1-292-02468-4.

Cite error: A list-defined reference named "Venn_1880_1" is not used in the content (see the help page).

Cite error: A list-defined reference named "Venn_1880_2" is not used in the content (see the help page).

Further reading

Digital electronics
Components
Theory
Design
Applications
Design issues
  1. Nelson, Raymond J. (June 1955). "Simplest Normal Truth Functions". Journal of Symbolic Logic. 20 (2). Association for Symbolic Logic: 105–108. doi:10.2307/2266893. JSTOR 2266893. (4 pages) (NB. A method converting a conjunctive normal form into a disjunctive normal form, followed by a procedure similar to Quine's.)
  2. Nelson, Raymond J. (September 1955). "Weak Simplest Normal Truth Functions". Journal of Symbolic Logic. 20 (3). Association for Symbolic Logic: 232–234. doi:10.2307/2268219. JSTOR 2268219. (3 pages)
  3. Lipp, Hans Martin; Becker, Jürgen (2011). Grundlagen der Digitaltechnik (in German) (reworked 7th ed.). Munich, Germany: Oldenbourg Wissenschaftsverlag GmbH [de] / Walter de Gruyter. ISBN 9783486706932. ISBN 3486706934. Retrieved 2020-05-12. (316 pages)
Categories: