Location: PHPKode > scripts > Quine-McCluskey Method > quine-mccluskey-method/second_algorithm_doc.txt

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>