Logic Minimization Using Quine McCluskey rule

Quine McCluskey       

  The Quine McCluskey rule is a method used for minimization of Boolean functions. It is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithm and also gives a determinate way to check that the minimal form of a Boolean function has been reached. It is particularly useful when minimizing
function that has large numbers of variables. The method reduces a function in standard sum of product from a set of prime implicants from which as many variables are eliminated as possible. The prime implicants are then examined to see if some are redundant. The Quine McCluskey makes repeated use of the law A + A’=1.

Quine-McClusky Minimization Procedure

            This is basically a tabular method of minimization and as much it is suitable for

computer applications. The procedure for optimization as follows:

Step 1: Describe individual minterms of the given expression by their equivalent binary

numbers.

Step 2: Form a table by grouping numbers with equivalent number of 1’s in them, i.e.

first numbers with no 1’s, then numbers with one 1, and then numbers with

two 1’s, … etc.

Step 3: Compare each number in the top group with each minterm in the next lower

group. If the two numbers are the same in every position but one, place a

check sign () to the right of both numbers to show that they have been

paired and covered. Then enter the newly formed number in the next column

(a new table). The new number is the old numbers but where the literal differ,

an “x” is placed in the position of that literal.

Step 4: Using (3) above, form a second table and repeat the process again until no

further pairing is possible. (On second repeat, compare numbers to numbers

in the next group that have the same “x” position.

Step 5: Terms which were not covered are the prime implicants and are ORed and

ANDed together to form final function.

Note: The procedure above gives you the prime implicant but not essential prime

implicant.

For Examples using Quine McCluskey Rule Check here.