Gray code

(definition)

Definition: An ordering of 2ⁿ binary numbers such that only one bit changes from one entry to the next.

See also Karnaugh map.

Note: Gray codes are useful in mechanical encoders since a slight change in location 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.
One Gray code for 3 bits is (000, 010, 011, 001, 101, 111, 110, 100). An n-bit Gray code corresponds to a Hamiltonian cycle on an n-dimensional hypercube. Note: Gray codes are not unique.
One way to construct a Gray code for n bits is to take a Gray code for n-1 bits with each code prefixed by 0 (for the first half of the code) and append the n-1 Gray code reversed with each code prefixed by 1 (for the second half). Here is an example of creating a 3-bit Gray code from a 2-bit Gray code.
00 01 11 10 A Gray code for 2 bits
000 001 011 010 the 2-bit code with a zero prefix
10 11 01 00 the 2-bit code reversed
110 111 101 100 the reversed code with a one prefix
000 001 011 010 110 111 101 100 A Gray code for 3 bits

Author: PEB

Entry modified Tue Jun 5 08:53:56 2001.
HTML page formatted Tue Jun 5 09:03:15 2001.

This page's URL is http://www.nist.gov/dads/HTML/graycode.html