Quine-McCluskey
Notes
- This is Carpanelli, chapter 2
- 3 input Quine-McCluskey
- Truth table
-
a b c f 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 - f = Σ(0,2,4,5,6)
-
- Build the list of implicants
-
000 ---- 010 100 ---- 101 110
- Generate combination terms.
-
000 ✓ ---- 000 - 010 => 0x0 010 ✓ 000 - 100 => x00 100 ✓ ---- 010 - 110 => x10 101 ✓ 100 - 101 => 10x 110 ✓ 100 - 110 => 1x0
- Note, in this step we could have ended up with duplicated implicants.
- In that case, just delete any duplicates.
-
- We have a new list (0x0, x00, x10, and 10x, 1x0) and nothing is circled, so we need to perform another round
-
0x0 ✓ 0x0 - x10 -> nothing x00 ✓ 0x0 - 10x -> nothing
After we finish, 10x is not checked so circle it.Circle 0x00x0 - 1x0 -> xx0 (I had missed this case) ---- x00 - x10 -> xx0 x10 ✓ x00 - 10x -> nothing 10x 1x0 ✓ - We have a new list (xx0 twice), but as the list has only one entry, circle it.
- Everything is circled, so we have the "prime" implicants.
-
Prime Implicant\Minterm 000 010 100 101 110 0X0✓ ✓ 10x ✓ ✓ xx0 ✓ ✓ ✓ ✓ - Note in this case 0x0 and xx0 both cover the same values, so we don't need 0x0.
- There
might bewas an error in the above computations. - In any case, this illustrates why the last step in necessary.
- There
- So we only need xx0 and 10x
- f = ab + c
-
-
- Truth table