Here is a list of nonlinear codes related to linear codes via the Gray map.
Code | Description | Relation |
---|---|---|
Best \((10,40,4)\) code | Binary nonlinear \((10,40,4)\) code that is unique [1]. Under Construction A, this code yields \(P_{10c}\), a non-lattice sphere packing that is the densest known in 10 dimensions [2][3; pg. 140]. | Codewords of the Best code can be obtained by applying the Gray map to the pentacode [4; Sec. 2]. |
Delsarte-Goethals (DG) code | Member of a family of \((2^{2t+2},2^{(2t+1)(t-d+2)+2t+3},2^{2t+1}-2^{2t+1-d})\) binary nonlinear codes for parameters \(r \geq 1\) and \(m = 2t+2 \geq 4\), denoted by DG\((m,r)\), that generalizes the Kerdock code. | DG codes can be seen, via the Gray map, as extended linear cyclic codes over \(\mathbb{Z}_4\) [5,6]. |
Gray code | The first Gray code [7], 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. | |
Hergert code | A nonlinear subcode of an RM code that is a formal dual of the nonlinear DG code in the sense that its distance distribution is equal to the MacWilliams transform of the distance distribution of a DG codes. | Hergert codes can be seen, via the Gray map, as linear codes over \(\mathbb{Z}_4\) [5,6]. |
Julin-Golay code | One of several nonlinear binary \((12,144,4)\) codes based on the Steiner system \(S(5,6,12)\) [8,9][10; Sec. 2.7][4; Sec. 4] or their shortened versions, the nonlinear \((11,72,4)\), \((10,38,4)\), and \((9,20,4)\) Julin-Golay codes. Several of these codes contain more codewords than linear codes of the same length and distance and yield non-lattice sphere-packings that hold records in 9 and 11 dimensions. | Julin codes can be obtained from simple nonlinear codes over \(\mathbb{Z}_4\) using the Gray map [4]. |
Kerdock code | Binary nonlinear \((2^m, 2^{2m}, 2^{m-1} - 2^{(m-2)/2})\) for even \(m\) consisting of the first-order Reed-Muller code RM\((1,m)\) with maximum-rank cosets of RM\((1,m)\) in RM\((2,m)\). | The image of the Kerdock code under the Gray map yields the QRM\((1,m)\) code [6; Thm. 19]. |
Phase-shift keying (PSK) code | A \(q\)-ary phase-shift keying (\(q\)-PSK) encodes one \(q\)-ary digit of information into a constellation of \(q\) points distributed equidistantly on a circle in \(\mathbb{C}\) or, equivalently, \(\mathbb{R}^2\). | 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. |
Preparata code | A nonlinear binary \((2^{m+1}-1, 2^{m+1}-2m-2, 5)\) code where \(m\) is odd. The size of this code is twice the size of the largest possible linear code with the same length and distance. | The image of the Preparata code under the Gray map yields the QRM\((m-2,m)\) code [6; Thm. 19]. |
Quadrature-amplitude modulation (QAM) code | Encodes into points into a subset of points lying on in \(\mathbb{R}^{2}\), here treated as \(\mathbb{C}\). Each pair of points is associated with a complex amplitude of an electromagnetic signal, and information is encoded into both the norm and phase of that signal [11; Ch. 16]. | 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. |
Quaternary RM (QRM) code | A quaternary linear code over \(\mathbb{Z}_4\) that is a quaternary version of the RM code in that its binary image under the Gray map is an RM code. This code subsumes the quaternary images of the Kerdock and Preparata codes under the Gray map. The code is usually noted as QRM\((r,m)\), with its image under the Gray map yielding the RM code RM\((r,m)\) [6; Thm. 19]. | The image of the QRM\((r,m)\) code under the Gray map is the RM\((r,m)\) code [6; Thm. 19]. |
Qubit code | Encodes \(K\)-dimensional Hilbert space into a \(2^n\)-dimensional (i.e., \(n\)-qubit) Hilbert space. Usually denoted as \(((n,K))\) or \(((n,K,d))\), where \(d\) is the code's distance. | Gray codes are useful for optimizing qubit unitary circuits [12] and for encoding qudits in multiple qubits [13]. |
Rank-modulation code | A family of codes in permutations derived from \(q\)-ary linear codes, such as Lee-metric codes, RS codes [14], quadratic residue codes, and most binary codes. | The rank-modulation Gray code is an extension of the original binary Gray code to a code on the permutation group [15]. |
Reed-Muller (RM) code | Member of the RM\((r,m)\) family of linear binary codes derived from multivariate polynomials. The code parameters are \([2^m,\sum_{j=0}^{r} {m \choose j},2^{m-r}]\), where \(r\) is the order of the code satisfying \(0\leq r\leq m\). First-order RM codes are also called biorthogonal codes, while \(m\)th order RM codes are also called universe codes. Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one coordinate from each codeword. | RM codes are images of linear quaternary codes over \(\mathbb{Z}_4\) under the Gray map [16; Sec. 6.3]. |
\(((2^m,2^{2^m−5m+1},8))\) Goethals-Preparata code | Member of a family of \(((2^m,2^{2^m−5m+1},8))\) CSS-like union stabilizer codes constructed using the classical Goethals and Preparata codes. | 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 [17]. |
References
- [1]
- S. Litsyn and A. Vardy, “The uniqueness of the Best code”, IEEE Transactions on Information Theory 40, 1693 (1994) DOI
- [2]
- J. Leech and N. J. A. Sloane, “Sphere Packings and Error-Correcting Codes”, Canadian Journal of Mathematics 23, 718 (1971) DOI
- [3]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [4]
- 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
- [5]
- 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
- [6]
- A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
- [7]
- Gray, Frank. "Pulse code communication." United States Patent Number 2632058 (1953).
- [8]
- J. A. Barrau, On the combinatory problem of Steiner, Proc. Section of Sciences, Koninklijke Akademie van Wetenschappen te Amsterdam 11 (1908), 352–360.
- [9]
- J. Leech, “Some Sphere Packings in Higher Space”, Canadian Journal of Mathematics 16, 657 (1964) DOI
- [10]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [11]
- A. Lapidoth, A Foundation in Digital Communication (Cambridge University Press, 2017) DOI
- [12]
- 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
- [13]
- 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
- [14]
- A. Mazumdar, A. Barg, and G. Zémor, “Constructions of Rank Modulation Codes”, (2011) arXiv:1110.2557
- [15]
- Anxiao Jiang et al., “Rank Modulation for Flash Memories”, IEEE Transactions on Information Theory 55, 2659 (2009) DOI
- [16]
- S. T. Dougherty, "Codes over rings." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [17]
- S. Ling and P. Sole. 2008. Nonadditive quantum codes from Z4-codes. https://hal.archives-ouvertes.fr/hal-00338309/fr/.