Editing Quine–McCluskey algorithm (section)

=== 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