• 107328  Infos

# Quine–McCluskey algorithm

Quine-McCluskey algorithm is a method used for minimisation of boolean functions. It is functionally identical to Karnaugh mapping, however the tabular form makes it more convenient for computers, and it also gives a deterministic way to check that the minimal form of a boolean function has been reached
The method involves two steps:
1. Finding all prime implicants of the function.
2. Using those prime implicants to find the essential prime implicants of the function, as well as using other prime implicants that are necessary to cover the function.

Here's an example minimizing an arbitrary function:''A'' ''B'' ''C'' ''f''(''A'', ''B'', ''C'') 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
All minterms are first placed in a minterm table:Number of 1s Minterm Binary Representation -------------------------------------------- 1 m1 001 m2 010 m4 100 -------------------------------------------- 2 m3 011 -------------------------------------------- 3 m7 111
At this point, one can start combining minterms with other minterms,Number of 1s Minterm 0-Cube | Size 2 Implicants ------------------------------|----------------------------- 1 m1 001 | m(1,3) 0-1 m2 010 | m(2,3) 01- m4 100 |----------------------------- ------------------------------| m(3,7) -11 2 m3 011 | ------------------------------| 3 m7 111 |
None of the terms can be combined any futher than this, so at this point we constuct an essential prime implicant table.
 1 2 3 4 7 m(4)* X m(1,3)* X X m(2,3)* X X m(3,7)* X X

Because all of the above are essential prime implicants, one can then simply convert it into an equation. Thus, the minimal AND-OR equation of the truth table given earlier is $f_\left\{A,B,C\right\} = A\text{'}C + A\text{'}B + BC + AB\text{'}C\text{'}$.