Thread: Karnaugh Maps
View Single Post
Kenneth Mann
#4
Nov20-05, 05:37 PM
P: 410
Karnaugh Maps

K-Map Numbering Method - Part 1

The position at which each possible minterm* is located within the K-Map corresponds directly to the number which is assigned to that cell in the map, thus the location of each cell of the map must be selected so as to assure that the following is true: - - - From any cell within the map, to its adjacent (vertically or horizontally) neighbor cell - - -one and only one bit in the cell numbering may change. This numbering sequence is accomplished as follows.

Referring to figures 5 and 6, we build a Karnaugh Map in the following manner: First we start with a base, or root, cell. To this cell we assign the number "0". From here on, we add cells and assign their cell numbers by what may be likened to an 'unfolding' process. This process we can liken to that of continually producing a new group of cells exactly like the ones we already have, but positioned exactly on top of the one(s) we already have. Each cell of this new layer, then has the same value as the one directly beneath it, plus 2^M (where M is the number of the 'unfolding' operation, starting at "0"). Each 'unfolding' step, is then done from the boundary (axis) following the last presently existing cell in the map (horizontally or vertically).

For a row-ordered K-Map, we first generate the cells of the first row as is illustrated in figure 5. The number of 'unfolding' operations will depend upon how wide to make the map. (In the illustration, we perform three 'unfolding' operations, in order to produce an eight-cell-wide map.) Starting with the "zero" cell, we generate a new cell on top of it, and give it the value "1" (0 + 2^0 = 1). Then we unfold this out - - around the 'axis' (figure 5.b) following the "0" value cell, and now have a two-cell-wide map. Next, we repeat the process, generating two new cells atop the ones we have, and give these new cells the values (0 + 2^1 = 2) and (1 + 2^1 = 3). Then when we unfold these out (figure 5.c), we have the map cells "0", "1", "3" and "2". Finally, when we perform the process again (this time adding 2^2), we end up with the cells "0", "1", "3", "2", "6", "7", "5" and "4" (figure 5.d).

We then produce the remaining rows of our K-Map in the same manner, but by unfolding each new row around an axis beneath the row from which it is derived (figure 6). For example, row 2 is formed by generating it above row one, with each cell in row 2 having the same value as as the cell beneath it, plus 2^3 (figure 6.b). The same process is then repeated to generate the next pair of rows (figure 6.c)

What we now have, is a map like that of figure 7. If we trace adjacent cells through the map, we now get a number arrangement which looks essentially like that of the standard 'Reflecting Gray Code" numbering sequence. In this sequence, every sequential number has one and only one bit different from its sequential neighbor (predecessor or following number). To be sure, our map doesn't necessarily come from the standard reflecting gray-code sequence, but is simply dirived in much the same way, thus we end up with the same pattern.

What's more, all the cells of the map are arranged so that each has only a one-bit difference from its neighbor, vertically or horizontally (the vertical relationship, other than at the dnds of rows, would be of no concern with gray-codes). The way the map was generated assures this two-way relationship.


KM

[* If there are N binary variables, then there will be a total of 2^N possible Simple-Sum-of-Products (SSOP)combinations of these N-variables, where each of these 'terms' contains each variable, represented in either its normal or its complemented (not) form. Each or these 2^N possible terms is called a minterm. For example, if there are two variables A and B, then there are four possible minterms; A'B', AB', AB and A'B.]
Attached Files
File Type: pdf Figure 5.pdf (13.6 KB, 71 views)
File Type: pdf Figure 6.pdf (17.2 KB, 68 views)
File Type: pdf MapGrayCode.pdf (10.1 KB, 74 views)