Definition: An ordering of 2n binary numbers such that only one bit changes from one entry to the next. Gray codes for 4 or more bits are not unique, even allowing for permutation or inversion of bits.
Aggregate parent (I am a part of or used in ...)
Note: Gray codes are particularly useful in mechanical encoders since a slight change in position only affects one bit. Using a typical binary code, up to n bits could change, and slight misalignments between reading elements could cause wildly incorrect readings.
An n-bit Gray code corresponds to a Hamiltonian cycle on an n-dimensional hypercube.
A Gray code was used in a telegraph demonstrated by French engineer Émile Baudot in 1878. Frank Gray, a Bell Labs researcher, patented a method using the codes in 1953.
See the Wikipedia entry for Gray code for more information.
See the links for polynomial-time algorithms to convert between binary numbers and certain Gray codes.
Image of a Gray code rotary railroad control.
Frank Gray, Pulse Code Communication, U.S. Patent 2,632,058, filed 13 November 1947, issued 17 March 1953.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 12 December 2011.
HTML page formatted Mon Dec 12 10:22:39 2011.
Cite this as:
Paul E. Black, "Gray code", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 12 December 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/graycode.html