Tabular Method of Minimisation

Introduction Introduction

Rules Rules of Tabular Method

Examples Examples

Problem Problems

Introduction Introduction

In order to understand the tabular method of minimisation, it is best you understand the numerical assignment of Karnaugh map cells and the incompletely specified functions also known as the can't happen conditions. This is because the tabular method is based on these principles.

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 A + = 1. 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 Rules of Tabular Method

Consider a function of three variables f(A, B, C):

Consider the function:

Listing the two minterms shows they can be combined
Now consider the following:

Note that these variables cannot be combined
This is because the FIRST RULE of the Tabular method for two terms to combine, and thus eliminate one variable, is that they must differ in only one digit position.

Bear in mind that when two terms are combined, one of the combined terms has one digit more at logic 1 than the other combined term. This indicates that the number of 1's in a term is significant and is referred to as its index.

For example: f(A, B, C, D)

0000...................Index 0
0010, 1000.............Index 1
1010, 0011, 1001.......Index 2
1110, 1011.............Index 3
1111...................Index 4

The necessary condition for combining two terms is that the indices of the two terms must differ by one logic variable which must also be the same.

Example Examples

Example 1:

Consider the function: Z = f(A,B,C) = + C + A + AC

To make things easier, change the function into binary notation with index value and decimal value.

Tabulate the index groups in a colunm and insert the decimal value alongside.

From the first list, we combine terms that differ by 1 digit only from one index group to the next. These terms from the first list are then seperated into groups in the second list. Note that the ticks are just there to show that one term has been combined with another term. From the second list we can see that the expression is now reduced to: Z = + + C + A

From the second list note that the term having an index of 0 can be combined with the terms of index 1. Bear in mind that the dash indicates a missing variable and must line up in order to get a third list. The final simplified expression is: Z =

Bear in mind that any unticked terms in any list must be included in the final expression (none occured here except from the last list). Note that the only prime implicant here is Z = .

The tabular method reduces the function to a set of prime implicants.

Note that the above solution can be derived algebracially. Attempt this in your notes.

Example 2:

Consider the function f(A, B, C, D) = (0,1,2,3,5,7,8,10,12,13,15), note that this is in decimal form.

(0000,0001,0010,0011,0101,0111,1000,1010,1100,1101,1111) in binary form.

(0,1,1,2,2,3,1,2,2,3,4) in the index form.

The prime implicants are: + + D + BD + A + AB

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.

From the above chart, BD is an essential prime implicant. It is the only prime implicant that covers the minterm decimal 15 and it also includes 5, 7 and 13. is also an essential prime implicant. It is the only prime implicant that covers the minterm denoted by decimal 10 and it also includes the terms 0, 2 and 8. The other minterms of the function are 1, 3 and 12. Minterm 1 is present in and D. Similarly for minterm 3. We can therefore use either of these prime implicants for these minterms. Minterm 12 is present in A and AB, so again either can be used.

Thus, one minimal solution is: Z = + BD + + A

Problems Problems

  1. Minimise the function below using the tabular method of simplification:
    Z = f(A,B,C,D) = + C + ACD + AC + BCD + BC + CD

  2. Using the tabular method of simplification, find all equally minimal solutions for the function below.
    Z = f(A,B,C,D) = (1,4,5,10,12,14)
Click here for answers.
Previous Next Previous Index Map
To submit your questions and queries please click here: Queries
Composed by David Belton - April 98