TAOCP 7.2.1.1 Exercise 67
Let $a_0, a_1, \ldots, a_{2^{n-1}-1}$ be the Gray binary code on $(n-1)$ bits from Section 7.
Section 7.2.1.1: Generating All n-Tuples
Exercise 67. [20] [20] Sometimes it is desirable to run through all n-bit binary strings by changing as many bits as possible from one step to the next, for example when testing a physical circuit for reliable behavior in worst-case conditions. Explain how to traverse all binary n-tuples in such a way that each step changes n or n −1 bits, alternately.
Verified: no
Solve time: 7m30s
Solution
Let $a_0, a_1, \ldots, a_{2^{n-1}-1}$ be the Gray binary code on $(n-1)$ bits from Section 7.2.1.1, so consecutive strings differ in exactly one bit, and every $(n-1)$-bit string appears exactly once. For each $k$, write $a_k = (a_k^{(1)}, \ldots, a_k^{(n-1)})$.
Define two $n$-bit strings from each $a_k$ by
$$ x_k = (0, a_k^{(1)}, \ldots, a_k^{(n-1)}), \qquad y_k = (1, \overline{a_k^{(1)}}, \ldots, \overline{a_k^{(n-1)}}), $$
where $\overline{a}$ denotes bit complement.
The proposed traversal is the sequence
$$ x_0, y_0, x_1, y_1, \ldots, x_{2^{n-1}-1}, y_{2^{n-1}-1}. $$
The sequence contains exactly $2 \cdot 2^{n-1} = 2^n$ distinct $n$-bit strings. Distinctness follows because the first coordinate of $x_k$ is always $0$ while the first coordinate of $y_k$ is always $1$, and the map $a_k \mapsto \overline{a_k}$ is a bijection on $(n-1)$-bit strings, so no collision occurs among the $x_k$ or among the $y_k$.
The Hamming distance between consecutive terms alternates as required. For fixed $k$, the distance between $x_k$ and $y_k$ is $n$, since the first bit differs and each of the remaining $n-1$ bits differs between $a_k$ and $\overline{a_k}$, contributing $n-1$ additional differences.
For the transition between $y_k$ and $x_{k+1}$, the first coordinate differs, contributing $1$. For the remaining $n-1$ coordinates, we compare $\overline{a_k}$ with $a_{k+1}$. Since $a_k$ and $a_{k+1}$ differ in exactly one position, the relation
$$ H(\overline{a_k}, a_{k+1}) = (n-1) - H(a_k, a_{k+1}) $$
holds, so $H(\overline{a_k}, a_{k+1}) = n-2$. Therefore the total distance is $1 + (n-2) = n-1$.
Thus every step from $x_k$ to $y_k$ changes exactly $n$ bits, and every step from $y_k$ to $x_{k+1}$ changes exactly $n-1$ bits. This yields a traversal of all binary $n$-tuples in which the number of bit changes alternates between $n$ and $n-1$ at successive steps.
This completes the construction. ∎