Group cells in these three-variable Karnaugh maps and write the reduced logic expression
Answer.
Lorem ipsum
Section 3.3 Karnaugh maps
What we now know about logic minimization:
- Logically adjacent rows of a truth table can be merged into a single row containing a "don’t care" entry for one of the variables.
- Equivalently, a logically adjacent pair of terms in an equation can be merged into single term with one fewer variable.
- Potential simplifications can be hard to spot, and results are not unique.
And some things we wish we knew:
- How can we systematically find all possible simplifications?
- How can we know if an equation is in its simplest possible form?
We will answer these questions, at least for fairly simple systems, in this section.
The basic Karnaugh map.
The Karnaugh map is a graphical representation of a truth table. It consists of an array of cells, one for each row of the table, Figure 3.3.1
Each cell of the Karnaugh map represents one row of the truth table, and one possible combination of the input variables \(A\) and \(B\) in a logic equation. The cells are all logically adjacent: on the top row, \(A'B'\) is adjacent to \(A'B\text{,}\) and on the bottom row, \(AB'\) is adjacent to \(AB\text{.}\) In the left column, \(A'B'\) is adjacent to \(AB'\text{,}\) and in the right column, \(A'B\) is adjacent to \(AB\text{.}\) The important difference between the truth table and the Karnaugh map is that, in a Karmaugh map, logically adjacent cells are also physically adjacent, whereas in the truth table they may or or may not be. In the figure, for example, the second and fourth rows of the truth table are logically adjacent but not physically adjacent, but their cells in the Karnaugh map are both.
With the practice you’ve had so far, it isn’t hard to inspect the truth table and see that as long as \(B\) is TRUE, \(Y\)is TRUE, regardless of the value of \(A\text{.}\) Also, you know how to write the logic equation from the truth table and simplify it by Boolean algebra: \(A'B + AB = (A'+A)B = 1 \cdot B = B\text{.}\) Here is how the Karnaugh map reveals the same simplification:
- The truth table is transferred to the Karnaugh map by writing a 1 in each cell that corresponds to a row of the truth table for which \(Y=1\text{.}\) The unreduced logic equation is the OR of the terms represented by each cell. Here, \(Y = A'B + AB\text{.}\)
- Two cells are merged if they contain 1s and are physically adjacent. The two cells in the right column, holding 1s, \(A'B\) and \(AB\text{,}\) are merged into a larger group.
- The truth of the larger group depends on fewer variables. If \(B\) is TRUE, then one of these cells will be TRUE; thus, \(B\) suffices to define the group. The simplified expression for the larger group is \(B\text{,}\) and the simplified equation is \(Y=B\text{.}\)
The simplification is accomplished simply by spotting adjacent 1s on the map and collecting them into larger groups. No algebra required.
Recall an example from the previous section, the nonintuitive simplification \(A + A'B = A + B\text{.}\) It hinged on expanding \(A = A(B+B')\text{,}\) and then copying \(AB\) so it could be used in two combinations:
\begin{align*}
A + A'B \amp= A \cdot 1 + A'B = A(B+B') + A'B = AB + AB' + A'B\\
\amp= (AB + AB) + AB' + A'B = (AB + AB') + (AB + A'B)\\
\amp= A(B+B') + (A+A')B = A+B
\end{align*}
Figure 3.3.2 shows the same simplification, on a Karnaugh map. The term \(A\) is TRUE in the two cells in the bottom row. \(A'B\) is in the upper right corner, where it is visually apparent that it is adjacent to \(AB\) and can be grouped into a pair, using the cell for \(AB\) twice. \(B\) is TRUE for these two cells. If either \(A=1\) or \(B=1\text{,}\) then \(Y=1\text{.}\) The simplified expression \(Y=A+B\text{.}\) Much easier than the algebraic simplification.
Larger Karnaugh maps.
The Karnaugh map for a function of three variables is shown in Figure 3.3.3
First, look at the map on the left, which is a three-variable extension of the version in Figure 3.3.1. With three variables, there are \(2^3=8\) possible combinations of the input variables \(A, B, C\text{.}\) Consequently, there are eight cells in the Karnaugh map. They are organized as two rows of four. Each cell in the top row is logically adjacent to the cell below it in the bottom row. Moving across the top row, each cell is logically adjacent to the cell to either side in the row, and the cells at each end of the row are also logically adjacent. To accomplish this, the columns are ordered in a non-binary sequence: \(BC = 00, 01, 11, 10\text{.}\) This is important. If you set up a grid with the columns ordered in a binary sequence, \(BC = 00, 01, 10, 11\text{,}\) the second and third columns will not be logically adjacent, the first and fourth columns will not be logically adjacent, and you will obtain incorrect results.
The map on the right is drawn the way Karnaugh maps typically appear. With practice, it is no harder to use, and considerably faster to draw. But of course, you can always add the additional notation if it helps you.
The individual 1s in the figure represent the logic equation \(Y = AB'C + ABC + A'BC\text{,}\) which we earlier saw has the simplified form \(Y = AB + AC\text{.}\) Here we will use the Karnaugh map to accomplish the simplification without algebra. We look for sets of logically adjacent cells, and find two, shown in Figure 3.3.4.
The cell for \(ABC\) is used twice, just as the term \(ABC\) was used twice in the algebraic simplification. Each pair of cells is represented by a term made of only two variables: \(AB'C + ABC = AC\text{,}\) and \(A'BC + ABC = BC\text{.}\) The simplified equation is the OR of the two groups, \(y = AC + BC\text{.}\)
Checkpoint 3.3.5.
A four-variable Karnaugh map is a \(4 \times 4\) array of cells, as shown in Figure 3.3.6
Cells are logically adjacent to their north-south-east-west neighbors, including wrap-around at the edges. With the larger playing field, larger groups are possible: sixteen, eight, four, two, and one. The example in Figure 3.3.7 shows some of these.
- There is a clear group of four in the rightmost column, simplifying to \(CD'\text{.}\) Algebraically, \(A'B'CD' + A'BCD' + ABCD' + AB'CD' = (A'B' + A'B + AB + AB') \cdot CD' = CD'\text{.}\) Without using algebra, note that one of the four cells will be TRUE if \(CD'\) is TRUE, so \(CD'\) suffices to define the group.
- The cells for \(ABCD'\) and \(AB'CD'\) are reused, to expand the pair of \(ABCD\) and \(AB'CD\) into a group of four in the lower right corner, simplifying to \(AC\text{.}\)
- The cell in the lower right corner, \(AB'C'D'\text{,}\) is logically adjacent to the other corner \(AB'CD'\text{,}\) forming a wraparound group of two, \(AB'D'\text{.}\)
- Finally, the single cell \(A'BC'D\) is not adjacent to any other cells and cannot be simplified.
The simplified expression is the OR of these simpler terms, \(AC + CD' +AB'D' + A'BC'D\text{.}\)
Always try to reuse cells to create the largest possible groups, since large groups are represented by simple product terms.
Checkpoint 3.3.8.
Return again to the two-bit \(x > y\) circuit, Checkpoint 3.2.4. Transfer the truth table to a Karnaugh map and derive a simplified logic equation.
Solution.
The reduced logic equation is \(g = x_1y_1' + x_0y_1'y_0' + x_1x_0y_0'\text{.}\)
Checkpoint 3.3.9.
We are always seeking groupings of size 1, 2, 4, 8, or even 16, but never 3, 5, 7, 9, 10, etc. Why is this?
Solution.
For example, on a three-variable map, try to simplify \(AB'C' + AB'C + ABC\) into a single product term.
Checkpoint 3.3.10.
Why can’t two cells on a diagonal be grouped?
Answer.
They are not logically adjacent, but are separated by two bits, e.g., \(AB' + A'B\text{.}\)
Finding logically adjacent terms to combine is easier on a Karnaugh map---just look for physically adjacent cells. We now have a method for simplifying logic, but aren’t quite finished. In a complex situation, how can you be sure you’ve found the simplest set of groups, leading to the simplest logic?
