Gray code and K-map adjacency
exam standardwhy K-map columns are ordered strangely
Answer
00 01 11 10
Why this example is worth doing
The K-map axis labels are a Gray sequence, and that is the entire reason the map works: neighbouring cells differ in one variable, so a pair of adjacent 1s always corresponds to a term where that variable cancels. Students who assume the labels are in binary counting order and reorder them destroy the property. This entry is the bridge between the Numbers section and the Boolean section, and it links both ways.
Try your own input in the Gray code. Convert binary to reflected Gray code and back, and build the sequence by reflection.
How the answer is reached
2-bit binary reflected Gray code
L1 = [0, 1]. For each extra bit, write the list, write it reversed below the mirror line, then prefix 0 to the top half and 1 to the bottom half.
| bits | sequence |
|---|---|
| 1 | 0, 1 |
| 2 | 00, 01, 11, 10 |
Consecutive codewords differ in exactly one bit, and so do the last and the first: the code is cyclic.
This is the binary reflected Gray code. It is one Gray code among many: any single-bit-change ordering of the codewords is a Gray code, and other constructions give different tables.
Source: Frank Gray, US Patent 2,632,058, "Pulse Code Communication" (filed 1947, granted 1953)