Gray code

From Academic Kids

2-bit Gray codes
00
01
11
10
3-bit Gray codes
000
001
011
010
110
111
101
100
4-bit Gray codes
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

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

Missing image
Encoder_disc.png
rotary encoder for angle-measuring devices marked in 3-bit binary-reflected Gray code (BRCG)

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

3-bit ternary Gray codes
000
001
002
012
011
010
020
021
022
122
121
120
110
111
112
102
101
100
200
201
202
212
211
210
220
221
222

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

es:Código Gray it:Codice Gray pl:Kod Graya ro:Cod Gray

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools