Main Page | See live article | Alphabetical index

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.

The algorithm to generate Gray code would then look like this:

 Let B[n:0] the array of bits in the usual binary representation
 Let G[n:0] the array of bits in gray code
   for i=n-1 down to i=0 {
     G[i]=G[i+1] XOR B[i]
Gray Decoding would be the same:
   for i=n-1 down to i=0 {
     B[i]=B[i+1] XOR G[i]

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.