Here is a list of Reed-Solomon-type and related codes over various alphabets.
| Code | Description |
|---|---|
| Alternant code | Given a length-\(n\) GRS code \(C\) over \(\mathbb{F}_{q^m}\), an alternant code is the \(\mathbb{F}_q\)-subfield subcode of the dual of \(C\); see [1; Ch. 12]. Its parity-check matrix is an alternant matrix. |
| Analog RS code | A block code over the real or complex numbers, called a real RS or complex RS (CRS) code respectively, whose encoding generalizes the RS code encoding over finite fields. |
| Concatenated code | A code whose encoding mapping is a composition of two mappings: first the message set is mapped onto the code space of the outer code, then each coordinate of the outer code is mapped on the code space of the inner code. In the basic construction, the outer code’s alphabet is the finite field \(\mathbb{F}_{p^m}\) and the \(m\)-dimensional inner code is over over the field \(\mathbb{F}_p\). The construction is not limited to linear codes. |
| Cross-interleaved RS (CIRS) code | An IRS code that is constructed using two shortened RS codes and two forms of interleaving. The code can also be visualized as a 2D array code [2]. |
| Extended GRS code | A GRS code with an additional parity-check coordinate with corresponding evaluation point of zero. In other words, an \([n+1,k,n-k+2]_q\) GRS code whose polynomials are evaluated at the points \((\alpha_1,\cdots,\alpha_n,0)\). The case when \(n=q-1\), multipliers \(v_i=1\), and \(\alpha_i\) are \(i-1\)st powers of a primitive \(n\)th root of unity is an extended narrow-sense RS code. |
| Folded RS (FRS) code | A linear \([n/m,k]_{q^m}\) code that is a modification of an \([n,k]_q\) RS code such that evaluations are grouped to yield a code with smaller length. In this case, the evaluation points are all powers of a generating field element \(\gamma\), \(\alpha_i=\gamma^i\). Each codeword \(\mu\) of an \(m\)-folded RS code is a string of \(n/m\) symbols, with each symbol being a string of values of a polynomial \(f_\mu\) at consecutive powers of \(\gamma\), \begin{align} \begin{split} \mu\to&\Big(\left(f_{\mu}(\alpha^{0}),\cdots,f_{\mu}(\alpha^{m-1})\right),\left(f_{\mu}(\alpha^{m}),\cdots,f_{\mu}(\alpha^{2m-1})\right)\cdots\\&\cdots,\left(f_{\mu}(\alpha^{n-m}),\cdots,f_{\mu}(\alpha^{n-1})\right)\Big)~. \end{split} \tag*{(1)}\end{align} |
| Folded quantum RS (FQRS) code | CSS code on \(q^m\)-dimensional Galois-qudits that is constructed from folded RS (FRS) codes (i.e., an RS code whose coordinates have been grouped together) via the Galois-qudit CSS construction. This code is used to construct Singleton-bound approaching approximate quantum codes. |
| Gabidulin code | A linear code over \(\mathbb{F}_{q^N}\) that corrects errors over rank metric instead of the traditional Hamming distance. Every element \(\mathbb{F}_{q^N}\) can be written as an \(N\)-dimensional vector with coefficients in \(\mathbb{F}_q\), and the rank of a set of elements is rank of the matrix formed by their coefficients. |
| Galois-qudit GRS code | True \(q\)-Galois-qudit stabilizer code constructed from GRS codes via either the Hermitian construction [3–5] or the Galois-qudit CSS construction [6,7]. |
| Generalized RS (GRS) code | An \([n,k,n-k+1]_q\) linear code that is a modification of the RS code where codeword polynomials are multiplied by additional prefactors. |
| Goppa code | Let \( G(x) \) be a polynomial describing a projective-plane curve with coefficients from \( \mathbb{F}_{q^m} \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( \mathbb{F}_{q^m} \) where \(q\) is prime (for simplicity), meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( \mathbb{F}_{q^m} \). A Goppa code \( \Gamma(L,G) \) is an \([n,k,d]_q\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(x) =0 \) modulo \(G(x)\), where \( R_a(x) = \sum_{i=1}^n \frac{a_i}{z - \alpha_i} \). |
| Hermitian code | Evaluation AG code of rational functions evaluated on points lying on a Hermitian curve in either affine or projective space. Hermitian codes improve over RS codes in length: that RS codes have length at most \(q+1\) while Hermitian codes have length \(q^3 + 1\). |
| Hyperbolic evaluation code | An evaluation code over polynomials in two variables. Generator matrices are determined in Ref. [8] following initial formulations of the codes as generalized concatenations of RS codes [9,10]; see [11; Exam. 4.26]. |
| Hyperoval code | A projective code constructed using hyperovals in projective space. |
| Interleaved RS (IRS) code | A modification of RS codes where multiple polynomials are used to define each codeword. Each codeword \(\mu\) of a \(t\)-interleaved RS code is a string of values of the corresponding set \(\{f_\mu^{(1)},f_\mu^{(2)},\cdots,f_\mu^{(t)}\}\) of \(t\) polynomials at the points \(\alpha_i\). The vector codewords can be arranged in an array whose rows are ordinary RS codes for each polynomial \(f^{j}\), yielding the encoding \begin{align} \mu\to\left( \begin{array}{cccc} f_{\mu}^{(1)}\left(\alpha_{1}\right) & f_{\mu}^{(1)}\left(\alpha_{2}\right) & \cdots & f_{\mu}^{(1)}\left(\alpha_{n}\right)\\ f_{\mu}^{(2)}\left(\alpha_{1}\right) & f_{\mu}^{(2)}\left(\alpha_{2}\right) & & f_{\mu}^{(2)}\left(\alpha_{n}\right)\\ \vdots & & \ddots & \vdots\\ f_{\mu}^{(t)}\left(\alpha_{1}\right) & f_{\mu}^{(t)}\left(\alpha_{2}\right) & \cdots & f_{\mu}^{(t)}\left(\alpha_{n}\right) \end{array}\right)~. \tag*{(2)}\end{align} |
| Linear \(q\)-ary code | An \((n,K,d)_q\) linear code is denoted as \([n,k,d]_q\), where \(k=\log_q K\) need not be an integer. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(\alpha x+ \beta y\) is also a codeword for any \(q\)-ary digits \(\alpha,\beta\). This extra structure yields much information about their properties, making them a large and well-studied subset of codes. |
| Linearized RS code | A linearized version of a skew RS code, i.e., an RS code constructed by evaluating skew polynomials [12,13]. |
| Locally recoverable code (LRC) | An LRC is a block code for which one can recover any coordinate of a codeword from at most \(r\) other coordinates of the codeword. In other words, an LRC of locality \(r\) is a block code for which, given a codeword \(c\) and coordinate \(c_i\), \(c_i\) can be recovered from at most \(r\) other coordinates of \(c\). An \(r\)-locally recoverable code of length \(n\) and dimension \(k\) is denoted as an \((n,k,r)\) LRC. The definition can be generalized to \(t\)-LRC, if every coordinate is recoverable from \(t\) disjoint subsets of coordinates. |
| Maximum distance separable (MDS) code | A type of \(q\)-ary code whose parameters satisfy the Singleton bound with equality. |
| Narrow-sense RS code | An \([q-1,k,n-k+1]_q\) RS code whose points \(\alpha_i\) are all \((i-1)\)st powers of a primitive element \(\alpha\) of \(\mathbb{F}_q\). |
| Parvaresh-Vardy (PV) code | An IRS code with additional algebraic relations (a.k.a. correlations) between the codeword polynomials \(\{f^{(j)}\}_{j=1}^{t}\). These relations yielded a list decoder that achieves list-decoding capacity. |
| Projective geometry code | Linear \(q\)-ary \([n,k,d]\) code such that columns of its generator matrix \(G\) does not contain any repeated columns or the zero column. That way, each column corresponds to a distinct point in the projective space \(PG(k-1,q)\) arising from a \(k\)-dimensional vector space over \(\mathbb{F}_q\). If the columns are linearly independent, then the codewords are collectively called an information set. Columns of a code’s parity-check matrix can similarly correspond to points in projective space. This formulation yields connections to projective geometry, which can be applied to determine code properties. |
| Quantum convolutional code | One-dimensional translationally invariant qubit stabilizer code whose whose stabilizer group can be partitioned into constant-size subsets of constant support and of constant overlap between neighboring sets. Initially formulated as a quantum analogue of convolutional codes, which were designed to protect a continuous and never-ending stream of information. Precise formulations sometimes begin with a finite-dimensional lattice, with the intent to take the thermodynamic limit; logical dimension can be infinite as well. |
| Quantum maximum-distance-separable (MDS) code | A type of block quantum code whose parameters satisfy the quantum Singleton bound with equality. |
| RS NRT code | An NRT analogue of an RS code. |
| Random code | Code whose construction is non-deterministic in some way, i.e., codes that utilize an elements of randomness somewhere in their construction. Members of this class range from fully non-deterministic codes, to codes whose multi-step construction is deterministic with the exception of a single step. |
| 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. |
| Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(\mathbb{F}_q\). |
| Repetition code | \([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. The idea is to increase the code distance by repeating the logical information several times. It is a \((n,1)\)-Hamming code. Its automorphism group is \(S_n\). |
| Roth-Lempel code | Member of a \(q\)-ary linear code family that includes many examples of MDS codes that are not GRS codes. |
| \([2^m,2^m-m-1,4]\) Extended Hamming code | Member of an infinite family of RM\((m-2,m)\) codes with parameters \([2^m,2^m-m-1, 4]\) for \(m \geq 2\) that are extensions of the Hamming codes by a parity-check bit. |
| \([2^m,m+1,2^{m-1}]\) First-order RM code | A member of the family of first-order RM codes. Its codewords are the rows of the \(2^m\)-dimensional Hadamard matrix \(H\) and its negation \(-H\) with the mapping \(+1\to 0\) and \(-1\to 1\). The family is self-orthogonal for \(m \geq 3\) [14]. They form a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping. |
| \([2^m-1,m,2^{m-1}]\) simplex code | A member of the equidistant code family that is dual to the \([2^m,2^m-m-1,3]\) Hamming family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,2)\), with each column being a chosen representative of the corresponding element. Simplex codes saturate the Plotkin bound and hence have nonzero codewords all of the same weight, \(2^{m-1}\) [1; Th. 11(a)]. The codewords form a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping. |
| \([4,2,3]_3\) Tetracode | The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [15]. |
| \([6,3,4]_4\) Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [15], and conformal field theory [16]. |
| \([8,4,4]\) extended Hamming code | Extension of the \([7,4,3]\) Hamming code by a parity-check bit. The smallest doubly even self-dual code. |
| \([n,n-1,2]\) Single parity-check (SPC) code | An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check bit or parity bit such that the parity (i.e., sum over all coordinates of each codeword) is zero. If the Hamming weight of a message is odd (even), then the parity bit is one (zero). This code requires only one extra bit of overhead and is therefore inexpensive. Its codewords are all even-weight binary strings. Its automorphism group is \(S_n\). |
| \([n,n-1,2]_q\) \(q\)-ary parity-check code | An \([n,n-1,2]_q\) linear \(q\)-ary code whose codewords consist of the message string appended with a parity-check or zero-sum check digit such that the sum over all coordinates of each codeword is zero. |
References
- [1]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [2]
- M. Blaum, P. G. Farrell, H. C. A. van Tilborg, 1998. Array codes. Handbook of coding theory, 2 (Part 2), pp. 1855-1909.
- [3]
- L. Jin and C. Xing, “A Construction of New Quantum MDS Codes”, (2020) arXiv:1311.3009
- [4]
- X. Liu, L. Yu, and H. Liu, “New quantum codes from Hermitian dual-containing codes”, International Journal of Quantum Information 17, 1950006 (2019) DOI
- [5]
- L. Jin, S. Ling, J. Luo, and C. Xing, “Application of Classical Hermitian Self-Orthogonal MDS Codes to Quantum MDS Codes”, IEEE Transactions on Information Theory 56, 4735 (2010) DOI
- [6]
- D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
- [7]
- Z. Li, L.-J. Xing, and X.-M. Wang, “Quantum generalized Reed-Solomon codes: Unified framework for quantum maximum-distance-separable codes”, Physical Review A 77, (2008) arXiv:0812.4514 DOI
- [8]
- O. Geil and T. Høholdt, “On Hyperbolic Codes”, Lecture Notes in Computer Science 159 (2001) DOI
- [9]
- K. Saints and C. Heegard, “On hyperbolic cascaded Reed-Solomon codes”, Lecture Notes in Computer Science 291 (1993) DOI
- [10]
- Gui-Liang Feng and T. R. N. Rao, “Improved geometric Goppa codes. I. Basic theory”, IEEE Transactions on Information Theory 41, 1678 (1995) DOI
- [11]
- T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
- [12]
- D. Boucher and F. Ulmer, “Linear codes using skew polynomials with automorphisms and derivations”, Designs, Codes and Cryptography 70, 405 (2012) DOI
- [13]
- S. Liu, F. Manganiello, and F. R. Kschischang, “Construction and decoding of generalized skew-evaluation codes”, 2015 IEEE 14th Canadian Workshop on Information Theory (CWIT) 9 (2015) DOI
- [14]
- M. Shi, S. Li, T. Helleseth, and J.-L. Kim, “Binary self-orthogonal codes which meet the Griesmer bound or have optimal minimum distances”, (2023) arXiv:2303.16729
- [15]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [16]
- J. A. Harvey and G. W. Moore, “Moonshine, superconformal symmetry, and quantum error correction”, Journal of High Energy Physics 2020, (2020) arXiv:2003.13700 DOI