Gray code

A Gray code is a code assigning to each of a contiguous set of integers, or to each member of a circular list, a word of symbols such that each two adjacent code words differ by one symbol. These codes are also known as single-distance codes. There can be more than one Gray code for a given word length, but the term was first applied to a particular binary code for the non-negative integers, the binary-reflected Gray code or BRGC, the four-bit version of which is as follows.

  0 0000
  1 0001
  2 0011
  3 0010
  4 0110
  5 0111
  6 0101
  7 0100
  8 1100
  9 1101
 10 1111
 11 1110
 12 1010
 13 1011
 14 1001
 15 1000

The BRGC for n bits can be generated recursively by prefixing a binary 0 to the Gray code for n-1 bits, then prefixing a binary 1 to the reflected (i.e. listed in reverse order) Gray code for n-1 bits.

Gray codes (not so named) were applied to mathematical puzzles before they became known to engineers. The French engineer Émile Baudot[?] used Gray codes in telegraphy in 1878. He received the French Legion of Honor medal for his work.

A vacuum tube using Gray encoding was patented (see below) by Frank Gray, a researcher at Bell Labs, who gave his name to the codes.

Gray codes are used in angle-measuring devices in preference to straightforward binary encoding. This avoids the possibility that, when several bits change in the binary representation of an angle, a misread could result from some of the bits changing before others. This application benefits from the cyclic nature of Gray codes, because the first and last values of the sequence differ by only one bit.

References

• F. Gray. Pulse code communication, March 17, 1953. U.S. patent no. 2,632,058.