

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 2bit
Comparator circuit compares
two 2bit 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 4bit input,
2bits represent A and
2bits represent B and a
3bit 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
A1
A0
B1
B0
A>B
A=B
A<B
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
1
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
0
0
1
1
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
1
1
0
0
1
0
0
1
1
0
1
1
0
0
1
1
1
0
1
0
0
1
1
1
1
0
1
0
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
00
01
11
10
0
00
0
0
0
1
0
01
0
0
11
1
1
0
1
10
1
1
0
0
(A > B) = A 1B1 + A 0 B1B 0 + A 1A 0 B 0
A1A0\B1B0
00
01
11
10
1
0
00
0
0
0
01
0
1
0
11
0
0
1
0
1
10
0
0
0
(A = B) = A1 A 0 B1B 0 + A 1A 0 B1B 0 + A1A 0B1B 0 + A 1 A 0B1B 0
01
11
A1A0\B1B0
00
10
00
0
1
1
1
01
0
0
1
1
0
11
0
0
0
10
0
0
1
0
(A < B) = A 1B1 + A1 A 0B 0 + A 0B1B 0
Figure
12.1ac
Simplified
Boolean expressions for the
A>B, A=B and A<B
outputs
QuineMcCluskey
Simplification Method
Karnuagh
map method becomes difficult
to manage when numbers of
variables
exceed 4.
Even with a 4varaiable
Kmap, 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 4variable Kmap
with the groups of 1s shown.
Figure 12.2.
01
11
AB\CD
00
11
10
AB\CD
00
01
10
1
0
1
00
0
0
00
0
1
0
0
1
0
0
01
1
1
01
1
1
11
11
1
1
1
0
1
1
1
1
1
10
0
0
1
0
10
1
1
0
Figure
12.2
4Variable
Karnaugh Maps with redundant
terms
110
CS302 
Digital Logic & Design
In the
4variable Kmap 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 Kmap 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
4variable Kmap 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
QuineMcCluskey
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.
QuineMcCluskey
is a program based method
that is able to carry out
the exhaustive
search
for removing shared
variables. The QuineMcCluskey
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
QuineMcCluskey 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
QuineMcCluskey
are based on the two
set of Minterms mapped to
the 4variable
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
A
B
C
D
Minterm
A
B
C
D
used
1
0
0
0
1
1
0
0
0
1
3
0
0
1
1
8
1
0
0
0
6
0
1
1
0
3
0
0
1
1
7
0
1
1
1
6
0
1
1
0
8
1
0
0
0
9
1
0
0
1
9
1
0
0
1
12
1
1
0
0
11
1
0
1
1
7
0
1
1
1
12
1
1
0
0
11
1
0
1
1
13
1
1
0
1
13
1
1
0
1
14
1
1
1
0
14
1
1
1
0
15
1
1
1
1
15
1
1
1
1
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.
A
B
C
D
used
1,3
0
0

1
1,9

0
0
1
8,9
1
0
0

8,12
1

0
0
3,7
0

1
1
3,11

0
1
1
6,7
0
1
1

6,14

1
1
0
9,11
1
0

1
9,13
1

0
1
12,13
1
1
0

12,14
1
1

0
7,15

1
1
1
11,15
1

1
1
13,15
1
1

1
14,15
1
1
1

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.
A
B
C
D
used
1,3,9,11

0

1
8,9,12,13
1

0

3,7,11,15


1
1
6,7,14,15

1
1

9,11,13,15
1


1
12,13,14,15
1
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 QuineMcCluskey
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
1
3
6
7
8
9
11
12
13
14
15
X
x
x
x
BD
x
x
x
x
AC
CD
x
x
x
x
BC
x
x
x
x
AD
x
x
x
x
AB
x
x
x
x
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
A
B
C
D
Minterm
A
B
C
D
Used
1
0
0
0
1
1
0
0
0
1
5
0
1
0
1
5
0
1
0
1
6
0
1
1
0
6
0
1
1
0
7
0
1
1
1
12
1
1
0
0
11
1
0
1
1
7
0
1
1
1
12
1
1
0
0
11
1
0
1
1
13
1
1
0
1
13
1
1
0
1
15
1
1
1
1
15
1
1
1
1
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
4
5,7
2
5,13
8
6,7
1
12,13
1
7,15
8
11,15
4
13,15
2
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 QuineMcCluskey
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
1
5
6
7
11
12
13
15
x
x
ACD
x
x
ABC
x
x
ABC
ACD
x
x
BD
x
x
x
x
Table
12.11
Table of
Prime Implicants
Comparator
Circuit
A 2bit
Comparator circuit that
compares two 2bit 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 4variable
Karnaugh
maps.
A comparator
circuit that compares two
3bit numbers A and B
instead of the 2bit
numbers
has an input of 6bits,
which represents an input
combination of 64. Writing a
truth
table
and simplifying the three
expressions using the
6variable Karnaugh maps
becomes
116
CS302 
Digital Logic & Design
unmanageable. A
program based QuineMcCluskey
method can easily handle
expression of 6
variables
represented in the Canonical
form ∑ A,B,C,D,E,F (8,16,17,24,.........)
OddPrime
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
5bit 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
5varaibale
Kmap
can take up considerable
amount of time.
QuineMcCluskey
method can be used to easily
simplify the 5variable
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
5bit input
combinations
(decimal
numbers) which are Odd
and Prime numbers.
117
Table of Contents:

