Introduction Determining the Prime Implicants What are these Prime Implicants?

Selecting a Minimum Set Another Example Rules for Table Reduction Incompletely Specified Functions Review

Quine-McCluskey Tabulation Method

Introduction
Quine-McCluskey Method is a step-by-step Advantages:
can be applied to problems of many variables suitable for machine computation

procedure which is guaranteed to produce a simplified standard form for given function.

BUT tedious and prone-to-errors for humans.

Introduction
Relies on repeated applications on terms using Unifying
Theorem: axb + ax'b = ab
where a and b stand for product terms;

Example: wxyz + wx'yz = wyz

Using binary representations (for the product terms), above

theorem correspond to: a1b + a0b = a-b
Examples: 111 + 101 = 1-1 101 + 100 = 1011-10 + 11-00 = 11--0 (abc + ab'c = ac) (ab'c + ab'c' = ab') (abde' + abd'e' = abe')

Introduction
Two steps procedure:
Find all prime implicants

Smallest set of prime implicants to cover

the minterms of function

Determining the Prime Implicants

Consider a 4-variable function.
F(A,B,C,D) = m(0,1,4,5,9,11,14,15)

Procedure:
Arrange the minterms in groups according to the number of

1s (see Column 1)
Combine terms from adjacent groups which differ by only 1

bit. (see Column 2)

Repeat step 2 with a new set of terms (see Column 3); until

no further combinations are possible.

Determining the Prime Implicants

Column 1 0 0000 1 0001 4 0100 5 0101 9 1001 11 1011 14 1110 15 1111
Column 2 P P P PP P P P P P P P P P P P 0, 1 0, 4 000- P 0-00 P Column 3 0,1,4,5 0-0-

1, 5 1, 9 4, 5

0-01 P -001 010- P

9,11 10-1 11,15 1-11 14,15 111-

The prime implicants (PIs) are those without a tick

mark, namely: {-001, 10-1, 1-11, 111-, 0-0-}
or
{B'C'D, AB'D, ACD, ABC, A'C'}

What are these Prime Implicants?

A prime implicant (PI) is a product term

obtained by combining the maximum possible number of minterms from adjacent squares in the map. correspond to prime implicants.

Largest groupings of minterms in K-map

What are these Prime Implicants?

For comparison, the equivalent K-map with the various
groupings of minterms are as follows:
Column 1 P 0 0000 P 1 0001 PP P P 4 0100 P 5 9 11 14 15 0101 1001 1011 1110 1111
P P P P P P P P P

Column 2
0, 1 0, 4 000- P 0-00 P

Column 3 0,1,4,5 0-0-

1, 5 1, 9 4, 5

0-01 P -001 010- P

CD AB

9,11 10-1

C 00 01 11 10

11,15 1-11 14,15 111A

00 01 11 10

1 1

1 1 1 1
D
B

What are these Prime Implicants?

For comparison, the equivalent K-map with the various
groupings of minterms are as follows:
Note that some of these groupings (prime implicants) are redundant.
CD

C 00 01 11 10

So we need to find the minimum set which would cover all minterms step 2 of the tabulation technique.

AB

00 01 11

1 1

1
1 1 1
D
B

A
10

Selecting a Minimum Set

Next step is to select a minimum set of prime implicants to
represent the function the covering problem.

Prepare a table for prime-implicant vs minterms a prime

implicant chart (PI Chart):

0 1,9 9,11 11,15 14,15 0,1,4,5 -001 10-1 1-11 1110-0-

1 X

9 X X

11 X X

14

15

X X X X X

X X

Selecting a Minimum Set

Choose essential prime implicants (EPIs) those with
unique minterm in it (i.e. single minterm in the column).

1,9 9,11 11,15 14,15 0,1,4,5

-001 10-1 1-11 1110-0-

1 X

9 X X

11 X X

14

15
CD AB

C 00 01 11 10

X X X X X

X X

00 01 11

1 1

1 1 1 1
D
B

Unique minterms: 0,4,5,14 Therefore, EPIs are: A'C', ABC.

A
10

Selecting a Minimum Set

P P P P

0 1,9 9,11 11,15 14,15 0,1,4,5 -001 10-1 1-11 1110-0-

1 X

9 X X

11 X X

14

15

X X X X X

X X

Remove rows of essential prime implicant (EPIs) and

1,9 -001 9,11 10-1 11,15 1-11 9 X X 11 X X

columns of minterms covered by these EPIs, to give a reduced PI chart:

Selecting a Minimum Set

Next, select one or more prime implicants which would
cover all the remaining minterms. (namely, AB'D)

1,9 -001 9,11 10-1 11,15 1-11

9 X X

11 X X
CD AB

C 00 01 11 10

Hence, minimum set of prime implicants to cover all the minterms is { A'C', ABC, AB'D } F = A'C' + ABC + AB'D

00 01

1 1

1 1 1 1
D B

11
A 10

Another Example
Try tabulation technique with function:
F(A,B,C,D) = S m(2,4,6,8,9,10,12,13,15)
Column 1 2 0010 4 0100 8 1000 6 0110 9 1001 10 1010 12 1100 13 1101 15 1111 Column 2 2,6 0-10 2,10 -010 4,6 01-0 4,12 -100 8,9 1008,10 10-0 8,12 1-00 9,13 1-01 12,13 11013,15 11-1 PI2 PI3 PI4 PI5 PI6 PI7 Column 3 8,9,12,13 1-0- PI1

Another Example
Prime implicants: 1-0-, 0-10, -010, 01-0, -100, 10-0, 11-1
or AC', A'CD', B'CD', A'BD', BC'D', AB'D', ABD
P 9 10 X
X X X X X X X X X

2 8,9,12,13 2,6 2,10 4,6 4,12 8,10 13,15 1-00-10 -010 01-0 -100 10-0 11-1 X X

6 X

8 X

12 X

13 X

P 15

EPIs: 1-0-, 11-1 or AC', ABD

Another Example
2 8,9,12,13 2,6 2,10 4,6 4,12 8,10 13,15 1-00-10 -010 01-0 -100 10-0 11-1 X X X X 4 6 X X X X X X X X 8 X

P 9 10 X

12 X

13 X

P 15

Reduced PI chart
2,6 2,10 4,6 4,12 8,10 0-10 -010 01-0 -100 10-0 2 X X 4 6 X X X 10 X X X

EPIs: AC', ABD

F = AC' + ABD + B'CD' + A'BD'

Another Example

Questions:
How would you obtain simplified product-of-sums

(POS) expressions with the tabulation technique?

How would you handle dont care conditions in

an incompletely specified function?

Rules for Table Reduction

After obtaining the EPIs, the rules for PI chart
reduction are:
Rule 1: A row that is covered by another row may be

eliminated from the chart. When identical rows are present, all but one of the rows may be eliminated.
Rule 2: A column that covers another column may be

eliminated. All but one column from a set of identical columns may be eliminated.

Rules for Table Reduction

Example: Given this reduced PI chart:
1,5,9,13 5,7,13,15 8,9,10,11 9,11,13,15 10,11,14,15 --01 -1-1 10-1--1 1-15 10 11 13 X X X X X X X X X X
5 10 X X

1,5,9,13 --01 8,9,10,11 10--

Apply rule 1: 2nd and 5th rows can be eliminated.

Apply rule 2: 3rd and 4th columns can be eliminated.

Incompletely Specified Functions

Functions with dont-cares.
Step 1: Finding prime implicants (no change).
Step 2: PI chart omit the dont-cares.

Example:
F(A,B,C,D,E) = S m(2,3,7,10,12,15,27) + S d(5,18,19,21,23)

Incompletely Specified Functions

F(A,B,C,D,E) = S m(2,3,7,10,12,15,27) + S d(5,18,19,21,23)
Column 1 2 3 5 10 12 18 7 19 21 15 23 27 00010 00011 00101 01010 01100 10010 00111 10011 10101 01111 10111 11011
PI7

Column 2 2,3 2,10 2,18 3,7 3,19 5,7 5,21 18,19 7,15 7,23 19,23 19,27 21,23 00010-010 -0010 00-11 -0011 001-1 -0101 10010-111 -0111 10-11 1-011 101-1
PI4

Column 3 2,3,18,19 3,7,19,23 5,7,21,23 -001-0-11 -01-1

PI1 PI2 PI3

PI5

PI chart
PI1 PI2 PI3 PI4 PI5 PI6 PI7 2 X 3 X X 7 X X

15

27

10 12

PI6

X X

X X X X

EPIs: PI4, PI5, PI6 and PI7. or PI2 + PI4 + PI5 + PI6 + PI7 F = PI1 + PI4 + PI5 + PI6 + PI7
Reduced PI chart:
PI1 PI2

3 X X

Review Quine-McCluskey Technique

Relies on unifying theorem:
axb + axb = ab

Procedure: (i) Find all prime implicants

arrange minterms according to the number of 1s. exhaustively combine pairs of terms from adjacent groups

which differ by 1 bit, to produce new terms.

tick those terms which have been selected. repeat with new set of terms until none possible. terms which are unticked are the prime implicants.

Review Quine-McCluskey Technique

(ii) select smallest set to cover function
prepare prime-implicants chart.

select essential prime implicants for which one or more of its

minterms are unique (only once in the column). obtain a new reduced PI chart for remaining prime-implicants and the remaining minterms. select one or more of remaining prime implicants which will cover all the remaining minterms.

Review Quine-McCluskey Technique

Example:
F(A,B,C,D) = S m(0,1,4,5,9,11,14,15)
Column 1 P 0 0000 P 1 0001 PP P P 4 0100 P 5 9 11 14 15 0101 1001 1011 1110 1111
P P P P P P P P P Column 2 Column 3 0,1,4,5 0-0-

0, 1 0, 4
1, 5 1, 9 4, 5

000- P 0-00 P
0-01 P -001 010- P

9,11 10-1 11,15 1-11 14,15 111-

Review Quine-McCluskey Technique

The prime implicants (those without a tick mark) are:
{ B'C'D, AB'D, ACD, ABC, A'C' }

0 1,9 9,11 11,15 14,15 0,1,4,5 -001 10-1 1-11 1110-0-

1 X

9 X X

11 X X

14

15

X X X X X

X X

Essential prime implicants : ABC, A'C' F = ABC + A'C' + AB'D

1,9 9,11 11,15 -001 10-1 1-11 9 X X 11 X X

Petricks method
Consider the PI table of f(ABCD) = Sm(4,5,7,12,14,15)
PI terms 4 ABC BCD ABD ABD BCD ABC a d c d e f X X X X X X X X X X 5 X X minterms 7 12 14 15

Petricks method
There are no essential prime implicants in this PI table. Also it is not possible to apply column and row reduction. Now we apply Petricks method. We formulate a p-expression for the PI table. The first column of the table indicates that either prime implicant a or b must be selected to cover minterm 4 .Corresponding to this we construct a term (a+b).Similarly, prime implicant a or c must be selected to cover minterm 5. Accordingly a term (a+c) is constructed. In the same way the other similar terms are constructed, which are as follows Prime implicants p = (a+b)(a+c)(c+e)(b+d)(d+f)(e+f)

Petricks method
p = (a+b)(a+c)(c+e)(b+d)(d+f)(e+f)---- (1) This expression can be manipulated using Boolean algebraic methods. It is to be expressed in SOP form p=(a+bc)(d+bf)(e+cf) ------------- (2) since (x+y)(x+z)= x.x+y.x+x.z+y.z = {x+x(y+z)} + yz = x+yz Simplify equn 2 we have P= ade+adcf+bcde+bcdf+abcf+bcfe+bcf+ abfe = ade+adcf+bcde+bcf(1+d+a+e)+abfe = ade+adcf+bcde+bcf+ abfe ----------------- (3) From equn 3, we obtain the condition that p must be equal to 1 only when a sufficient subset of the prime implicants is selected to cover the PI table.

Petricks method
From equn (3), we can write five possible minimal expressions corresponding to each term as follows
f1(ABCD)= a f2(ABCD)= a f3(ABCD)= b f4(ABCD)= b f5(ABCD)= a + + + + + d d c c b + + + + + e = ABC +ABD + BCD ------ (4) c + f = ABC+ABD +ABD + ABC ------ (5) d + e =BCD+ABD+ABD+BCD ------ (6) f = BCD+ABD+ABC ------ (7) f + e =ABC+BCD+BCD+ABC ------ (8)

Thus we see that the Petricks method not only provides minimal expression, it also gives all the possible minimal expressions. Now, we can select one of these expression, Logically all are equivalent, but may need different number of components for realization resulting in different costs.

Petricks method
From equn (4) 3+3+3+3 =12 From equn (5) 3+3+3+3+4 =16 From equn (6) 3+3+3+3+4 =16 From equn (7) 3+3+3+3 =12 From equn (8) 3+3+3+3+4 =16 So equn 4 and equn 7 gives the optimal solution.

Example 2
PI terms 0 ABDE ACD ABC ABD a b c d X X 4 X X X X X X 10 13 MINTERMS 15 16 22 23 26

BCDE
ACE BCDE ABDE

e
f g h X

X
X X X

X
X

ABCD
ABCE

i
j

X
X

Example 2
In the PI table, the row i dominates over rows h and j, therefore, h & j rows are eliminated. Now, columns 22 and 23 have single X, therefore, row is secondary EPI, i.e. ABCD term will be a part of minimal expression. Now we use Petricks method. Then expression for p is given by p = (a+g)(a+b)(d+e)(b+c)(c+d)(f+g)(e+f)

Example 2
p = (a+g)(a+b)(d+e)(b+c)(c+d)(f+g)(e+f) =(a+bg)(d+ce)(b+c)(f+ge)

=(ad+bdg+ace+bceg)(bf+cf+beg+ceg)
=(abdf+acdf+abdeg+acdeg+bdfg+bcdfg+bdeg+bcdeg+abcef+acef+abceg+a ceg+bcefg+bcefg+bceg+bceg =abdf+acdf+(abdeg+bdeg+bcdeg)+(acdeg+aceg)+ (bdfg+bcdfg)+(abcef+acef))+abceg+(bcefg+bceg) =abdf+acdf+bdeg+aceg+bdfg+acef+(abceg+bceg) =abdf+acdf+bdeg+aceg+bdfg+acef+bceg There are seven minimal functions corresponding to the above p expression

f1(ABCDE) =a+b+d+f =ABDE+ACD+ABD+ACE COMPONENT = 4+3+3+3+4 =17 f2(ABCDE)=a+c+d+f = ABDE+ABC+ABD+ACE COMPONENT = 4+3+3+3+4 =17 f3(ABCDE)=b+d+e+g = ACD+ABD+BCDE+BCDE COMPONENT = 3+3+4+4+4 =18 f4(ABCDE)=a+c+e+g = ABDE+ABC+BCDE+BCDE COMPONENT = 4+3+4+4+4 =19 f5(ABCDE)=b+d+f+g = ACD+ABD+ACE+BCDE COMPONENT = 3+3+3+4+4 =17 f6(ABCDE)= a+c+e+f = ABDE+ABC+BCDE+ ACE COMPONENT = 3+3+4+4+4 =18 f6(ABCDE)= b+ c+e+g = ACD+ ABC+BCDE+BCDE COMPONENT = 3+3+4+4+4 =18 The term ABCD corresponding to i in table will be included in each of the above functions. This will add 5 to the component cost of each function. The cost is minimum for the functions f1,f2, and f5. Any one of these can be selected.