Gray code

Suppose you want to list the numbers from 0 to N in such a way that only one bit at a time changes between consecutive numbers. It’s not clear that this is even possible, but in fact it’s easy using Gray code, a method named after Frank Gray.

To convert an integer to its Gray code, take the XOR of the number with the number shifted right by 1.

    def gray(n): return n ^ n >> 1

Here’s a little Python code to demonstrate this.

    for i in range(8): print(format(gray(i), '03b'))

produces

    000
    001
    011
    010
    110
    111
    101
    100

Note that the numbers from 0 to 7 appear once, and each differs in exactly one bit from the numbers immediately above and below.

Let’s visualize the bits in Gray code with black squares for 1s and white squares for 0s.

The code that produced the plot is very brief.

    N = 4
    M = 2**N
    for i in range(N):
        for j in range(M):
            if gray(j) & 1<<i: # ith bit set
                plt.fill_between([j, j+1], i, i+1, color="k")
    plt.axes().set_aspect(1)
    plt.ylabel("Gray code bit")

The bits are numbered from least significant to most significant, starting with 1.

If you want to see the sequence carried out further, increase N. If you do, you may want to comment out the line that sets the aspect ratio to be square because otherwise your plot will be much longer than tall.

Note that the Gray code of 2n-1 is 2n-1, i.e. it only has one bit set. So if you were to wrap the sequence around, making a cylinder, you’d only change one bit at a time while going around the cylinder.

This could make a simple classroom activity. Students could reproduce the plot above by filling in squares on graph paper, then cut out the rectangle and tape the ends together.

See the next post for how to compute the inverse Gray code.

Related posts

3 thoughts on “Gray code

  1. Jakub Narębski

    If one does not remember the equation for Gray code, it is quite easy to reconstruct (if you know that it exists) recursively, starting from trivial 1-bit code: take Grey code sequence for 2^{n-1}, reverse it, then extend original sequence with 0 most significant bit, and the reversed sequence with 1 in most significant bit position.

    0

    1

    00
    01

    11
    10

    000
    001
    011
    010

    010
    111
    101
    100

  2. Can I suggest replacing

    plt.fill_between([j, j+1], i, i+1, color=”k”)

    with

    plt.fill_between([j, j+1], i-0.5, i+1-0.5, color=”k”)

    The edges of the blocks in that figure fall right on the tick marks along the x-axis, making it hard to tell if a bit is set or not for a particular value. And if that isn’t ironic I don’t know what is.

Leave a Reply

Your email address will not be published. Required fields are marked *