4.8 C
New York
Monday, November 25, 2024

Quine McCluskey Methodology – GeeksforGeeks

Share To Your Friends

[ad_1]

Boolean operate simplification is likely one of the fundamentals of Digital Electronics. The quine-McCluskey methodology additionally referred to as the tabulation methodology is a really helpful and handy methodology for simplification of the Boolean capabilities for numerous variables (larger than 4). This methodology is helpful over Okay-map when the variety of variables is bigger for which Okay-map formation is tough. This methodology makes use of prime implicants for simplification. 

On this methodology, we assemble a number of tables based on the query and on the final, we make a first-rate implicant desk which is used to acquire important prime implicants that are current within the simplified boolean expression. This methodology requires prior information of decimal to binary illustration and the fundamentals of boolean algebra. It’s a appropriate methodology for numerous enter variables which may be simply solved by this methodology however the computation complexity is excessive. Majorly, this methodology consists of using minterms, and prime implicants and obtains important prime implicants that are additional used within the simplified boolean capabilities. 

Quine McCluskey Methodology (QMC):

  • Quine McCluskey methodology also called the tabulation methodology is used to reduce the Boolean capabilities.
  • It simplifies boolean expression into the simplified type utilizing prime implicants.
  • This methodology is handy to simplify boolean expressions with greater than 4 enter variables.
  • It makes use of an computerized simplification routine.

Terminologies:

Implicant: Implicant is outlined as a gaggle of 1’s(for minterm).  

Prime implicant: It’s the largest potential group of 1’s(for minterm).

Important Prime implicant: Important prime implicants are teams that cowl no less than one minterm which can’t be coated by different candidates.

Observe: This methodology makes use of decimal to binary illustration.

Steps for Quine McCluskey Methodology:

  1. Organize the given minterms based on the variety of ones current of their binary illustration in ascending order.
  2. Take the minterms from the continual group if there may be solely a one-bit change to make their pair. 
  3. Place the ‘-‘ image the place there’s a bit change accordingly and maintain the remaining bits the identical.
  4. Repeat steps 2 to three till we get all prime implicants (when all of the bits current within the desk are completely different).
  5. Make a first-rate implicant desk that consists of the prime implicants (obtained minterms) as rows and the given minterms (given in downside) as columns.
  6. Place ‘1’ within the minterms (cell) that are coated by every prime implicant.
  7. Observe the desk, if the minterm is roofed by just one prime implicant then it’s an important to prime implicant.
  8. Add the important prime implicants to the simplified boolean operate. 

Instance: Simplify utilizing tabulation methodology : F(A,B,C,D) =∑ m(0,1,2,4,6,8,9,11,13,15)

Answer: Convert the given minterms into their binary illustration and prepare them based on the variety of ones current within the binary illustration. 

                     TABLE 1
Group  Minterm  A  B  C  D
    0      0  0  0  0  0
   1

     1

     2

     4

     8

 0 

 0

 0

 1

 0

 0

 1

 0

 0

 1

 0

 0

 1

 0

 0

 0

   2

     6

     9

 0

 1

 1

 0

 1

 0

 0

 1

   3

     11

     13

 1

 1

 0

 1

 1

 0

 1

 1

   4      15  1  1  1  1

As 0 has no 1 in its illustration it’s saved in a single group(0). Equally, 1 2 4, and eight include one 1 of their illustration so it’s saved within the subsequent group(1). 6 and 9 within the subsequent group(2), 11, and 13 within the subsequent group(3), 15 within the final group(4). 

Now, for table-2 take minterms from successive teams(simultaneous group solely) which have an solely a 1-bit distinction of their illustration and type their pair by merging them and making a gaggle of the pairs that are from the identical teams which are merged (for instance 0 is from group 0 and 1 is from group 1 so it’s added to the group 0. 0 belongs to group 0 in desk 1 and a pair of belongs to group 1 in desk 1 so its saved in the identical group in desk 2. Equally, make all of the potential pairs with the assistance of the above desk and mark – the place there’s a bit distinction. 

                   TABLE-2
Group Pair  A  B  C  D
    0

(0,1)

(0,2)

(0,4)

(0,8)

 0

 0

 0

 –

 0

 0

 –

 0

 0

 –

 0

 0

 –

 0

 0

 0

    1

(1,9) 

(2,6)

(4,6)

(8,9)

 –

 0

 0

 1

 0

 –

 1

 0

 0

 1

 –

 0

 1

 0

 0 

 –

    2

(9,11)

(9,13)

 1

 1 

 0

 –

 –

 0

 1

 1

    3

(11,15)

(13,15)

 1

 1

 –

 1

 1

 –

 1

 1

For desk 3 repeat the identical step by taking pairs of successive teams merging them the place there may be solely a 1-bit distinction and protecting them in teams based on the teams from the place they’re merged and positioned – in bit distinction.

                      TABLE-3
Group    Quad  A  B  C  D
    0

  (0,1,8,9)

  (0,2,4,6)

 –

 0

 0 

 –

 0

 –

 –

 0

    1 (9,11,13,15)  1  –   –  1

After desk 3 the method is stopped as there isn’t a 1-bit distinction within the remaining group minterms within the simultaneous teams of desk 3.

Now, the remaining quads current in desk 3 characterize the prime implicants for the given boolean operate. So, we assemble prime implicants desk which comprises the obtained prime implicants as rows and the given minterms as columns. Place 1 within the corresponding place which the minterm can characterize. Add the minterm to the simplified boolean expression if the given minterm is barely coated by this prime implicant.  

                  PRIME IMPLICANT TABLE

Minterms ⇢

Prime Implicants ⇣

 0  1  2  4  6  8  9  11  13  15
       B’C’ (0,1,8,9)  1  1              1   1
       A’D'(0,2,4,6)  1      1  1  1
       AD(9,11,13,15)                           1    1    1     1
Simplified Boolean operate = B’C’ + A’D’ + AD

B’C’ is in simplified operate as minterm 1 is barely coated by B’C’. Equally, minterms 2,4,6 are solely coated by A’D’ and minterms 11,13,15 are solely coated by AD.

Instance: Simplify utilizing tabulation methodology : F(A,B,C,D,E,F,G) = ∑m(20,28,52,60)

Answer: Convert the given minterms of their binary illustration and prepare them based on variety of one’s current within the binary illustration. 

                                  TABLE-1
Group Minterms  A  B  C  D  E   F  G
    0      20  0   0  1   0  1  0   0
    1

     28

     52

 0

 0

 0

 1

 1 

 1

 1

 0

 1

 1

 0

 0 

 0

 0

    2      60  0  1  1   1   1  0  0

As 20 has 2 1s in its illustration it’s saved in a single group(0). Equally, 28 and 52 include 3 1s of their illustration so it’s saved within the subsequent group(1). 60 within the subsequent group(2).

Now, for table-2 take minterms from successive teams(simultaneous group solely) which have an solely a 1-bit distinction of their illustration and type their pair by merging them and making a gaggle of the pairs that are from the identical teams which are merged (for instance 20 is from group 0 and 28 is from group 1 so it’s added to the group 0. 20 belongs to group 0 in desk 1 and 52 belongs to group 1 in desk 1 so its saved in the identical group in desk 2. Equally, make all of the potential pairs with the assistance of the above desk and mark – the place it’s a bit completely different. 

                                TABLE-2
Group   Pair  A  B  C  D  E   F  G
    0

 (20,28)

 (20,52)

 0

 0

 0

 –

 1

 1

 –

 0

 1

 1

 0

 0

 0

 0

    1

 (28,60)

 (52,60)

 0

 0

 –

 1

 1

 1

 1

 –

 1

 1

 0

 0

 0

 0

For desk 3 repeat the identical step by taking pairs of successive teams merging them the place there may be solely a 1-bit distinction and protecting them in teams based on the teams from the place they’re merged and positioned – in bit distinction.

                                  TABLE-3
Group    Quad  A  B  C  D  E   F  G
    0 (20,28,52,60)  0   –  1  –  1  0  0

After desk 3 the method is stopped as there isn’t a 1-bit distinction within the remaining group minterms within the simultaneous teams of desk 3.

Now, the remaining quads current in desk 3 characterize the prime implicants for the given boolean operate. So, we assemble prime implicants desk which comprises the obtained prime implicants as rows and the given minterms as columns. Place 1 within the corresponding place which the minterm can characterize. Add the minterm to the simplified boolean expression if the given minterm is barely coated by this prime implicant. 

A’CEF’G’ is obtained from desk 3 as A, F, G comprises 0 so A’F’G’, C, and E include 1 so CE. 

              Prime Implicants Desk

Minterms ⇢

Prime Implicants ⇣

 20  28  52  60
 A’CEF’G'(20,28,52,60)   1    1    1     1
Simplified Boolean Perform = A’CEF’G’

A’CEF’G’ is in simplified operate as it’s the solely prime implicant that covers all minterms.

Benefits of Quine McClusky Methodology:

  • This methodology is appropriate for numerous inputs(n>4) for which Okay-map building is a tedious process.
  • It doesn’t require sample recognition.

Disadvantages of Quine McClusky Methodology:

  • The computational complexity of this methodology is excessive.

[ad_2]


Share To Your Friends

Related Articles

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Latest Articles