Introduction to Gray Code

The Gray Code, dimension k, is the list of 2k bit strings of length k, where neighboring (including wrap-around) entries always have a distance of 1.

For example, consider G3, which is the dimension 3 gray code. The bit strings are length 3, and there are 23 = 8 values.

0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
The distance between two bit strings x=x0x1x2 and y=y0y1y2 is the sum of the xor (⊕) of the corresponding bits: Σ2i=0 (xi ⊕ yi).

So the distance between, e.g., 0 1 1 and 0 1 0 (neighboring codes) is (0 ⊕ 0) + (1 ⊕ 1) + (1 ⊕ 0) = 0 + 0 + 1 = 1.
The distance between 0 0 0 and 1 0 0 (again, neighbors) is (0 ⊕ 1) + (0 ⊕ 0) + (0 ⊕ 0) = 1 + 0 + 0 = 1.

Construction

A gray code of any dimension k can be constructed from the gray code of the dimension k-1. The construction algorithm is as follows:

Gray Codes for dimension 0 through 3