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. The code was designed by Bell Labs researcher Frank Gray and patented in 1953.
| 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:
Dec Gray Binary 0 000 000 1 001 001 2 011 010 3 010 011 4 110 100 5 111 101 6 101 110 7 100 111
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. A good way to remember gray coding is by being aware that the least significant bit follows a repetitive pattern of 2. That is 11, 00, 11 etc. and the second digit follows a pattern of fours.
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}. Note that the base case can also be thought of as a single zero-bit Gray code (n=0, G = { " " }) which is made into the one-bit code by the recursive process, as demonstrated in the Haskell example below.
The BRGC may also be constructed iteratively.
Here are the first few steps of the above-mentioned reflect-and-prepend method:
Missing image
Gray_code_reflect.png
Image:Gray_code_reflect.png
Programming algorithms
Here is one algorithm to generate an array of Gray codes to a particular depth in Perl using the reflect-and-prepend method:
my $depth = 16; # generate 16 Gray codes, 4 bits wide each
my @gray_codes = ( '0', '1' );
while(scalar(@gray_codes)<$depth)
{
my @forward_half=map{'0'.$_} @gray_codes;
my @reverse_half=map{'1'.$_} reverse(@gray_codes);
@gray_codes=(@forward_half,@reverse_half);
}
Here is another algorithm to generate a list of Gray codes to any given depth in Haskell, also using the reflect-and-prepend method:
genList :: Int -> [[Char]]
-- Generates 2^n codes, n bits wide each
genList 0 = [[]]
genList n = (map ((:)'0') (genList (n-1))) ++
(map ((:)'1') (reverse (genList (n-1))))
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
Encoder_disc.png
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. The Gray code is sometimes incorrectly attributed to Elisha Gray.
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 (http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html#tower).
Due to the Hamming distance properties of Gray codes, they are sometimes used in Genetic Algorithms. Gray codes are also used in labelling the axes of Karnaugh maps.
When Gray codes are used in computers to address program memory, the computer uses less power because fewer address lines change as the program counter advances.
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 [6] 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, an Irish 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] (http://mechatronics.mech.northwestern.edu/mechatronics/design_ref/sensors/encoders.html).
- Black, Paul E. Gray code. 25 Feb. 2004. NIST. [2] (http://www.nist.gov/dads/HTML/graycode.html).
- Etzion, Tuvi, and Moshe Schwartz. "The Structure of Single-Track Gray Codes." IEEE Transactions on Information Theory 45 (1999): 2383-2396. [3] (http://www.cs.technion.ac.il/~etzion/PUB/Gray2.pdf).
- 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] (http://www.math.sfu.ca/~goddyn/Courses/343/supMaterials.pdf).
- Guan, Dah-Jyu. "Generalized Gray Codes with Applications." Proc. Natl. Sci. Counc. Repub. Of China (A) 22 (1998): 841-848. [5] (http://nr.stic.gov.tw/ejournal/ProceedingA/v22n6/841-848.pdf).
- Knuth, Donald E. "Generating all n-tuples." The Art of Computer Programming, Volume 4A: Enumeration and Backtracking, pre-fascicle 2a, October 15, 2004. http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz
- Savage, Carla. "A Survey of Combinatorial Gray Codes." Society of Industrial and Applied Mathematics Review 39 (1997): 605-629. [6] (http://epubs.siam.org/sam-bin/getfile/SIREV/articles/29527.pdf).
- The Venn Diagram Page -- Symmetric Diagrams. Mar. 2001. The Electronic Journal of Combinatorics. [7] (http://www.combinatorics.org/Surveys/ds5/VennSymmEJC.html).
External links
- NIST Dictionary of Algorithms and Data Structures: Gray code (http://www.nist.gov/dads/HTML/graycode.html)
- Numerical Recipes in C, section 20.2 (http://lib-www.lanl.gov/numerical/bookcpdf/c20-2.pdf) describing Gray codes in detail (ISBN 0521431085)
- Hitch Hiker's Guide to Evolutionary Computation, Q21: What are Gray codes, and why are they used? (http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/www/Q21.htm), including C code to convert between binary and BRGC
- Subsets or Combinations (http://www.theory.cs.uvic.ca/~cos/gen/comb.html) Can generate BRGC stringsde:Gray-Code