Here is a list of codes related to locally correctable codes.
| Code | Description |
|---|---|
| Analog code | Encodes states (codewords) into coordinates in the \(n\)-dimensional (real or complex) coordinate space (\(\mathbb{R}^n\) or \(\mathbb{C}^n\)). Codes for storing discrete sets of symbols include sphere packings, tilings, and any other codes that use real or complex numbers for encoding. The number of codewords may be infinite because the coordinate space is infinite, so various restricted versions have to be constructed in practice. |
| 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. |
| Five-qubit perfect code | Five-qubit cyclic stabilizer code that is the smallest qubit stabilizer code to correct a single-qubit error. |
| Generalized RM (GRM) code | Reed-Muller code GRM\(_q(r,m)\) of length \(n=q^m\) over \(GF(q)\) with \(0\leq r\leq m(q-1)\). Its codewords are evaluations of the set of all degree-\(\leq r\) polynomials in \(m\) variables at the points of \(GF(q)\). |
| Hadamard code | An \([2^m,m,2^{m-1}]\) balanced binary code. The \([2^m,m+1,2^{m-1}]\) augmented Hadamard code is the first-order RM code (a.k.a. RM\((1,m)\)), while the \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)). |
| Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [1], and conformal field theory [2]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [3]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). |
| Locally correctable code (LCC) | Recall that a block code encodes a length-\(k\) message into a length-\(n\) codeword, which is then sent through a noise channel to yield an error word. Informally, an LCC is a block code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). |
| Locally decodable code (LDC) | Recall that a block code encodes a length-\(k\) message into a length-\(n\) codeword, which is then sent through a noise channel to yield an error word. Informally, an LDC is a block code for which one can recover any coordinate of the message from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). Efficiency of the correction is quantified by the code's query complexity \(r\), and correction is performed by sampling subsets of \(r\) bits. |
| Locally testable code (LTC) | Code for which one can efficiently check whether a given string is a codeword or is far from a codeword. Efficiency of the verification is quantified by the code's query complexity \(u\), while effectiveness is quantified by the code's soundness \(R\). |
| Multiplicity code | A generalization of an \(m\)-variate polynomial evaluation code based on evaluating polynomials and \(s\) of their derivatives at all points in \(GF(q)^m\). Originally proposed for coding using the Rosenbloom-Tsfasman metric [4]. Univariate (\(m=1\)) [4,5] and multivariante (\(m>1\)) [6] codes have been proposed. |
| Projective RM (PRM) code | Reed-Muller code for nonzero points \(\{\alpha_1,\cdots,\alpha_n\}\) with \(n=m+1\) whose leftmost nonzero coordinate is one, corresponding to an evaluation code of polynomials over projective coordinates. |
| 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 irregular convolutional code (QIRCC) | Quantum convolutional code whose stabilizer group consists of different constant-size subsets. |
| Quantum locally recoverable code (QLRC) | A QLRC of locality \(r\) is a block quantum code whose code states can be recovered after a single erasure by performing a recovery map on at most \(r\) subsystems. |
| Quantum turbo code | A quantum version of the turbo code, obtained from an interleaved serial quantum concatenation [7; Def. 30] of quantum convolutional codes. |
| 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. |
| 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\). |
| 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\). |
| Tetracode | The \([4,2,3]_3\) self-dual MDS code that has connections to lattices [1]. |
| \((5,1,2)\)-convolutional code | Family of quantum convolutional codes that are 1D lattice generalizations of the five-qubit perfect code, with the former''s lattice-translation symmetry being the extension of the latter''s cyclic permutation symmetry. |
| \([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\). They form a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping. |
| \([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. |
| \(q\)-ary linear LCC | A linear code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). |
References
- [1]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [2]
- 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
- [3]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [4]
- M. Yu. Rosenbloom, M. A. Tsfasman, “Codes for the m-Metric”, Probl. Peredachi Inf., 33:1 (1997), 55–63; Problems Inform. Transmission, 33:1 (1997), 45–52
- [5]
- Rasmus R. Nielsen. List decoding of linear block codes. PhD thesis, Technical University of Denmark, 2001
- [6]
- S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
- [7]
- D. Poulin, J.-P. Tillich, and H. Ollivier, “Quantum serial turbo-codes”, (2009) arXiv:0712.2888