Content deleted Content added
Corrected typo in algorithm pseudocode |
Extended the pseudocode of the algorithm. It can now be used to create a complete implementation of the algorithm. The final processing of producing the minimised expression needs to be added as well though. |
||
Line 250:
res ← m1 '''^''' m2
'''return''' res != 0 && (res & res - 1) == 0
=== 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(primeImplicant) '''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";
'''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.
==See also==
| |||