Gray Codes

Recently I was thinking about Gray codes (http://en.wikipedia.org/wiki/Gray_code).

Gray codes are, effectively, a way to count from 0 to (2ⁿ-1) on an n-bit counter while only flipping 1 bit at a time. Most simply, they are mappings of the form f : ℤ_(2ⁿ) → ℤ_(2ⁿ) such that for an k ∈ ℤ_(2ⁿ), f(k) and f(k+1) differ by exactly 1 bit.

These have a variety of uses, for instance, in robotics one can make an n-bit encoder wheel such that a smooth rotation of the wheel only changes one bit at a time, avoiding ambiguities when multiple detectors change their state at the same angle and give wildly inconclusive readings : see https://www.google.com/search?q=gray+code+encoder+wheel&safe=off&source=lnms&tbm=isch.
More examples can be found on wikipedia
The context in which they have come up the most often in my life is when thinking about how to enumerate all possible 2ⁿ settings on an n-bit dip switch (http://en.wikipedia.org/wiki/DIP_switch). I don't like having to flip k switches to have to go from the setting corresponding to (2^k-1) to 2^k for every integer k ≤ n, but I would also like to be able to compute which bit to flip next without having to expend a lot of mental effort. I recently came up with a trick for this. I am likely not the first person to come up with this trick, but I couldn't find it written up anywhere else, so I am blogging about it

Method for finding the next bitstring in a Gray Code

To iterate through an n-bit Gray code do:
Starting at 0, repeat the following steps

1. On every even iteration (we number our iterations starting at 0), flip the rightmost bit of the current number to get the next number
2. On every odd iteration, find the rightmost 1 bit (the rightmost bit that is set to 1) in the current number. Flip the bit to the left of that to get the next number. If there is no bit to the left (if the current number is 2^(n-1)) flip the remaining 1 to get back to 0
.

If you get lost, simply count the number of 1s in the current number. If it is odd, you are on step 2. If it is even, you are on step 1.
Reversing the order of the steps traverses the Gray code in reverse order.

Background on "reflected binary Gray codes"

One of the earliest examples of a Gray code is what seems to be called a "reflected binary Gray code".
Here is how it works :
We will construct it on n bits recursively as a sequence of 2ⁿ bitstrings each of n bits. The kth bitstring in the sequence will be the number mapped to by k.

1. The reflected binary Gray code on 1 bit is just the sequence [0, 1].
2. To get the reflected binary Gray code on n bits, compute the code on (n-1) bits, add a leading 0 to each bitstring, then compute the code on (n-1) bits in reverse order, adding a leading 1 to each bitstring. Concatenate the resulting sequences (putting the "reflected" (or reversed) sequence after the forward sequence)

This yields a Gray code because : (we induct on the number of bits in the code)

• Each n-bit number is included once in the n-bit code. Inductively the rightmost (n-1) bits of this number must occur in the code on (n-1) bits. Either a given number starts with a leading 1, putting it in the second half of the sequence, or it starts with a leading 0, putting it in the first half of the sequence.
• Each two consecutive numbers in the n-bit code differ by one bit. Either their leading (leftmost) digits are the same, in which case they differ by 1 bit in their rightmost (n-1) bits (by induction), or their leading (leftmost) digits differ, in which case the bitstrings differ by 1 bit (by construction).

It is well-known that translating from the kth bitstring in this form of Gray code to the integer k can be done by recognizing that the ith bit of the number k is equal to the xor (sum modulo 2) of the leftmost n-i bits (assuming the rightmost bit is bit 0) of the kth bitstring in the Gray Code. TODO : replicate proof(s) here : Proof via matching to above construction, and proof by showing this to be a bijection, and showing that succ only filps one bit at a time

Proof that the algorithm presented here works

Reversing the order of operations reverses the order of traversal

Because each operation is just a "flip" (addition modulo 2) of a bit, each operation is it's own inverse. Since there is one unique "rightmost bit set to 1" in any number, repeating the two steps in reverse order will apply the inverses to the last sequence of steps required to get to the current number, which should reverse the iteration. ∎

The algorithm described at the top of this post ("Method for finding the next bitstring in a Gray Code") replicates the "reflected binary Gray code" described above.

Assume this is true for m-bit Gray codes for any m < n. Show for n by induction.

• The first 2^(n-1) steps are identical to the steps in the case for (n-1) bits. These match the first 2^(n-1) steps of the reflected binary Gray code (by induction).
• After this we are left with a single bit set to 1 in the next-to-leftmost bit. Since we've taken an odd number of steps, the next step is to flip the leftmost bit to 1. From here on, we are replicating the case for (n-1) bits, but in reverse (see above) and with the leftmost bit set to 1.

Proof by XOR

You can also prove this using the XOR fact stated in the section on reflected binary Gray codes. Incrementing a regular binary number involves either

• If the rightmost bit is 0, flip it to 1. In the Graycode version, this corresponds to "If there are an even number of 1 bits, flip the rightmost bit".
• Otherwise (if the rightmost bit of the number is 1) flip the rightmost 0 to 1, and flip all 1s to the right of it to 0 (i.e. ripple-carry). In the Graycode version, this corresponds to "If there are an odd number of 1 bits, flip the bit 1 to the left of the rightmost 1."

Example

Start with

0 0 1 0 1 1 0

Since there are an odd number of 1s, we are at the "odd" step of the iteration.

So we find the rightmost 1 bit.

0 0 1 0 1 1 0
          ^

find the bit 1 to the left of it

0 0 1 0 1 1 0
        ^

and flip that

0 0 1 0 0 1 0

Then we flip the rightmost bit (even iteration).

0 0 1 0 0 1 1

Now find the rightmost 1 bit.

0 0 1 0 0 1 1
            ^

and flip the bit 1 to the left of it.

0 0 1 0 0 0 1

Then we flip the rightmost bit again.

0 0 1 0 0 0 0

and so on.