ZeePedia

COMPARATOR: Quine-McCluskey Simplification Method

<< Converting between POS and SOP using the K-map
ODD-PRIME NUMBER DETECTOR, Combinational Circuit Implementation >>
img
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
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
img
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.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.
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
4-Variable Karnaugh Maps with redundant terms
110
img
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
img
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
img
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 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
img
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
img
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
img
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
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 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
img
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:
  1. AN OVERVIEW & NUMBER SYSTEMS
  2. Binary to Decimal to Binary conversion, Binary Arithmetic, 1’s & 2’s complement
  3. Range of Numbers and Overflow, Floating-Point, Hexadecimal Numbers
  4. Octal Numbers, Octal to Binary Decimal to Octal Conversion
  5. LOGIC GATES: AND Gate, OR Gate, NOT Gate, NAND Gate
  6. AND OR NAND XOR XNOR Gate Implementation and Applications
  7. DC Supply Voltage, TTL Logic Levels, Noise Margin, Power Dissipation
  8. Boolean Addition, Multiplication, Commutative Law, Associative Law, Distributive Law, Demorgan’s Theorems
  9. Simplification of Boolean Expression, Standard POS form, Minterms and Maxterms
  10. KARNAUGH MAP, Mapping a non-standard SOP Expression
  11. Converting between POS and SOP using the K-map
  12. COMPARATOR: Quine-McCluskey Simplification Method
  13. ODD-PRIME NUMBER DETECTOR, Combinational Circuit Implementation
  14. IMPLEMENTATION OF AN ODD-PARITY GENERATOR CIRCUIT
  15. BCD ADDER: 2-digit BCD Adder, A 4-bit Adder Subtracter Unit
  16. 16-BIT ALU, MSI 4-bit Comparator, Decoders
  17. BCD to 7-Segment Decoder, Decimal-to-BCD Encoder
  18. 2-INPUT 4-BIT MULTIPLEXER, 8, 16-Input Multiplexer, Logic Function Generator
  19. Applications of Demultiplexer, PROM, PLA, PAL, GAL
  20. OLMC Combinational Mode, Tri-State Buffers, The GAL16V8, Introduction to ABEL
  21. OLMC for GAL16V8, Tri-state Buffer and OLMC output pin
  22. Implementation of Quad MUX, Latches and Flip-Flops
  23. APPLICATION OF S-R LATCH, Edge-Triggered D Flip-Flop, J-K Flip-flop
  24. Data Storage using D-flip-flop, Synchronizing Asynchronous inputs using D flip-flop
  25. Dual Positive-Edge triggered D flip-flop, J-K flip-flop, Master-Slave Flip-Flops
  26. THE 555 TIMER: Race Conditions, Asynchronous, Ripple Counters
  27. Down Counter with truncated sequence, 4-bit Synchronous Decade Counter
  28. Mod-n Synchronous Counter, Cascading Counters, Up-Down Counter
  29. Integrated Circuit Up Down Decade Counter Design and Applications
  30. DIGITAL CLOCK: Clocked Synchronous State Machines
  31. NEXT-STATE TABLE: Flip-flop Transition Table, Karnaugh Maps
  32. D FLIP-FLOP BASED IMPLEMENTATION
  33. Moore Machine State Diagram, Mealy Machine State Diagram, Karnaugh Maps
  34. SHIFT REGISTERS: Serial In/Shift Left,Right/Serial Out Operation
  35. APPLICATIONS OF SHIFT REGISTERS: Serial-to-Parallel Converter
  36. Elevator Control System: Elevator State Diagram, State Table, Input and Output Signals, Input Latches
  37. Traffic Signal Control System: Switching of Traffic Lights, Inputs and Outputs, State Machine
  38. Traffic Signal Control System: EQUATION DEFINITION
  39. Memory Organization, Capacity, Density, Signals and Basic Operations, Read, Write, Address, data Signals
  40. Memory Read, Write Cycle, Synchronous Burst SRAM, Dynamic RAM
  41. Burst, Distributed Refresh, Types of DRAMs, ROM Read-Only Memory, Mask ROM
  42. First In-First Out (FIFO) Memory
  43. LAST IN-FIRST OUT (LIFO) MEMORY
  44. THE LOGIC BLOCK: Analogue to Digital Conversion, Logic Element, Look-Up Table
  45. SUCCESSIVE –APPROXIMATION ANALOGUE TO DIGITAL CONVERTER