Why gray code is an exclusive or of the bits in a binary code

Question

I understood the purpose of gray codes in a clear way. EE Times: Gray Code Fundamentals

But I am not able to conceptually understand why the gray code can be generated as below

G_i = B_i+1 ⊕ B_i , i = n − 1, . . . , 0, where B_n is taken as 0.

Could someone help me on this conceptually.

Answer 1

In standard binary, if you exclusive-or a number less than n**2 with n**2-1, then you effectively reverse the order of that count:

x   x^11
00  11
01  10
10  01
11  00

So, for a two-bit number, if we exclusive-or the bottom bit with the next bit:

x   x^(x>>1)
00  00
01  01
10  11
11  10

We are alternately reversing the order of the count for the bottom bit, depending on whether the bit above it is set or clear. This ensures that when bit 1 changes, bit 0 stays the same (where it would otherwise have wrapped around to zero and started counting up again).

For every bit that is added at the top of the counter, we need to repeat this reflection of the count of the bit below, to ensure that it doesn't become cleared as the new bit becomes set. The remaining bits follow in the same pattern, being reflected by the bit above them such that they count backwards rather than wrapping around.

Answer 2

When you look into Wikipedia, you will see that it is:

G0 = B0
Gi = Bi EXOR Gi-1

Does that make more sense? Check this for the Graycodes given in the pages you've read - you'll see it holds.

Would you like to see a proof of the above, or is looking at the examples enough?

Answer 3

I find Vovanium's answer really helpful to understand the formula that generates Gray Code sequence. The idea is that we want to generate a sequence where G(n+1) only changes one bit from G(n), i.e. G(n+1) xor G(n) only has 1 bit set. Vovanium's answer is partially copied below.

If you look at binary counting sequence, you note, that neighboring codes differ at several last bits (with no holes), so if you xor them, pattern of several trailing 1's appear. Also, when you shift numbers right, xors also will be shifted right: (A xor B)>>N == A>>N xor B>>N.

        N                    N>>1                  gray
 0000           .        0000           .      0000           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0001          .         0000          .       0001          .
   || >xor = 0011           | >xor = 0001           >xor = 0010
 0010           .        0001           .      0011           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0011         .          0001         .        0010         .
  ||| >xor = 0111          || >xor = 0011           >xor = 0100
 0100                    0010                  0110

Original Xor results and shifted results differ in single bit (i marked them by dot above). This means that if you xor them, you'll get pattern with 1 bit set. So,

(A xor B) xor (A>>1 xor B>>1) == (A xor A>>1) xor (B xor B>>1) == gray (A) xor gray (B)