Online Encyclopedia
Gray code
A Gray code is a binary numeral system where two successive values differ in only one digit, originally designed to prevent spurious output from electromechanical switches.
Contents |
Motivation
Many devices indicate position by closing and opening switches. If that device uses natural binary codes, these two positions would be right next to each other:
... 011 100 ...
The problem with natural binary codes is that, with real (mechanical) switches, it is very unlikely that switches will change states exactly in synchrony. In the transition between the two states shown above, all three switches change state. In the brief period while all are changing, the switches will read some spurious position. Even without keybounce , the transition might look like 011 -- 001 -- 101 -- 100. When the switches appear to be in position 001, the observer cannot tell if that is the "real" position 001, or a transitional state between two other positions.
A Gray code solves this problem by changing only one switch at a time, so there is never any ambiguity of position:
0 000 1 001 2 011 3 010 4 110 5 111 6 101 7 100
Notice that state 7 can roll over to state 0 with only one switch change. This is called the "cyclic" property of a Gray code.
More formally, 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, reflecting the Hamming distance of 1 between adjacent 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 three-bit version of which is shown above.
Construction
The binary-reflected Gray code 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 base case, for n=1 bit, is the most basic Gray code, G = {0, 1}. The BRGC may also be constructed iteratively.
Here are the first few steps of the above-mentioned reflect-and-prepend method:
Programming algorithms
Here is one algorithm in pseudocode to convert natural binary codes to Gray code (encode):
Let B[n:0] the array of bits in the usual binary representation Let G[n:0] the array of bits in Gray code G[n]=B[n] for i=n-1 down to i=0 { G[i]=B[i+1] XOR B[i] }
or in C:
unsigned int grayencode(unsigned int g) { return(g^g>>1); }
Here is one pseudocode algorithm to convert Gray code to natural binary codes (decode):
B[n]=G[n] for i=n-1 down to i=0 { B[i]=B[i+1] XOR G[i] }
or in C:
unsigned int graydecode(unsigned int b) { b^=b>>1; b^=b>>2; b^=b>>4; b^=b>>8; return(b^(b>>16)); }
History and practical application
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) in 1953 by Frank Gray , a researcher at Bell Labs, who gave his name to the codes. The use of his eponymous codes that Gray was most interested in was to minimize the effect of error in the transmission of digital signals; his codes are still used today for this purpose, and others.
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.
The binary-reflected Gray code can also be used to serve as a solution guide for the Tower of Hanoi problem. A detailed method may be found here.
Due to the Hamming distance properties of Gray codes, they are sometimes used in Genetic Algotithms.
Special types of Gray codes
n-ary Gray code
There are many specialized types of Gray codes other than the binary-reflected Gray code. One such type of Gray code is the n-ary Gray code, also known as a non-Boolean Gray code. As the name implies, this type of Gray code uses non-Boolean values in its encodings. For example, a 3-ary (ternary) Gray code would use the values {0, 1, 2}. The (n,k)-Gray code is the n-ary Gray code with k digits [5]. The sequence of elements in the (3,2)-Gray code is: {00, 01, 02, 12, 11, 10, 20, 21, 22}. It is important to note that an (n,k)-Gray code with odd n lacks the cyclic property of a binary Gray code; it can be observed that in going from the last element in the sequence, 22, and wrapping around to the first element in the sequence, 00, two digits change, unlike in a binary Gray code, in which only one digit would change. An (n,k)-Gray code with even n, however, retains the cyclic property of the binary Gray code. The (n,k)-Gray code may be constructed recursively, as the BRGC, or may be constructed iteratively. A pseudocode algorithm to iteratively generate the (n,k)-Gray code based off the work of Dah-Jyu Guan [5] is presented:
int n[k+1]; // stores the maximum for each digit int g[k+1]; // stores the Gray code int u[k+1]; // stores +1 or -1 for each element int i, j; // initialize values for(i = 0; i <= k; i++) { g[i] = 0; u[i] = 1; n[i] = n; } // generate codes while(g[k] == 0) { i = 0; j = g[0] + u[0]; while((j >= n[i]) || (j < 0)) { u[i] = -u[i]; i++; j = g[i] + u[i]; } g[i] = j; } // g[i] now holds the (n,k)-Gray code
Beckett-Gray code
Another interesting type of Gray code is the Beckett-Gray code. The Beckett-Gray code is named after Samuel Beckett, a British playwright especially interested in symmetry. One of his plays, "Quad ", was divided into sixteen time periods. At the end of each time period, Beckett wished to have one of the four actors either entering or exiting the stage; he wished the play to begin and end with an empty stage; and he wished each subset of actors to appear on stage exactly once [4]. Clearly, this meant the actors on stage could be represented by a 4-bit binary Gray code. Beckett placed an additional restriction on the scripting, however: he wished the actors to enter and exit such that the actor who had been on stage the longest would always be the one to exit. The actors could then be represented by a first in, first out queue data structure, so that the first actor to exit when a dequeue is called for is always the first actor which was enqueued into the structure [4]. Beckett was unable to find a Beckett-Gray code for his play, and indeed, an exhaustive listing of all possible sequences reveals that no such code exists for n = 4. Computer scientists interested in the mathematics behind Beckett-Gray codes have found these codes very difficult to work with. It is today known that codes exist for n = {2, 5, 6} and they do not exist for n = {3, 4}. The search space for n = 6 is so large that it has not been exhaustively searched and several hundred thousand Beckett-Gray codes for n = 6 are known; the search space for n = 7 is so large that only a non-cyclic Beckett-Gray code (and therefore not technically of the kind originally proposed by Beckett) was found after several months of computing time [4].
Single-track Gray code
The single-track Gray code was originally defined by Hiltgen, Paterson and Brandestini. The STGC is a cyclical list of P unique binary encodings of length n such that two consecutive words differ in exactly one position, and when the list is examined as a P x n matrix, each column is a cyclic shift of the first column [3]. An n = 5 STGC is reproduced here:
10000 01000 00100 00010 00001 10100 01010 00101 10010 01001 11100 01110 00111 10011 11001 11110 01111 10111 11011 11101 11010 01101 10110 01011 10101 11000 01100 00110 00011 10001
Note that each column is a cyclic shift of the first column, and if each entry is read down each column and from the bottom entry of one column to the top of the next, only one bit changes [7]. The STGC is useful to measure the absolute angular position of a rotating wheel by encoding (optically) the code words on n concentric tracks [3]. The single-track nature is useful in the fabrication of these wheels, as only one track design is needed, thus reducing their cost; and the Gray code nature is useful, as only one track will change at any one time, so the uncertainty during a transition between two discrete states will only be plus or minus one degree of angular measurement the device is capable of resolving [1].
See also
References
- Alciatore and Histand. Introduction to Mechatronics and Measurement Systems. [1].
- Black, Paul E. Gray code. 25 Feb. 2004. NIST. [2].
- Etzion, Tuvi, and Moshe Schwartz. "The Structure of Single-Track Gray Codes." IEEE Transactions on Information Theory 45 (1999): 2383-2396. [3].
- F. Gray. Pulse code communication, March 17 1953. U.S. patent no. 2,632,058.
- Goddyn, Luis. MATH 343 Applied Discrete Math Supplementary Materials. 30 Nov. 1999. Dept. of Math., Simon Fraser U. [4].
- Guan, Dah-Jyu. "Generalized Gray Codes with Applications." Proc. Natl. Sci. Counc. Repub. Of China (A) 22 (1998): 841-848. [5].
- Savage, Carla. "A Survey of Combinatorial Gray Codes." Society of Industrial and Applied Mathematics Review 39 (1997): 605-629. [6].
- The Venn Diagram Page -- Symmetric Diagrams. Mar. 2001. The Electronic Journal of Combinatorics. [7].
External links
- NIST Dictionary of Algorithms and Data Structures: Gray code
- Numerical Recipes in C, section 20.2 describing Gray codes in detail (ISBN 0521431085)
- Hitch Hiker's Guide to Evolutionary Computation, Q21: What are Gray codes, and why are they used?, including C code to convert between binary and BRGC