Gray code

The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one digit.

The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.

Name

Bell Labs researcher Frank Gray introduced the term "reflected binary code" in his 1947 patent application, remarking that the code had "as yet no recognized name."F. Gray. "Pulse code communication", March 17, 1953 (filed Nov. 1947). ] , lack this property when k is odd. On the other hand, while only one digit at a time changes with this method, it can change by wrapping (looping from n-1 to 0). In Dah-Jyu Guan's algorithm, the count alternately rises and falls, so that the numeric difference between two graycode digits is always one.

Gray codes are not uniquely defined, because a permutation of the columns of such a code is a Gray code too. The above procedure produces a code in which the lower the significance of a digit, the more often it changes, making it similar to normal counting methods.

Balanced Gray code

A balanced Gray code is one in which the bit changes are distributed as equally as possible among the bit positions. Strictly speaking, a (cyclic) Gray code is called "balanced" if $|TC(i)-TC(j)|leq\; 2$ for any two bit positions "i, j", where $TC(i)$ is the number of times the bit "i" changes in the code ("transition count" of the bit "i"). Similarly, a Gray code is called "totally balanced" if $TC(i)=TC(j)$ for any two bit positions "i, j". Balanced "n"-bit Gray codes exist for any "n" while totally balanced "n"-bit Gray codes exist only when "n" is a power of 2. [cite journal| author=Girish S. Bhat and Carla D. Savage| title=Balanced Gray codes |journal=The Electronic Journal of Combinatorics |year=1996 |volume=3 |issue=1 |pages=R25 |url=http://www.combinatorics.org/Volume_3/Abstracts/v3i1r25.html]

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.cite web | title=MATH 343 Applied Discrete Math Supplementary Materials | last=Goddyn | first=Luis | year=1999 | publisher=Dept. of Math, Simon Fraser U | url=http://www.math.sfu.ca/~goddyn/Courses/343/supMaterials.pdf ] 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. 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, 7, 8}" and they do not exist for "n = {3, 4}". An example of an 8-bit Beckett–Gray code can be found in .According to [J. Sawada and D. Wong, "A Fast Algorithm to generate Beckett-Gray codes" Electronic notes in Discrete Mathematics (EuroComb 2007) Vol . 29 pp. 571–577, 2007.] ,the search space for "n = 6" can be explored in 15 hours, and more than 9,500 solutions for the case"n = 7" have been found.

Snake-in-the-box codes

Snake-in-the-box codes, or "snakes", are the sequences of nodes of induced paths in an "n"-dimensional hypercube graph, and coil-in-the-box codes, or "coils", are the sequences of nodes of induced cycles in a hypercube. Viewed as Gray codes, these sequences have the property of being able to detect any single-bit coding error. Codes of this type were first described by W. H. Kautz in the late 1950s; [cite journal
author = Kautz, W. H.
title = Unit-distance error-checking codes
journal = IRE Trans. Elect. Comput.
volume = 7
pages = 177–180
year = 1958] since then, there has been much research on finding the code with the largest possible number of codewords for a given hypercube dimension.

ingle-track Gray code

Yet another kind of Gray code is the single-track Gray code (STGC), originallyVerify source|date=July 2008 defined by Hiltgen, Paterson and Brandestini in "Single-track Gray codes" (1996)cite journal | url=http://ieeexplore.ieee.org/iel1/18/11236/00532900.pdf | title=Single-Track Gray Codes | last=Hiltgen | first=Alain P. | coauthors=Kenneth G. Paterson, Marco Brandestini | journal=IEEE Transactions on Information Theory | volume=42 | year=1996 | pages=1555-1561 | doi=10.1109/18.532900] . 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.cite journal | url=http://www.cs.technion.ac.il/~etzion/PUB/Gray2.pdf | title=The Structure of Single-Track Gray Codes | last=Etzion | first=Tuvi | coauthors=Moshe Schwartz | journal=IEEE Transactions on Information Theory | volume=45 | year=1999 | pages=2383–2396 | doi=10.1109/18.796379]

The name comes from their use with rotary encoders, where a number of tracks are being sensed by contacts, resulting for each in an output of 0 or 1. To reduce noise due to different contacts not switching at the exact same moment in time, one preferably sets up the tracks so that the data output by the contacts are in Gray code. To get high angular accuracy, one needs lots of contacts; in order to achieve at least 1 degree accuracy, one needs at least 360 distinct positions per revolution, which requires a minimum of 9 bits of data, and thus the same number of contacts.

If all contacts are placed at the same angular position, then 9 tracks are needed to get a standard BRGC with at least 1 degree accuracy. However, 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, [http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/gray 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 were 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 positionsFact|date=August 2008, 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).

An STGC for "P = 30" and "n = 5" is reproduced here: 10000 10100 11100 11110 11010 11000 01000 01010 01110 01111 01101 01100 00100 00101 00111 10111 10110 00110 00010 10010 10011 11011 01011 00011 00001 01001 11001 11101 10101 10001 Note that each column is a cyclic shift of the first column, and from any row to the next row only one bit changes. [cite web | title=Venn Diagram Survey — Symmetric Diagrams | work=The Electronic Journal of Combinatorics | year=2001 | url=http://www.combinatorics.org/Surveys/ds5/VennSymmEJC.html ] 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 sensor 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. [cite web | url=http://mechatronics.mech.northwestern.edu/mechatronics/design_ref/sensors/encoders.html | author=Alciatore and Histand | title = Introduction to Mechatronics and Measurement Systems ]

See also

* Linear feedback shift register

Footnotes

References

*Black, Paul E. "Gray code". 25 February 2004. NIST. [http://www.nist.gov/dads/HTML/graycode.html] .
*Savage, Carla. "A Survey of Combinatorial Gray Codes." "Society of Industrial and Applied Mathematics Review" 39 (1997): 605–629. [http://epubs.siam.org/sam-bin/getfile/SIREV/articles/29527.pdf] .
*Wilf, Herbert S. "Combinatorial algorithms: an update", SIAM, 1989, ISBN 0-89871-231-9. Chapters 1-3.

External links

* [http://engknowledge.com/shaft_absolute_encoder_gray_code.aspx Absolute Encoder Using Gray Code] - Absolute encoding for rotating shaft, with a comprehensive discussion of gray code.
* [http://demonstrations.wolfram.com/BinaryGrayCode/ "Gray Code" demonstration] by Michael Schreiber, The Wolfram Demonstrations Project (with Mathematica implementation). 2007.
* [http://www.nist.gov/dads/HTML/graycode.html NIST Dictionary of Algorithms and Data Structures: Gray code]
* [http://www.nrbook.com/a/bookcpdf/c20-2.pdf "Numerical Recipes in C", section 20.2] describing Gray codes in detail (ISBN 0-521-43108-5)
* [http://www.aip.de/~ast/EvolCompFAQ/Q21.htm 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
* [http://www.theory.cs.uvic.ca/~cos/gen/comb.html Subsets or Combinations] Can generate BRGC strings
* [http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1998/CS/CS0937 "The Structure of Single-Track Gray Codes"] by Moshe Schwartz, Tuvi Etzion
* [http://www.hpl.hp.com/techreports/2000/HPL-2000-81.html Single-Track Circuit Codes] by Hiltgen, Alain P.; Paterson, Kenneth G.
* Dragos A. Harabor uses [http://www.ugcs.caltech.edu/~dragos/3DP/coord.html Gray codes in a 3D digitizer] .
* single-track gray codes, binary chain codes ( [http://tinaja.com/text/chain01.html 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).
* [http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=4475352&arnumber=4475394&count=44&index=39 Computing Binary Combinatorial Gray Codes Via Exhaustive Search With SAT Solvers] by Zinovik, I.; Kroening, D.; Chebiryak, Y.
* [http://etc.manuel-breitfeld.de/gray-code-java-implementierung.html A Gray code implementation in Java to convert decimals]

* [http://www.freepatentsonline.com/20020126407.html Use of snake-in-the-box codes for reliable identification of tracks in servo fields of a disk drive]
* [http://www.patentstorm.us/patents/6496312.html United States Patent 6496312: Use of snake-in-the-box codes for reliable identification of tracks in servo fields of a disk drive]