Find the neighbors in Gray Code sequence

Question

I want to find a way to figure out what are the most closest neighbors in a Gray Code sequence.

For example I have 010110, and I need to figure out which are its neighbors.

I can apply the binary reflection algorithm from Wikipedia, I know. I did it and found 010010 and 010111, but what if I have 0101100101010 instead of 010110?

Answer 1

If you want find the neighbours of a Gray code, there are better methods than converting the Gray code to a regular binary representation, adding/subtracting $1$ and converting it back to a Gray code. We can use the properties described in The Gray Code by R. W. Doran. Let's take the first property from the paper:

Property P1: Adjacent words in the Gray code sequence differ in one bit position only.

That means that, in order to find a neighbour, you will only have to find the bit to switch in the sequence. The twelfth property from the paper gives us the position of the bit that has to be switched (the rightmost bit is at position $0$):

Property P12: When counting an n-bit Gray Code in direction d ($=0$ for up, $=1$ for down), the next bit s to be switched is given by:

• $ P(G) = d $ then $ s = 0 $
• $ P(G) = $ not $ d $ then s is such that $ G_{s-1} = 1 $ and $ G_i = 0, i > s-1 $

That means that, depending on the parity of the Gray code, the next bit to switch will either the lowest (rightmost) one, either the one left to the rightmost $1$ in the sequence. Lets take an example: $0111$ is the Gray code for $5$. If you switch the rightmost bit, you get $0110$ which is the Gray code for $4$. If you switch the bit which is at the left of the rightmost $1$ in the sequence, you get $0101$ which is the Gray code for $6$.

If your Gray code is even, switching the rightmost bit will give the Gray code corresponding to the next integer, otherwise it will give you the Gray code corresponding to the previous integer. However, in order to perform these simple switches, we need to know the parity of the Gray code. We can use the following porperty:

A Gray code sequence is even iff the number of $1$ in the sequence is even.

To sum up: to find the neighbours of a Gray code, switch either the rightmost bit or the bit left to the rightmost $1$ and check the parity to know whether you just got the next or the previous neighbour. It is easy to do by hand and can be faster than a conversion to and from a regular integer for a computer (it will depend on the algorithm used to compute the parity).

Answer 2

The specific code that Frank Gray called "reflected binary code" (1947 patent application, granted 1953) is now often labeled BRGC for "binary reflected Gray code" after him. [However such a code appears as early as 1878 with Baudot's work on telegraphy.]

A formula for calculating the binary pattern appearing in the $k$th position of the BRGC sequence, $k=1,..,2^n$, is given in the Wikipedia article and discussed in this StackOverflow Q&A: the nth gray code. Mathematically speaking, let $k$ be the entry we want and $g(k)$ the corresponding BRGC entry:

$$ g(k) = \lfloor (k-1)/2 \rfloor \text{ XOR } (k-1) $$

The minus 1 from $k$ is only to start the sequence with first element all zeros. If you are comfortable with 0-indexing, feel free to simplify.

It follows that many questions such as the one posed here (find neighboring entries) can be solved if an inverse to this formula is known, telling us in which BRGC position a specified binary pattern can be found. The Wikipedia article also supplies us with code for that operation, though it is less easily expressed in a single formula (but see Added below).

As a C-like looping routine:

unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num+1;
}

This differs from the Wikipedia snippet only in adding 1 to the return value, consistent with what we discuss above about 1-indexing vs. 0-indexing of the BRGC sequence.

That is, given a binary pattern g of width that fits in an unsigned integer, we can call the routine k = grayToBinary(g). The return value k or $k$ can then be incremented/decremented to produce the successor/predecessor BRGC entries by applying the formula previously cited.

Note that the code snippet does not reference the entry widths $n$ of the binary patterns. This is possible because the BRGC sequences of different widths agree on (conserve) common initial segments (an easy consequence of the recursive definition).

Added:

I implemented the coding (index to Gray code) formula and decoding (Gray code to index) routine above in a spreadsheet (to make sure I hadn't committed an obscure error), and they both worked.

We could write the decoding as a formula if only we had a symbol for accumulating bitwise exclusive-or in a manner like $\Sigma$ accumulates summation. For no particular reason other than it looks cool to me, I'll nominate $\Xi$ for this purpose. After all, bitwise exclusive-or on unsigned (nonnegative) integers is associate and commutative, so an iterated XOR makes as much sense as iterated sums or products. Then we could locate the index of bit pattern $m$ as follows:

$$ g^{-1}(m) = 1 + \operatorname{\Xi}\limits_{j=0}^{\lfloor \log_2 m \rfloor} \left\lfloor \frac{m}{2^j} \right\rfloor $$

Answer 3

In all Gray codes, successive values differ in only one bit. Here are two different (cyclic) Gray codes: $$000,001,011,010,110,111,101,100$$ and $$000,001,011,111,101,100,110,010$$ The first is the standard binary reflected Gray code. The Wikipedia article you link to describes a method to convert standard binary reflected Gray code representation of $n$ to natural binary representation of $n$, and also how to convert from natural binary representation of $n$ to standard binary reflected Gray code representation of $n$.

So, given Gray code 0101100101010 which is the standard binary reflected Gray code representation of some integer $n$ (you don't, as yet, know what $n$ is)

1. Convert the Gray code representation to natural binary representation using the method in the Wikipedia article. At this point, you can more easily find out the value of $n$, but knowledge that $n$ equals $1135$ (say) is not necessary for finding the neighbors.
2. Add and subtract $1$ to the natural binary representation of $n$ that you found in Step 1. You now have the natural binary representations of $n-1$ and $n+1$.
3. Convert the natural binary representations of $n-1$ and $n+1$ to standard binary reflected Gray code representations as described in the Wikipedia article. These are the neighbors of 0101100101010 in the standard binary reflected Gray code.