Gray Code - Constructing An n-bit Gray Code

Constructing An n-bit Gray Code

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. For example, generating the n = 3 list from the n = 2 list:

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+1 from G_n makes the following properties of the standard reflecting code clear:

• G_n is a permutation of the numbers 0, ..., 2n−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.)

These characteristics suggest a simple and fast method of translating a binary value into the corresponding Gray code. Each bit is inverted if the next higher bit of the input value is set to one. This can be performed in parallel by a bit-shift and exclusive-or operation if they are available: the nth Gray code is obtained by computing

A similar method can be used to perform the reverse translation, but the computation of each bit depends on the computed value of the next higher bit so it cannot be performed in parallel. Assuming is the th gray-coded bit ( being the most significant bit), and is the th binary-coded bit ( being the most-significant bit), the reverse translation can be given recursively:, and . Alternatively, decoding a Gray code into a binary number can be described as a prefix sum of the bits in the Gray code, where each individual summation operation in the prefix sum is performed modulo two.

To construct the binary-reflected Gray code iteratively, start with the code 0, and at step i find the bit position of the least significant '1' in the binary representation of i - flip the bit at that position in the previous code to get the next code. The bit positions start 0, 1, 0, 2, 0, 1, 0, 3, ... (sequence A007814 in OEIS). See find first set for efficient algorithms to compute these values.