k map 3
Larger 4-variable Karnaugh maps
Knowing how to generate Gray code should allow us to build larger maps. Actually, all we need to do is look at the left to right sequence across the top
of the 3-variable map, and copy it down the left side of the 4-variable map. See below.
The following four variable Karnaugh maps illustrate reduction of Boolean expressions too tedious for Boolean algebra. Reductions could be done with
Boolean algebra. However, the Karnaugh map is faster and easier, especially if there are many logic reductions to do.
The above Boolean expression has seven product terms. They are mapped top to bottom and left to right on the K-map above. For example, the first P-term
A’B’CD is first row 3rd cell, corresponding to map location A=0, B=0, C=1, D=1. The other product terms are placed in a similar manner.
Encircling the largest groups possible, two groups of four are shown above. The dashed horizontal group corresponds the the simplified product term
AB. The vertical group corresponds to Boolean CD. Since there are two groups, there will be two product terms in the Sum-Of-Products result of
Out=AB+CD.
Fold up the corners of the map below like it is a napkin to make the four cells physically adjacent.
The four cells above are a group of four because they all have the Boolean variables B’ and D’ in common. In other words, B=0 for the
four cells, and D=0 for the four cells. The other variables (A, B) are 0 in some cases, 1 in other cases with respect to the
four corner cells. Thus, these variables (A, B) are not involved with this group of four. This single group comes out of the map as one product term
for the simplified result: Out=B’C’
For the K-map below, roll the top and bottom edges into a cylinder forming eight adjacent cells.
The above group of eight has one Boolean variable in common: B=0. Therefore, the one group of eight is covered by one p-term: B’. The original
eight term Boolean expression simplifies to Out=B’
The Boolean expression below has nine p-terms, three of which have three Booleans instead of four. The difference is that while four Boolean variable
product terms cover one cell, the three Boolean p-terms cover a pair of cells each.
The six product terms of four Boolean variables map in the usual manner above as single cells. The three Boolean variable terms (three each) map as cell
pairs, which is shown above. Note that we are mapping p-terms into the K-map, not pulling them out at this point.
For the simplification, we form two groups of eight. Cells in the corners are shared with both groups. This is fine. In fact, this leads to a better
solution than forming a group of eight and a group of four without sharing any cells. Final Solution is Out=B’+D’
Below we map the unsimplified Boolean expression to the Karnaugh map.
Above, three of the cells form into a groups of two cells. A fourth cell cannot be combined with anything, which often happens in “real world” problems. In
this case, the Boolean p-term ABCD is unchanged in the simplification process. Result: Out= B’C’D’+A’B’D’+ABCD
Often times there is more than one minimum cost solution to a simplification problem. Such is the case illustrated below.
Both results above have four product terms of three Boolean variable each. Both are equally valid minimal cost solutions. The difference in the final
solution is due to how the cells are grouped as shown above. A minimal cost solution is a valid logic design with the minimum number of gates with the
minimum number of inputs.
Below we map the unsimplified Boolean equation as usual and form a group of four as a first simplification step. It may not be obvious how to pick up the
remaining cells.
Pick up three more cells in a group of four, center above. There are still two cells remaining. the minimal cost method to pick up those is to group them
with neighboring cells as groups of four as at above right.
On a cautionary note, do not attempt to form groups of three. Groupings must be powers of 2, that is, 1, 2, 4, 8 …
Below we have another example of two possible minimal cost solutions. Start by forming a couple of groups of four after mapping the cells.
The two solutions depend on whether the single remaining cell is grouped with the first or the second group of four as a group of two cells. That cell
either comes out as either ABC’ or ABD, your choice. Either way, this cell is covered by either Boolean product term. Final results are shown
above.
Below we have an example of a simplification using the Karnaugh map at left or Boolean algebra at right. Plot C’