It might be a bit easier to work with K-Maps, if we explain a little bit just why they work. For this, I have attached a couple of template maps. One (Attachment 2) is laid out with the first variables (A & B) identifying
rows (the way success2be does it above), and the other (Attachment 1) is laid out with the first variables identifying the
columns of the map. Both methods will work, but I prefer The approach given in Attachment 1, because it reads out the way we are more accustomed --- so, this one is used to illustrate.
The map has both the binary number values for A, B, C & D given along the top and side, and the identification of the states of the Literals (A or A', B or B', etc.). The actual map is put together in the standard way.
The reason that the map is configured with the progression 1, 2, 4, 3, etc...., is because, in this way, as we move either vertically or horizontally from one "cell" of the map, to an adjacent cell, --- one and only one bit changes. (A Reflecting Gray-code arrangement). This means that when we take any cell and its adjacent cell, we will have
one literal (say N) for which the values N and N' will be the case. And, where we have NN', we know from the Boolean Postulates that the result of this is that the represented variable equals '1', and can be eliminated.
The attachments show which variable changes in any couple. In Attachment 1, for example, the indicators show which single variable changes as we cross any of the vertical or horizontal 'divider lines' between any two 'adjacent' cells. You can put in the binary values for the 'cell numbers' and see this.
From this we can state the following:
1) Call a "couple" any pair of adjacent cells on a map. (Take, for example cells '1' and '5' on attachment 1, or cells '14' and '15'.) {This holds for a map of any size, and is exclusive for a map of four variables or fewer. For larger maps, there may be couples that are not physically adjacent, but this is beyond the scope of what we are discussing here. Suffice it to say, any two adjacent cells form a couple.}
2) Couples consist of vertically or horizontally adjacent cells only. Diagonally adjacent cells cannot form couples.
3) Whenever a couple is formed one variable is eliminated from the term. That variable is the one that had a
change ("0" to "1", or "1" to "0").
4) Higher order couples can be formed by coupling adjacent lower order couples. Thus, two first-order couples, when coupled (adjacent) form a second-order couple (two variables are eliminated).
5) From the way that higher order couples are formed, every coupling must have 2^N terms (ie. 2, 4, 8, 16 ....). Furthermore, a coupling must be rectangular.
6) A K-Map is a closed entity. Therefore, the leftmost column is 'adjacent' to the rightmost column, and the top row is adjacent to the bottom row. Thus, couplings can occur across these.
[7) If the map cells are numbered, as are the ones that I have attached, then the numbers in the cells, of any coupling will differ by an integral power of two. This is unimportant at the elementary level, but if ordered maps of more than four variables are employed this can be a useful checking tool.]
8) The greatest minimization is obtained if a coupling of the greatest number of cells is taken. This is true even if there is an 'overlap' of the various terms.
I hope this has been of some help, Now to answer some of the concerns:
Originally Posted by success2be
But I'm missing C in the equation and obviously wrong.
|
Actually, the fact that C is missing is good. This implies that where you have A'D', this occurrs when there is C and when there is C', but then, that is all the time with respect to C, so you can drop it out, as "waht" says in the following:
Originally Posted by waht
you still could add 2 more terms A'C'D' + A'CD' but there is really no point.
|
Originally Posted by success2be
I had a guy at work who's a phd candidate for EE and CE and he insisted that the equation must have C.
|
Not so!
Originally Posted by success2be
He said looking at my K-map that I can wrap the entire row 2 but can't cancel out C and D. He's reasoning is that they're more than 2 bits apart. Only adjacent cells can be canceled.
|
Read number "6" above.
Originally Posted by success2be
When I told him that my original answer was correct based on you guys' response, he told me I had to work out the entire equation step by step and not use the K-map. That's like going back into the stone age.
|
The K-Map is a lot less prone to human error, and is totally reliable if used correctly.
KM
