Gray code

Gray code[1–3]

Description

The first Gray code [1], now called the binary reflected Gray code, is a trivial \([n,n,1]\) 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\).

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 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

Linear binary code

Cousins

Qubit code — Gray codes are useful for optimizing qubit unitary circuits [11] and for encoding qudits in multiple qubits [12].
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.
Hergert code — Hergert codes can be seen, via the Gray map, as linear codes over \(\mathbb{Z}_4\) [13,14].
Preparata code — The image of the Preparata code under the Gray map yields the QRM\((m-2,m)\) code [14; Thm. 19].
Delsarte-Goethals (DG) code — DG codes can be seen, via the Gray map, as extended linear cyclic codes over \(\mathbb{Z}_4\) [13,14].
Kerdock code — The image of the Kerdock code under the Gray map yields the QRM\((1,m)\) code [14; Thm. 19].
Best \((10,40,4)\) code — Codewords of the Best code can be obtained by applying the Gray map to the pentacode [15; Sec. 2].
Julin-Golay code — Julin codes can be obtained from simple nonlinear codes over \(\mathbb{Z}_4\) using the Gray map [15].
Reed-Muller (RM) code — RM codes are images of linear quaternary codes over \(\mathbb{Z}_4\) under the Gray map [16; Sec. 6.3].
Rank-modulation code — The rank-modulation Gray code is an extension of the original binary Gray code to a code on the permutation group [17].
Quaternary RM (QRM) code — The image of the QRM\((r,m)\) code under the Gray map is the RM\((r,m)\) code [14; Thm. 19].
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.
\(((2^m,2^{2^m−5m+1},8))\) Goethals-Preparata code — A construction using the \(\mathbb{Z}_4\) versions of the Goethals and Preparata codes and the Gray map yields qubit code families with similar parameters as the \(((2^m,2^{2^m−5m+1},8))\) Goethals-Preparata code [18].

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”, (2024) arXiv:2202.01280
[11]: J. J. Vartiainen, M. Möttönen, and M. M. Salomaa, “Efficient Decomposition of Quantum Gates”, Physical Review Letters 92, (2004) arXiv:quant-ph/0312218 DOI
[12]: N. P. D. Sawaya et al., “Resource-efficient digital quantum simulation of d-level systems for photonic, vibrational, and spin-s Hamiltonians”, npj Quantum Information 6, (2020) arXiv:1909.12847 DOI
[13]: A. R. Hammons et al., “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
[14]: A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
[15]: J. H. Conway and N. J. A. Sloane, “Quaternary constructions for the binary single-error-correcting codes of Julin, Best and others”, Designs, Codes and Cryptography 4, 31 (1994) DOI
[16]: S. T. Dougherty, "Codes over rings." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[17]: Anxiao Jiang et al., “Rank Modulation for Flash Memories”, IEEE Transactions on Information Theory 55, 2659 (2009) DOI
[18]: S. Ling and P. Sole. 2008. Nonadditive quantum codes from Z4-codes. https://hal.archives-ouvertes.fr/hal-00338309/fr/.

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/edit/main/codes/classical/bits/nonlinear/gray_map/gray.yml.