Module
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Module as PDF for free.
More details
- Words: 1,639
- Pages: 5
Module 0092: Boolean expression minimization Tak Auyeung, Ph.D. November 15, 2006
1
About this module Prerequisites: 0091 Objectives: This module discusses the K-map technique for expression minimization.
2
Notation
In this module, we use the multiple symbol for conjunction and the addition symbol for disjunction. Negation is represented by a prime symbol. These notation symbols are consistent with the convention used in computer and electrical engineering. Furthermore, we use 1 to represent true and 0 to represent false.
3
SOP and POS
SOP (sum of products) and POS (product of sums) are two basic techniques to encode boolean functions in programmable and non-programmable circuits.
3.1
SOP
Sum of products is the more common encoding method. Let us consider an example. Given three terms, X, Y and Z, we can define a truth table for the output as in table 1. We can define a product term for each row of the table, yielding table 2. Note that in table 2, only the rows with an output of 1 are represented by their product terms. This is because there is no need to represent the rows with 0 as the output. Given the product terms in table 2, we can summarize and write the equation as follows: W = X 0 Y 0 Z 0 + X 0 Y Z + XY 0 Z 0 + XY Z 0 + XY Z X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
output 1 0 0 1 1 0 1 1 Table 1: An arbitrary truth table of three variables.
1
(1)
X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
W (output) 1 0 0 1 1 0 1 1
product X 0Y 0Z 0
X 0Y Z XY 0 Z 0 XY Z 0 XY Z Table 2: True product terms for truth table 1.
X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
W (output) 1 0 0 1 1 0 1 1
product X 0Y 0Z X 0Y Z 0
XY 0 Z
Table 3: False product terms for truth table 1.
3.2
POS
Product of sums is a less common method to encode binary logic. However, it is not much more difficult. Let us reuse truth table 1. Instead of representing the rows with 1 as the output, now we represent all the rows with an output of 0. This yields table 3. The product terms are intentionally inverted from the output. This yields the following equation: W = (X 0 Y 0 Z + X 0 Y Z 0 + XY 0 Z)0
(2)
This expression is currently the negation of a sum of products. We can now apply de Morgan’s law, so the expression becomes the following: W = (X 0 Y 0 Z)0 (X 0 Y Z 0 )0 (XY 0 Z)0
(3)
Next, we apply de Morgan’s law for each product term: W = (X + Y + Z 0 )(X + Y 0 + Z)(X 0 + Y + Z 0 )
4
(4)
Optimization
Let us revisit equation 1. Can we do better than this? Can we simplify the equation, somehow? A quick visual inspection reveals that we have both the terms XY Z 0 and XY Z in the sum. XY Z 0 + XY Z = XY (Z 0 + Z) = XY (1) = XY . In other words, we can optimize Z out of the equation, yielding W = X 0 Y 0 Z 0 + X 0 Y Z + XY 0 Z 0 + XY . Next, we recognize that we have X 0 Y 0 Z 0 + XY 0 Z 0 = Y 0 Z 0 . This further reduces the equation to W = Y 0 Z 0 + X 0 Y Z + XY . Can we reduce the equation any further? Is there a systematic method to simply Boolean functions?
4.1
Karnaugh Map
A Karnaugh Map (K-map) is a tool so that an engineer can visually inspect a boolean output function and identify optimization possibilities. For three variables, we can use a K-map with two rows, where each row has 4 values. This is represented in table 4.
2
Z ↓ XY → 0 1
00 1
01 1
11 1 1
10 1
Table 4: K-map for table 1. Z ↓ XY → 0 1
00 1 {d}
01 1 {b}
11 1 {a, c} 1 {b, c}
10 1 {a, d}
Table 5: K-map for table 1, with cell group membership identified.
4.2
Singles, pairs, quads, octs, etc
A “single” is a cell that has a value of 1. In our example, we have five of these. Next, we try to identify groups of two singles (vertical or horizontal). Note that variable X wraps around from the last column to the first column. We can identify four pairs. In table 5, we represent the membership of a cell to each pair by a set. The pairs are identified as a, b, c, d. Note that each adjacent pair represents that a variable is not significant in the product term. We have, thus, identified four methods to reduce the equation. The next step is to identify pairs of pairs. In other words, we want to locate two pairs that are adjacent to each other. In this table, however, we do not have such cases. If the cell corresponding to XY = 01, Z = 0 is also a 1, then the entire first row (consisting of two pairs) can be combined. Because we cannot create any pairs of pairs, then there is no need to look for pairs of pairs of pairs. Once we can no longer combine pairs into larger units, we need to select the smallest number of singles, pairs, pairs of pairs and etc.
4.3
Selection
To select the least number of groups (singles, pairs, quads, octs, etc.), we start with the largest size. In our example, we start with pairs. Since there are four pairs, we need to select the highest number of pairs that leaves the least number of singles. Fortunately, we don’t have any singles. This means we only need to select enough pairs to cover all the 1s. In our case, we have multiple possible combinations of pairs: {a, b, d} and {b, c, d} will both cover all the 1s. It is okay to have multiple groups covering the same cell. Selecting pairs {a, b, d} means the output function is W = XZ 0 (a) + Y Z(b) + Y 0 Z 0 (d). Selecting pairs {b, c, d} means the output function is W = Y Z(b) + XY (c) + Y 0 Z 0 (d).
4.4
Another example
In module 0079, the “Merge” algorithm has a look up table based on comparison results. For simplicity, let X = lv ≤ in0, Y = lv ≤ in1, Z = in0 ≤ in1. Then, table 6 represents the truth table. We can rewrite the truth table as a k-map as in table 7. Next, we identify pairs of singles. There are three pairs. Let us name them {a, b, c}. We now rewrite the k-map to represent the pair ownership, represented by table 8. X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
output 1 0 1 1 0 0 1 0 Table 6: The truth table corresponding to the merge algorithm of module 0079.
3
Z ↓ XY → 0 1
00 1
01 1 1
11 1
10
Table 7: K-map for table 6. Z ↓ XY → 0 1
00 1 {a}
01 1{a, b, c} 1 {c}
11 1 {b}
10
Table 8: K-map for table 6 with pair ownership. In this case, we have to select all the pairs, which means the result is W = X 0 Z 0 (a) + Y Z 0 (b) + X 0 Y (c).
4.5
Don’t care entries
Note that in this case, we know that certain combinations are impossible. XY 0 Z is impossible because (lv ≤ in0) ∧ (lv > in1) ⇒ (in0 > in1). Likewise, X 0 Y Z 0 is also impossible. As a result, we can add the “don’t care” symbol in our original truth table because if an input combination is not possible, we don’t care about the output. This new truth table is represented by table 9. We can now rewrite the k-map as table 10. Next, we identify pairs of singles. There are three pairs. Let us name them {a, b, c}. We now rewrite the k-map to represent the pair ownership, represented by table 8. The use of the “don’t care symbol can possibly help simplify the equation. This is because a question mark can be included or excluded by the groups (singles, pairs and etc.). It gives us the extra flexibility to combine groups. Unfortunately, even the “don’t care” symbol does not help us in this example!
X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
output 1 0 ? 1 0 ? 1 0
Table 9: The truth table corresponding to the merge algorithm of module 0079 with “don’t care” entries. 4
Z ↓ XY → 0 1
00 1
01 ? 1
11 1
10 ? Table 10: K-map for table 6.
5
1
About this module Prerequisites: 0091 Objectives: This module discusses the K-map technique for expression minimization.
2
Notation
In this module, we use the multiple symbol for conjunction and the addition symbol for disjunction. Negation is represented by a prime symbol. These notation symbols are consistent with the convention used in computer and electrical engineering. Furthermore, we use 1 to represent true and 0 to represent false.
3
SOP and POS
SOP (sum of products) and POS (product of sums) are two basic techniques to encode boolean functions in programmable and non-programmable circuits.
3.1
SOP
Sum of products is the more common encoding method. Let us consider an example. Given three terms, X, Y and Z, we can define a truth table for the output as in table 1. We can define a product term for each row of the table, yielding table 2. Note that in table 2, only the rows with an output of 1 are represented by their product terms. This is because there is no need to represent the rows with 0 as the output. Given the product terms in table 2, we can summarize and write the equation as follows: W = X 0 Y 0 Z 0 + X 0 Y Z + XY 0 Z 0 + XY Z 0 + XY Z X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
output 1 0 0 1 1 0 1 1 Table 1: An arbitrary truth table of three variables.
1
(1)
X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
W (output) 1 0 0 1 1 0 1 1
product X 0Y 0Z 0
X 0Y Z XY 0 Z 0 XY Z 0 XY Z Table 2: True product terms for truth table 1.
X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
W (output) 1 0 0 1 1 0 1 1
product X 0Y 0Z X 0Y Z 0
XY 0 Z
Table 3: False product terms for truth table 1.
3.2
POS
Product of sums is a less common method to encode binary logic. However, it is not much more difficult. Let us reuse truth table 1. Instead of representing the rows with 1 as the output, now we represent all the rows with an output of 0. This yields table 3. The product terms are intentionally inverted from the output. This yields the following equation: W = (X 0 Y 0 Z + X 0 Y Z 0 + XY 0 Z)0
(2)
This expression is currently the negation of a sum of products. We can now apply de Morgan’s law, so the expression becomes the following: W = (X 0 Y 0 Z)0 (X 0 Y Z 0 )0 (XY 0 Z)0
(3)
Next, we apply de Morgan’s law for each product term: W = (X + Y + Z 0 )(X + Y 0 + Z)(X 0 + Y + Z 0 )
4
(4)
Optimization
Let us revisit equation 1. Can we do better than this? Can we simplify the equation, somehow? A quick visual inspection reveals that we have both the terms XY Z 0 and XY Z in the sum. XY Z 0 + XY Z = XY (Z 0 + Z) = XY (1) = XY . In other words, we can optimize Z out of the equation, yielding W = X 0 Y 0 Z 0 + X 0 Y Z + XY 0 Z 0 + XY . Next, we recognize that we have X 0 Y 0 Z 0 + XY 0 Z 0 = Y 0 Z 0 . This further reduces the equation to W = Y 0 Z 0 + X 0 Y Z + XY . Can we reduce the equation any further? Is there a systematic method to simply Boolean functions?
4.1
Karnaugh Map
A Karnaugh Map (K-map) is a tool so that an engineer can visually inspect a boolean output function and identify optimization possibilities. For three variables, we can use a K-map with two rows, where each row has 4 values. This is represented in table 4.
2
Z ↓ XY → 0 1
00 1
01 1
11 1 1
10 1
Table 4: K-map for table 1. Z ↓ XY → 0 1
00 1 {d}
01 1 {b}
11 1 {a, c} 1 {b, c}
10 1 {a, d}
Table 5: K-map for table 1, with cell group membership identified.
4.2
Singles, pairs, quads, octs, etc
A “single” is a cell that has a value of 1. In our example, we have five of these. Next, we try to identify groups of two singles (vertical or horizontal). Note that variable X wraps around from the last column to the first column. We can identify four pairs. In table 5, we represent the membership of a cell to each pair by a set. The pairs are identified as a, b, c, d. Note that each adjacent pair represents that a variable is not significant in the product term. We have, thus, identified four methods to reduce the equation. The next step is to identify pairs of pairs. In other words, we want to locate two pairs that are adjacent to each other. In this table, however, we do not have such cases. If the cell corresponding to XY = 01, Z = 0 is also a 1, then the entire first row (consisting of two pairs) can be combined. Because we cannot create any pairs of pairs, then there is no need to look for pairs of pairs of pairs. Once we can no longer combine pairs into larger units, we need to select the smallest number of singles, pairs, pairs of pairs and etc.
4.3
Selection
To select the least number of groups (singles, pairs, quads, octs, etc.), we start with the largest size. In our example, we start with pairs. Since there are four pairs, we need to select the highest number of pairs that leaves the least number of singles. Fortunately, we don’t have any singles. This means we only need to select enough pairs to cover all the 1s. In our case, we have multiple possible combinations of pairs: {a, b, d} and {b, c, d} will both cover all the 1s. It is okay to have multiple groups covering the same cell. Selecting pairs {a, b, d} means the output function is W = XZ 0 (a) + Y Z(b) + Y 0 Z 0 (d). Selecting pairs {b, c, d} means the output function is W = Y Z(b) + XY (c) + Y 0 Z 0 (d).
4.4
Another example
In module 0079, the “Merge” algorithm has a look up table based on comparison results. For simplicity, let X = lv ≤ in0, Y = lv ≤ in1, Z = in0 ≤ in1. Then, table 6 represents the truth table. We can rewrite the truth table as a k-map as in table 7. Next, we identify pairs of singles. There are three pairs. Let us name them {a, b, c}. We now rewrite the k-map to represent the pair ownership, represented by table 8. X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
output 1 0 1 1 0 0 1 0 Table 6: The truth table corresponding to the merge algorithm of module 0079.
3
Z ↓ XY → 0 1
00 1
01 1 1
11 1
10
Table 7: K-map for table 6. Z ↓ XY → 0 1
00 1 {a}
01 1{a, b, c} 1 {c}
11 1 {b}
10
Table 8: K-map for table 6 with pair ownership. In this case, we have to select all the pairs, which means the result is W = X 0 Z 0 (a) + Y Z 0 (b) + X 0 Y (c).
4.5
Don’t care entries
Note that in this case, we know that certain combinations are impossible. XY 0 Z is impossible because (lv ≤ in0) ∧ (lv > in1) ⇒ (in0 > in1). Likewise, X 0 Y Z 0 is also impossible. As a result, we can add the “don’t care” symbol in our original truth table because if an input combination is not possible, we don’t care about the output. This new truth table is represented by table 9. We can now rewrite the k-map as table 10. Next, we identify pairs of singles. There are three pairs. Let us name them {a, b, c}. We now rewrite the k-map to represent the pair ownership, represented by table 8. The use of the “don’t care symbol can possibly help simplify the equation. This is because a question mark can be included or excluded by the groups (singles, pairs and etc.). It gives us the extra flexibility to combine groups. Unfortunately, even the “don’t care” symbol does not help us in this example!
X 0 0 0 0 1 1 1 1
Y 0 0 1 1 0 0 1 1
Z 0 1 0 1 0 1 0 1
output 1 0 ? 1 0 ? 1 0
Table 9: The truth table corresponding to the merge algorithm of module 0079 with “don’t care” entries. 4
Z ↓ XY → 0 1
00 1
01 ? 1
11 1
10 ? Table 10: K-map for table 6.
5
