## Constructing an n-bit Gray code

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 G1 = (0, 1). This can be thought of as built recursively as above from a zero-bit Gray code G0 = { Λ } consisting of a single entry of zero length. This iterative process of generating Gn+1from Gn makes the following properties of the standard reflecting code clear:
• Gn is a permutation of the numbers 0, ..., 2n−1. (Each number appears exactly once in the list.)
• Gn is embedded as the first half of Gn+1.
• Therefore the coding is stable, in the sense that once a binary number appears in Gn 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 Gn differs by only one bit from the previous entry. (The Hamming distance is 1.)
• The last entry in Gn differs by only one bit from the first entry. (The code is cyclic.)