Gray code

Gray code[1–3]

Description

The first Gray code [1], now called the binary reflected Gray code, is a trivial code that orders length-\(n\) binary strings such that nearest-neighbor strings differ by only one digit.

A simple example is the case \(n=2\), also known as the Gray map, which produces the ordering \(0\to 00\), \(1\to 01\), \(2\to 11\), and \(3\to 10\). The Gray map differs in the last two numbers from the usual binary expansion of the natural numbers, which maps \(0\to 00\), \(1\to 01\), \(2\to 10\), and \(3\to 11\).

Layout out the Gray-map output strings counterclockwise on the corners of a 1D square, gray codes have been generalized such that nearest-neighbor strings differ by only one digit when the strings are arranged in higher-dimensional hypercubes [2]. Further generalizations called combinatorial Gray codes [3] refer to methods to generate organize combinatorial objects such that successive objects differ in some particular way. Particular \(q\)-ary extensions [4] of Gray codes may be useful in digital imaging and signal processing.

Encoding

Efficient encoder for binary reflected Gray code [5].

Realizations

Three-dimensional imaging [6].Broadcasting and communication [7].

Notes

See Refs. [8–10] reviews of various Gray codes.

Parent

Binary code

Cousins

Quadrature-amplitude modulation (QAM) code — 2D Gray codes are often concatenated with \(n=1\) lattice-based QAM codes so that the Hamming distance between the bitstrings encoded into the points is a discretized version of the Euclidean distance between the points.
Rank-modulation Gray code (RMGC) — The rank-modulation Gray code is an extension of the original binary Gray code to a code on the permutation group [11].
Phase-shift keying (PSK) code — 1D Gray codes are often concatenated with PSKs so that the Hamming distance between the bitstrings encoded into the points is a discretized version of the Euclidean distance between the points.

References

[1]: Gray, Frank. "Pulse code communication." United States Patent Number 2632058 (1953).
[2]: E. N. Gilbert, “Gray Codes and Paths on the n-Cube”, Bell System Technical Journal 37, 815 (1958) DOI
[3]: J. T. Joichi, D. E. White, and S. G. Williamson, “Combinatorial Gray Codes”, SIAM Journal on Computing 9, 130 (1980) DOI
[4]: Yicong Zhou et al., “(n, k, p)-Gray code for image systems”, IEEE Transactions on Cybernetics 43, 515 (2013) DOI
[5]: J. R. Bitner, G. Ehrlich, and E. M. Reingold, “Efficient generation of the binary reflected gray code and its applications”, Communications of the ACM 19, 517 (1976) DOI
[6]: G. Sansoni et al., “Three-dimensional imaging based on Gray-code light projection: characterization of the measuring algorithm and development of a measuring system for industrial applications”, Applied Optics 36, 4463 (1997) DOI
[7]: S. L. Johnsson and C.-T. Ho, “Optimum broadcasting and personalized communication in hypercubes”, IEEE Transactions on Computers 38, 1249 (1989) DOI
[8]: C. Savage, “A Survey of Combinatorial Gray Codes”, SIAM Review 39, 605 (1997) DOI
[9]: L. S. Barasch, S. Lakshmivarahan, and S. K. Dhall, “Generalized Gray Codes and Their Properties”, Mathematics for Large Scale Computing 203 (2020) DOI
[10]: T. Mütze, “Combinatorial Gray codes-an updated survey”, (2023) arXiv:2202.01280
[11]: Anxiao Jiang et al., “Rank Modulation for Flash Memories”, IEEE Transactions on Information Theory 55, 2659 (2009) DOI

Page edit log

Victor V. Albert (2022-11-07) — most recent

Cite as:

“Gray code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/gray

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/nonlinear/gray.yml.