Logic optimization: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 05:18, 19 November 2024

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.^[1] Usually, the smaller circuit with the same function is cheaper,^[2] takes less space, consumes less power, has 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.

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 and costs time and money to produce. 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.^{[nb 1]} 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).^[3]

Methods

The methods of logic circuit simplifications are equally applicable to 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 (aka Eulerian circle) (1768) by Leonhard P. Euler (1707–1783)
Venn diagram (1880) by John Venn (1834–1923)
Karnaugh map (1953) by Maurice Karnaugh

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, a result finally proved in 2008,^[4] but there are effective heuristics such as Karnaugh maps and the Quine–McCluskey algorithm that facilitate the process.

Boolean function minimizing methods include:

Optimal multi-level methods

Methods that find optimal circuit representations of Boolean functions are often referred to 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 problem.^[5]^[6] This allows finding optimal circuit representations using a SAT solver.

Heuristic methods

A heuristic 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.

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^{[clarification needed]} — 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 representation (binary decision diagrams, algebraic decision diagrams) 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₁ and F₂:

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₁ = AP + AD.

F₂ = A'P + A'E.

While the number of levels here is 3, the total number of product terms and literals reduce ^[quantify] because of the sharing of the term B + C.

Similarly, we distinguish between combinational circuits and sequential circuits. Combinational circuits produce their outputs based only on the current inputs. They can be represented by Boolean relations. Some examples are priority encoders, binary decoders, multiplexers, demultiplexers.

Sequential circuits produce their output based on both current and past inputs, depending on a clock signal to distinguish the previous inputs from the current inputs. They can be represented by finite state machines. Some examples are flip-flops and 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.^[7] Consider the circuit used to represent $(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$ 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 simply means an XOR gate (exclusive or). Therefore, $(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

Notes

^ The netlist size can be used to measure simplicity.

References

^ 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.
^ 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)
^ Theobald, M.; Nowick, S. M. (November 1998). "Fast heuristic and exact algorithms for two-level hazard-free logic minimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 17 (11): 1130–1147. doi:10.1109/43.736186.
^ 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)
^ Haaswijk, Winston. "SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism" (PDF). EPFL. Retrieved 2022-12-07.
^ Haaswijk, Winston. "SAT-Based Exact Synthesis for Multi-Level Logic Networks" (PDF). EPFL. Retrieved 2022-12-07.
^ 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.

@@ Line 1: / Line 1: @@
-{{short description|Process in digital electronics and integrated circuit design}}
+{{short description|Process in digital electronics and integrated circuit design}}
 {{other uses|Minimisation (disambiguation){{!}}Minimisation}}
 {{bots|deny=Citation bot}}
 {{Use dmy dates|date=May 2019|cs1-dates=y}}
 {{Use list-defined references|date=January 2022}}
 '''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.<ref name="Maxfield_2008"/> The smaller circuit with the same function is cheaper,<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018"/> takes less space, [[Power efficiency|consumes less power]], have shorter latency, and minimizes risks of unexpected [[Crosstalk|cross-talk]], [[Hazard (logic)|hazard of delayed signal processing]], and other issues present at the nano-scale level of metallic structures on a [[integrated circuit]].
+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.<ref name="Maxfield_2008"/> Usually, the smaller circuit with the same function is cheaper,<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018"/> takes less space, [[Power efficiency|consumes less power]], has shorter latency, and minimizes risks of unexpected [[Crosstalk|cross-talk]], [[Hazard (logic)|hazard of delayed signal processing]], and other issues present at the nano-scale level of metallic structures on an [[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.
+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 [[Electronic circuit|circuit]] (i.e. one with many elements, such as [[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]]s.
+The problem with having a complicated [[Electronic circuit|circuit]] (i.e. one with many elements, such as [[logic gate]]s) is that each element takes up physical space and costs time and money to produce. Circuit minimization may be one form of logic optimization used to reduce the area of complex logic in [[integrated circuit]]s.
-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.<ref group="nb" name="NB_Netlist"/>  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 language]]s for circuit description, formalized the logic optimization domain as it exists today, including [[Logic Friday]] (graphical interface), Minilog, and ESPRESSO-IISOJS (many-valued logic).<ref>https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download</ref>
+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.<ref group="nb" name="NB_Netlist"/>  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 language]]s for circuit description, formalized the logic optimization domain as it exists today, including [[Logic Friday]] (graphical interface), Minilog, and ESPRESSO-IISOJS (many-valued logic).<ref>{{Cite journal |last=Theobald |first=M. |last2=Nowick |first2=S. M. |date=November 1998 |title=Fast heuristic and exact algorithms for two-level hazard-free logic minimization |url=https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download |journal=IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |volume=17 |issue=11 |pages=1130–1147 |doi=10.1109/43.736186}}</ref>
 == Methods ==
-The methods of logic circuit simplifications are equally applicable to the [[#Boolean expression minimization|boolean expression minimization]].
+The methods of logic circuit simplifications are equally applicable to [[#Boolean expression minimization|Boolean expression minimization]].
 === Classification ===
@@ Line 39: / Line 40: @@
 * ''[[Euler diagram]]'' (aka ''Eulerian circle'') (1768) by [[Leonhard P. Euler]] (1707–1783)
 * ''[[Venn diagram]]'' (1880) by [[John Venn]] (1834–1923)
 * ''[[Karnaugh map]]'' (1953) by [[Maurice Karnaugh]]
 === {{Anchor|Circuit minimization in Boolean algebra}}Boolean expression minimization ===
-{{Clean up|date=October 2021|reason=We need more consistent, simpler and prose-like summary on every method|section}}
+{{Cleanup|date=October 2021|reason=We need more consistent, simpler and prose-like summary on every method|section}}
-The same methods of boolean expression minimization (simplification) listed below may be applied to the circuit optimization.
+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 [[polynomial hierarchy|<math>\Sigma_2^P</math>-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,<ref name="Buchfuhrer_2011"/> but there are effective heuristics such as [[Karnaugh map]]s and the [[Quine–McCluskey algorithm]] that facilitate the process.
+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 [[polynomial hierarchy|<math>\Sigma_2^P</math>-complete]] in [[time complexity]], a result finally proved in 2008,<ref name="Buchfuhrer_2011"/> but there are effective heuristics such as [[Karnaugh map]]s and the [[Quine–McCluskey algorithm]] that facilitate the process.
 Boolean function minimizing methods include:
 * [[Quine–McCluskey algorithm]]
 * [[Petrick's method]]
-=== Espresso heuristic logic minimizer ===
+=== Optimal multi-level methods ===
+Methods that find optimal circuit representations of Boolean functions are often referred to 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 [[Satisfiability|Boolean satisfiability]] problem.<ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism |url=https://si2.epfl.ch/~demichel/publications/archive/2020/winston-exact.pdf |website=EPFL |access-date=7 December 2022}}</ref><ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis for Multi-Level Logic Networks |url=https://si2.epfl.ch/~demichel/graduates/theses/winston.pdf |website=EPFL |access-date=7 December 2022}}</ref> This allows finding optimal circuit representations using a [[SAT solver]].
-{{Excerpt|Espresso heuristic logic minimizer|ESPRESSO algorithm}}
+=== Heuristic methods ===
+A [[heuristic]] 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]].
 ===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]]) &mdash; which is more applicable to a [[Programmable logic array|PLA]] implementation of the design{{Clarify|date=February 2010}} &mdash; 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.
+While a two-level circuit representation of circuits strictly refers to the flattened view of the circuit in terms of SOPs ([[sum-of-products]]) &mdash; which is more applicable to a [[Programmable logic array|PLA]] implementation of the design{{Clarify|date=February 2010}} &mdash; 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 representation ([[binary decision diagram]]s, [[algebraic decision diagram]]s) 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''<sub>1</sub> and ''F''<sub>2</sub>:
@@ Line 76: / Line 80: @@
 While the number of levels here is 3, the total number of product terms and literals reduce {{Quantify|date=February 2010}} because of the sharing of the term B + C.
-Similarly, we distinguish between [[Sequential logic|sequential]] and [[Combinational logic|combinational circuits]], whose behavior can be described in terms of [[finite-state machine]] state tables/diagrams or by Boolean functions and relations respectively.
+Similarly, we distinguish between [[Combinational logic|combinational circuits]] and [[Sequential logic|sequential circuits]]. Combinational circuits produce their outputs based only on the current inputs. They can be represented by Boolean [[Relation (mathematics)|relations]]. Some examples are [[priority encoder]]s, [[binary decoder]]s, [[multiplexer]]s, [[demultiplexer]]s.
-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]].
+Sequential circuits produce their output based on both current and past inputs, depending on a clock signal to distinguish the previous inputs from the current inputs. They can be represented by finite state machines. Some examples are [[Flip-flop (electronics)|flip-flops]] and [[Counter (digital)|counters]].
 ==Example==
@@ Line 109: / Line 112: @@
 * [[Function decomposition]]
 * [[Gate underutilization]]
+* [[Logic redundancy]]
 * <!-- some of the Wikiversity/Wikibook contents could be used to create a local article at -->[[Harvard minimizing chart]] [[:wikiversity:Harvard chart method|(Wikiversity)]] [[:wikibooks:Harvard Chart Method|(Wikibooks)]]
@@ Line 118: / Line 122: @@
 == References ==
 {{reflist|refs=
-<ref name="Maxfield_2008">{{cite book |title=FPGAs |chapter=Chapter 5: "Traditional" Design Flows |author-last=Maxfield |author-first=Clive "Max" |date=2008-01-01 |editor-last=Maxfield |editor-first=Clive "Max" |series=Instant Access |publication-place=Burlington |publisher=[[Newnes (publisher)|Newnes]] / [[Elsevier Inc.]] |isbn=978-0-7506-8974-8 |<!-- chapter- -->doi=10.1016/B978-0-7506-8974-8.00005-3 |pages=75–106 |chapter-url=https://www.sciencedirect.com/science/article/pii/B9780750689748000053 |access-date=2021-10-04 |url-status=live |archive-url= |archive-date=}}</ref>
+<ref name="Maxfield_2008">{{cite book |title=FPGAs |chapter=Chapter 5: "Traditional" Design Flows |author-last=Maxfield |author-first=Clive "Max" |date=2008-01-01 |editor-last=Maxfield |editor-first=Clive "Max" |series=Instant Access |publication-place=Burlington |publisher=[[Newnes (publisher)|Newnes]] / [[Elsevier Inc.]] |isbn=978-0-7506-8974-8 |<!-- chapter- -->doi=10.1016/B978-0-7506-8974-8.00005-3 |pages=75–106 |chapter-url=https://www.sciencedirect.com/science/article/pii/B9780750689748000053 |access-date=2021-10-04 }}</ref>
 <ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018">{{cite web |title=Digital Electronics |author-last1=Balasanyan |author-first1=Seyran |author-last2=Aghagulyan |author-first2=Mane |author-last3=Wuttke |author-first3=Heinz-Dietrich |author-last4=Henke |author-first4=Karsten |date=2018-05-16 |id=DesIRE |series=Bachelor Embedded Systems - Year Group |publisher=Tempus |pages= |url=https://ec.europa.eu/programmes/erasmus-plus/project-result-content/120e4810-0d29-4397-9ad4-b4091c2e3d19/Digital%20Electronics.pdf |access-date=2021-10-04 |url-status=live |archive-url=https://web.archive.org/web/20211004200546/https://ec.europa.eu/programmes/erasmus-plus/project-result-content/120e4810-0d29-4397-9ad4-b4091c2e3d19/Digital%20Electronics.pdf |archive-date=2021-10-04}} (101 pages)</ref>
-<ref name="Venn_1880_1">{{cite journal |author-last=Venn |author-first=John |author-link=John Venn |title=I. On the Diagrammatic and Mechanical Representation of Propositions and Reasonings |journal=[[The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science]] |volume=10 |issue=59 |date=July 1880 |series=5 |doi=10.1080/14786448008626877 |pages=1–18 |url=https://www.cis.upenn.edu/~bhusnur4/cit592_fall2014/venn%20diagrams.pdf |url-status=live |archive-url=https://web.archive.org/web/20170516204620/https://www.cis.upenn.edu/~bhusnur4/cit592_fall2014/venn%20diagrams.pdf |archive-date=2017-05-16}} [http://www.tandfonline.com/doi/abs/10.1080/14786448008626877] [https://books.google.com/books?id=k68vAQAAIAAJ&pg=PA1]</ref>
-<ref name="Venn_1880_2">{{cite journal |author-last=Venn |author-first=John |author-link=John Venn |date=1880 |url=https://archive.org/stream/proceedingsofcam4188083camb#page/47/mode/1up |title=On the employment of geometrical diagrams for the sensible representations of logical propositions |journal=[[Proceedings of the Cambridge Philosophical Society]] |volume=4 |pages=47–59}}</ref>
 <ref name="Buchfuhrer_2011">{{cite journal |doi=10.1016/j.jcss.2010.06.011 |title=The complexity of Boolean formula minimization |journal=[[Journal of Computer and System Sciences]] (JCSS) |volume=77 |issue=1 |pages=142–153 |date=January 2011 |location=Computer Science Department, [[California Institute of Technology]], Pasadena, California, USA |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans |publisher=[[Elsevier Inc.]] |url=http://users.cms.caltech.edu/~umans/papers/BU07.pdf}} This is an extended version of the conference paper: {{cite book |doi=10.1007/978-3-540-70575-8_3 |chapter=The Complexity of Boolean Formula Minimization |title=Proceedings of Automata, Languages and Programming |work=35th International Colloquium (ICALP) |volume=5125 |pages=24–35 |publisher=[[Springer-Verlag]] |publication-place=Berlin / Heidelberg, Germany |series=[[Lecture Notes in Computer Science]] (LNCS) |date=2008 |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans |isbn=978-3-540-70574-1 |url=http://users.cms.caltech.edu/~umans/papers/BU07.pdf |access-date=2018-01-14 |url-status=live |archive-url=https://web.archive.org/web/20180114141842/http://users.cms.caltech.edu/~umans/papers/BU07.pdf |archive-date=2018-01-14}}</ref>
 <ref name="Mano_2014">{{cite book |author-first1=M. Morris |author-last1=Mano |author-first2=Charles R. |author-last2=Kime |title=Logic and Computer Design Fundamentals |edition=4th new international |publisher=[[Pearson Education Limited]] |date=2014 |page=54 |isbn=978-1-292-02468-4}}</ref>
 }}
 == Further reading ==
+* {{cite book |author-last1=Lind |author-first1=Larry Frederick |author-last2=Nelson |author-first2=John Christopher Cunliffe |title=Analysis and Design of Sequential Digital Systems |date=1977 |publisher=[[Macmillan Press]] |isbn=0-33319266-4 |url=https://archive.org/details/AnalysisDesignOfSequentialDigitalSystems/}} (146 pages)
-* {{cite journal |author-last=Hwa |author-first="Sherman" Hsuen Ren |title=A Method of Generating Prime Implicants of a Boolean Expression |journal=[[IEEE Transactions on Computers]] |issn=0018-9340 |eissn=1557-9956 |id=CD-{{ISSN|2326-3814}}. 1F09 |publisher=[[IEEE]] |volume=C-23 |issue=6 |date=June 1974 |doi=10.1109/T-C.1974.224003 |s2cid=10646917 |pages=637–641 |url=https://ieeexplore.ieee.org/document/1672596 |access-date=2020-05-12 |postscript=;}} {{cite book |author-last=Hwa |author-first="Sherman" Hsuen Ren |title=A Method of Generating Prime Implicants of a Boolean Expression |publisher=Basser Department of Computer Science, [[University of Sydney]] |date=April 1973 |id=Technical Report 82}}
-* {{cite book |author-last1=Lind |author-first1=Larry Frederick |author-last2=Nelson |author-first2=John Christopher Cunliffe |title=Analysis and Design of Sequential Digital Systems |date=1977 |publisher=[[Macmillan Press]] |isbn=0-33319266-4 |url=https://archive.org/details/AnalysisDesignOfSequentialDigitalSystems/}} [https://books.google.com/books?id=fj1dDwAAQBAJ] (146 pages)
-* {{cite journal |title=A method of generating prime factors of a Boolean Expression in a conjunctive normal form with the possibility of inclusion of Don't care combination |author-first=Debidas |author-last=Ghosh |journal=Journal of Technology |volume=XXII |number=1 |date=June 1977 |orig-date=1977-01-21 |location=Department of Mathematics, Bengal Engineering College, Howrah, India |url=https://shodhganga.inflibnet.ac.in/bitstream/10603/158814/10/10_reprints.pdf |access-date=2020-05-12 |url-status=live |archive-url=https://web.archive.org/web/20200512132724/https://shodhganga.inflibnet.ac.in/bitstream/10603/158814/10/10_reprints.pdf |archive-date=2020-05-12}}
 * {{cite book |title=Synthesis and Optimization of Digital Circuits |author-first=Giovanni |author-last=De Micheli |author-link=Giovanni De Micheli |date=1994 |publisher=[[McGraw-Hill]] |isbn=0-07-016333-2}} (NB. Chapters 7–9 cover combinatorial two-level, combinatorial multi-level, and respectively sequential circuit optimization.)
 * {{cite book |author-first1=Gary D. |author-last1=Hachtel |author-first2=Fabio |author-last2=Somenzi |title=Logic Synthesis and Verification Algorithms |date=2006 |orig-date=1996 |publisher=[[Springer Science & Business Media]] |isbn=978-0-387-31005-3}}
 * {{cite book |author-first1=Zvi |author-last1=Kohavi |author-first2=Niraj K. |author-last2=Jha |title=Switching and Finite Automata Theory |edition=3rd |publisher=[[Cambridge University Press]] |date=2009 |isbn=978-0-521-85748-2 |chapter=4–6}}
-* {{cite book |title=The Art of Computer Programming |title-link=The Art of Computer Programming |date=2010 |author-last=Knuth |author-first=Donald Ervin |author-link=Donald Ervin Knuth |volume=4A |chapter=7.1.2: Boolean Evaluation |publisher=[[Addison-Wesley]] |pages=96–133 |isbn=978-0-201-03804-0}}
 * {{cite book |author-first=Rob A. |author-last=Rutenbar |title=Multi-level minimization, Part I: Models & Methods |type=lecture slides |publisher=[[Carnegie Mellon University]] (CMU) |id=Lecture 7 |url=https://www.ece.cmu.edu/~ee760/760docs/lec07.pdf |access-date=2018-01-15 |url-status=live |archive-url=https://web.archive.org/web/20180115125725/https://www.ece.cmu.edu/~ee760/760docs/lec07.pdf |archive-date=2018-01-15 |postscript=;}} {{cite book |author-first=Rob A. |author-last=Rutenbar |title=Multi-level minimization, Part II: Cube/Cokernel Extract |type=lecture slides |publisher=[[Carnegie Mellon University]] (CMU) |id=Lecture 8 |url=https://www.ece.cmu.edu/~ee760/760docs/lec08.pdf |access-date=2018-01-15 |url-status=live |archive-url=https://web.archive.org/web/20180115125733/https://www.ece.cmu.edu/~ee760/760docs/lec08.pdf |archive-date=2018-01-15}}
-* {{cite journal |author-last1=Tomaszewski |author-first1=Sebastian P. |author-last2=Celik |author-first2=Ilgaz U. |author-last3=Antoniou |author-first3=George E. |title=WWW-based Boolean function minimization |journal=[[International Journal of Applied Mathematics and Computer Science]] |volume=13 |issue=4 |date=December 2003 |orig-date=2003-03-05, 2002-04-09 |pages=577–584 |url=http://matwbn.icm.edu.pl/ksiazki/amc/amc13/amc13414.pdf |access-date=2020-05-10 |url-status=live |archive-url=https://web.archive.org/web/20200510214937/http://matwbn.icm.edu.pl/ksiazki/amc/amc13/amc13414.pdf |archive-date=2020-05-10}} [https://www.researchgate.net/publication/228862329_WWW-based_Boolean_function_minimization][https://archive.today/20180115131301/http://matwbn.icm.edu.pl/ksiazki/amc/amc13/amc13414.pdf] (7 pages)
-* <!-- Kudielka already cited above, but contains other relevant papers as well -->{{cite book |editor-first1=Johannes |editor-last1=Dörr |editor-first2=Ernst Ferdinand |editor-last2=Peschl |editor-link2=Ernst Ferdinand Peschl |editor-first3=Heinz |editor-last3=Unger |editor-link3=:de:Heinz Unger (Mathematiker) |author-first1=Alexander |author-last1=Wilhelmy |author-first2=Viktor |author-last2=Kudielka |author-first3=Peter |author-last3=Deussen |author-first4=Karl Heinz |author-last4=Böhling |author-link4=:de:Karl Heinz Böhling |author-first5=Wolfgang |author-last5=Händler |author-link5=Wolfgang Händler |author-first6=Joachim |author-last6=Neander |title=2. Colloquium über Schaltkreis- und Schaltwerk-Theorie - Vortragsauszüge vom 18. bis 20. Oktober 1961 in Saarbrücken |language=de |series=Internationale Schriftenreihe zur Numerischen Mathematik [International Series of Numerical Mathematics] (ISNM) |volume=4 |date=January 1963 |orig-date=1961-10-18 |edition=2013-12-20 reprint of 1st |location=Institut für Angewandte Mathematik, [[Universität Saarbrücken]], Rheinisch-Westfälisches Institut für Instrumentelle Mathematik |publisher=[[Springer Basel AG]] / [[Birkhäuser Verlag Basel]] |isbn=978-3-0348-4081-1 |doi=10.1007/978-3-0348-4156-6 |url=https://books.google.com/books?id=exCmBgAAQBAJ |access-date=2020-04-15 }} (152 pages)
-* {{cite journal |author-first1=Robert King |author-last1=Brayton |author-link1=:wikidata:Q15842652 |author-first2=Richard L. |author-last2=Rudell |author-first3=Alberto Luigi |author-last3=Sangiovanni-Vincentelli |author-link3=Alberto Luigi Sangiovanni-Vincentelli |author-first4=Albert R. |author-last4=Wang |title=MIS: A Multiple-Level Logic Optimization System |journal=[[IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems]] |volume=6 |number=6 |pages=1062–1081 |date=December 1987 |doi=10.1109/TCAD.1987.1270347 |url=https://www.researchgate.net/publication/3225465_MIS_A_Multiple-Level_Logic_Optimization_System}} (MIS) (20 pages)
-* {{cite journal |author-first1=Aart J. |author-last1=De Geus |author-link1=Aart de Geus |author-first2=William W. |author-last2=Cohen |title=A Rule-Based System for Optimizing Combinational Logic |journal=[[IEEE Design & Test of Computers]] |issn=0740-7475 |eissn=1558-1918 |volume=2 |number=4 |date=July–August 1985 |doi=10.1109/MDT.1985.294719 |s2cid=46651690 |pages=22–32 |url=https://dl.acm.org/doi/10.1109/MDT.1985.294719 |access-date=2021-02-19 |url-status=live |archive-url=https://web.archive.org/web/20210219095415/https://dl.acm.org/doi/10.1109/MDT.1985.294719 |archive-date=2021-02-19}} (11 pages) [https://web.archive.org/web/20210219102125/https://www.computer.org/csdl/magazine/dt/1985/04/04069623/13rRUy3gmYS] (SOCRATES)
-* {{cite book |title=Advanced Techniques in Logic Synthesis, Optimizations and Applications |editor-first1=Sunil P. |editor-last1=Khatri |editor-first2=Kanupriya |editor-last2=Gulati |edition=1 |isbn=978-1-4419-7517-1 |publisher=[[Springer Science+Business Media, LLC]] |date=2011 |publication-place=New York / Dordrecht / Heidelberg / London}} (xxii+423+1 pages)
-* {{cite magazine |title=A More Efficient Use of Karnaugh Maps |author-first=Jobst E. |author-last=Jesse |magazine=Computer Design |issn=0010-4566 |id={{CODEN|CMPDA}} |oclc=828863003 |publisher=Computer Design Publishing Corporation |publication-place=Concord, Massachusetts, USA |location=Sunnyvale, California, USA |volume=11 |issue=2 |date=February 1972 |pages=80–82 |url=https://books.google.com/books?id=oSFHAQAAIAAJ&dq=editions%3ASTANFORD36105000958269&focus=searchwithinvolume&q=A+More+Efficient+Use+of+Karnaugh+Maps}} (3 pages)
-* {{cite journal |author-first=Bernd |author-last=Reusch |title=Generation of Prime Implicants from Subfunctions and a Unifying Approach to the Covering Problem |journal=[[IEEE Transactions on Computers]] |issn=0018-9340 |eissn=1557-9956 |id=CD-{{ISSN|2326-3814}} |publisher=[[IEEE]] |volume=C-24 |number=9 |date=September 1975 |doi=10.1109/T-C.1975.224338 |s2cid=32090834 |pages=924–930 |url=https://dl.acm.org/doi/abs/10.1109/T-C.1975.224338 |access-date=2021-02-19}} (7 pages)
-* {{cite magazine |title=To the Editor |department=Letters to the editor |author-first=R. L. |author-last=Dineley |magazine=Computer Design |issn=0010-4566 |id={{CODEN|CMPDA}} |oclc=828863003 |publisher=Computer Design Publishing Corporation |publication-place=Concord, Massachusetts, USA |volume=8 |issue=4 |date=April 1969 |page=16 |url=https://books.google.com/books?id=Uy4-AQAAIAAJ&dq=%22infrequent+variable%22+karnaugh&focus=searchwithinvolume&q=Dineley |quote-page=16 |quote=[…] I would like to offer a method for the simplification of [[maxterm]] type [[Boolean expression]] by use of the [[Veitch diagram]]. To the best of my knowledge, I am the originator of the method, having derived it in 1960 while attending the Digital Computer Fundamentals course at [[Redstone Arsenal]]. Most texts simplify the maxterm ([[product of sums]]) type expression by plotting the individual terms on separate Veitch diagrams and then overlaying the diagrams to discover the intersects, or "anded," function. […] The method offered here permits the plotting of all terms on one diagram with the "anded" relationship easily discernible. […] Each sum term of the expression is assigned a symbol. This symbol is plotted on the Veitch for each of the or'd factors of the term. The "and" function occurs whenever any square or combination of 2<sup>n</sup> adjacent squares contain all of the assigned symbols. A simple example will illustrate. […] (A + BC)<sup>[1]</sup> (A + C)<sup>[2]</sup> = A + BC […] Yours truly, R. L. Dineley, Sperry Rand Corp.}} (1 page) (NB. Referred to in [[#Schultz-1969-2|Schultz's letter]] above.)
-* {{cite book |title=A Survey of Literature on Function Decomposition |chapter=6. Historical Overview of the Research on Decomposition |version=Version IV |author-first1=Marek A. |author-last1=Perkowski |author-first2=Stanislaw |author-last2=Grygiel |publisher=Functional Decomposition Group, Department of Electrical Engineering, Portland University, Portland, Oregon, USA |date=1995-11-20 |citeseerx=10.1.1.64.1129 |url=http://web.cecs.pdx.edu/~mperkows/=PUBLICATIONS/PER/G1995/survey.pdf |access-date=2021-03-28 |url-status=live |archive-url=https://web.archive.org/web/20210328181709/http://web.cecs.pdx.edu/~mperkows/=PUBLICATIONS/PER/G1995/survey.pdf |archive-date=2021-03-28}} (188 pages)<!-- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.4349&rep=rep1&type=pdf -->
-* {{cite web |title=Publications in the First Twenty Years of Switching Theory and Logic Design |author-first1=Radomir S. |author-last1=Stanković |author-first2=Tsutomu |author-last2=Sasao |author-first3=Jaakko T. |author-last3=Astola |series=Tampere International Center for Signal Processing (TICSP) Series |id=#14 |issn=1456-2774 |location=Tampere University of Technology / TTKK, Monistamo, Finland |date=August 2001 |s2cid=62319288 |url=http://ticsp.cs.tut.fi/images/a/a5/Stari-radovi-report.pdf |access-date=2021-03-28 |url-status=live |archive-url=https://web.archive.org/web/20170809064702/http://ticsp.cs.tut.fi/images/a/a5/Stari-radovi-report.pdf |archive-date=2017-08-09}} (4+60 pages)
-<ref name="Nelson_1955_1">{{cite journal |title=Simplest Normal Truth Functions |author-first=Raymond J. |author-last=Nelson |journal=[[Journal of Symbolic Logic]] |publisher=[[Association for Symbolic Logic]] |doi=10.2307/2266893 |jstor=2266893 |volume=20 |number=2 |date=June 1955 |pages=105–108}} (4 pages) (NB. A method converting a [[conjunctive normal form]] into a [[disjunctive normal form]], followed by a procedure similar to [[Willard Van Orman Quine|Quine]]'s.)</ref>
-<ref name="Nelson_1955_2">{{cite journal |title=Weak Simplest Normal Truth Functions |author-first=Raymond J. |author-last=Nelson |journal=[[Journal of Symbolic Logic]] |publisher=[[Association for Symbolic Logic]] |volume=20 |number=3 |date=September 1955 |doi=10.2307/2268219 |jstor=2268219 |pages=232–234}} (3 pages)</ref>
-<ref name="Lipp_2011">{{cite book |title=Grundlagen der Digitaltechnik |language=de |author-first1=Hans Martin |author-last1=Lipp |author-first2=Jürgen |author-last2=Becker |publisher={{ill|Oldenbourg Verlag{{!}}Oldenbourg Wissenschaftsverlag GmbH|de|Oldenbourg Wissenschaftsverlag}} / [[Walter de Gruyter]] |publication-place=Munich, Germany |date=2011 |isbn=9783486706932 |id={{ISBN|3486706934}} |edition=reworked 7th |url=https://books.google.com/books?id=xinpBQAAQBAJ |access-date=2020-05-12}} (316 pages)</ref>
 {{digital electronics}}

v t e Digital electronics
Components	Transistor Resistor Inductor Capacitor Printed electronics Printed circuit board Electronic circuit Flip-flop Memory cell Combinational logic Sequential logic Logic gate Boolean circuit Integrated circuit (IC) Hybrid integrated circuit (HIC) Mixed-signal integrated circuit Three-dimensional integrated circuit (3D IC) Emitter-coupled logic (ECL) Erasable programmable logic device (EPLD) Macrocell array Programmable logic array (PLA) Programmable logic device (PLD) Programmable Array Logic (PAL) Generic Array Logic (GAL) Complex programmable logic device (CPLD) Field-programmable gate array (FPGA) Field-programmable object array (FPOA) Application-specific integrated circuit (ASIC) Tensor Processing Unit (TPU)
Theory	Digital signal Boolean algebra Logic synthesis Logic in computer science Computer architecture Digital signal Digital signal processing Circuit minimization Switching circuit theory Gate equivalent
Design	Logic synthesis Place and route Placement Routing Transaction-level modeling Register-transfer level Hardware description language High-level synthesis Formal equivalence checking Synchronous logic Asynchronous logic Finite-state machine Hierarchical state machine
Applications	Computer hardware Hardware acceleration Digital audio radio Digital photography Digital telephone Digital video cinematography television Electronic literature
Design issues	Metastability Runt pulse