(definition)
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 ...)
Karnaugh map.
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.
There are polynomial-time algorithms to convert between binary numbers and certain Gray codes.
Author: PEB
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 Black.
Entry modified 7 June 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "Gray code", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 7 June 2014. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/graycode.html