1. Prime Implicants by Quine-McCluskey Tabulational Method

Prime Implicants: product terms that remains after exhaustively applying the theorem, AB + AB' = A.

The Quine-McCluskey Technique is a procedure to reduce the function to a minimum SOP form. This are carried by tabulation. The basic steps are:

Determine all the Prime Implicants.
Keep all the essential prime implicants along with all those implicants to produce a minimum SOP expression.

DEFINITION:

"P is an implicant of an n variables function F if and only if for every combination of values of the n variables for which P = 1, F is also equal to 1."

DEFINITION:

"PI is a prime implicant of function F if PI is P and no longer a P if any literal is deleted from it. Thus, suppose P = A'BCD' of a four variables function F, then PI = P, since A'BC is no longer P and therefore not PI either.

SAMPLE:

Find all the prime implicants of f = SUM(0, 1, 2, 4, 5, 7)

By K-Map
ANSWER:

Clearly, f = B' + A'C' + AC
Implicants: B', A'C' and AC
Observe, P = A'C' is also a PI since f = 1 if P =1. f = 0 if say C' is 'deleted' from A'C'. Notice, the three given PI are all "essential". K-Map is suitable only for small number of variables. For variables greater than say 5, determination of prime implement is better done using the tabulational method given next.

By Tabulational Method

ANSWER:

     DEC ABC      DEC  ABC        DEC      ABC
     -------      --------        ------------
     0   000 /    0,1  00X /      0,1,4,5  X0X PI3
     -------      0,2  0X0 PI1    ------------
     1   001 /    0,4  X00 /
     2   010 /    --------
     4   100 /    1,5  X01 /
     -------      4,5  10X /
     5   101 /    --------
     -------      5,7  1X1 PI2
     7   111 /    --------
     -------

The same three PI as before. PI1 = A'C', PI2 = AC & PI3 = B'

2. Essential Prime Implicants

SAMPLE #1:
Determine the essential prime implicants and final minimum SOP of f.

Selection Chart,

	PI     0   1   2   4   5   7
	----------------------------
	PI1    X       X
	PI2                    X   X
	PI3    X   X       X   X
	----------------------------

HINT: For essential PI selection
A PI is essential if this PI contain a single minterm that can not be cover by any other PI. Clearly, all the PI1, PI2 and PI3 are essential here.

The minimum SOP, f = A'C' + AC + B'

SAMPLE #2:
Repeat question in SAMPLE #1 for g = SUM( 0, 1, 2, 5, 6 )

	DEC  ABC        DEC    ABC       
	--------        ----------
	0    000 /      0,1    00X  PI1
	--------        0,2    0X0  PI2
	1    001 /      ----------
	2    010 /      1,5    X01  PI3
	--------        2,6    X10  PI4
	5    101 /      ----------


	Selection chart,

	PI     0   1   2   5   6
	------------------------
	PI1    X   X
	PI2    X       X
	PI3        X       X
	PI4            X       X
	------------------------

Observe, PI3 and PI4 are essential PI and we must include either the non-essential PI PI1 or PI2, but not both to express g in minimum SOP form.

Thus,
g = B'C + BC' + A'B', or
g = B'C + BC' + A'C'

Incompletely Specified Function

SAMPLE: (Divide 3)
Consider, Y = SUM(0, 3, 6) + d(2, 5)
This was under the K-map.

Find a minimum SOP expression.

	DEC  ABC       DEC   ABC       PI      0   3   6
	--------       ---------       -----------------
	0    000 /     0,2   0X0 PI2   PI1
	--------       ---------       PI2     X
	2    010 /     2,3   01X PI3   PI3         X
	--------       2,6   X10 PI4   PI4             X
	3    011 /     ---------       -----------------
	5    101 PI1   
	6    110 /
	--------

Thus,
Y = A'C' + A'C + BC'

3. Petrick's Method

Petrick's Method can determine all of the minimum SOP solution. This is especially important, because in Quine-McCluskey method, it is often left to the user to determine that. The technique is systematic but rather tedious.

Use the chart of the earlier SAMPLE #2.
PI 0 1 2 5 6 ------------------------ PI1 X X PI2 X X PI3 X X PI4 X X ------------------------

Illustrated Procedure:

Redraw PI chart without the essential PI and without the corresponding minterm columns. Relabel the rows.
PI 0 -------- P1 X P2 X --------
Here essential PI3 and PI4 and their minterms 1, 5 and 2, 6 has been eliminated. PI1 and PI2 is relabeled as P1 and P2 for simplicity.

Form function P = PROD(P_i0 + P_i1 + P_i2 + ... )
where: P_i's = rows which cover column minterm i.

Expand P into SOP form. Apply (X + Y)(X + Z) = X + YZ, and/or, X + XY = X, to produce a minimum SOP expression of P in terms of the P1, P2, P3, ...
In this illustration, the result is P = P1 + P2

Each factor of each product term in this newly developed P function along with the original essential PI is/are Boolean equivalent to the original function. So we take the minimum product term of P(with the smallest number of literals of P1, P2, P3,..)
Thus the solution is either,
g = PI3 + PI4 + P1 = B'C + BC' + A'B' , or
g = PI3 + PI4 + P2 = B'C + BC' + A'C'

The same result as before.

SAMPLE: with Cyclic Selection Chart
h = SUM(1, 2, 3, 4, 5, 6)
DEC ABC DEC ABC PI 1 2 3 4 5 6 --------- --------- ---------------- 1 001 1,3 0X1 a X X 2 010 1,5 X01 b X X 4 100 2,3 01X c X X --------- 2,6 X10 d X X 3 011 4,5 10X e X X 5 101 4,6 1X0 f X X 6 110 --------- ---------------- ---------

Apply The Petrick's Method:

Redraw PI Chart without the essential PI & their minterms
(N/A) does not apply, no change to PI chart

Form P = (a + b)(c + d)(a + c)(e + f)(b + e)(d + f)

Find min SOP. Use, (X + Y)(X + Z) = X + YZ, and/or, X + XY = X, to simplify function
P = (a + bc)(e + bf)(d + cf)
. = (ae + abf + bce + bcf)(d + cf)
. = ade + acef + abdf + abcf + bcde + bcef + bcdf + bcf
. = ade + acef + abdf + abcf + bcde + bcf

We take those with the minimum number of literals:
therefore: ade & bcf

In summary:
a = A'C
d = BC'
e = AB'
b = B'C
c = A'B
f = AC'

ANSWER:
h = A'C + BC' + AB'
or,
h = B'C + A'B + AC'

Use K-map to check:

Return to:
Digital syllabus