210
Digital Electronics
single term where the position of the unmatched literals is replaced with a dash (—). These new
terms formed as a result of the matching process find a place in the second table. The terms in the
first table that do not find a match are called the prime implicants and are marked with an asterisk
(∗). The matched terms are ticked ().
4. Terms in the second group are compared with those in the third group to look for a possible match.
Again, terms in the second group that do not find a match become the prime implicants.
5. The process continues until we reach the last group. This completes the first round of matching.
The terms resulting from the matching in the first round are recorded in the second table.
6. The next step is to perform matching operations in the second table. While comparing the terms for
a match, it is important that a dash (—) is also treated like any other literal, that is, the dash signs
also need to match. The process continues on to the third table, the fourth table and so on until the
terms become irreducible any further.
7. An optimum selection of prime implicants to account for all the original terms constitutes the terms
for the minimized expression. Although optional (also called ‘don’t care’) terms are considered for
matching, they do not have to be accounted for once prime implicants have been identified.
Let us consider an example. Consider the following sum-of-products expression:
AABBC + AABBD + AACCD + BBCCD + AABBCCD
(6.35)
In the first step, we write the expanded version of the given expression. It can be written as follows:
AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCD
+ AABBCCD + AABBCCD
The formation of groups, the placement of terms in different groups and the first-round matching are
shown as follows:
A
B
C
D
A
B
C
D
A
B
C
D
0
0
0
1
0
0
0
1
0
0
−
1
0
0
1
1
0
1
0
0
0
−
0
1
0
1
0
0
−
0
0
1
0
1
0
1
0
0
1
1
0
1
0
−
0
1
1
0
0
1
0
1
0
1
−
0
0
1
1
1
0
1
1
0
−
1
0
0
1
0
0
1
1
0
0
1
1
1
0
0
1
1
0
0
0
−
1
1
1
1
0
1
0
1
1
1
0
1
−
1
1
1
0
1
−
1
0
1
0
1
1
−
1
−
0
1
1
1
0
−
Digital Electronics
single term where the position of the unmatched literals is replaced with a dash (—). These new
terms formed as a result of the matching process find a place in the second table. The terms in the
first table that do not find a match are called the prime implicants and are marked with an asterisk
(∗). The matched terms are ticked ().
4. Terms in the second group are compared with those in the third group to look for a possible match.
Again, terms in the second group that do not find a match become the prime implicants.
5. The process continues until we reach the last group. This completes the first round of matching.
The terms resulting from the matching in the first round are recorded in the second table.
6. The next step is to perform matching operations in the second table. While comparing the terms for
a match, it is important that a dash (—) is also treated like any other literal, that is, the dash signs
also need to match. The process continues on to the third table, the fourth table and so on until the
terms become irreducible any further.
7. An optimum selection of prime implicants to account for all the original terms constitutes the terms
for the minimized expression. Although optional (also called ‘don’t care’) terms are considered for
matching, they do not have to be accounted for once prime implicants have been identified.
Let us consider an example. Consider the following sum-of-products expression:
AABBC + AABBD + AACCD + BBCCD + AABBCCD
(6.35)
In the first step, we write the expanded version of the given expression. It can be written as follows:
AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCD + AABBCCD
+ AABBCCD + AABBCCD
The formation of groups, the placement of terms in different groups and the first-round matching are
shown as follows:
A
B
C
D
A
B
C
D
A
B
C
D
0
0
0
1
0
0
0
1
0
0
−
1
0
0
1
1
0
1
0
0
0
−
0
1
0
1
0
0
−
0
0
1
0
1
0
1
0
0
1
1
0
1
0
−
0
1
1
0
0
1
0
1
0
1
−
0
0
1
1
1
0
1
1
0
−
1
0
0
1
0
0
1
1
0
0
1
1
1
0
0
1
1
0
0
0
−
1
1
1
1
0
1
0
1
1
1
0
1
−
1
1
1
0
1
−
1
0
1
0
1
1
−
1
−
0
1
1
1
0
−