Tuesday, 18 November 2014

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 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.)

No comments:

Post a Comment