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 construction over finite fields. As in the finite-field case, codewords are obtained by evaluating low-degree polynomials at distinct real or complex evaluation points. |
| 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 onto 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 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]. |
| Dual linear code | For any \([n,k]_q\) linear code \(C\), the dual code is the set of \(q\)-ary strings that are orthogonal to the codewords of \(C\) under a particular inner product. |
| Extended GRS code | A GRS code extended by one extra coordinate to form an \([n+1,k,n-k+2]_q\) MDS code. In projective language, this corresponds to adding one more evaluation point, often interpreted as the point at infinity; in suitable equivalent descriptions, one may instead use an affine point such as \(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 code obtained from an RS code by bundling consecutive symbols into larger alphabet symbols. This preserves the algebraic structure of the parent RS code while lowering the block length over an extension alphabet, and it is a key ingredient in capacity-approaching list-decoding constructions. |
| 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. |
| Generalized Srivastava code | An \([n,k \geq n-mst,d \geq st+1 ]_q\) alternant code defined for \(n+s\) distinct elements \(\alpha_1,\alpha_2,\cdots,\alpha_n,w_1,w_2,\cdots,w_s\) and \(n\) nonzero elements \(z_1,z_2,\cdots,z_n\) of \(\mathbb{F}_{q^m}\). |
| Goppa code | A linear \(q\)-ary code defined from a polynomial \(G(x)\) over an extension field and a set of evaluation points \(L\) avoiding the roots of \(G\). Goppa codes form a central family of alternant codes, admit efficient algebraic decoding algorithms, and include the binary Goppa codes used in the McEliece cryptosystem. They can also be viewed as residue AG codes on the projective line. |
| Hermitian code | Evaluation AG code of rational functions on a Hermitian curve over \(\mathbb{F}_{q^2}\). |
| 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 | Projective code constructed from a hyperoval in the projective plane \(PG(2,q)\), where \(q\) is even. Since a hyperoval is a set of \(q+2\) points with no three collinear, the corresponding projective code has parameters \([q+2,3,q]_q\) [12; Exam. 19.2.1]; the \([6,3,4]_4\) hexacode is the smallest example. |
| 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*{(1)}\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\) is 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 field elements \(\alpha,\beta \in \mathbb{F}_q\). 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 [13,14]. |
| 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 \(q\)-ary linear 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 yield 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\) do 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\). A choice of \(k\) linearly independent columns determines 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 | 1D translationally invariant qubit stabilizer code 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 element of randomness somewhere in their construction. Members of this class range from fully non-deterministic codes to codes whose multi-step construction is deterministic except for 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. Majority decoding requires \(n\) to be odd in order to avoid ties. 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\) [15]. They form a \((2^m,2^{m+1})\) biorthogonal 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 [16]. |
| \([4,2,3]_4\) RS\(_4\) code | A Type II Euclidean self-dual extended RS code that is the smallest quaternary extended QR code [1; pg. 296][17; Sec. 2.4.2]. |
| \([6,3,4]_4\) Hexacode | The \([6,3,4]_4\) Hermitian self-dual MDS code that has connections to projective geometry, lattices [16], and conformal field theory [18]. |
| \([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, and its parity-check matrix is a row vector of all ones. 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. |
| \(q\)-ary repetition code | An \([n,1,n]_q\) code consisting of codewords \((j,j,\cdots,j)\) for \(j \in \mathbb{F}_q\). |
| \(q\)-ary simplex code | An \([n,m,q^{m-1}]_q\) equidistant projective code with \(n=\frac{q^m-1}{q-1}\), denoted as \(S(q,m)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,q)\), with each column being a chosen representative of the corresponding element. All nonzero simplex codewords have a constant weight of \(q^{m-1}\) [19,20]. |
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]
- A. E. Brouwer, “Two-weight Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [13]
- D. Boucher and F. Ulmer, “Linear codes using skew polynomials with automorphisms and derivations”, Designs, Codes and Cryptography 70, 405 (2012) DOI
- [14]
- 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
- [15]
- 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
- [16]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [17]
- Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
- [18]
- 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
- [19]
- A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
- [20]
- E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI