Content deleted Content added
Tags: Mobile edit Mobile web edit |
Started to add the pseudocode for the algorithm, still need to add the essential prime implicant pseudocode. |
||
Line 5:
The '''Quine–McCluskey algorithm''' ('''QMC'''), also known as the '''method of prime implicants''', is a method used for [[Minimization of Boolean functions|minimization]] of [[Boolean function]]s that was developed by [[Willard Van Orman Quine|Willard V. Quine]] in 1952<ref name="Quine_1952"/><ref name="Quine_1955"/> and extended by [[Edward J. McCluskey]] in 1956.<ref name="McCluskey_1956"/> As a general principle this approach had already been demonstrated by the logician [[Hugh McColl (mathematician)|Hugh McColl]] in 1878,<ref name="McColl_1878"/><ref name="Ladd_1883"/><ref name="Brown_2010"/> was proved by [[Archie Blake (mathematician)|Archie Blake]] in 1937,<ref name="Blake_1937"/><ref name="Blake_1932"/><ref name="Blake_1938"/><ref name="Brown_2010"/> and was rediscovered by Edward W. Samson and Burton E. Mills in 1954<ref name="Samson_1954"/><ref name="Brown_2010"/> and by Raymond J. Nelson in 1955.<ref name="Nelson_1955"/><ref name="Brown_2010"/> {{anchor|Decimal tabulation}}Also in 1955, Paul W. Abrahams and John G. Nordahl<ref name="Nordahl_2017"/> as well as [[Albert A. Mullin]] and Wayne G. Kellner<ref name="Mullin_Kellner_1958"/><ref name="Caldwell_1958"/><ref name="Mullin_1959"/><ref name="McCluskey_1960"/> proposed a decimal variant of the method.<ref name="Abrahams_Nordahl_1955"/><ref name="Caldwell_1958"/><ref name="Mullin_1959"/><ref name="McCluskey_1960"/><ref name="Fielder_1966"/><ref name="Kämmerer_1969"/><ref name="Holdsworth_2002"/><ref name="Majumder_2015"/>
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
The Quine-McCluskey algorithm works as follows:
# Finding all [[implicant|prime implicants]] of the function.
# 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.
Line 190:
Both of those final equations are functionally equivalent to the original, verbose equation:
:''f''{{sub|A,B,C,D}} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.
== Algorithm ==
=== Finding the prime implicants ===
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.
// Computes the prime implicants from a list of minterms.
// each minterm is of the form "1001", "1010", etc.
'''function''' getPrimeImplicants(list minterms) '''is'''
primeImplicants ← empty list
merges ← new boolean array of length equal to the number of minterms, each set to false
numberOfmerges ← 0
mergedMinterm, minterm1, minterm2 ← empty strings
'''for''' i = 0 '''to''' length(minterms) '''do'''
'''for''' c = i + 1 '''to''' length(minterms) '''do'''
minterm1 ← minterms[i]
minterm2 ← minterms[c]
// Checking that two minters can be merged
'''if''' CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2) '''then'''
mergedMinterm ← MergeMinterms(minterm1, minterm2)
primeImplicants.Add(mergedMinterm)
numberOfMerges ← numberOfMerges + 1
merges[i] ← true
merges[c] ← true
// 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 Contains minterms[j] '''then'''
add minterms[j] to primeImplicants
// if no merges have taken place then all of the prime implicants have been found so return, otherwise
// keep merging the minterms.
'''if''' numberOfmerges == 0 '''then'''
'''return''' primeImplicants
'''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.
'''function''' MergeMinterms(minterm1, minterm2) '''is'''
mergedMinterm ← empty string
'''for''' i = 0 '''to''' length(minterm1) '''do'''
//If the bits vary then replace it with a dash, otherwise the bit remains in the merged minterm.
'''if''' minterm[i] != minterm2[i] '''then'''
mergedMinterm ← mergedMinterm + '-'
'''else'''
mergedMinterm ← mergedMinter + minterm1[i]
'''return''' mergedMinterm
'''function''' CheckDashesAlign(minterm1, minterm2) '''is'''
'''for''' i = 0 '''to''' length(minterm1) '''do'''
// If one minterm has dashes and the other does not then the minterms cannot be merged.
'''if''' minterm1[i] != '-' && minterm2[i] == '-' '''then'''
'''return''' false
'''return''' true
'''function''' CheckMintermDifference(minterm1, minterm2) '''is'''
// minterm1 and minterm2 are strings representing all of the currently found prime implicants and merged
// minterms. Examples include '01--' and '10-0'
m1, m2 '''←''' integer representation of minterm1 and minterm2 with the dashes removed, these are replaced with 0
res ← m1 '''^''' m2
'''return''' res != 0 && (res & res - 1) == 0
==See also==
| |||