Content deleted Content added
Rescuing 2 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
|||
| (16 intermediate revisions by 11 users not shown) | |||
Line 12:
==Complexity==
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 [[Boolean satisfiability problem|problem]] it solves is [[NP-complete]].<ref name="Masek_1979"/><ref name="Czort_1999"/><ref name="Umans_2006"/> The [[running time]] of the Quine–McCluskey algorithm grows [[exponential growth|exponentially]] with the number of variables. For a function of ''n'' variables the number of prime implicants can be as large as <math>3^n/\sqrt{n}</math> ,<ref name="ChandraMarkowsky_1978"/> e.g. for 32 variables there may be over 534 × 10<sup>12</sup> prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal [[Heuristic algorithm|heuristic]] methods, of which the [[Espresso heuristic logic minimizer]] was the de facto standard in 1995.{{update inline|date=May 2017|reason=The reference correctly describes the situation in 1995. We need to expand this to include the changes of the past twenty years, however.}}<ref name="Nelson_1995"/> For one natural class of functions <math>f</math>, the precise complexity of finding all prime implicants is better-understood: Milan Mossé, Harry Sha, and Li-Yang Tan discovered a near-optimal algorithm for finding all prime implicants of a formula in [[conjunctive normal form]].<ref>{{Cite journal |last1=Mossé |first1=Milan |last2=Sha |first2=Harry |last3=Tan |first3=Li-Yang |date=2022 |title=A Generalization of the Satisfiability Coding Lemma and Its Applications |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9 |series=Leibniz International Proceedings in Informatics (LIPIcs) |volume=236 |pages=9:1–9:18 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.SAT.2022.9|doi-access=free |isbn=978-3-95977-242-6 }}</ref>
Step two of the algorithm amounts to solving the [[set cover problem]];<ref name="Feldman_2009"/> [[NP-hard]] instances of this problem may occur in this algorithm step.<ref name="Gimpel_1965"/><ref name="Paul_1974"/>
Line 23:
This expression says that the output function f will be 1 for the minterms <math>4,8,10,11,12</math> and <math>15</math> (denoted by the 'm' term) and that we don't care about the output for <math>9</math> and <math>14</math> combinations (denoted by the 'd' term). The summation symbol <math>\sum</math> denotes the logical sum (logical OR, or disjunction) of all the terms being summed over.
===Step 1:
First, we write the function as a table (where 'x' stands for don't care):
:{| class="wikitable"
Line 93:
|}
At this point, one can start combining minterms with other minterms in adjacent groups
If two terms differ by only a single digit, that digit is replaced with a dash indicating that the digit doesn't matter. For instance <code>1000</code> and <code>1001</code> can be combined to give <code>100-</code>, indicating that both minterms imply the first digit is <code>1</code> and the next two are <code>0</code>. Terms that can't be combined any more are marked with an asterisk ({{color|red|*}}).
:{| class="wikitable"
Line 160 ⟶ 162:
|}
Note: In this example, none of the terms in the size 4 implicants table can be combined any further. In general, this process
===Step 2:
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 (these are the ones that have been marked with a "{{color|red|*}}" in the previous step), 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.
Line 196 ⟶ 198:
The pseudocode below recursively computes the prime implicants given the list of minterms of a boolean function. It does this by trying to merge all possible minterms and filtering out minterms that have been merged until no more merges of the minterms can be performed and hence, the prime implicants of the function have been found.
// Computes the prime implicants from a list of minterms.
// each minterm is of the form "1001", "1010", etc and can be represented with a string.
'''function''' getPrimeImplicants(list minterms) '''is'''
primeImplicants ← empty list
Line 210 ⟶ 212:
'''if''' CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2) '''then'''
mergedMinterm ← MergeMinterms(minterm1, minterm2)
'''if''' primeImplicants
primeImplicants.Add(mergedMinterm)
numberOfMerges ← numberOfMerges + 1
merges[i] ← true
Line 217 ⟶ 220:
// Filtering all minterms that have not been merged as they are prime implicants. Also removing duplicates
'''for''' j = 0 '''to''' length(minterms) '''do'''
'''if''' merges[j] == false && primeImplicants
// if no merges have taken place then all of the prime implicants have been found so return, otherwise
Line 226 ⟶ 229:
'''else'''
'''return''' getPrimeImplicants(primeImplicants)
In this example the <code>CheckDashesAlign</code> and <code>CheckMintermDifference</code> functions perform the necessary checks for determining whether two minterms can be merged. The function <code>MergeMinterms</code> merges the minterms and adds the dashes where necessary. The utility functions below assume that each minterm will be represented using strings.
'''function''' MergeMinterms(minterm1, minterm2) '''is'''
mergedMinterm ← empty string
Line 234 ⟶ 237:
mergedMinterm ← mergedMinterm + '-'
'''else'''
mergedMinterm ←
'''return''' mergedMinterm
Line 248 ⟶ 251:
// minterms. Examples include '01--' and '10-0'
m1, m2 '''←''' integer representation of minterm1 and minterm2 with the dashes removed, these are replaced with 0
// ^ here is a bitwise XOR
res ← m1 '''^''' m2
'''return''' res != 0 && (res & res - 1) == 0
Line 258 ⟶ 262:
==== Creating the prime implicant chart ====
The prime implicant chart can be represented by a dictionary where each key is a prime implicant and the
# Iterate through each key (prime implicant of the dictionary).
Line 279 ⟶ 283:
'''for''' j = 0 '''to''' length(minterms) '''do'''
// If there is a match between the regular expression and the minterm than append a 1 otherwise 0.
'''if''' regularExpression.matches(
primeImplicantChart[primeImplicant] += "1"
'''else'''
Line 292 ⟶ 296:
'''if''' primeImplicant[i] == "-" '''then'''
// Add the literal character "\d".
regularExpression += @"\d"
'''else'''
regularExpression += primeImplicant[i]
'''return''' regularExpression
==== Finding the essential prime implicants ====
Using the function, <code>CreatePrimeImplicantChart</code>, defined above, we can find the essential prime implicants by simply iterating column by column of the values in the dictionary, and where a single <code>"1"</code> is found then an essential prime implicant has been found. This process is described by the pseudocode below.
'''function''' getEssentialPrimeImplicants(Dictionary primeImplicantChart, list minterms)
essentialPrimeImplicants ← new list
mintermCoverages ← list with all of the values in the dictionary
'''for''' i = 0 '''to''' length(ticks) '''do'''
mintermCoverage ← ticks[i]
'''for''' j = 0 '''to''' length(mintermCoverage) '''do'''
'''if''' mintermCoverage[j] == "1" '''then'''
essentialPrimeImplicants.Add(primeImplicantChart.Keys[i])
'''return''' essentialPrimeImplicants
Using the algorithm above it is now possible to find the minimised boolean expression, by converting the essential prime implicants into the canonical form ie. <code>-100 -> BC'D'</code> and separating the implicants by [[Logical disjunction|logical OR]]. The pseudocode assumes that the essential prime implicants will cover the entire boolean expression.
==See also==
Line 320 ⟶ 337:
<ref name="Nordahl_2017">{{cite web |title=Welcome to the memorial page for John "Jack" G Nordahl June 14, 1933 ~ November 20, 2017 (age 84) |publisher=Jellison Funeral Home and Cremation Services |url=https://www.jellisonfuneralhome.com/obituary/JohnJack-Nordahl |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505151004/https://www.jellisonfuneralhome.com/obituary/JohnJack-Nordahl |archive-date=2020-05-05}}</ref>
<ref name="Caldwell_1958">{{cite book |title=Switching Circuits and Logical Design |chapter=5.8. Operations Using Decimal Symbols |first=Samuel Hawks |last=Caldwell |author-link=Samuel Hawks Caldwell |version=5th printing September 1963 |date=1958-12-01 |orig-date=February 1958 |edition=1st |publisher=[[John Wiley & Sons Inc.]] |publication-place=New York, USA |___location=Watertown, Massachusetts, USA |isbn=0-47112969-0 |lccn=58-7896 |pages=162–169 |quote-page=166 |quote=[...] 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: {{citeref|Abrahams|Nordahl|1955|P. W. Abraham and J. G. Nordahl|style=plain}} [...]}} (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".)</ref>
<ref name="Mullin_Kellner_1958">{{cite journal |title=A Residue Test for Boolean Functions |first1=Albert Alkins |last1=Mullin |author-link1=Albert Alkins Mullin |first2=Wayne G. |last2=Kellner |journal=Transactions of the Illinois State Academy of Science |volume=51 |number=3–4 |date=1958<!-- |orig-date=November 1955 According to Caldwell --> |publication-place=Springfield, Illinois, USA |___location=University of Illinois, Urbana, USA and Electrical Engineering Department, [[Massachusetts Institute of Technology]], Massachusetts, USA |type=Teaching memorandum |s2cid=125171479 |pages=14–19 |url=https://ilacadofsci.com/wp-content/uploads/2016/03/051-16-print.pdf |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505163915/https://ilacadofsci.com/wp-content/uploads/2016/03/051-16-print.pdf |archive-date=2020-05-05 }} [https://ilacadofsci.com/archives/9279] {{Webarchive|url=https://web.archive.org/web/20200817055259/https://ilacadofsci.com/archives/9279 |date=2020-08-17 }} (6 pages) (NB. In {{citeref|Caldwell|1958|his book|style=plain}}, Caldwell dates this to November 1955 as a teaching memorandum. Since Mullin dates their work to 1958 in {{citeref|Mullin|1960|another work|style=plain}} and Abrahams/Nordahl's {{citeref|Abrahams|Nordahl|1955|class memorandum|style=plain}} is also dated November 1955, this could be a copy error.)</ref>
<ref name="Mullin_1959">{{cite journal |title=Two Applications of Elementary Number Theory |first=Albert Alkins |last=Mullin |author-link=Albert Alkins Mullin |journal=Transactions of the Illinois State Academy of Science |volume=52 |number=3–4 |date=1960-03-15 |orig-date=1959-09-19 |___location=University of Illinois, Urbana, USA |publication-place=Springfield, Illinois, USA |editor-first1=Harvey I. |editor-last1=Fisher |editor-first2=George E. |editor-last2=Ekblaw |editor-first3=F. O. |editor-last3=Green |editor-first4=Reece |editor-last4=Jones |editor-first5=Francis |editor-last5=Kruidenier |editor-first6=John |editor-last6=McGregor |editor-first7=Paul |editor-last7=Silva |editor-first8=Milton |editor-last8=Thompson |pages=102–103 |url=https://ilacadofsci.com/wp-content/uploads/2016/03/052-15-print.pdf |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505143916/https://ilacadofsci.com/wp-content/uploads/2016/03/052-15-print.pdf |archive-date=2020-05-05 }} [https://ilacadofsci.com/archives/9203] {{Webarchive|url=https://web.archive.org/web/20200817055316/https://ilacadofsci.com/archives/9203 |date=2020-08-17 }}[https://archive.org/details/transactionsofil5219unse][https://archive.org/stream/transactionsofil5219unse/transactionsofil5219unse_djvu.txt] (2 pages)</ref>
<ref name="McCluskey_1960">{{cite journal |title=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. |type=Review |last=McCluskey |first=Edward Joseph Jr.|author-link=Edward Joseph McCluskey, Jr. |journal=[[The Journal of Symbolic Logic]] |volume=25 |issue=2 |date=June 1960 |doi=10.2307/2964263 |page=185 |jstor=2964263 |s2cid=123530443 |quote-page=185 |quote=[...] The results of this paper are presented in the more readily available {{citeref|Caldwell|1958|book|style=plain}} by S. H. Caldwell [...<!-- XXIII 433 -->]. In this book, the author gives credit to {{citeref|Mullin|Kellner|1958|Mullin and Kellner|style=plain}} for development of the manipulations with the decimal numbers.}} (1 page)</ref>
<ref name="Kämmerer_1969">{{cite book |title=Digitale Automaten – Theorie, Struktur, Technik, Programmieren |language=de |chapter=I.12. Theorie: Minimierung Boolescher Funktionen |first=Wilhelm |last=Kämmerer |author-link=:de:Wilhelm Kämmerer |editor-first1=Hans |editor-last1=Frühauf |editor-link1=:de:Hans Frühauf |editor-first2=Wilhelm |editor-last2=Kämmerer |editor-first3=Kurz |editor-last3=Schröder |editor-first4=Helmut |editor-last4=Winkler |edition=1 |date=May 1969 |publisher=[[Akademie-Verlag GmbH]] |publication-place=Berlin, Germany |___location=Jena, Germany |volume=5 |id=License no. 202-100/416/69. Order no. 4666 ES 20 K 3. |series=Elektronisches Rechnen und Regeln |pages=98, 103–104 |url=https://books.google.com/books?id=jkcgAQAAIAAJ&q=P.+W.+Abraham+I.+G.+Nordahl |quote-page=98 |quote=[...] 1955 wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt ({{citeref|Abrahams|Nordahl|1955|P. W. Abraham und I. G. Nordahl|style=plain}} in [<nowiki/>{{citeref|Caldwell|1958|Caldwell|style=plain}}<nowiki/>]). [...]}} (NB. A second edition 1973 exists as well.<!-- where the relevant quote is located on page 99 rather than 98 -->)</ref>
<ref name="McColl_1878">{{cite journal |first=Hugh |last=McColl |author-link=Hugh McColl (mathematician) |date=1878-11-14 |title=The Calculus of Equivalent Statements (Third Paper) |journal=[[Proceedings of the London Mathematical Society]] |volume=s1-10<!-- or 10? --> |issue=1 |doi=10.1112/plms/s1-10.1.16 |pages=16–28 |url=https://academic.oup.com/plms/article-abstract/s1-10/1/16/1503062|url-access=subscription }}</ref>
<ref name="Blake_1932">{{cite journal |first=Archie |last=Blake |title=Canonical expressions in Boolean algebra |series=Abstracts of Papers |journal=[[Bulletin of the American Mathematical Society]] |date=November 1932 |page=805}}</ref>
<ref name="Blake_1937">{{cite book |last=Blake |first=Archie |date=1938 |orig-date=1937 |title=Canonical Expressions in Boolean Algebra |type=Dissertation |publisher=[[University of Chicago Libraries]] |___location=Chicago, Illinois, USA |edition=Lithographed |page=36 |url=https://books.google.com/books?id=gqRYAAAAMAAJ |quote-page=36 |quote=[...] this method was known to [[Charles Sanders Peirce|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)</ref>
<ref name="Blake_1938">{{cite journal |first=Archie |last=Blake |title=Corrections to ''Canonical Expressions in Boolean Algebra'' |journal=[[The Journal of Symbolic Logic]] |issn=0022-4812 |publisher=[[Association for Symbolic Logic]] |volume=3 |issue=2 |date=June 1938 |doi=10.2307/2267595 |jstor=2267595 |url=https://projecteuclid.org/euclid.jsl/1183385465 |pages=112–113|s2cid=5810863 |url-access=subscription }}</ref>
<ref name="Samson_1954">{{cite book |last1=Samson |first1=Edward Walter |last2=Mills |first2=Burton E. |date=April 1954 |title=Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions |publisher=[[Air Force Cambridge Research Center]] |id=Technical Report AFCRC TR 54-21 |___location=Bedford, Massachusetts, USA}}</ref>
<ref name="Nelson_1955">{{cite journal |last=Nelson |first=Raymond J. |date=June 1955 |title=Simplest Normal Truth Functions |journal=[[The Journal of Symbolic Logic]] |publisher=[[Association for Symbolic Logic]] |volume=20 |issue=2 |doi=10.2307/2266893 |jstor=2266893 |pages=105–108|s2cid=32920372 }} (4 pages)</ref>
| |||