• RSS
  • Delicious
  • Digg
  • Facebook
  • Twitter
  • Linkedin
  • Youtube

You need to upgrade your Flash Player to version 10 or newer.

QUINE-McCLUSKEY MINIMIZATION Method

Posted by AJ On Thursday, 11 July 2013 0 comments

Quine-McCluskey minimization method uses the same theorem to produce the solution as the K-map method, namely X(Y+Y')=X
Minimization Technique
  • The expression is represented in the canonical SOP form if not already in that form.
  • The function is converted into numeric notation.
  • The numbers are converted into binary form.
  • The minterms are arranged in a column divided into groups.
  • Begin with the minimization procedure.
  • Each minterm of one group is compared with each minterm in the group immediately below.
  • Each time a number is found in one group which is the same as a number in the group below except for one digit, the numbers pair is ticked and a new composite is created.
  • This composite number has the same number of digits as the numbers in the pair except the digit different which is replaced by an "x".
  • The above procedure is repeated on the second column to generate a third column.
  • The next step is to identify the essential prime implicants, which can be done using a prime implicant chart.
  • Where a prime implicant covers a minterm, the intersection of the corresponding row and column is marked with a cross.
  • Those columns with only one cross identify the essential prime implicants. -> These prime implicants must be in the final answer.
  • The single crosses on a column are circled and all the crosses on the same row are also circled, indicating that these crosses are covered by the prime implicants selected.
  • Once one cross on a column is circled, all the crosses on that column can be circled since the minterm is now covered.
  • If any non-essential prime implicant has all its crosses circled, the prime implicant is redundant and need not be considered further.
  • Next, a selection must be made from the remaining nonessential prime implicants, by considering how the non-circled crosses can be covered best.
  • One generally would take those prime implicants which cover the greatest number of crosses on their row.
  • If all the crosses in one row also occur on another row which includes further crosses, then the latter is said to dominate the former and can be selected.
  • The dominated prime implicant can then be deleted.
Example
Find the minimal sum of products for the Boolean expression,
f=clip_image001(1,2,3,7,8,9,10,11,14,15), using Quine-McCluskey method.
Firstly these minterms are represented in the binary form as shown in the table below. The above binary representations are grouped into a number of sections in terms of the number of 1's as shown in the table below.
Binary representation of minterms
Minterms
U
V
W
X
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
7
0
1
1
1
8
1
0
0
0
9
1
0
0
1
10
1
0
1
0
11
1
0
1
1
14
1
1
1
0
15
1
1
1
1
Group of minterms for different number of 1's
No of 1's
Minterms
U
V
W
X
1
1
0
0
0
1
1
2
0
0
1
0
1
8
1
0
0
0
2
3
0
0
1
1
2
9
1
0
0
1
2
10
1
0
1
0
3
7
0
1
1
1
3
11
1
0
1
1
3
14
1
1
1
0
4
15
1
1
1
1
Any two numbers in these groups which differ from each other by only one variable can be chosen and combined, to get 2-cell combination, as shown in the table below.
2-Cell combinations
Combinations
U
V
W
X
(1,3)
0
0
-
1
(1,9)
-
0
0
1
(2,3)
0
0
1
-
(2,10)
-
0
1
0
(8,9)
1
0
0
-
(8,10)
1
0
-
0
(3,7)
0
-
1
1
(3,11)
-
0
1
1
(9,11)
1
0
-
1
(10,11)
1
0
1
-
(10,14)
1
-
1
0
(7,15)
-
1
1
1
(11,15)
1
-
1
1
(14,15)
1
1
1
-
From the 2-cell combinations, one variable and dash in the same position can be combined to form 4-cell combinations as shown in the figure below.
Combinations
U
V
W
X
(1,3,9,11)
-
0
-
1
(2,3,10,11)
-
0
1
-
(8,9,10,11)
1
0
-
-
(3,7,11,15)
-
-
1
1
(10,11,14,15)
1
-
1
-
The cells (1,3) and (9,11) form the same 4-cell combination as the cells (1,9) and (3,11). The order in which the cells are placed in a combination does not have any effect. Thus the (1,3,9,11) combination could be written as (1,9,3,11).
From above 4-cell combination table, the prime implicants table can be plotted as shown in table below.
Prime Implicants Table
Prime Implicants
1
2
3
7
8
9
10
11
14
15
(1,3,9,11)
X
-
X
-
-
X
-
X
-
-
(2,3,10,11)
-
X
X
-
-
-
X
X
-
-
(8,9,10,11)
-
-
-
-
X
X
X
X
-
-
(3,7,11,15)
-
-
-
-
-
-
X
X
X
X
-
X
X
-
X
X
-
-
-
X
-
The columns having only one cross mark correspond to essential prime implicants. A yellow cross is used against every essential prime implicant. The prime implicants sum gives the function in its minimal SOP form.
Y = V'X + V'W + UV' + WX + UW


0 comments:

Post a Comment