Home | | **Digital Principles and System Design** | Quine-Mccluskey Method or Tabular method of minimization of logic functions

The tabular method which is also known as the Quine-McCluskey method is particularly useful when minimising functions having a large number of variables, e.g. The six-variable functions. Computer programs have been developed employing this algorithm.

**QUINE- MCCLUSKEY METHOD**

The tabular method
which is also known as the Quine-McCluskey method is
particularly useful when minimising functions having a large number of
variables, e.g. The six-variable functions. Computer programs have been
developed employing this algorithm. The method reduces a function in standard
sum of products form to a set of prime implicants from which as many variables
are eliminated as possible. These prime implicants are then examined to see if
some are redundant.

The tabular method makes repeated use of the law

Note that Binary notation is used
for the function, although decimal notation is also used for the functions. As
usual a variable in true form is denoted by 1, in inverted form by 0, and the
abscence of a variable by a dash ( - ).

**Rules of Tabular Method**

1. The
Boolean expression to be simplified is expanded if it is not in expanded form.

2. Different
terms in the expression are divided into groups depending upon the number of 1s
they have.

3. The terms
of the first group are successively matched with those in the next adjacent
higher order group to look for any possible matching and consequent reduction.
The terms are considered

matched when all literals except for one match. The pairs of
matched terms are replaced with a single term where the position of the
unmatched literals is replaced with a dash (**—** ). These
new terms** _{∗}** formed
as a result of the matching process find a place in the second table. The terms
in the first table that do not find a match are called the prime implicants and
are marked with an asterisk ( ). The matched terms are ticked (_).

4. Terms in
the second group are compared with those in the third group to look for a
possible match.

Again,
terms in the second group that do not find a match become the prime implicants.

5. The
process continues until we reach the last group. This completes the first round
of matching. The terms resulting from the matching in the first round are
recorded in the second table.

6. The next
step is to perform matching operations in the second table. While comparing the
terms for a match, it is important that a dash (**—** ) is
also treated like any other literal, that is, the dash signs also need to
match. The process continues on to the third table, the fourth tables and so on
until the terms become irreducible any further.

7. An
optimum selection of prime implicants to account for all the original terms
constitutes the

terms for the minimized expression. Although optional (also
called **‗****do ‘t care‘) ter s are** considered for matching, they do not have
to be accounted for once prime implicants have been identified.

**Example 1: **Let us consider an example.
Consider the following sum-of-products expression:

The
second round of matching begins with the table shown on the previous page. Each
term in the first

group is
compared with every term in the second group. For instance, the first term in
the first group

**00−1 matches with the second term in the
second group 01−1 to−1,yield**which is**0−**recorded
in the** **table shown below. The process
continues until all terms have been compared for a possible match. Since this
new table has only one group, the terms contained therein are all prime
implicants.

In the present example, the terms in the first and second
tables have all found a match. But that is not always the case.

The next table is what is known as the prime implicant table.
The prime implicant table contains all the original terms in different columns
and all the prime implicants recorded in different rows as shown below:

Each prime implicant is identified by a letter. Each prime
implicant is then examined one by one and the terms it can account for are
ticked as shown. The next step is to write a product-of-sums expression using
the prime implicants to account for all the terms. In the present illustration,
it is given as follows.

Obvious simplification reduces this expression to PQRS which
can be interpreted to mean that all prime implicants, that is, P, Q, R and S,
are needed to account for all the original terms.

Therefore, the minimized expression =

**Example 2:**

The procedure is similar to that described for the case of
simplification of sum-of-products expressions. The resulting tables leading to
identification of prime implicants are as follows:

The prime implicant table is constructed after all prime
implicants have been identified to look for the optimum set of prime implicants
needed to account for all the original terms. The prime implicant table shows
that both the prime implicants are the essential ones:

The chart is
used to remove redundant prime implicants. A grid is prepared having all the
prime implicants listed at the left and
all the minterms of the function along the top. Each minterm covered by a
given prime implicant is marked in the appropriate position.

**Ref: ****John F. Wakerly, “Digital Design Principles and Practices”,**FourthEdition, Pearson Education,2007.** **Pg.No:264.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.