Gray code
From Free net encyclopedia
|
A Gray code is a binary numeral system where two successive values differ in only one digit.
Gray codes were 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. If the output feeds into a sequential system (possibly via combinatorial logic) then the sequential system may store a false value.
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}. (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:
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) {
unsigned int output = b;
for (unsigned int shift = 1; shift <= sizeof(unsigned int)*8; shift++) {
output ^= (b >> shift);
}
return output;
}
or in Perl:
use POSIX qw(floor);
sub gray_decode {
my $num = shift;
my $out = $num;
return 0 if ($num < 1);
my $bits = floor(log($num) / log(2));
foreach my $bit (1 .. $bits) {
$out ^= ($num >> $bit);
}
return $out;
}
History and practical application
Image: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. It also forms a Hamiltonian cycle on a hypercube, where each bit is seen as one dimension.
Due to the Hamming distance properties of Gray codes, they are sometimes used in Genetic Algorithms. They are very useful in this field, since mutations in the code allow for mostly incremental changes, but occasionally a single bit-change can cause a big leap and lead to new properties.
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
In practice, a "Gray code" almost always refers to a binary-reflected Gray code. However, mathematicians have discovered other kinds of Gray codes. Like BRGCs, each consists of a lists of words, where each word differs from the next in only one digit (each word has a Hamming distance of 1 from the next word).
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 <ref>Template:Cite journal</ref>. 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 on 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 <ref name=goddyn>Template:Cite web</ref>. 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 <ref name=goddyn />. 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 <ref name=goddyn />.
Snake-in-the-box codes
The snake-in-the-box problem is a problem in mathematics and computer science that deals with finding the longest-possible constrained path that can be formed by following the edges of a multi-dimensional hypercube. This problem was first described by W. H. Kautz in the late 1950's. Snake-in-the-box codes, or snakes, are the node or transition sequences of constrained open paths through an n-dimensional hypercube. Coil-in-the-box codes, or coils, are the node or transition sequences of constrained closed paths, or cycles, through an n-dimensional hypercube. Snakes and coils have many applications in electrical engineering, coding theory, and computer network topologies. Generally, the longer the snake or coil for a given dimension, the more useful it is in these applications.
Single-track Gray code
Yet another kind of gray code is the single-track Gray code.
To get high angular accuracy with a BRGC, one needs lots of tracks. If one wants at least 1 degree accuracy (at least 360 distinct positions per revolution) with standard BRGC, it requires at least 9 tracks. (That actually gives 512 distinct positions).
If the manufacturer moves a contact to a different angular position (but at the same distance from the center shaft), then the corresponding "ring pattern" needs to be rotated the same angle to give the same output. If the most significant bit (the inner ring in Figure 1) is rotated enough, it exactly matches the next ring out. Since both rings are then identical, the inner ring can be cut out, and the sensor for that ring moved to the remaining, identical ring (but offset at that angle from the other sensor on that ring).
Those 2 sensors on a single ring make a quadrature encoder.
That reduces the number of tracks for a "1 degree resolution" angular encoder to 8 tracks.
Reducing the number of tracks still further can't be done with BRGC.
For many years, Torsten Sillke and other mathematicians believed that it was impossible to encode position on a single track such that consecutive positions differed at only a single sensor, except for the 2-sensor, 1-track quadrature encoder.
So for applications where 8 tracks was too bulky, people used single-track incremental encoders (quadrature encoders) or 2-track "quadrature encoder + reference notch" encoders.
However, in 1996 Hiltgen, Paterson and Brandestini published a paper showing it was possible, with several examples.
In particular, a single-track gray code has been constructed that has exactly 360 angular positions, using only 9 sensors, the same as a BRGC with the same resolution (it would be impossible to discriminate that many positions with any fewer sensors).
The single-track Gray code was originally defined by Hiltgen, Paterson and Brandestini in "Single-track Gray codes" (1996). 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 <ref name=etzion>Template:Cite journal</ref>. 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 <ref>Template:Cite web</ref>. The single-track nature (like a code chain) is useful in the fabrication of these wheels (compared to BRGC), as only one track is needed, thus reducing their cost and size. The Gray code nature is useful (compared to chain codes), 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 unit of angular measurement the device is capable of resolving <ref>Template:Cite web</ref>.
See also
Footnotes
<references/>
References
- Black, Paul E. Gray code. 25 Feb. 2004. NIST. [1].
- F. Gray. Pulse code communication, March 17 1953. U.S. patent no. 2,632,058.
- 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. [2].
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
- Subsets or Combinations Can generate BRGC strings
- "The Structure of Single-Track Gray Codes" by Moshe Schwartz, Tuvi Etzion
- Single-Track Circuit Codes by Hiltgen, Alain P.; Paterson, Kenneth G.
- Dragos A. Harabor uses Gray codes in a 3D digitizer.
- single-track gray codes, binary chain codes (Lancaster 1994), and linear feedback shift registers are all useful in finding one's absolute position on a single-track rotary encoder (or other position sensor).
- A Gray code implementation in Java to convert decimals
- Use of snake-in-the-box codes for reliable identification of tracks in servo fields of a disk drive
- United States Patent 6496312: Use of snake-in-the-box codes for reliable identification of tracks in servo fields of a disk drivede:Gray-Code
es:Código Gray it:Codice Gray he:קוד גריי nl:Gray-code pl:Kod Graya ro:Cod Gray fi:Gray-koodi zh:格雷码