The Q-M algorithms are two algorithms that are used to minimize a cover of a boolean function. The first algorithm
generates a cover of prime implicants (implicants that are fully reduced by adjacency). The second algorithm takes the
prime implicants from the first algorithm and eliminates those that are not needed.
The second algorithm:
The first part of the second algorithm is to make a table whose rows are labeled by the prime implicants and whose
columns are labeled by the minterms of the function.
Example: f(A,B,C,D,E) = m(4,5,6,7,12,22, 28,30)
**************second_algorithm.gif******************
The don't care terms are not placed on top. they are omitted from this section because they are not necessary inputs. To
implement the second algorithm, I made a 2-dimensional array for the table of checks and a 1-dimensional array to store
which minterms are “circled”.
1. Pick the column with the least number of checks in it. If there is a tie, pick the first one.
2. In this column, pick the check whose row will get us the greatest number of uncovered minterms.
***************************
Function QM2( minterms, implicants ) returns essentialPrimes
put a 2-dimensional array into checkTable (a value of false indicates there
is no check. The first dimension is the minterms (columns) and the second
dimension is the implicants (rows))
for every implicant implicant of implicants do
for every minterm minterm of minterms do
if implicant implies (covers) minterm then
put true into checkTable[minterm][implicant]
else
put false into checkTable[minterm][implicant]
end if
end for of minterm
end for of implicant
put { } (empty set) into essentialPrimes
put a 1-dimensional array of all false into mintermsDone (to keep track of circles)
while not every index in mintermsDone contains true do
put the column of checkTable with the least number of checks into minChecksCol
put the row with a check in minChecksCol that contains the greatest number of
checks in columns not in mintermsDone into maxChecksRow
put true into every index of mintermsDone that corresponds to a column with a
check in maxChecksRow
add implicant maxChecksRow to essentialPrimes
end while
return essentialPrimes
**************************
*(Pseudocode: David Eigen Minimizing Boolean Sum of Products Functions Page25)
- Online Web Application: http://www.omnistream.co.uk/qm/
- Armin Randjbar-Daemi <randjbar at gmail dot com>
|
Download
