Minimize the following expression using Quine McClusky Technique F(A, B, C, D)= ∑m(1,2,5,7,9,15)+d(0,3,11)

989views

written 3.6 years ago by

teamques10 ★ 69k

Quine-McClusky method:-

Quine-McClusky method is a systematic approach for simplification of boolean functions.It does not have the limitation of number of variables. The tabular form is used during simplification so it is also called as the tabulation method.

Steps of Quine-McClusky method:-

Find all prime implicants of the given Boolean equation.

Count the Number of 1’s in each min term given in the problem.
In stage 1 group the minterms which have the same number of 1’s in their binary equivalents.
In stage 2, we form pairs, i.e. compare minterms of group n and group n + 1 and place a dash ( - ) whoose binary values differ by 1 bit.
In stage 3, we repeat the process in stage 2 on the table obtained in stage 2, This process is repeated until no further pairing is possible
After no further pairing is possible, then the unchecked minterms are the prime implicants.

Use the prime implicants in a prime implicant chart to find the essential prime implicants and other prime implicants that are required to completely cover the given equation.

Put all prime implicants in a cover table (don’t cares excluded).
Identify essential minterms, and hence essential prime implicants.

Simplify the following function: F(A, B, C, D)= ∑m(1,2,5,7,9,15)+d(0,3,11)

Step 1: Find all prime implicants of the given Boolean equation.

Count the Number of 1’s in each min term given in the problem.

Minterms	Binary value	No. of 1’s	Minterms	Binary value	No. of 1’s
0	0000	0	7	0111	3
1	0001	1	9	1001	2
2	0010	1	11	1011	3
3	0011	2	15	1111	4
5	0101	2	---	---	---

* In stage 1 group the minterms which have the same number of 1’s in their binary equivalents.

Stage 1
No. of 1’s	Minterms	Binary value	Check mark if pairing is possible in next stage
0	0	0000	X
1	1	0001	X
2	0010	X
2	3	0011	X
5	0101	X
9	1001	X
3	7	0111	X
11	1011	X
4	15	1111	X

* In stage 2, we form pairs, i.e. compare minterms of group n and group n + 1 and place a dash mark i.e '-' whoose binary values differ by 1 bit.

Stage 2
No. of 1’s	Minterms	Binary value	Check mark if pairing is possible in next stage
0	(0,1)	000_	X
(0, 2)	00_0	X
1	(1, 3)	00_1	X
(1, 5)	0_01	X
(1, 9)	_001	X
(2, 3)	001_	X
2	(3, 7)	0_11	X
(3, 11)	_011	X
(5, 7)	01_1	X
(9, 11)	10_1	X
3	(7, 15)	_111	X
(11, 15)	1_11	X

* In stage 3, we form pairs on stage 2, i.e. compare minterms of group n and group n + 1 and place a dash mark i.e '-' whoose binary values differ by 1 bit.

Stage 3
No. of 1’s	No. of 1’s	Binary value	Check mark if pairing is possible in next stage
0	(0, 1, 2, 3)	00_ _
(0, 2, 1, 3)	00_ _
1	(1, 3, 5, 7)	0_ _1
(1, 3, 9, 11)	_0_1
(1, 5, 3, 7)	0_ _1
(1, 9, 3, 11)	_0_1
2	(3, 7, 11, 15)	_ _ 11
(3, 11, 7, 15)	_ _ 11

After the stage 3 process we stop since further pairing is not possible.

After no further pairing is possible, then the unchecked minterms are the prime implicants

Check the tablesof stage 1, stage 2, stage 3 for unchecked minterms. Thus prime implicants are

$ \overline A\ \overline B \\ \overline A \ D\\ \overline B \ D \\C \ D $

The function can now be written as

$Y= \overline A\ \overline B + \overline A \ D + \overline B \ D+C \ D $

Step 2: Use the prime implicants in a prime implicant chart to find the essential prime implicants and other prime implicants that are required to completely cover the given equation.

Put all prime implicants in a cover table (don’t cares excluded)

Prime Implicants	1	2	5	7	9	15
$\overline A \ \overline B$	X	X
$\overline A\ D$	X		X	X
$\overline B\ D$	X				X
$C \ D$				X		X
Check whether all minterms are covered with essential prime implicants		X	X		X	X

* Identify essential minterms, and hence essential prime implicants

Identify the minterms which contain only one X in the column. The corresponding row gives you the essential prime implicant.

2, 5, 9 &15 is the minterms which contain only one X in the column. Thus the essential prime implicants are

$ \overline A\ \overline B \\ \overline A \ D\\ \overline B \ D \\C \ D $

Since all the minterms are checked off, we have

The function can now be written as

$Y=\overline A\ \overline B + \overline A \ D+ \overline B \ D +C \ D $

K-map simplification of ∑m(1,2,5,7,9,15)+d(0,3,11)

K-Map:-

The simplification of boolean expressions using boolean laws and therorems becomes complex with increase in number variables and terms.
K-Map provides a systematic method for simplifying boolean expressions. N variable K-Map has 2N cell entries. There is a gray code ordering of K-Map rows and columns(i.e. adjacent rows or columns differ by one bit position).

Procedure for simplifying boolean expressions using K-Map:-

Construct K-Map and enter 1's in the cells given in the expression and remaining cells are filled with 0's. Sometimes empty cells are treated as 0's.
Group the adjacent 1's in two(pair), four(quad) or eight(octet) etc.
The variables that remain same in all the cells of the group appear in the terms corresponding to the group or we can say that variables that change get eliminated.

The initial 4 variable karanugh map is as follows

The karanugh map after plotting the following function∑m(1,2,5,7,9,15)+d(0,3,11) and grouping cells is as follo

The simplified boolean expression is as follows

$Y=\overline A\ \overline B + \overline A \ D+ \overline B \ D +C \ D $

which is the same as boolean expresssion obtained by Quine-McCluskey method.

ADD COMMENT EDIT