TAOCP 7.2.1.1 Exercise 17

Section 7.2.1.1: Generating All n-Tuples

Exercise 17. [20] [20] A well-known construction called the Karnaugh map [M. Karnaugh, Amer. Inst. Elect. Eng. Trans. 72, part I (1953), 593–599] uses Gray binary code in two dimensions to display all 4-bit numbers in a 4 × 4 torus: 0000 0001 0011 0010 0100 0101 0111 0110 1100 1101 1111 1110 1000 1001 1011 1010 (The entries of a torus “wrap around” at the left and right and also at the top and bottom, just as if they were tiles, replicated infinitely often in a plane.) Show that, similarly, all 6-bit numbers can be arranged in an 8×8 torus so that only one coordinate position changes when we move north, south, east, or west from any point.

Verified: yes
Solve time: 1m39s

Solution

Let $\Gamma_3 = g(0), g(1), \dots, g(7)$ denote the 3-bit Gray binary code from Section 7.2.1.1, where successive elements differ in exactly one bit and where the cyclic property holds that $g(7)$ and $g(0)$ also differ in exactly one bit, since $\Gamma_3$ is obtained from the reflected construction (5).

Define an $8 \times 8$ array indexed by $(r,c)$ with $0 \le r,c \le 7$. Assign to each cell the 6-bit string

$$ A(r,c) = g(r), g(c), $$

where concatenation is taken in the sense of bit strings, so the first three bits encode the row index in Gray code and the last three bits encode the column index in Gray code.

Consider two horizontally adjacent cells $(r,c)$ and $(r,c+1)$, where addition is modulo $8$ on the torus. The labels are

$$ A(r,c) = g(r), g(c), \quad A(r,c+1) = g(r), g(c+1). $$

By the defining property of $\Gamma_3$, the strings $g(c)$ and $g(c+1)$ differ in exactly one bit, including the case $c=7$ and $c+1 \equiv 0 \pmod 8$. The first three bits $g(r)$ remain unchanged, so the full 6-bit labels differ in exactly one coordinate position.

Consider two vertically adjacent cells $(r,c)$ and $(r+1,c)$, again with addition modulo $8$. Their labels are

$$ A(r,c) = g(r), g(c), \quad A(r+1,c) = g(r+1), g(c). $$

The strings $g(r)$ and $g(r+1)$ differ in exactly one bit, including the wraparound pair $g(7)$ and $g(0)$, while the last three bits $g(c)$ remain fixed. Hence the full labels differ in exactly one coordinate position.

Both horizontal and vertical adjacency preserve the property that exactly one bit changes. Since each vertex of the torus has exactly four neighbors given by $(r \pm 1, c)$ and $(r, c \pm 1)$ modulo $8$, every move north, south, east, or west changes exactly one bit of the associated 6-bit number.

The construction assigns all $2^6 = 64$ distinct 6-bit strings, since $\Gamma_3$ lists all 3-bit strings exactly once and the Cartesian product of two such lists produces all pairs $(g(r), g(c))$ exactly once.

This completes the proof. ∎