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 CheckDashesAlign and CheckMintermDifference functions perform the necessary checks for determining whether two minterms can be merged. The function MergeMinterms 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 corresponding 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 \d 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 "1" to the corresponding string in the dictionary. Otherwise append a "0". • 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, ConvertToRegularExpression, 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, CreatePrimeImplicantChart, 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 "1" 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. -100 -> BC'D' and separating the implicants by
logical OR. The pseudocode assumes that the essential prime implicants will cover the entire Boolean expression. ==See also==