Editing Quine–McCluskey algorithm (section)

==Example==
===Input===
In this example, the input is a Boolean function in four variables, <math>f :\{0,1\}^4 \to \{0,1\}</math> which evaluates to <math>1</math> on the values <math>4,8,10,11,12</math> and <math>15</math>, evaluates to an unknown value on <math>9</math> and <math>14</math>, and to <math>0</math> everywhere else (where these integers are interpreted in their binary form for input to <math>f</math> for succinctness of notation). The inputs that evaluate to <math>1</math> are called 'minterms'. We encode all of this information by writing

:<math>f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14). \,</math>
This expression says that the output function f will be 1 for the minterms <math>4,8,10,11,12</math> and <math>15</math> (denoted by the 'm' term) and that we don't care about the output for <math>9</math> and <math>14</math> combinations (denoted by the 'd' term). The summation symbol <math>\sum</math> denotes the logical sum (logical OR, or disjunction) of all the terms being summed over.

===Step 1: Finding the prime implicants===
First, we write the function as a table (where 'x' stands for don't care):
:{| class="wikitable"
|-
!   !! A !! B !! C !! D !! f
|-
| m0 || 0 || 0 || 0 || 0 || 0
|-
| m1 || 0 || 0 || 0 || 1 || 0
|-
| m2 || 0 || 0 || 1 || 0 || 0
|-
| m3 || 0 || 0 || 1 || 1 || 0
|-
| m4 || 0 || 1 || 0 || 0 || 1
|-
| m5 || 0 || 1 || 0 || 1 || 0
|-
| m6 || 0 || 1 || 1 || 0 || 0
|-
| m7 || 0 || 1 || 1 || 1 || 0
|-
| m8 || 1 || 0 || 0 || 0 || 1
|-
| m9 || 1 || 0 || 0 || 1 || x
|-
| m10 || 1 || 0 || 1 || 0 || 1
|-
| m11 || 1 || 0 || 1 || 1 || 1
|-
| m12 || 1 || 1 || 0 || 0 || 1
|-
| m13 || 1 || 1 || 0 || 1 || 0
|-
| m14 || 1 || 1 || 1 || 0 || x
|-
| m15 || 1 || 1 || 1 || 1 || 1
|}

One can easily form the canonical [[sum of products]] expression from this table, simply by summing the [[minterm]]s (leaving out [[Don't-care (logic)|don't-care terms]]) where the function evaluates to one:

:''f''{{sub|A,B,C,D}} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

which is not minimal. So to optimize, all minterms that evaluate to one are first placed in a minterm table. Don't-care terms are also added into this table (names in parentheses), so they can be combined with minterms:

:{| class="wikitable"
|-
! Number<br/>of 1s !! Minterm !! Binary<br/>Representation
|-
| rowspan="2" | 1
| m4 || {{mono|0100}}
|-
| m8 || {{mono|1000}}
|-
| rowspan="3" | 2
| (m9) || {{mono|1001}}
|-
| m10 || {{mono|1010}}
|-
| m12 || {{mono|1100}}
|-
| rowspan="2" | 3
| m11 || {{mono|1011}}
|-
| (m14) || {{mono|1110}}
|-
|| 4
| m15 || {{mono|1111}}
|}

At this point, one can start combining minterms with other minterms in adjacent groups; as in, we compare minterms in nth group with (n+1)th group. So for the m4 minterm in with only one Number of 1s, we compare it to m9, m10, and m12 which have two Number of 1s.

If two terms differ by only a single digit, that digit is replaced with a dash indicating that the digit doesn't matter. For instance <code>1000</code> and <code>1001</code> can be combined to give <code>100-</code>, indicating that both minterms imply the first digit is <code>1</code> and the next two are <code>0</code>. Terms that can't be combined any more are marked with an asterisk ({{color|red|*}}).

:{| class="wikitable"
|-
! Number<br/>of 1s !! Minterm !! 0-Cube !! colspan="2" | Size 2 Implicants 
|-
| rowspan="4" | 1
| m4 || {{mono|0100}} || m(4,12) || {{mono|-100 {{color|red|*}}}}
|-
| m8 || {{mono|1000}} || m(8,9) || {{mono|100-}}
|-
| colspan="2" {{sdash}} || m(8,10) || {{mono|10-0}}
|-
| colspan="2" {{sdash}} || m(8,12) || {{mono|1-00}}
|-
| rowspan="4" | 2
| m9 || {{mono|1001}} || m(9,11) || {{mono|10-1}}
|-
| m10 || {{mono|1010}} || m(10,11) || {{mono|101-}}
|-
| colspan="2" {{sdash}} || m(10,14) || {{mono|1-10}}
|-
| m12 || {{mono|1100}} || m(12,14) || {{mono|11-0}}
|-
| rowspan="2" | 3
| m11 || {{mono|1011}} || m(11,15) || {{mono|1-11}}
|-
| m14 || {{mono|1110}} || m(14,15) || {{mono|111-}}
|-
| rowspan="1" | 4
| m15 || {{mono|1111}} || colspan="2" {{sdash}}
|}

When going from Size 2 to Size 4, treat <code>-</code> as a third bit value. Match up the <code>-</code>'s first.  The terms represent products and to combine two product terms they must have the same variables. One of the variables should be complemented in one term and uncomplemented in the other. The remaining variables present should agree. So to match two terms the <code>-</code>'s must align and all but one of the other digits must be the same. For instance, <code>-110</code> and <code>-100</code> can be combined to give <code>-1-0</code>, as can <code>-110</code> and <code>-010</code> to give <code>--10</code>, but <code>-110</code> and <code>011-</code> cannot since the <code>-</code>'s do not align. <code>-110</code> corresponds to BCD' while 
<code>011-</code> corresponds to A'BC, and BCD' + A'BC is not equivalent to a product term.
:{| class="wikitable"
|-
! Number<br/>of 1s !! Minterm !! 0-Cube !! colspan="2" | Size 2 Implicants !! colspan="2" | Size 4 Implicants
|-
| rowspan="4" | 1
| m4 || {{mono|0100}} || m(4,12) || {{mono|-100 {{color|red|*}}}} ||colspan="2" {{sdash}}
|-
| m8 || {{mono|1000}} || m(8,9) || {{mono|100-}} || m(8,9,10,11) || {{mono|10-- {{color|red|*}}}}
|-
| colspan="2" {{sdash}} || m(8,10) || {{mono|10-0}} || m(8,10,12,14)  || {{mono|1--0 {{color|red|*}}}}
|-
| colspan="2" {{sdash}} || m(8,12) || {{mono|1-00}} ||colspan="2" {{sdash}}
|-
| rowspan="4" | 2
| m9 || {{mono|1001}} || m(9,11) || {{mono|10-1}} ||colspan="2" {{sdash}}
|-
| m10 || {{mono|1010}} || m(10,11) || {{mono|101-}} || m(10,11,14,15) || {{mono|1-1- {{color|red|*}}}}
|-
| colspan="2" {{sdash}} || m(10,14) || {{mono|1-10}} ||colspan="2" {{sdash}}
|-
| m12 || {{mono|1100}} || m(12,14) || {{mono|11-0}} ||colspan="2" {{sdash}}
|-
| rowspan="2" | 3
| m11 || {{mono|1011}} || m(11,15) || {{mono|1-11}} ||colspan="2" {{sdash}}
|-
| m14 || {{mono|1110}} || m(14,15) || {{mono|111-}} ||colspan="2" {{sdash}}
|-
| rowspan="1" | 4
| m15 || {{mono|1111}} || colspan="2" {{sdash}}
| colspan="2" {{sdash}}
|}

Note: In this example, none of the terms in the size 4 implicants table can be combined any further. In general, this process is continued in sizes that are powers of 2 (sizes 8, 16 etc.) until no more terms can be combined.

===Step 2: Prime implicant chart===
None of the terms can be combined any further than this, so at this point we construct an essential prime implicant table. Along the side goes the prime implicants that have just been generated (these are the ones that have been marked with a "{{color|red|*}}" in the previous step), and along the top go the minterms specified earlier. The don't care terms are not placed on top—they are omitted from this section because they are not necessary inputs.

:{| class="wikitable" style="text-align:center;"
|-
!                             || 4 || 8 || 10 || 11 || 12 || 15 || ⇒ || A || B || C || D
|-
| style="text-align:left;" | m(4,12) {{color|blue|<sup>#</sup>}}        || {{Ya|✓}} || || || || {{Ya|✓}} ||   || ⇒ || {{sdash}} || 1 || 0 || 0
|-
| style="text-align:left;" | m(8,9,10,11)    || || {{Ya|✓}} || {{Ya|✓}} || {{Ya|✓}} || || || ⇒ || 1 || 0 || {{sdash}} || {{sdash}}
|-
| style="text-align:left;" | m(8,10,12,14)   || || {{Ya|✓}} || {{Ya|✓}} || || {{Ya|✓}} || || ⇒ || 1 || {{sdash}} || {{sdash}} || 0
|-
| style="text-align:left;" | m(10,11,14,15) {{color|blue|<sup>#</sup>}} || || || {{Ya|✓}} || {{Ya|✓}} || || {{Ya|✓}} || ⇒ || 1 || {{sdash}} || 1 || {{sdash}}
|}

To find the essential prime implicants, we look for columns with only one "✓". If a column has only one "✓", this means that the minterm can only be covered by one prime implicant. This prime implicant is ''essential''.

For example: in the first column, with minterm 4, there is only one "✓". This means that m(4,12) is essential (hence marked by {{color|blue|<sup>#</sup>}}). Minterm 15 also has only one "✓", so m(10,11,14,15) is also essential. Now all columns with one "✓" are covered. The rows with minterm m(4,12) and m(10,11,14,15) can now be removed, together with all the columns they cover.

The second prime implicant can be 'covered' by the third and fourth, and the third prime implicant can be 'covered' by the second and first, and neither is thus essential. If a prime implicant is essential then, as would be expected, it is necessary to include it in the minimized boolean equation. In some cases, the essential prime implicants do not cover all minterms, in which case additional procedures for chart reduction can be employed. The simplest "additional procedure" is trial and error, but a more systematic way is [[Petrick's method]]. In the current example, the essential prime implicants do not handle all of the minterms, so, in this case, the essential implicants can be combined with one of the two non-essential ones to yield one equation:

:''f''{{sub|A,B,C,D}} = BC'D' + AB' + AC<ref name="Logic_Friday"/>
or
:''f''{{sub|A,B,C,D}} = BC'D' + AD' + AC

Both of those final equations are functionally equivalent to the original, verbose equation:
:''f''{{sub|A,B,C,D}} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.