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 0The 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.
G0 = { }