Logic optimization: Difference between revisions

Revision as of 02:53, 31 May 2022

Latest revision as of 13:37, 23 April 2025

(39 intermediate revisions by 20 users not shown)

Line 1:

{{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}}

{{Use dmy dates|date=May 2019|cs1-dates=y}}

'''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"/> TheUsually, the smaller circuit with the same function is cheaper,<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018"/> takes less space, [[Power efficiency|consumes less power]], havehas 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 aan [[integrated circuit]].

In terms of [[Boolean algebra]], the optimization of a complex [[booleanBoolean 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.

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|booleanBoolean expression minimization]].

=== Classification ===

Line 39 ⟶ 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 upCleanup|date=October 2021|reason=We need more consistent, simpler and prose-like summary on every method|section}}

The same methods of booleanBoolean 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.

Boolean function minimizing methods include:

* [[Quine–McCluskey algorithm]]

* [[Petrick's method]]

=== EspressoOptimal heuristicmulti-level logic minimizermethods ===

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 representation ([[Binarybinary decision diagramsdiagram]]s, Algebraic[[algebraic Decisiondecision Diagrams (ADDs)diagram]]s) 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''₁ and ''F''₂:

Line 76 ⟶ 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 [[SequentialCombinational logic|sequentialcombinational circuits]] and [[CombinationalSequential logic|combinationalsequential circuits]],. Combinational circuits produce their outputs based only on the current whoseinputs. behaviorThey can be describedrepresented inby terms ofBoolean [[finite-stateRelation machine(mathematics)|relations]]. stateSome tables/diagramsexamples orare by[[priority Booleanencoder]]s, functions[[binary anddecoder]]s, relations[[multiplexer]]s, respectively[[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 areproduce thosetheir whichoutput are dependentbased on clockboth cyclescurrent and dependspast inputs, depending on presenta asclock wellsignal asto pastdistinguish the previous inputs tofrom generatethe anycurrent outputinputs. ExamplesThey –can be represented by finite state machines. Some examples are [[Flip-flop (electronics)|flip-flops]], and [[CountersCounter (digital)|counters]].

==Example==

Line 109 ⟶ 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 ⟶ 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="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="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="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/}} [https://books.google.com/books?id=fj1dDwAAQBAJ] (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ⁿ adjacent squares contain all of the assigned symbols. A simple example will illustrate. […] (A + BC)^[1] (A + C)^[2] = 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}}