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

Rank-modulation Gray code (RMGC) | Also known as a code in permutations. 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 [12], 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 [13]. |

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 or more coordinates from each codeword. | RM codes are images of linear quaternary codes over \(\mathbb{Z}_4\) under the Gray map [14; 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 [15]. |

## 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]
- A. Mazumdar, A. Barg, and G. Zemor, “Constructions of rank modulation codes”, 2011 IEEE International Symposium on Information Theory Proceedings (2011) DOI
- [13]
- Anxiao Jiang et al., “Rank Modulation for Flash Memories”, IEEE Transactions on Information Theory 55, 2659 (2009) DOI
- [14]
- S. T. Dougherty, "Codes over rings." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [15]
- S. Ling and P. Sole. 2008. Nonadditive quantum codes from Z4-codes. http://hal.archives-ouvertes.fr/hal-00338309/fr/.