Quine–McCluskey algorithm

From Wikipedia, the free encyclopedia

Jump to navigation Jump to search

algorithm for the minimization of Boolean functions

Hasse diagram of the search graph of the algorithm for 3 variables. Given e.g. the subset ${\displaystyle S=\{abc,a{\overline {b}}c,{\overline {a}}bc,{\overline {a}}b{\overline {c}},{\overline {a}}{\overline {b}}c\}}$ of the bottom-level nodes (light green), the algorithm computes a minimal set of nodes (here: ${\displaystyle \{{\overline {a}}b,c\}}$, dark green) that covers exactly ${\displaystyle S}$.

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^[1][2] and extended by Edward J. McCluskey in 1956.^[3] As a general principle this approach had already been demonstrated by the logician Hugh McColl in 1878,^[4][5][6] was proved by Archie Blake in 1937,^[7][8][9][6] and was rediscovered by Edward W. Samson and Burton E. Mills in 1954^[10][6] and by Raymond J. Nelson in 1955.^[11][6] Also in 1955, Paul W. Abrahams and John G. Nordahl^[12] as well as Albert A. Mullin and Wayne G. Kellner^{[13][14][15][16]} proposed a decimal variant of the method.^{[17][14][15][16][18][19][20][21]}

The Quine–McCluskey algorithm is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method.

The method involves two steps:

1. Finding all prime implicants of the function.
2. Use those prime implicants in a prime implicant chart to find the essential prime implicants of the function, as well as other prime implicants that are necessary to cover the function.

Contents

• 1 Complexity
• 2 Example
  • 2.1 Input
  • 2.2 Step 1: finding prime implicants
  • 2.3 Step 2: prime implicant chart
• 3 See also
• 4 References
• 5 Further reading
• 6 External links

Complexity[edit]

Although more practical than Karnaugh mapping when dealing with more than four variables, the Quine–McCluskey algorithm also has a limited range of use since the problem it solves is NP-complete.^[22][23][24] The running time of the Quine–McCluskey algorithm grows exponentially with the number of variables. For a function of n variables the number of prime implicants can be as large as 3ⁿ / ln(n),^{[citation needed]} e.g. for 32 variables there may be over 534 × 10¹² prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal heuristic methods, of which the Espresso heuristic logic minimizer was the de facto standard in 1995.^{[needs update][25]}

Step two of the algorithm amounts to solving the set cover problem;^[26] NP-hard instances of this problem may occur in this algorithm step.^[27][28]

Example[edit]

Input[edit]

In this example, the input is a Boolean function in four variables, ${\displaystyle f:\{0,1\}^{4}\to \{0,1\}}$ which evaluates to ${\displaystyle 1}$ on the values ${\displaystyle 4,8,10,11,12}$ and ${\displaystyle 15}$, evaluates to an unknown value on ${\displaystyle 9}$ and ${\displaystyle 14}$, and to ${\displaystyle 0}$ everywhere else (where these integers are interpreted in their binary form for input to ${\displaystyle f}$ for succinctness of notation). The inputs that evaluate to ${\displaystyle 1}$ are called 'minterms'. We encode all of this information by writing

${\displaystyle f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,}$

This expression says that the output function f will be 1 for the minterms ${\displaystyle 4,8,10,11,12}$ and ${\displaystyle 15}$ (denoted by the 'm' term) and that we don't care about the output for ${\displaystyle 9}$ and ${\displaystyle 14}$ combinations (denoted by the 'd' term).

Step 1: finding prime implicants[edit]

First, we write the function as a table (where 'x' stands for don't care):

	A	B	C	D	f
m0	0	0	0	0	0
m1	0	0	0	1	0
m2	0	0	1	0	0
m3	0	0	1	1	0
m4	0	1	0	0	1
m5	0	1	0	1	0
m6	0	1	1	0	0
m7	0	1	1	1	0
m8	1	0	0	0	1
m9	1	0	0	1	x
m10	1	0	1	0	1
m11	1	0	1	1	1
m12	1	1	0	0	1
m13	1	1	0	1	0
m14	1	1	1	0	x
m15	1	1	1	1	1

One can easily form the canonical sum of products expression from this table, simply by summing the minterms (leaving out don't-care terms) where the function evaluates to one:

f_A,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

which is not minimal. So to optimize, all minterms that evaluate to one are first placed in a minterm table. Don't-care terms are also added into this table (names in parentheses), so they can be combined with minterms:

Number of 1s	Minterm	Binary Representation
1	m4	0100
	m8	1000
2	(m9)	1001
	m10	1010
	m12	1100
3	m11	1011
	(m14)	1110
4	m15	1111

At this point, one can start combining minterms with other minterms. If two terms differ by only a single digit, that digit can be replaced with a dash indicating that the digit doesn't matter. Terms that can't be combined any more are marked with an asterisk (*). For instance 1000 and 1001 can be combined to give 100-, indicating that both minterms imply the first digit is 1 and the next two are 0.

Number of 1s	Minterm	0-Cube	Size 2 Implicants
1	m4	0100	m(4,12)	-100*
	m8	1000	m(8,9)	100-
	—	—	m(8,10)	10-0
	—	—	m(8,12)	1-00
2	m9	1001	m(9,11)	10-1
	m10	1010	m(10,11)	101-
	—	—	m(10,14)	1-10
	m12	1100	m(12,14)	11-0
3	m11	1011	m(11,15)	1-11
	m14	1110	m(14,15)	111-
4	m15	1111	—

When going from Size 2 to Size 4, treat - as a third bit value. For instance, -110 and -100 can be combined to give -1-0, as can -110 and -11- to give -11-, but -110 and 011- cannot because -110 is implied by 1110 while 011- is not. (Trick: Match up the - first.)

Number of 1s	Minterm	0-Cube	Size 2 Implicants		Size 4 Implicants
1	m4	0100	m(4,12)	-100*	m(8,9,10,11)	10--*
	m8	1000	m(8,9)	100-	m(8,10,12,14)	1--0*
	—	—	m(8,10)	10-0	—
	—	—	m(8,12)	1-00	—
2	m9	1001	m(9,11)	10-1	m(10,11,14,15)	1-1-*
	m10	1010	m(10,11)	101-	—
	—	—	m(10,14)	1-10	—
	m12	1100	m(12,14)	11-0	—
3	m11	1011	m(11,15)	1-11	—
	m14	1110	m(14,15)	111-	—
4	m15	1111		—	—

Note: In this example, none of the terms in the size 4 implicants table can be combined any further. In general this process should be continued (sizes 8, 16 etc.) until no more terms can be combined.

Step 2: prime implicant chart[edit]

None of the terms can be combined any further than this, so at this point we construct an essential prime implicant table. Along the side goes the prime implicants that have just been generated, and along the top go the minterms specified earlier. The don't care terms are not placed on top—they are omitted from this section because they are not necessary inputs.

	4	8	10	11	12	15	⇒	A	B	C	D
m(4,12)*							⇒	—	1	0	0
m(8,9,10,11)							⇒	1	0	—	—
m(8,10,12,14)							⇒	1	—	—	0
m(10,11,14,15)*							⇒	1	—	1	—

To find the essential prime implicants, we run along the top row. We have to look for columns with only one "✓". If a column has only one "✓", this means that the minterm can only be covered by one prime implicant. This prime implicant is essential.

For example: in the first column, with minterm 4, there is only one "✓". This means that m(4,12) is essential. So we place a star next to it. Minterm 15 also has only one "✓", so m(10,11,14,15) is also essential. Now all columns with one "✓" are covered.

The second prime implicant can be 'covered' by the third and fourth, and the third prime implicant can be 'covered' by the second and first, and neither is thus essential. If a prime implicant is essential then, as would be expected, it is necessary to include it in the minimized boolean equation. In some cases, the essential prime implicants do not cover all minterms, in which case additional procedures for chart reduction can be employed. The simplest "additional procedure" is trial and error, but a more systematic way is Petrick's method. In the current example, the essential prime implicants do not handle all of the minterms, so, in this case, the essential implicants can be combined with one of the two non-essential ones to yield one equation:

f_A,B,C,D = BC'D' + AB' + AC^[29]

or

f_A,B,C,D = BC'D' + AD' + AC

Both of those final equations are functionally equivalent to the original, verbose equation:

f_A,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.

See also[edit]

• Blake canonical form^[7][6]
• Buchberger's algorithm – analogous algorithm for algebraic geometry
• Petrick's method
• Qualitative comparative analysis (QCA)

References[edit]

1. ^ Quine, Willard Van Orman (October 1952). "The Problem of Simplifying Truth Functions". The American Mathematical Monthly. 59 (8): 521–531. doi:10.2307/2308219. JSTOR 2308219.
2. ^ Quine, Willard Van Orman (November 1955). "A Way to Simplify Truth Functions". The American Mathematical Monthly. 62 (9): 627–631. doi:10.2307/2307285. hdl:10338.dmlcz/142789. JSTOR 2307285.
3. ^ McCluskey, Jr., Edward Joseph (November 1956). "Minimization of Boolean Functions". Bell System Technical Journal. 35 (6): 1417–1444. doi:10.1002/j.1538-7305.1956.tb03835.x. hdl:10338.dmlcz/102933. Retrieved 2014-08-24.
4. ^ McColl, Hugh (1878-11-14). "The Calculus of Equivalent Statements (Third Paper)". Proceedings of the London Mathematical Society. s1-10 (1): 16–28. doi:10.1112/plms/s1-10.1.16.
5. ^ Ladd, Christine (1883). "On the algebra of logic". In Peirce, Charles Sanders (ed.). Studies in Logic. Boston, USA: Little, Brown & Company. pp. 17–71. p. 23: [...] If the reduction [of an expression to simplest form] is not evident, it may be facilitated by taking the negative of the expression, reducing it, and then restoring it to the positive form. [...]
6. ^ ^{a b c d e} Brown, Frank Markham (November 2010) [2010-10-27]. "McColl and Minimization". History and Philosophy of Logic. Taylor & Francis. 31 (4): 337–348. doi:10.1080/01445340.2010.517387. ISSN 1464-5149. Archived from the original on 2020-04-15. Retrieved 2020-04-15.
7. ^ ^{a b} Blake, Archie (1938) [1937]. Canonical Expressions in Boolean Algebra (Dissertation) (Lithographed ed.). Chicago, Illinois, USA: University of Chicago Libraries. p. 36. p. 36: [...] this method was known to Peirce and his students [...] It is mentioned at several places in Studies in Logic, by members of the Johns Hopkins University, 1883 [...] (ii+60 pages)
8. ^ Blake, Archie (November 1932). "Canonical expressions in Boolean algebra". Bulletin of the American Mathematical Society. Abstracts of Papers: 805.
9. ^ Blake, Archie (June 1938). "Corrections to Canonical Expressions in Boolean Algebra". The Journal of Symbolic Logic. Association for Symbolic Logic. 3 (2): 112–113. doi:10.2307/2267595. ISSN 0022-4812. JSTOR 2267595.
10. ^ Samson, Edward Walter; Mills, Burton E. (April 1954). Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions. Bedford, Massachusetts, USA: Air Force Cambridge Research Center. Technical Report AFCRC TR 54-21.
11. ^ Nelson, Raymond J. (June 1955). "Simplest Normal Truth Functions". The Journal of Symbolic Logic. Association for Symbolic Logic. 20 (2): 105–108. doi:10.2307/2266893. JSTOR 2266893. (4 pages)
12. ^ "Welcome to the memorial page for John "Jack" G Nordahl June 14, 1933 ~ November 20, 2017 (age 84)". Jellison Funeral Home and Cremation Services. Archived from the original on 2020-05-05. Retrieved 2020-05-05.
13. ^ Mullin, Albert Alkins; Kellner, Wayne G. (1958). Written at University of Illinois, Urbana, USA and Electrical Engineering Department, Massachusetts Institute of Technology, Massachusetts, USA. "A Residue Test for Boolean Functions" (PDF). Transactions of the Illinois State Academy of Science (Teaching memorandum). Springfield, Illinois, USA. 51 (3–4): 14–19. S2CID 125171479. Archived (PDF) from the original on 2020-05-05. Retrieved 2020-05-05. [1] (6 pages) (NB. In his book, Caldwell dates this to November 1955 as a teaching memorandum. Since Mullin dates their work to 1958 in another work and Abrahams/Nordahl's class memorandum is also dated November 1955, this could be a copy error.)
14. ^ ^{a b} Caldwell, Samuel Hawks (1958-12-01) [February 1958]. "5.8. Operations Using Decimal Symbols". Written at Watertown, Massachusetts, USA. Switching Circuits and Logical Design. 5th printing September 1963 (1st ed.). New York, USA: John Wiley & Sons Inc. pp. 162–169. ISBN 0-47112969-0. LCCN 58-7896. p. 166: [...] It is a pleasure to record that this treatment is based on the work of two students during the period they were studying Switching Circuits at the Massachusetts Institute of Technology. They discussed the method independently and then collaborated in preparing a class memorandum: P. W. Abraham and J. G. Nordahl [...] (xviii+686 pages) (NB. For the first major treatise of the decimal method in this book, it is sometimes misleadingly known as "Caldwell's decimal tabulation".)
15. ^ ^{a b} Mullin, Albert Alkins (1960-03-15) [1959-09-19]. Written at University of Illinois, Urbana, USA. Fisher, Harvey I.; Ekblaw, George E.; Green, F. O.; Jones, Reece; Kruidenier, Francis; McGregor, John; Silva, Paul; Thompson, Milton (eds.). "Two Applications of Elementary Number Theory" (PDF). Transactions of the Illinois State Academy of Science. Springfield, Illinois, USA. 52 (3–4): 102–103. Archived (PDF) from the original on 2020-05-05. Retrieved 2020-05-05. [2][3][4] (2 pages)
16. ^ ^{a b} McCluskey, Jr., Edward Joseph (June 1960). "Albert A. Mullin and Wayne G. Kellner. A residue test for Boolean functions. Transactions of the Illinois State Academy of Science, vol. 51 nos. 3 and 4, (1958), pp. 14–19". The Journal of Symbolic Logic (Review). 25 (2): 185. doi:10.2307/2964263. JSTOR 2964263. p. 185: [...] The results of this paper are presented in the more readily available book by S. H. Caldwell [...]. In this book, the author gives credit to Mullin and Kellner for development of the manipulations with the decimal numbers. (1 page)
17. ^ Abrahams, Paul William; Nordahl, John "Jack" G. (November 1955). The Modified Quine–McCluskey Reduction Procedure (Class memorandum). Electrical Engineering Department, Massachusetts Institute of Technology, Massachusetts, USA. (4 pages) (NB. Some sources list the authors as "P. W. Abraham" and "I. G. Nordahl", the title is also cited as "Modified McCluskey–Quine Reduction Procedure".)
18. ^ Fielder, Daniel C. (December 1966). "Classroom Reduction of Boolean Functions". IEEE Transactions on Education. IEEE. 9 (4): 202–205. Bibcode:1966ITEdu...9..202F. doi:10.1109/TE.1966.4321989. eISSN 1557-9638. ISSN 0018-9359.
19. ^ Kämmerer, Wilhelm (May 1969). "I.12. Theorie: Minimierung Boolescher Funktionen". Written at Jena, Germany. In Frühauf, Hans; Kämmerer, Wilhelm; Schröder, Kurz; Winkler, Helmut (eds.). Digitale Automaten – Theorie, Struktur, Technik, Programmieren. Elektronisches Rechnen und Regeln (in German). 5 (1 ed.). Berlin, Germany: Akademie-Verlag GmbH. pp. 98, 103–104. License no. 202-100/416/69. Order no. 4666 ES 20 K 3. p. 98: [...] 1955 wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt (P. W. Abraham und I. G. Nordahl in [Caldwell]). [...] (NB. A second edition 1973 exists as well.)
20. ^ Holdsworth, Brian; Woods, Clive (2002). "3.17 Decimal approach to Quine–McCluskey simplification of Boolean algebra". Digital Logic Design (4 ed.). Newnes Books / Elsevier Science. pp. 65–67. ISBN 0-7506-4588-2. Retrieved 2020-04-19.CS1 maint: ignored ISBN errors (link) (519 pages) [5]
21. ^ Majumder, Alak; Chowdhury, Barnali; Mondal, Abir J.; Jain, Kunj (2015-01-30) [2015-01-09]. Investigation on Quine McCluskey Method: A Decimal Manipulation Based Novel Approach for the Minimization of Boolean Function. 2015 International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV), Shillong, India (Conference paper). Department of Electronics & Communication, Engineering National Institute of Technology, Arunachal Pradesh Yupia, India. pp. 18–22. doi:10.1109/EDCAV.2015.7060531. Archived from the original on 2020-05-08. Retrieved 2020-05-08. [6] (NB. This work does not cite the prior art on decimal methods.) (5 pages)
22. ^ Masek, William J. (1979). Some NP-complete set covering problems. unpublished.
23. ^ Czort, Sebastian Lukas Arne (1999). The complexity of minimizing disjunctive normal form formulas (Master's thesis). University of Aarhus.
24. ^ Umans, Christopher; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto Luigi (2006-06-05). "Complexity of two-level logic minimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 25 (7): 1230–1246. doi:10.1109/TCAD.2005.855944. S2CID 10187481.
25. ^ Nelson, Victor P.; Nagle, H. Troy; Carroll, Bill D.; Irwin, J. David (1995). Digital Logic Circuit Analysis and Design (2 ed.). Prentice Hall. p. 234. ISBN 978-0-13463894-2. Retrieved 2014-08-26.
26. ^ Feldman, Vitaly (2009). "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries". Journal of Computer and System Sciences. 75: 13–25 [13–14]. doi:10.1016/j.jcss.2008.07.007.
27. ^ Gimpel, James F. (1965). "A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table". IEEE Transactions on Computers. 14: 485–488. doi:10.1109/PGEC.1965.264175.
28. ^ Paul, Wolfgang Jakob (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (in German). 4 (4): 321–336. doi:10.1007/BF00289615. S2CID 35973949.
29. ^ Logic Friday program

Further reading[edit]

• Curtis, Herbert Allen (1962). "Chapter 2.3. McCluskey's Method". A new approach to the design of switching circuits. The Bell Laboratories Series (1 ed.). Princeton, New Jersey, USA: D. van Nostrand Company, Inc. pp. 90–160. ISBN 0-44201794-4. OCLC 1036797958. S2CID 57068910. ISBN 978-0-44201794-1. ark:/13960/t56d6st0q. (viii+635 pages) (NB. This book was reprinted by Chin Jih in 1969.)
• Coudert, Olivier (October 1994). "Two-level logic minimization: an overview" (PDF). Integration, the VLSI Journal. 17–2 (2): 97–140. doi:10.1016/0167-9260(94)00007-7. ISSN 0167-9260. Archived (PDF) from the original on 2020-05-10. Retrieved 2020-05-10. (47 pages)
• Jadhav, Vitthal; Buchade, Amar (2012-03-08). "Modified Quine-McCluskey Method". arXiv:1203.2289 [cs.OH]. (4 pages)
• Crenshaw, Jack (2004-08-19). "All about Quine-McClusky". embedded.com. Archived from the original on 2020-05-10. Retrieved 2020-05-10.
• Tomaszewski, Sebastian P.; Celik, Ilgaz U.; Antoniou, George E. (December 2003) [2003-03-05, 2002-04-09]. "WWW-based Boolean function minimization" (PDF). International Journal of Applied Mathematics and Computer Science. 13 (4): 577–584. Archived (PDF) from the original on 2020-05-10. Retrieved 2020-05-10. [7][8] (7 pages)
• Duşa, Adrian (2008-10-01) [September 2007]. "A mathematical approach to the boolean minimization problem". Quality & Quantity. 44: 99–113. doi:10.1007/s11135-008-9183-x. S2CID 123042755. Article number: 99 (2010). [9] (22 pages)
• Duşa, Adrian (2007). "Enhancing Quine-McCluskey" (PDF). University of Bucharest. Archived (PDF) from the original on 2020-05-12. Retrieved 2020-05-12. (16 pages) (NB. QCA, an open source, R based implementation used in the social sciences.)

External links[edit]

• Quine-McCluskey algorithm implementation with a search of all solutions, by Frédéric Carpon.
• Karċma 3, A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS) - UFRGS, Brazil.
• BFunc, QMC based Boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously), by António Costa
• Python Implementation by Robert Dick, with an optimized version.
• Python Implementation for symbolically reducing Boolean expressions.
• Quinessence, an open source implementation written in Free Pascal by Marco Caminati.
• minBool an implementation by Andrey Popov.
• QMC applet, an applet for a step by step analyze of the QMC- algorithm by Christian Roth
• C++ implementation SourceForge.net C++ program implementing the algorithm.
• Perl Module by Darren M. Kulp.
• Tutorial Tutorial on Quine-McCluskey and Petrick's method.
• Petrick C++ implementation (including Petrick) based on the tutorial above.
• C program Public Domain console based C program on SourceForge.net.
• For a fully worked out example visit: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
• The Boolean Bot: A JavaScript implementation for the web: http://booleanbot.com/
• open source gui QMC minimizer
• Computer Simulation Codes for the Quine-McCluskey Method, by Sourangsu Banerji.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Quine–McCluskey_algorithm&oldid=1032310618"

Categories:

• Boolean algebra
• Willard Van Orman Quine

Hidden categories:

• CS1: Julian–Gregorian uncertainty
• CS1: long volume value
• CS1 location test
• CS1 German-language sources (de)
• CS1 maint: ignored ISBN errors
• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from August 2019
• All articles with unsourced statements
• Articles with unsourced statements from February 2021
• Wikipedia articles in need of updating from May 2017
• All Wikipedia articles in need of updating

Navigation menu

Personal tools

• Not logged in
• Talk
• Contributions
• Create account
• Log in

Namespaces

• Article
• Talk

Variants expanded collapsed

Views

• Read
• Edit
• View history

More expanded collapsed

Search

Navigation

• Main page
• Contents
• Current events
• Random article
• About Wikipedia
• Contact us
• Donate

Contribute

• Help
• Learn to edit
• Community portal
• Recent changes
• Upload file

Tools

• What links here
• Related changes
• Upload file
• Special pages
• Permanent link
• Page information
• Cite this page
• Wikidata item

Print/export

• Download as PDF
• Printable version

Languages

• العربية
• Deutsch
• Español
• فارسی
• Français
• 한국어
• Italiano
• 日本語
• Polski
• Português
• Русский
• Српски / srpski
• ไทย
• Türkçe
• Українська
• 中文

Edit links

• This page was last edited on 6 July 2021, at 17:26 (UTC).
• Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.

• Privacy policy
• About Wikipedia
• Disclaimers
• Contact Wikipedia
• Mobile view
• Developers
• Statistics
• Cookie statement

• 
•