Quine-McCluskey Method orTabulation Method

In my last blog I have given you some examples, solving Sum of Product (SOP) and Product of Sum (POS) using Karnaugh Map. Today we will solving the same using Quine-McCluskey Method (Tabulation Method) Example 1: Simplify the following using Quine-McCluskey Method (Tabulation Method) f(A,B,C) = Σm(0,1,4,5,6) + Σd(6) Example 1: f(A,B,C) = Σm(0,1,4,5,6) + Σd(6) Terms given that includes the don't care option
0	000
1	001
4	100
5	101
6	110
7	111
Repetition of 1's is the basis of grouping.

Group 1
	0	000	Weight = 0 [Group with zero : 1's]
Group2
	1	001	Weight = 1[Group with one : 1's]
	4	100
Group 3
	5	101	Weight = 2 [Group with two : 1's]
	6	110
Group 4
	7	111	Weight = 3 [Group with three  : 1's]
Combine a suitable pair to form Column 2, pair can be formed between adjacent group basis of difference. Put a hyphen(-) to indicate difference between the terms. Forming column three will be on the basis of   adjacent pairs that having a hyphen (-) in the identical place. Those terms is used should be marked, here to mark, I used √.

Column I (Number of 1' Implicants)

Column II (Size 2)

Column III (Size 4)

Group1
	0	000 √	(0,1) √	00-	(0,1,4,5)	-0-
			(0,4) √	-00	(0,4,1,5)	-0-
Group 2
	1	001 √	(1,5)  √	-01
	4	100 √	(4,5) √	10-	(4,5,6,7)	1--
			(4,6) (not used)	1-0
Group 3
	5 6	101√ 110 √	(5,7) (6,7)	1-1 11-
Group 4
	7	111 √

Rows = prime implicants and columns = ON-set elements place an "X",  if  ON-set element is covered by the prime implicant.Make the following chart using the given terms but do not use the don't care options (cell 7). Also omit the if any duplicate entries like  (0,1,4,5) (0,4,1,5).
			0	1	4	5	6
-0-	B'	(0,1,4,5)	X	X	X	X
-0-	B'	(0,4,1,5)	X	X	X	X
1--	A	(4,5,6,7)			X	X	X
1- 0	AC'	(4,6)			X		X

After removing duplicate entries we get the following. Now columns 0 and 1  also to be removed as these column has a single X, it has the implicant associated with the row (+) is essential. It must appear in minimum cover. (**) columns has only one X and row  to be covered is (0,1,4,5) = B' (*) omit 0,1,4,5 as it is already covered.
			0 (**)	1 (**)	4	5	6
-0-	B'	(0,1,4,5) +	X (*)	X (*)	X (*)	X (*)
1--	A	(4,5,6,7)			X	X	X
1- 0	AC'	(4,6)			X		X

Eliminate all columns covered by essential primes  (4,5). Find minimum set of rows that cover the remaining columns (4,5,6,7) = A. f(A,B,C) = Σm(0,1,4,5,6) + Σd(6) = A + B'.

Example 2:   Simplify the following using Quine-McCluskey Method (Tabulation Method)

f(A,B,C,D) = Σm(0,2,8,10,12,13,14,15) + Σd(5,7)

Terms given :
0	0000
2	0010
5	0101
7	0111
8	1000
10	1010
12	1100
13	1101
14	1110

Rewriting in the List basis of weight of 1's
0	0000
2	0010
8	1000
5	0101
10	1010
12	1100
7	0111
13	1101
14	1110
15	1111

Group it basis of repetition of 1's
Group 1
	0	0000	Weight = 0[Group with zero : 1's]
Group2
	2	0010	Weight = 1[Group with one : 1's]
	8	1000
Group 3
	5	0101	Weight = 2 [Group with two : 1's]
	10	1010
	12	1100
Group 4
	7	0111	Weight = 3[Group with three : 1's]
	13	1101
	14	1110
Group 5
	15	1111	Weight = 4[Group with three : 1's]
Combine a suitable pair to form Column 2, pair can be formed between adjacent group basis of difference. Put a hyphen(-) that indicate difference between the terms. Column three only can be formed on the basis of  the pairs having a hyphen (-) in the identical place. Those terms already combined should be marked, here to mark, I used √.

Column I (Number of 1' Implicants)

Column II (Size 2)

Column III (Size 4)

Group1
	0	0000 √	(0,2) √	00-0	(0,2,8,10)	-0-0
			(0,8) √	-000	(0,8,2,10)	-0-0
Group 2
	2	0010	(2,10) √	-010	(8,10,12,14)	1--0
	8	1000 √	(8,10) √	10-0	(8,12,10,14)	1--0
			(8,12) √	1-00
Group 3
	5	0101 √	(5,7) √	01-1	(5,7,13,15)	-1-1
	0	1010 √	(5,13) √	-101	(5,13,7,15)	-1-1
	12	1100 √	(10,14) √	1-10	(12,13,14,15)	11--
			(12,13) √	110-	(12,14,13,15)	11--
			(12,14) √	11-0
Group 4
	7	0111 √	(7,15) √	-111
	13	1101 √	(13,15) √	11-1
	14	1110 √	(14,15) √	111-
Group 5
	15	1111 √

Rows = prime implicants and columns = ON-set elements, place an "X", if  ON-set element is covered by the prime implicant. Make the following chart using the given terms but do not use the don't care options. Also omit the duplicate entries such like (0,2,8,10) and (0,8,2,10), (8,10,12,14) and .(8,12,10,14), (5,7,13,15) and  (5,13,7,15), (12,13,14,15) and (12,14,13,15).
			0	2	8	10	12	13	14	15
B'D'	-0-0	(0,2,8,10)	X	X	X	X
B'D'	-0-0	(0,8,2,10)	X	X	X	X
AD'	1--0	(8,10,12,14)			X	X	X		X
AD'	1--0	(8,12,10,14)			X	X	X		X
BD	-1-1	(5,7,13,15)						X		X
BD	-1-1	(5,13,7,15)						X		X
A	11--	(12,13,14,15)					X	X	X	X
AB	11--	(12,14,13,15)					X	X	X	X
After removing duplicate entries we get the following. Now columns 0 and 2 column has a single X, the implicant associated with the row (+) is essential. It must appear in minimum cover. (**) columns has only one X and row to be covered is (0,2,8,10) = B'.D'. * omit 0,2,8,10 as it has already covered.

			0 **	2 **	8	10	12	13	14	15
B'D'	-0-0	(0,2,8,10) +	X *	X *	X *	X *
AD'	1--0	(8,10,12,14)			X	X	X		X
BD	-1-1	(5,7,13,15)						X		X
AB	11--	(12,13,14,15)					X	X	X	X
Eliminate all columns covered by essential primes  (8,10). Find minimum set of rows that cover the remaining columns (5,7,13,15) and (12,13,14,15) =BD and AB. Therefore, from given minterms f(A,B,C,D) = Σm(0,2,8,10,12,13,14,15) + Σd(5,7) = AB + B'D' + BD To give you these two examples I have to spent a couple of hours when easily could have solve it within couple of minutes using Karnaugh Map. Often students ask me why to learn this when it is taken more time than the other easier process, frankly I have no idea. My next target will be booth algorithm and hope will post in time. !!!For those students who are going to  appear in I.C.S.E. and I.Sc., best wishes for your exam.!!!

Boolean algebra Canonical Forms and Solution, Karnaugh Map

Hi, this is the first one in this year and once again failed to post on time but not going to tender apology for it, among you, who knows me will understand that it is examination time and I am little more pre-occupied. Today we will solve a few minterm and maxterm using Karnaugh map as well as other aspect of Canonical form Solution for Sum of Product (SOP) Examples 1:  Using three literals. Reduce this term using K-Map : f(x,y,z) = Σm(0,2,3,4,6,7) The sigma sign and as well as 'm' written in lowercase indicate that it is SOP (sum of Product), so we have to find the minterm.

First mark the given cell with 1's and rest with 0's. We have two Quad here, first one using 0,2,4,6 (Map rolling) and second 2,3,6,7. Quad(0,2,4,6) having m0+m2+m4+m6, we get :  x'y'z' +x'y'z+xy'z'+xyz', common factor is : z'. Quad(2,3,6,7) having m2+m3+m6+m7, we get : x'yz' + x'yz+xyz'+xyz, common factor is : y Quad(0,2,4,6) = z' Quad(2,3,6,7) = y f(x,y,z)=Σm(0,2,3,4,6,7) = y + z'

Examples 2: Using four literals. Reduce this term using K-Map : f(a,b,c,d)=Σm(0,1,3,5,7,10,11,12,13,14,15)

Pair(0,1) = m0+m1 = a'b'c'd' + a'b'c'd = a'b'c' Quad(1,3,5,7)=m1+m3+m5+m7 = a'b'c'd + a'b'cd + a'bc'd + a'bcd = a'd Quad(12,13,14,15) = m12+m13+m14+m15 =abc'd' + abc'd + abcd' + abcd = ab Quad(10,11,14,15) = m10+m11+m14+m15 =ab'cd' + ab'cd' + abcd' + abcd = ac f(a,b,c,d)=Σm(0,1,3,5,7,10,11,12,13,14,15)  = a'b'c' + a'd + ab  + ac

Example 3: Using don't care

f(a,b,c,d)=Σm(0,1,3,8,9,12,13) + Σd(2,6)

Quad(0,1,2,3) = m0 + m1 + m2 + m3 = a'b'c'd' + a'b'c'd + a'b'cd' + a'b'cd   = a'b'          Quad(8,9,12,13) = m8 + m9 + m12 + m13 = ab'c'd' + ab'c'd + abc'd' + abc'd =  ac'  [We are using cell 2 to create a quad as it is given as don't care but we cannot use only don't care so left the cell No. 6 as it is failed make any pair or quad with other given cell.]   f(a,b,c,d)=Σm(0,1,3,8,9,12,13)+Σd(2,6)  =a'b' + ac'

Solution for Product of Sum (POS)

Example 1: Using four literals.

f(a,b,c,d) = p(0,1,6,7,8,9,12,13)

Quad(0,1,8,9) = M0 . M1 . M8 . M9 = (a+b+c+d) . (a+b+c+d') . (a'+b+c+d) . (a'+b+c+d') = b+c Pair(6,7) = M6 . M7 = (a+b'+c'+d) . (a+b'+c'+d') = a+b'+c' Quad(8,9,12,13) = M8 . M9 . M12 . M13 = (a'+b+c+d) . (a'+b+c+d') + (a'+b'+c+d) . (a'+b'+c+d') = a' +c f(a,b,c,d) = ΠM(0,1,6,7,8,9,12,13) =Π(b+c)+(a+b'+c')+(a'+c)

Convert Boolean expression to Canonical form using Boolean Laws Sum of Products

F(A,B,C) = A + B'C = A.1 + B'C.1 = A(B+B') + B'C(A+A') =AB + AB' + AB'C + A'B'C =AB.1 + AB'.1+AB'C + A'B'C =AB(C+C')+AB'(C+C')+AB'C+A'B'C =ABC + ABC' + AB'C + AB'C' + AB'C +A'B'C =A'B'C+ AB'C' +AB'C+ABC' + ABC                (REMOVE THE DUPLICATE ENTRIES) f(A,B,C) = m(1,4,5,6,7)

Using Truth Table

A	B	C	B'	B'C	A+B'C
0	0	0	1	0	0
0	0	1	1	1	0	A'BC'
0	1	0	0	0	1
0	1	1	0	1	1	A'BC
1	0	0	1	0	0
1	0	1	1	0	1	AB'C
1	1	0	0	1	1	ABC'
1	1	1	0	1	1	ABC

Sum of Products F(A,B,C)=(A+ B)( B + C) = (A + B+0).(0+B+C) (X+0 = X) = (A + B + C.C').(AA'+B+C) (0 = XX') =(A + B+ C)( A+B+C')(A+B+C)(A'+B+C)              (REMOVE THE DUPLICATE ENTRIES) = (A + B+ C)( A+B+C')(A'+B+C) F(A,B,C) = m(0,1,4)

Using Truth Table

A	B	C	A+B	B+C	(A+ B)( B + C)
0	0	0	0	0	0	ABC
0	0	1	0	1	0	ABC'
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	1	0	0	A'BC
1	0	1	1	1	1
1	1	0	1	1	1
1	1	1	1	1	1

Definitely coming back within forthright with  using Quine-McCluskey Method (Tabulation Method)

!!!Hope going to have a nice time with Saraswati Puja, till then Bye!!!