(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 Gray_code [Wikipedia] entry for more information.
There are polynomial-time algorithms to convert between binary numbers and certain Gray codes.
Author: PEB
How to create (one kind of) Gray code with diagram of rotary encoder.
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 14 December 2020.
HTML page formatted Mon Dec 14 11:38:56 2020.
Cite this as:
Paul E. Black, "Gray code", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 14 December 2020. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/graycode.html