P: 410

Karnaugh Maps
KMap Numbering Method  Part 1
The position at which each possible minterm* is located within the KMap 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 rowordered KMap, 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 eightcellwide 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 twocellwide 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 KMap 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 graycode 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 onebit difference from its neighbor, vertically or horizontally (the vertical relationship, other than at the dnds of rows, would be of no concern with graycodes). The way the map was generated assures this twoway relationship.
KM
[* If there are N binary variables, then there will be a total of 2^N possible SimpleSumofProducts (SSOP)combinations of these Nvariables, 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.]
