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 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]. |
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. |
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. |
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 Gray code (RMGC) | A family of codes that encode a finite set of size \(M\) into a group \(S_n\) of permutations of \([n]=(1,2,...,n)\). They can be derived from Lee-metric codes, Reed-Solomon 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. http://hal.archives-ouvertes.fr/hal-00338309/fr/.