Algorithm for Two-Level Minimization
Algorithm: minimum sum of products expression from a K-map
- step 1: choose an element of the ON-set
- step 2: find "maximal" groupings of 1s and Xs adjacent to that element
- remember to consider top/bottom row, left/right column, and corner adjacencies, this forms prime implicants (number of elements always a power of 2)
- repeat steps 1 and 2 to find all prime implicants
- step 3: revisit the 1's in the K-map
- if covered by single prime implicant, it is essential, and participates in final cover, the 1s it covers do not need to be revisited
- step 4: if there remain 1s not covered by essential prime implicants, then select the smallest number of prime implicants that cover the remaining 1s