Here is a list of codes related to locally correctable codes.

[Jump to code graph excerpt]

Code Description
Analog code Encodes states (codewords) into continuous 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.
Generalized RM (GRM) code Extensions of RM codes to \(q\)-ary coordinates that can be described as multivariate polynomial evaluation codes over affine or projective space.
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)\)).
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 \(\mathbb{F}_q^m\). Originally proposed for coding using the Rosenbloom-Tsfasman metric [1]. Univariate (\(m=1\)) [1,2] and multivariante (\(m>1\)) [3] codes have been proposed.
Projective RM (PRM) code GRM 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 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.
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\).
\([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\) [4]. 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}\) [5; 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 [6].
\([6,3,4]_4\) Hexacode The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [6], and conformal field theory [7].
\([7,3,4]\) simplex code Second-smallest member of the simplex code family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(2,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((8,9)\) simplex 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.
\([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\).
\(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\)).
\(q\)-ary repetition code An \([n,1,n]_q\) code encoding consisting of codewords \((j,j,\cdots,j)\) for \(j \in \mathbb{F}_q\). The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information.
\(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}\) [8,9].

References

[1]
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
[2]
Rasmus R. Nielsen. List decoding of linear block codes. PhD thesis, Technical University of Denmark, 2001
[3]
S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
[4]
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
[5]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[6]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[7]
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
[8]
A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
[9]
E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI