courses:discrete_structures:spring_2013:assignment-graycodes

Gray Codes

Due 20 Feb 2013 at the start of class.

A Gray code cycle is a sequence of binary strings, where each string differs from the one before it in only one position, and the ending string differs from the starting string in only one position. One very common Gray code is the reflected binary code on $n$-bit binary strings, which we denote $\Gamma_n$ using the notation from Knuth, section 7.2.1.1 of volume 4a of The Art of Computer Programming). We define $\Gamma_n$ recursively as $$\Gamma_1=0,1;\quad \Gamma_{n+1}=0\Gamma_n,1\Gamma_n^R,$$ where $0\Gamma_n$ is the sequence found by taking each binary string in $\Gamma_n$ and prefixing it with 0, and $1\Gamma_n^R$ is the sequence found by reversing the order of the binary strings in $\Gamma_n$, then prefixing 1 to each string. For example, $\Gamma_2$ is the sequence

00
01
11
10

and $\Gamma_3$ is the sequence

000
001
011
010
110
111
101
100

Assignment

  1. What is $\Gamma_4$?
  2. Let $(\ldots)_2$ denote the binary (base 2) representation of a number (e.g., $5=(101)_2$), and let $\oplus$ be the binary XOR operation (i.e., $0\oplus 0 = 1\oplus 1 = 0$, $0\oplus 1 = 1\oplus 0=1$). Let $g:\mathbb{N}\to\mathbb{N}$ be a function with the following rule: if $b=(\ldotsb_3b_2b_1b_0)_2$, then $g(b)=(\ldotsa_3a_2a_1a_0)_2$, where $a_j = b_{j+1} \oplus b_j$. For example, $g(4)=g((0100)_2)=(110)_2$. In this case, $b_3b_2b_1b_0=0100$, so $$\begin{align*} a_0=b_1\oplus b_0=0\oplus 0=0\\ a_1=b_2\oplus b_1=1\oplus 0=1\\ a_2=b_3\oplus b_2=0\oplus 1=1, \end{align*}$$ so $g(4)=g((0100)_2)=(a_2a_1a_0)_2 = (110)_2$. In summary, to get $g(k)$, just XOR successive bits of the binary representation of $k$. Compute $g(4586)$. [Hint: $4586$ in binary is $1000111101010$]
  3. Prove that the Gray code $\Gamma_n$ is the sequence $g(0), g(1), g(2), \ldots, g(2^n-1)$.
  4. Use the fact that $\Gamma_n$ is the sequence $g(0), g(1), g(2), \ldots, g(2^n-1)$ to implement a program to calculate the Gray code $\Gamma_n$. Your program should use only a constant amount of memory. Your program should work from the command line, and should take a single parameter, $n$, and should print out the Gray code sequence $\Gamma_n$ with each binary string on a separate line. For example, a command-line session would look like:
    $ python gray.py 3
    000
    001
    011
    010
    110
    111
    101
    100

    I will test your program on a variety of inputs to test its validity (and I encourage you to do the same). Your program should come with only source code (no binaries).

To submit this assignment, turn the answers to the written questions in during class. To turn in the program, email me a zip file by the start of class which includes your program and a README text file that gives a command to compile your program (if needed) and run your program.

hello.py is a short example program in Python that reads values in from the command line and prints out a result. You might find this useful if you do the assignment in Python. Also, output.zip contains three different output examples.


Page Tools