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 via what is known as the Gray map.

Gray map: The Gray map converts a quaternary string over \(\mathbb{Z}_4\) into a binary string such that the Hamming distance of the binary representation is one between any two consecutive quaternary digits. For a single digit, the mapping is \(0\to 00\), \(1\to 01\), \(2\to 11\), and \(3\to 10\). This differs from the usual binary expansion of the natural numbers, which maps \(0\to 00\), \(1\to 01\), \(2\to 10\), and \(3\to 11\). A linear code \(C\) over \(\mathbb{Z}_4\) can be mapped, via the Gray map, to a distance invariant binary code [4; Thm. 2]. The binary code is linear if and only if doubling the component-wise product of any two codewords in \(C\) yields another codeword in \(C\) [5; Thm. 12.2.3]. The map converts Lee to Hamming weight, and Lee distance to Hamming distance [6; Thm. 3.1 and Prop. 3.3].

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 [7] of Gray codes may be useful in digital imaging and signal processing.

Encoding

Efficient encoder for binary reflected Gray code [8].

Realizations

Three-dimensional imaging [9].Broadcasting and communication [10].

Notes

See Refs. [11–13] reviews of various Gray codes.

Cousins

Qubit code— Gray codes are useful for optimizing qubit unitary circuits [14] and for encoding qudits in multiple qubits [15].
Linear code over \(\mathbb{Z}_4\)— A linear code \(C\) over \(\mathbb{Z}_4\) can be mapped, via the Gray map, to a binary code. The binary code is linear if and only if doubling the component-wise product of any two codewords in \(C\) yields another codeword in \(C\) [5; Thm. 12.2.3].
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\) [4,6,16].
Preparata code— The image of the Preparata code under the Gray map is the QRM\((m-2,m)\) code [4; Thm. 19].
Delsarte-Goethals (DG) code— DG codes can be seen, via the Gray map, as extended linear cyclic codes over \(\mathbb{Z}_4\) [4,16].
Kerdock code— The image of the Kerdock code under the Gray map is the QRM\((1,m)\) code, an extended cyclic code over \(\mathbb{Z}_4\) [4; Thm. 19] (see also Ref. [17]).
\((10,40,4)\) Best code— Codewords of the Best code can be obtained by applying the Gray map to the pentacode [18; Sec. 2].
Julin-Golay code— Julin codes can be obtained from simple nonlinear codes over \(\mathbb{Z}_4\) using the Gray map [18].
Rank-modulation code— The rank-modulation Gray code is an extension of the original binary Gray code to a code on the permutation group [19].
Quaternary RM (QRM) code— The mod-two reduction of the QRM\((r,m)\) code is the RM\((r,m)\) code [4; Thm. 19].
ZRM code— The image of the ZRM\((r,m-1)\) code under the Gray map is the RM\((r,m)\) code [4; Thm. 7].
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 [20].

Member of code lists

Primary Hierarchy

Classical Domain

Binary Kingdom

Binary codeECC

Binary group-orbit codeECC

Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC

Parents

Linear binary code

A linear code \(C\) over \(\mathbb{Z}_4\) can be mapped, via the Gray map, to a binary code. The binary code is linear if and only if doubling the component-wise product of any two codewords in \(C\) yields another codeword in \(C\) [5; Thm. 12.2.3].

Gray code

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]: A. R. Hammons Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
[5]: W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[6]: Z. X. Wan, Quaternary Codes (WORLD SCIENTIFIC, 1997) DOI
[7]: Yicong Zhou, K. Panetta, S. Agaian, and C. L. P. Chen, “(n, k, p)-Gray code for image systems”, IEEE Transactions on Cybernetics 43, 515 (2013) DOI
[8]: 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
[9]: G. Sansoni, S. Corini, S. Lazzari, R. Rodella, and F. Docchio, “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
[10]: S. L. Johnsson and C.-T. Ho, “Optimum broadcasting and personalized communication in hypercubes”, IEEE Transactions on Computers 38, 1249 (1989) DOI
[11]: C. Savage, “A Survey of Combinatorial Gray Codes”, SIAM Review 39, 605 (1997) DOI
[12]: L. S. Barasch, S. Lakshmivarahan, and S. K. Dhall, “Generalized Gray Codes and Their Properties”, Mathematics for Large Scale Computing 203 (2020) DOI
[13]: T. Mütze, “Combinatorial Gray codes-an updated survey”, (2024) arXiv:2202.01280
[14]: 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
[15]: N. P. D. Sawaya, T. Menke, T. H. Kyaw, S. Johri, A. Aspuru-Guzik, and G. G. Guerreschi, “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
[16]: A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Sole, “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
[17]: A. A. NECHAEV, “Kerdock code in a cyclic form”, Discrete Mathematics and Applications 1, (1991) DOI
[18]: 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
[19]: Anxiao Jiang, R. Mateescu, M. Schwartz, and J. Bruck, “Rank Modulation for Flash Memories”, IEEE Transactions on Information Theory 55, 2659 (2009) DOI
[20]: 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.