Quine-McCluskey (Q-M) Tabular Method

    

Quine-McCluskey (Q-M) method  minimizes a logical expression realizing a given Boolean function which is more efficient for computer algorithm, makes this more useful than the K- Map method as for more than 5 variables it gets complex . Q-M method utilizes the following three basic simplification laws:

(i) x + x’ =1 (Complement)

(ii) x + x = x (Idempotent)

(iii) x ( y + z) = xy + xz (Distributive)

Before knowing how to minimize function using Q-M Method, we must know following terms:

• Literal: It is a variable or its negation ( x or x’ )
• Minterm: A product of the literals where each variable appears exactly once either true or complemented form, i.e., a normal product term consisting of n literals for n variable function.
• Maxterm: A sum of the literals where each variable appears exactly once either true or complemented form i.e a normal sum term consisting of n literals.
• DNF Form (sum-of-product): The disjunctive normal form is the sum of minterms of the variables.
• CNF Form (product-of-sum): Conjunctive normal form is a product-of-maxterm of the variables.
• Prime Implicant: A prime implicant of a function is the product which can not be combined with another term to eliminate a variable for further simplification.
• Essential Prime Implicant: Prime implicant that is able to cover an output of the function which is not covered by any combination of prime implicant called essential prime implicant.

Q-M Method is also known as tabulation method because it uses a table to check for the minimum form of function. Steps can be broadly categorized in three steps:

(a) Find the Prime Implicant

In this step, we replace the literals in form of 0 and 1 and generate a table. Initially, the number of rows in table is equal to the total number of minterms of the original unsimplified function. If two terms are only different in one bit like 101 and 111 i.e. one variable is appearing in both form (variable and its negation), then we can use complement law. Iteratively, we compare all term and generate the prime implicant.

(b) Find the Essential Prime Implicant

Using prime implicants from above step, we generate the table to find essential prime implicants. Note that some prime implicants can be redundant and may be omitted, but if they appear only once, they cannot be omitted and provide prime implicant.

(c) Find Other Prime Implicant

It is not necessary that essential prime implicants cover all the minterms. In that case, we consider other prime implicant to make sure that all minterms has been covered.

Let us see an example to understand better.

Example:

Find the minimal sum of products for the Boolean expression, f = (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:

 Group of minterms for different number of 1's:

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:

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.

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:

The columns having only one cross mark correspond to essential prime implicants.The prime implicants sum gives the function in its minimal SOP form.

Y = V'X + V'W + UV' + WX + UW

In general, Q-M method provides better method for the function simplification than K-map.