COMPARATOR: Quine-McCluskey Simplification Method

<< Converting between POS and SOP using the K-map

ODD-PRIME NUMBER DETECTOR, Combinational Circuit Implementation >>

CS302 - Digital Logic & Design

Lesson No. 12

COMPARATOR

A comparator circuit compares two numbers and sets one of its three outputs to 1

indicating the result of the comparison operation. A Comparator circuit has multiple inputs and

three outputs.

A 2-bit Comparator circuit compares two 2-bit numbers A and B. The comparator circuit

has three outputs. It sets the A>B output to 1 if A>B. It sets the A=B output to 1 if A=B and

sets A<B output to 1 if A < B.

The output A>B is set to 1 when the input combinations are 01 00, 10 00, 10 01, 11 00, 11

01 and 11 10

The output A=B is set to 1 when the input combinations are 00 00, 01 01, 10 10 and 11 11

The output A<B is set to 1 when the input combinations are 00 01, 00 10, 00 11, 01 10, 01

11 and 10 11

The circuit has 4-bit input, 2-bits represent A and 2-bits represent B and a 3-bit output

representing A>B, A=B and A<B. To represent the function of a Comparator circuit, three

function tables are required for each of the three outputs. A single function table is drawn with

three outputs. Table 12.1.

Input

Output

A>B

A=B

A<B

Table 12.1

Function Table of a Comparator Circuit

Each of the three outputs, A>B, A=B and A<B are mapped separately using three 4-

variable Karnaugh maps. The Karnuagh Maps and the simplified expressions for the three

outputs are shown. Figure 12.1

109

CS302 - Digital Logic & Design

A1A0\B1B0

(A > B) = A 1B1 + A 0 B1B 0 + A 1A 0 B 0

A1A0\B1B0

(A = B) = A1 A 0 B1B 0 + A 1A 0 B1B 0 + A1A 0B1B 0 + A 1 A 0B1B 0

A1A0\B1B0

(A < B) = A 1B1 + A1 A 0B 0 + A 0B1B 0

Figure 12.1a-c

Simplified Boolean expressions for the A>B, A=B and A<B outputs

Quine-McCluskey Simplification Method

Karnuagh map method becomes difficult to manage when numbers of variables

exceed 4. Even with a 4-varaiable K-map, grouping of 1s or 0s depends on the ability of the

user to detect optimum groups. Some times some redundant groups are included which adds

a product term or a sum term which is not required and thus the expression is not the

simplified version.

Consider the two 4-variable K-map with the groups of 1s shown. Figure 12.2.

AB\CD

Figure 12.2

4-Variable Karnaugh Maps with redundant terms

110

CS302 - Digital Logic & Design

In the 4-variable K-map on the left, 6 groups of 4 cells each are formed. The 6 groups

form the six terms AB , AC , AD , BC , CD and BD . Out of these six terms three terms are

redundant and therefore they are introducing three extra product terms which are not required.

The essential terms that are required are AC , BC and BD .

In the first K-map the group of 1s formed by cells 9, 11, 13 and 15, the group formed by

cells 12, 13, 14 and 15 and the group formed by cells 3, 7, 11 and 15 are redundant.

In the 4-variable K-map on the right, 5 groups are formed. The 5 groups form the five

terms ABC , ACD , ABC , ACD and BD . Out of these five groups the largest group of 4 cells

is redundant and therefore it is introducing an extra product term which is not required. The

essential terms that are required are ABC , ACD , ABC and ACD .

In both the Karnaugh maps, finding the redundant terms is not very obvious. The

Quine-McCluskey approach of simplifying Boolean expression is based on an exhaustive

search where each minterm is compared with every other minterm in order to remove single

variables. The exhaustive search is continued until only a few terms remain which do not

share any common variable that can be eliminated. From these remaining terms the minimal

product terms are selected that represent the simplified form of Boolean expression.

Quine-McCluskey is a program based method that is able to carry out the exhaustive

search for removing shared variables. The Quine-McCluskey method is a two step method

which comprises of finding Prime Implicants and selecting a minimal set of Prime Implicants.

Find Prime Implicants: Find by an exhaustive search all the terms that are candidates for

inclusion in the simplified function. These terms are known as Prime Implicants.

Selecting Minimal Set of Prime Implicants: Choose from amongst the Prime Implicants

those that give expression with the least number of literals.

The Quine-McCluskey is explained with the help of two examples, each of which uses

a slightly different variation of the exhaustive search method. The methods describe the

algorithms of the Quine McCluskey method. The two expressions that are simplified using

Quine-McCluskey are based on the two set of Minterms mapped to the 4-variable Karnaugh

maps shown in figure 12.2

Example 1

A function is defined in Canonical Sum form ∑ A,B,C,D (1,3,6,7,8,9,11,12,13,14,15) . As the

first step of the Quine McCluskey method to find the Prime Implicants through an exhaustive

search, all the Minterms are listed in a tabular form. Table 12.2.

111

CS302 - Digital Logic & Design

Minterm

Minterm A

used

Table 12.2

Table of Minterms

Table 12.3

Rearranged Minterms

The Table of Minterms is reorganized and the Minterms are arranged in groups of

minterms having 0, 1, 2, 3 and 4 1s. This is done to allow different minterms to be easily

compared and allow for elimination of single variables. The rearranged Minterm table is shown

in table 12.3. Four group of Minterms are formed.

· Minterms 1 and 8 have only single 1s

· Minterms 3, 6, 9 and 12 have two 1s each

· Minterms 7, 11, 13 and 14 have three 1s each

· Minterm 15 has 4 1s.

An extra column is added to the table of minterms which is used to mark the terms that are

compared together to eliminate a variable. All pairs of minterms which can be compared

together to eliminate a variable are marked as used.

When comparing minterms the rule is to compare each minterm in one group with each

minterm in the other group. Thus in this example, minterms 1 and 8 in group having single 1s

are compared with each of the 4 minterms 3, 6, 9 and 12 in the group having minterms of 2 1s

each. Similarly, each of the 4 minterms 3, 6, 9 and 12 are compared with each of the minterms

in the next group having 3 1s, that is, minterms 7, 11, 13 and 14. Finally, each of the minterms

7, 11, 13 and 14 are compared with the minterm 15 in the last group having all 1s or 4 1s.

used

1,3

1,9

8,9

8,12

3,7

3,11

6,7

6,14

9,11

9,13

12,13

12,14

7,15

11,15

13,15

14,15

Table 12.4

Compared Minterms, Single variable removed

112

CS302 - Digital Logic & Design

The results of the comparisons between two minterms are represented in a separate

table. Table 12.4. The first column lists the minterms that have been compared together to

eliminate common variables. So terms 1 and 3 forms a single term eliminating variable C,

forming the product term ABD . The comparison terms 1 and 3 are marked as used in table

12.3. Similarly, terms 1 and 9 form a single term eliminating variable A, forming the product

term BCD . Both these terms are marked as used in table 12.3. Similarly, terms 8, 9 eliminate

variable D, terms 8, 12 eliminate variable B, terms 3, 7 eliminate variable B and so on. All

these terms are marked as used in table 12.3.

As a result of comparison a total of 16, three variable product terms are formed,

eliminating a single variable from each term. All the 16 terms are represented in table 12.4. All

the minterms in table 12.3 are shown to be used.

The exhaustive search for finding prime implicants has not completed. The three

variable terms in table 12.4 are compared to eliminate another single variable. All terms that

combine to eliminate a variable are represented in table 12.5.

used

1,3,9,11

8,9,12,13

3,7,11,15

6,7,14,15

9,11,13,15

12,13,14,15 1

Table 12.5

Compared Minterms, Two variable removed

Thus terms 1,3 and terms 9,11 in table 12.4 form the product term BD eliminating

variable A. Whilst comparing terms in table 12.4, a pair of terms which are different in a single

variable are used. The terms 1,3 and 9,11 are different in a single variable A only. All terms in

table 12.4 which form a simpler product term eliminating a single variable are marked as used

in table 12.4.

In table 12.5 there are 6 product terms of two variables each. If the terms in table 12.5

are compared, none of them form pairs to eliminate a variable, thus all the 6 terms are marked

as not used. An unmarked term represents a Prime Implicant. The exhaustive search for

Prime Implicants has been completed. No more terms can be eliminated therefore the

terms BD , AC , CD , BC , AD and AB are considered to be Prime Implicants.

In the second step of Quine-McCluskey method the essential and minimal Prime

Implicants are found. The Prime Implicants found in the first step are listed in left most column

of the table. Table 12.6. All the original minterms are listed in the top row.

113

CS302 - Digital Logic & Design

Table 12.6

Table of Prime Implicants

In each cell an x is marked indicating that the Prime Implicant listed in the left column

covers the minterm mentioned in the top row. Thus the Prime Implicant BD covers the

minterms 1, 3, 9 and 11. In other words minterms 1, 3, 9 and 11 all have the product terms

BD . The table 12.6 can be directly implemented from table 12.5.

Circles are marked in cells having x, which represent minterms covered by only a

single Prime Impicant. Thus the minterms 1, 6 and 8 are covered by only the Prime Implicants

BD , AC and BC respectively. These three Prime Implicants in fact are the three essential

Prime Implicants that cover all the minterms. The simplified expression therefore has the terms

BD , AC and BC . The Prime Implicants CD , AD and AB are redundant product terms which

are not required. The simplified expression is BD + AC + BC

Example 2

A function is defined in Canonical Sum form as ∑ A,B,C,D (1,5,6,7,11,12,13,15) . The

Minterms along with variables ABCD are written in a tabular form. Each minterm is

represented in terms of its binary value. Table 12.7.

Minterm

Used

Table 12.7

Table of Minterms

Table 12.8

Rearranged Minterms

The table of minterms is reorganized in terms of groups of minterms having 0, 1, 2, 3

and 4 1s.

· Minterms 1 has a single 1

· Minterms 5, 6 and 12 have two 1s each

· Minterms 7, 11 and 13 have three 1s each

· Minterm 15 has 4 1s.

114

CS302 - Digital Logic & Design

An extra column is added to the table of minterms which indicates which minterms have been

compared together to eliminate a variable. Table 12.8. All pairs of minterms which can be

compared together to eliminate a variable are marked as used.

When comparing minterms the rule is to compare each minterm in one group with each

minterm in the other group. Thus, in this example, minterm 1 in group having single 1s is

compared with each of the 3 minterms 5, 6 and 12 in the group having minterms of 2 1s each.

Similarly, each of the 3 minterms 5, 6 and 12 are compared with each of the 3 minterms in the

next group having 3 1s, that is, minterms 7, 11 and 13. Finally, each of the 3 minterms 7, 11

and 13 are compared with the minterm 15 in the last group having all 1s or 4 1s.

The results of the comparisons between two minterms are represented in a separate

table. Table 12.9. The first column lists the minterms that have been compared together to

eliminate common variables. The second column shows the variable in terms of its binary

value. So terms 1 and 5 form a single term eliminating variable B, forming the product

term ACD . Variables A, B, C and D have binary values 8, 4, 2 and 1 respectively.

Minterms

Variable used

removed

1,5

5,7

5,13

6,7

12,13

7,15

11,15

13,15

Table 12.9

Compared Minterms, Single variable eliminated

The comparison terms 1 and 5 are marked as used in table 12.8. Similarly terms 5 and

7 form a single term eliminating variable C, forming the product term ABD . Both these terms

are marked as used in table 12.8. Similarly, terms 5, 13 eliminate variable A, terms 6, 7

eliminate variable D, terms 12, 13 eliminate variable D and so on.

As a result of comparison a total of 8, three variable product terms are formed,

eliminating a single variable from each term. All the 8 terms are represented in table 12.9.

The exhaustive search for finding Prime Implicants has not completed.

Terms 5,7 and 13, 15 compare to form a product term BD eliminating variable A. The

terms 5,7 and 13,15 are marked as used in table 12.9. Similarly, terms 5,13 and 7,15 compare

to form an identical product term BD eliminating variable A. Both the terms 5,13 and 7, 15 are

marked as used in table 12.9. To speed up the comparison process terms having the same

missing or removed variables are compared. However, the comparison should eliminate only a

single variable. Thus in table 12.9 terms 1,5 and terms 11,15 have their B variable eliminated.

Considering that 1,5 represents the product term ACD and terms 11, 15 represent the product

term ACD can not be compared as two variables are different. Terms 5,7 and 13,15 can be

compared as in both the product terms the variable C is missing and by comparing the two

product terms removes variable A.

115

CS302 - Digital Logic & Design

Minterms

Term

used

removed

5,7,13,15

2,8

Table 12.10

Minterms compared, two variables removed

No more comparisons of terms and elimination of variables take place. Thus the Prime

Implicants have been found. There are 4 prime implicants in table 3 and another prime

implicant in table 12.10. The five prime implicants are represented by product

terms ACD , ABC , ABC , ACD and BD .

In the second step of Quine-McCluskey method the essential and minimal Prime

implicants are found. The Prime Implicants found in the first step are listed in left most column

of the table. Table 12.11. All the original minterms are listed in the top row. In each cell an x is

marked indicating that the Prime Implicant listed in the left column covers the minterm

mentioned in the top row.

The Prime Implicant ACD covers the minterms 1 and 5. In other words minterms 1 and

5 all have the product terms ACD . The table 12.11 can be directly implemented from table

12.9 and 12.10.

Circles are marked in cells having x, which represent minterms covered by only a

single Prime Impicant. Thus the minterms 1, 6, 11 and 12 are covered by only the Prime

Implicants ACD , ABC , ABC and ACD respectively. These 4 implicants in fact are the three

essential Prime Implicants that cover all the minterms. The simplified expression is

ACD + ABC + ABC + ACD

ACD

ABC

ACD

Table 12.11

Table of Prime Implicants

Comparator Circuit

A 2-bit Comparator circuit that compares two 2-bit numbers A and B and activates one

of its three outputs A>B, A=B and A<B depending upon the magnitudes of the numbers A and

B has been discussed earlier. The function outputs of the three outputs A>B, A=B and A<B

can easily be represented using truth tables which can then be written in a simplified Boolean

expression form after simplifying the three function expressions using 4-variable Karnaugh

maps.

A comparator circuit that compares two 3-bit numbers A and B instead of the 2-bit

numbers has an input of 6-bits, which represents an input combination of 64. Writing a truth

table and simplifying the three expressions using the 6-variable Karnaugh maps becomes

116

CS302 - Digital Logic & Design

unmanageable. A program based Quine-McCluskey method can easily handle expression of 6

variables represented in the Canonical form ∑ A,B,C,D,E,F (8,16,17,24,.........)

Odd-Prime Number Detector

A circuit that detects Odd Prime numbers between 0 and 9 has been considered

earlier. The circuit is to be improved to detect Odd Prime numbers for a decimal number range

represented by 5-bit binary numbers or in terms of decimal numbers between the decimal

number range 0 to 31. Writing out a function table to represent the 32 input combinations and

their corresponding outputs, and then simplifying the function expression using a 5-varaibale

K-map can take up considerable amount of time.

Quine-McCluskey method can be used to easily simplify the 5-variable Boolean

expression represented in Canonical Sum form as ∑ A,B,C,D,E (1,3,5,7,11,13,17,19,23,29,31) . The

minterms 1, 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31 represent the 5-bit input combinations

(decimal numbers) which are Odd and Prime numbers.

117

Table of Contents: