TOPICS
Search

Gray Code


A Gray code is an encoding of numbers so that adjacent numbers have a single digit differing by 1. The term Gray code is often used to refer to a "reflected" code, or more specifically still, the binary reflected Gray code.

To convert a binary number d_1d_2...d_(n-1)d_n to its corresponding binary reflected Gray code, start at the right with the digit d_n (the nth, or last, digit). If the d_(n-1) is 1, replace d_n by 1-d_n; otherwise, leave it unchanged. Then proceed to d_(n-1). Continue up to the first digit d_1, which is kept the same since d_0 is assumed to be a 0. The resulting number g_1g_2...g_(n-1)g_n is the reflected binary Gray code.

To convert a binary reflected Gray code g_1g_2...g_(n-1)g_n to a binary number, start again with the nth digit, and compute

 Sigma_n=sum_(i=1)^(n-1)g_i (mod 2).

If Sigma_n is 1, replace g_n by 1-g_n; otherwise, leave it the unchanged. Next compute

 Sigma_(n-1)=sum_(i=1)^(n-2)g_i (mod 2),

and so on. The resulting number d_1d_2...d_(n-1)d_n is the binary number corresponding to the initial binary reflected Gray code.

The code is called reflected because it can be generated in the following manner. Take the Gray code 0, 1. Write it forwards, then backwards: 0, 1, 1, 0. Then prepend 0s to the first half and 1s to the second half: 00, 01, 11, 10. Continuing, write 00, 01, 11, 10, 10, 11, 01, 00 to obtain: 000, 001, 011, 010, 110, 111, 101, 100, ... (OEIS A014550). Each iteration therefore doubles the number of codes.

Binary plot of the Gray code

The plots above show the binary representation of the first 255 (top figure) and first 511 (bottom figure) Gray codes. The Gray codes corresponding to the first few nonnegative integers are given in the following table.

00201111040111100
11211111141111101
211221110142111111
310231110043111110
4110241010044111010
5111251010145111011
6101261011146111001
7100271011047111000
81100281001048101000
91101291001149101001
101111301000150101011
111110311000051101010
1210103211000052101110
1310113311000153101111
1410013411001154101101
1510003511001055101100
16110003611011056100100
17110013711011157100101
18110113811010158100111
19110103911010059100110

The binary reflected Gray code is closely related to the solutions of the tower of Hanoi and baguenaudier, as well as to Hamiltonian cycles of hypercube graphs (including direction reversals; Skiena 1990, p. 149).


See also

Baguenaudier, Binary, Hilbert Curve, Ryser Formula, Thue-Morse Sequence, Tower of Hanoi

Explore with Wolfram|Alpha

References

Gardner, M. "The Binary Gray Code." Ch. 2 in Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, 1986.Gilbert, E. N. "Gray Codes and Paths on the n-Cube." Bell System Tech. J. 37, 815-826, 1958.Gray, F. "Pulse Code Communication." United States Patent Number 2632058. March 17, 1953.Nijenhuis, A. and Wilf, H. Combinatorial Algorithms for Computers and Calculators, 2nd ed. New York: Academic Press, 1978.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Gray Codes." §20.2 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 886-888, 1992.Skiena, S. "Gray Code." §1.5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 42-43 and 149, 1990.Sloane, N. J. A. Sequence A014550 in "The On-Line Encyclopedia of Integer Sequences."Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 111-112 and 246, 1991.Wilf, H. S. Combinatorial Algorithms: An Update. Philadelphia, PA: SIAM, 1989.

Referenced on Wolfram|Alpha

Gray Code

Cite this as:

Weisstein, Eric W. "Gray Code." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GrayCode.html

Subject classifications