Need help with Knuth's proof for Gray Codes

Question

I am reading Knuth's "The Art of Computer Programming" Volume 4 Fascicle 2A.

Needless to say I am pretty poor in Mathematics and I need help understanding some of the proofs. If anyone has any suggestions on how to understand these problems please let me know.

I am on Page 3 Section 7.2.1.1-:

Another way to define the sequence $\Gamma_n = g(0),g(1),..g(2^n-1)$ is to give explicit formula for its individual elements. [...]

When $k=2^n+r$, where $0\leq r < 2^n$, relation (5) tells us that $g(k)$ is equal to $2^n+g(2^n-1-r)$. Therefore we can prove by induction on $n$ that the integer $k$ whose binary representation is $(\ldots b_2b_1b_0)_2$ has a Gray binary equivalent $g(k)$ with the representation $(\ldots a_2a_1a_0)_2$ where $$a_j = b_j \oplus b_{j+1}\quad\text{for $j\geq0$}$$

[...] by inverting the system of equations [we get]:$$b_j=a_j \oplus a_{j+1} \oplus a_{j+2} \oplus\cdots \quad\text{for $j\geq0$} $$

Okay now my questions are as follows-:

1. Why is $k=2^n+r$ ? What is $r$ ? If $k$ representts the nth term for which the Gray code is calculated then why is it $2^n+r$ ? Isn't that more than the number of possible combinations ?
2. Can someone tell me the induction proof that is done to get the formula for the Gray code from binary ? That is, what is the intuition behind the XOR ing two binary digits to get one gray digit ?
3. It says that if we invert the system of equations we get back the binary from the Gray Code, but what I don't understand is that only two binary digits are required to get one Gray Code digit, but how come when obtaining binary from Gray we have to XOR all digits of Gray Code ? How is that inverting the equations ?

Also if anyone has any advice on how make reading this book easy, please let me know.

Answer 1

A field is a set of numbers together with "addition" and "multiplication" operations ( also some rules must apply to how these operations behave, but we skip them here ). In the $\mathbb{Z}_2$ field of numbers, which only has 2 numbers: 0 and 1, we can write these operations with small "tables":

$$\begin{array}{|c|cc|}\hline+&0&1\\\hline0&0&1\\1&1&0\\\hline\end{array}\hspace{1cm}\begin{array}{|c|cc|}\hline\times&0&1\\\hline0&0&0\\1&0&1\\\hline\end{array}$$

If you investigate these tables, you realize they are the same as the logical XOR and AND operations (if you replace 1 with "true" and 0 with "false"). Since this is a field, which is "compatible" with linear algebra, we can build vectors and matrices and stuffing these things inside.

You can now view $a_j$ as being a discrete linear differential operator over the ${\mathbb Z}_2$ field. The inverse of a differential is an integral, and since "-" operator is the same operator as "+" in this particular field ( both correspond to "xor" ), the sum that would approximate the integral turns into a chain of "xor"s and the difference in the differentiator becomes a pairwise sum.

To clarify the differential and integral operator part of the explanation let us consider the field of real numbers, the matrix $\bf D$:

$${\bf D} = \left[\begin{array}{rrrrr}1&-1&0&0&0\\0&1&-1&0&0\\0&0&1&-1&0\\0&0&0&1&-1\\0&0&0&0&1\end{array}\right]$$ This matrix approximates a differential operator. Now, it's inverse:

$${\bf D}^{-1} = \left[\begin{array}{rrrrr}1&1&1&1&1\\0&1&1&1&1\\0&0&1&1&1\\0&0&0&1&1\\0&0&0&0&1\end{array}\right]$$

Is the integral (or at least the discrete counterpart, a cumulative sum!)

In the ${\mathbb Z}_2$ field the number $-1$ is simply the same as the number $1$. $1$ is it's own additive inverse.

If we stuff the $a_j$:s into a column vector $\bf a$ and the $b_j$:s into $\bf b$, we can write:

$${\bf a = Db} \Leftrightarrow {\bf D}^{-1}{\bf a = b}$$

Which are precisely the equations given on scalar form.

Answer 2

Consider $g$ as a map of binary digits from $\{b_i\}\mapsto \{a_i\}$. We need to prove Equation 1 \begin{equation} a_i = b_i \oplus b_{i+1} \end{equation} Knuth noted that if $g(k)$ indicates the map from binary to Gray code, and if $r$ is defined as $k \bmod 2^{n}$, we find Equation 2, that \begin{equation} g(k) = 2^n + g(2^n - 1 - r) \end{equation} We note that Equation 1 is true for $k=0$ then induce on the size of $k$, where $2^{j} \le k < 2^{j+1}$. Clearly equation Equation 1 is true for $j=0$. Suppose Equation 1 is true for all $j \le n-1$. We will show it is true for $j=n$.

Suppose $2^{n} \le k < 2^{n+1}$, and let $k=\{b_i\}$. We note that $b_n=1$.

Then $r=\{r_i\},$ where $$r_i = \left\{ \begin{array}{rcl} b_i &,& i < n \\ 0 &,& i \ge n \\ \end{array} \right. $$

Let $s=2^n-1-r$. Then $s=\{s_i\},$ where $$s_i = \left\{ \begin{array}{rcl} b_i \oplus 1 &,& i < n \\ 0 &,& i \ge n \\ \end{array} \right. $$

Plugging $s$ into Equation 2, we have for $i<n-1$, $$ \begin{array}{rcl} a_i &=& s_i \oplus s_{i+1} \\ &=& (b_i \oplus 1) \oplus (b_{i+1} \oplus 1) \\ &=& b_i \oplus b_{i+1} \oplus 1\oplus 1 \\ &=& b_i \oplus b_{i+1}, \\ \end{array} $$ which is of the desired form.

For $i=n-1$, we observe that $s_n=0, b_n=1$ implies $$ s_n = b_n \oplus 1.$$ Then $$ \begin{array}{rcl} a_{n-1} &=& s_{n-1} \oplus s_n\\ a_{n-1} &=& (b_{n-1} \oplus 1) \oplus (b_n \oplus 1)\\ &=& b_{n-1} \oplus b_{n} \\ \end{array} $$

Thus, for $i=n$, we have from Equation 2 $$ \begin{array}{rcl} a_{n}&=&b_{n} \\ 0&=&b_{n+1} \\ a_{n} &=& b_{n} \oplus b_{n+1}.\\ \end{array} $$
For $i>n$, Equation 1 is trivially true. This completes the proof of the first direction.