COMPARATOR
Digital Logic & DesignCOMPARATOR
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 4variable Karnaugh maps. The Karnuagh Maps and the simplified expressions for the three outputs are shown. Figure 12.1
A1A0\B1B0 | 00 | 01 | 11 | 10 |
00 | 0 | 0 | 0 | 0 |
01 | 1 | 0 | 0 | 0 |
11 | 1 | 1 | 0 | 1 |
10 | 1 | 1 | 0 | 0 |
(A > B) = AB + A BB + AA B
11 010 100
A1A0\B1B0 | 00 | 01 | 11 | 10 |
00 | 1 | 0 | 0 | 0 |
01 | 0 | 1 | 0 | 0 |
11 | 0 | 0 | 1 | 0 |
10 | 0 | 0 | 0 | 1 |
(A = B) = AA BB + AA BB + AA BB + AABB
1 010 1010 1010 1 010
In the 4-variable K-map on the left, 6 groups of 4 cells each are formed. The 6 groups
form the six termsAB,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, BCandBD.
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
termsABC, ACD, ABC, ACDand 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 andACD.
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.
Minterm | A | B | C | D |
1 | 0 | 0 | 0 | 1 |
3 | 0 | 0 | 1 | 1 |
6 | 0 | 1 | 1 | 0 |
7 | 0 | 1 | 1 | 1 |
8 | 1 | 0 | 0 | 0 |
9 | 1 | 0 | 0 | 1 |
11 | 1 | 0 | 1 | 1 |
12 | 1 | 1 | 0 | 0 |
13 | 1 | 1 | 0 | 1 |
14 | 1 | 1 | 1 | 0 |
15 | 1 | 1 | 1 | 1 |
Minterm | A | B | C | D | used |
1 | 0 | 0 | 0 | 1 | â€¢ |
8 | 1 | 0 | 0 | 0 | â€¢ |
3 | 0 | 0 | 1 | 1 | â€¢ |
6 | 0 | 1 | 1 | 0 | â€¢ |
9 | 1 | 0 | 0 | 1 | â€¢ |
12 | 1 | 1 | 0 | 0 | â€¢ |
7 | 0 | 1 | 1 | 1 | â€¢ |
11 | 1 | 0 | 1 | 1 | â€¢ |
13 | 1 | 1 | 0 | 1 | â€¢ |
14 | 1 | 1 | 1 | 0 | â€¢ |
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
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 termBCD. 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
termsBD,AC,CD,BC,ADand 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.
1 | 3 | 6 | 7 | 8 | 9 | 11 | 12 | 13 | 14 | 15 | |
BD | X | x | x | x | |||||||
AC | x | x | x | x | |||||||
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 andAB 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 âˆ‘_{ABCD }(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 |
1 | 0 | 0 | 0 | 1 |
5 | 0 | 1 | 0 | 1 |
6 | 0 | 1 | 1 | 0 |
7 | 0 | 1 | 1 | 1 |
11 | 1 | 0 | 1 | 1 |
12 | 1 | 1 | 0 | 0 |
13 | 1 | 1 | 0 | 1 |
15 | 1 | 1 | 1 | 1 |
Minterm | A | B | C | D | Used |
1 | 0 | 0 | 0 | 1 | â€¢ |
5 | 0 | 1 | 0 | 1 | â€¢ |
6 | 0 | 1 | 1 | 0 | â€¢ |
12 | 1 | 1 | 0 | 0 | â€¢ |
7 | 0 | 1 | 1 | 1 | â€¢ |
11 | 1 | 0 | 1 | 1 | â€¢ |
13 | 1 | 1 | 0 | 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.
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 removed | used |
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.
Minterms | Term removed | used |
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
termsACD,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,ABCandACD 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 | |
ACD | x | x | ||||||
ABC | x | x | ||||||
ABC | x | x | ||||||
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
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.
Recent Comments