Gray code Sequence generation

Constructing an n-bit Gray code[edit]

The first few steps of the reflect-and-prefix method.

4-bit Gray code permutation

The binary-reflected Gray code list for n bits can be generated recursively from the list for n−1 bits by reflecting the list (i.e. listing the entries in reverse order), concatenating the original list with the reversed list, prefixing the entries in the original list with a binary 0, and then prefixing the entries in the reflected list with a binary 1.^[6] For example, generating the n = 3 list from the n = 2 list:

2-bit list:	00, 01, 11, 10
Reflected:		10, 11, 01, 00
Prefix old entries with 0:	000, 001, 011, 010,
Prefix new entries with 1:		110, 111, 101, 100
Concatenated:	000, 001, 011, 010,	110, 111, 101, 100

The one-bit Gray code is G₁ = (0, 1). This can be thought of as built recursively as above from a zero-bit Gray code G₀ = { Λ } consisting of a single entry of zero length. This iterative process of generating G_n+1from G_n makes the following properties of the standard reflecting code clear:

• G_n is a permutation of the numbers 0, ..., 2ⁿ−1. (Each number appears exactly once in the list.)
• G_n is embedded as the first half of G_n+1.
• Therefore the coding is stable, in the sense that once a binary number appears in G_n it appears in the same position in all longer lists; so it makes sense to talk about the reflective Gray code value of a number: G(m) = the m-th reflecting Gray code, counting from 0.
• Each entry in G_n differs by only one bit from the previous entry. (The Hamming distance is 1.)
• The last entry in G_n differs by only one bit from the first entry. (The code is cyclic.)