Editing Quine–McCluskey algorithm (section)

== Algorithm ==

=== Step 1: 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 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
     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 minterms can be merged
             '''if''' CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2) '''then'''
                 mergedMinterm ← MergeMinterms(minterm1, minterm2) 
                 '''if''' primeImplicants Does Not Contain mergedMinterm then
                     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 Does Not Contain minterms[j] '''then'''
             primeImplicants.Add(minterms[j]) 
 
     // 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. The utility functions below assume that each minterm will be represented using strings.  
 '''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 ← mergedMinterm + 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
     // ^ here is a bitwise XOR
     res ← m1 '''^''' m2
     '''return''' res != 0 && (res & res - 1) == 0

=== Step 2: Prime implicant chart ===
The pseudocode below can be split into two sections: 

# Creating the prime implicant chart using the prime implicants 
# Reading the prime implicant chart to find the essential prime implicants. 

==== Creating the prime implicant chart ====
The prime implicant chart can be represented by a dictionary where each key is a prime implicant and the corrresponding value is an empty string that will store a binary string once this step is complete. Each bit in the binary string is used to represent the ticks within the prime implicant chart. The prime implicant chart can be created using the following steps: 

# Iterate through each key (prime implicant of the dictionary). 
# Replace each dash in the prime implicant with the <code>\d</code> character code. This creates a regular expression that can be checked against each of the minterms, looking for matches. 
# Iterate through each minterm, comparing the regular expression with the binary representation of the minterm, if there is a match append a <code>"1"</code> to the corresponding string in the dictionary. Otherwise append a <code>"0"</code>.
# Repeat for all prime implicants to create the completed prime implicant chart. 

When written in pseudocode, the algorithm described above is: 
 '''function''' CreatePrimeImplicantChart(list primeImplicants, list minterms) 
     primeImplicantChart ← new dictionary with key of type string and value of type string
     // Creating the empty chart with the prime implicants as the key and empty strings as the value. 
     '''for''' i = 0 '''to''' length(primeImplicants) '''do'''
         // Adding a new prime implicant to the chart. 
         primeImplicantChart.Add(primeImplicants[i], "")
     
     '''for''' i = 0 '''to''' length(primeImplicantChart.Keys) '''do'''
         primeImplicant ← primeImplicantChart.Keys[i]
         // Convert the "-" to "\d" which can be used to find the row of ticks above.
         regularExpression ← ConvertToRegularExpression(primeImplicant)
         '''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(minterms[j]) '''then'''
                 primeImplicantChart[primeImplicant] += "1"
             '''else''' 
                 primeImplicantChart[primeImplicant] += "0"
 
     // The prime implicant chart is complete so return the completed chart. 
     '''return''' primeImplicantChart
The utility function, <code>ConvertToRegularExpression</code>, is used to convert the prime implicant into the regular expression to check for matches between the implicant and the minterms. 
 '''function''' ConvertToRegularExpression(string primeImplicant)
     regularExpression ← new string 
     '''for''' i = 0 '''to''' length(primeImplicant) '''do'''
         '''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.