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

Code | Description |
---|---|

Accumulate-repeat-accumulate (ARA) code | A generalization of the RA code in which the outer repetition-code encoding step is augmented with an acumulator acting on a fraction of the incoming bits. In addition, the code may be punctured after the final acumulating step. |

Algebraic LDPC code | LDPC code whose parity check matrix is constructed explicitly (i.e., non-randomly) from a particular graph [1,2] or an algebraic structure such as a combinatorial design [3–5], balanced incomplete block design [6], a partial geometry [7], or a generalized polygon [8,9]. The extra structure and/or symmetry [10] of these codes can often be used to gain a better understanding of their properties. |

Alternant code | Given a length-\(n\) GRS code \(C\) over \(GF(q^m)\), an alternant code is the \(GF(q)\)-subfield subcode of the dual of \(C\). |

Array-based LDPC (AB-LDPC) code | QC-LDPC code constructed deterministically from a disk array code known as a B-code. Its parity-check matrix admits a compact representation [11] and is related to RS codes. |

Availability code | Stub. |

Batch code | Binary code designed for minimizing the total amount of storage and the worst-case maximal load on any devices in a distributed system. |

Binary BCH code | Cyclic binary code of odd length \(n\) whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\) (see Cyclic-to-polynomial correspondence). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=2^r-1\) for some \(r\geq 2\). |

Block LDPC (B-LDPC) code | Member of a particular class of irregular QC-LDPC codes with efficient encoders. |

Bose–Chaudhuri–Hocquenghem (BCH) code | Cyclic \(q\)-ary code, with \(n\) and \(q\) relatively coprime, whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=q^r-1\) for some \(r\geq 2\). |

Classical Goppa code | Let \( G(x) \) be a polynomial describing a projective-plane curve with coefficients from \( GF(q^m) \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( GF(q^m) \) where \(q\) is prime, meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( GF(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} \). |

Cycle LDPC code | An LDPC code whose parity-check matrix forms the incidence matrix of a graph, i.e., has weight-two columns. |

Denniston code | Projective code that is part of a family of \([2^{a+i}+2^i-2^a,3,2^{a+i}-2^a]_{GF(2^a)}\) codes for \(i < a\) constructed using Denniston arcs. |

Difference-set cyclic (DSC) code | Cyclic LDPC code constructed deterministically from a difference set. Certain DCS codes satisfy more redundant constraints than Gallager codes and thus can outperform them [12]. |

Expander code | LDPC code whose parity-check matrix is derived from the adjacency matrix of bipartite expander graph [13] such as a Ramanujan graph or a Cayley graph of a projective special linear group over a finite field [14,15]. Expander codes admit efficient encoding and decoding algorithms and yield an explicit (i.e., non-random) asymptotically good LDPC code family. |

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

Extended IRA (eIRA) code | A generalization of the IRA code in which the outer LDGM code is replaced by a random sparse matrix containing no weight-two columns. |

Finite-geometry LDPC (FG-LDPC) code | LDPC code whose parity-check matrix is the incidence matrix of points and hyperplanes in either a Euclidean or a projective geometry. Such codes are called Euclidean-geometry LDPC (EG-LDPC) and projective-geometry LDPC (PG-LDPC), respectively. Such constructions have been generalized to incidence matrices of hyperplanes of different dimensions [16]. |

Gallager (GL) code | The first LDPC code. The rows of the parity check matrix of this regular code are divided into equal subsets, and columns in the first subset are randomly permuted to yield the corresponding rows in subsequent subsets. |

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 a set of distinct points \(\{\alpha_1,\cdots,\alpha_n\}\) in \(GF(q)\). |

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

Glynn code | The unique trace-Hermitian self-dual \([10,5,6]_9\) code, constructed using a 10-arc in \(PG(4,9)\) that is not a rational curve. |

Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [17] and sporadic simple groups [18]. Adding a parity bit to the code results in the \([24, 12, 8]\) extended Golay code. Up to equivalence, both codes are unique for their respective parameters [19]. Shortening the Golay code yields the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) shortened Golay codes [20]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [21,22]. |

Griesmer code | A \([n,k,d]_q\) code is a Griesmer code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the Griesmer bound \begin{align} n\geq\sum_{j=0}^{k-1}\left\lceil \frac{d}{q^{j}}\right\rceil ~, \tag*{(1)}\end{align} where \(\left\lceil x\right\rceil \) is the ceiling function, becomes an equality. |

Hadamard code | An \([2^m,m,2^{m-1}]\) balanced binary code dual to an extended Hamming 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)\)). |

Hermitian code | Evaluation AG code of rational functions evaluated on points lying on a Hermitian curve \(H(x,y) = x^{q+1} + y^{q+1} - 1\) over \(\mathbb{F}_q = GF(q)\) in either affine or projective space. Hermitian codes directly improve over RS codes in the sense that RS codes have length at most \(q\) while Hermitian codes have length \(q^3 + 1\). |

Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [17], and conformal field theory [23]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [24]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). |

Hsu-Anastasopoulos LDPC (HA-LDPC) code | A regular LDPC code obtained from a concatenation of a certain random regular LDPC code and a certain random LDGM code. Using rate-one LDGM codes eliminates high-weight codewords while admitting an amount of low-weight codewords that asymptotically vanishes, allowing code families to achieve the GV bound with high probability. |

Irregular LDPC code | An LDPC code whose parity-check matrix has a variable number of entries in each row or column. |

Irregular repeat-accumulate (IRA) code | A generalization of the RA code in which the outer 1-in-3 repetition encoding step is replaced by an LDGM code. A simple version is when different bits in the RA block are repeated a different number of times. |

Lazebnik-Ustimenko (LU) code | LDPC code whose Tanner graph comes from a particular family of \(q\)-regular graphs [25] of known girth and relatively large stopping sets. |

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

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 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 \(x\) and coordinate \(i\), \(x_i\) can be recovered from at most \(r\) other coordinates of \(x\). An \(r\)-locally recoverable code of length \(n\) and dimension \(k\) is denoted as an \((n,k,r)\) LRC code. The definition can be generalized to \(t\)-LRC code, if every coordinate is recoverable from \(t\) disjoint subsets of coordinates. |

Low-density parity-check (LDPC) code | A binary linear code with a sparse parity-check matrix. Alternatively, a member of an infinite family of \([n,k,d]\) codes for which the number of nonzero entries in each row and column of the parity-check matrix are both bounded above by a constant as \(n\to\infty\). |

MacKay-Neal LDPC (MN-LDPC) code | Codes whose parity-check matrix is constructed non-deterministically via the MacKay-Neal prescription. The parity-check matrix of an \((l,r,g\))-MN-LDPC code is of the form \((H_1~H_2)\), where \(H_1\) is a random binary matrix of column weight \(l\) and row weight \(r\), and \(H_2\) is a random binary matrix of column and row weight \(g\) [26]. |

Margulis LDPC code | Member of a class of LDPC codes deterministically constructed using a class of regular graphs with no short cycles. Related explicit LDPC constructions [27] utilize Ramanujan graphs [14,15]. |

Maximum distance separable (MDS) code | A \([n,k,d]_q\) binary or \(q\)-ary linear code is an MDS code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the Singleton bound \begin{align} d \leq n-k+1 \tag*{(2)}\end{align} becomes an equality. A code is called almost MDS (AMDS) when \(d=n-k\). A bound for general (i.e., nonlinear or unrestricted) \(q\)-ary codes can also be formulated; see [28; Thm. 1.9.10]. A code is near MDS (NMDS) if the code and its dual are mode AMDS. |

Multi-edge LDPC code | Irregular LDPC code whose construction generalizes those of the original examples of irregular LDPC as well as RA codes. |

Optimal LRC | An LRC whose parameters saturate a generalized Singleton bound. |

Parallel-recovery code | Stub. |

Projective RM (PRM) code | Reed-Muller code for nonzero points \(\{\alpha_1,\cdots,\alpha_n\}\) whose leftmost nonzero coordinate is one, corresponding to an evaluation code of polynomials over projective coordinates. |

Protograph LDPC code | Binary version of a \(q\)-ary protograph LDPC code. Its parity check matrix can be put into the form of a block matrix consisting of either a sum of permutation sub-matrices or the zero sub-matrix. |

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

Quasi-cyclic LDPC (QC-LDPC) code | LDPC code that can be put into quasi-cyclic form. Its parity check matrix can be put into the form of a block matrix consisting of either circulant permutation sub-matrices or the zero sub-matrix. Such codes are often constructed by lifting certain protographs into such block matrices [29]. Their simple structure makes them useful for several wireless communication standards. |

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

Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). |

Regular LDPC code | An LDPC code whose parity-check matrix has a fixed number of entries for each row or column. |

Repeat-accumulate (RA) code | An LDPC code whose parity-check matrix has weight-two columns arranged in a step-like pattern for its last columns [30]. |

Repeat-accumulate-accumulate (RAA) code | Generalization of the RA code in which two accumulators and permutations are used. |

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

Sequential-recovery code | Stub. |

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

Spatially coupled LDPC (SC-LDPC) code | LDPC code whose parity-check matrix is constructed by "spatially" coupling several copies of a regular LDPC parity-check matrix in chain-like fashion (or, more generally, in grid-like fashion) to yield a band matrix. A finite-length chain is then capped by imposing either open boundary conditions (yielding non-tail-biting SC-LDPC codes) or open boundary conditions (yielding tail-biting SC-LDPC codes); sometimes extra terminating vertices are added to the ends of the chain. Matrices corresponding to translationally invariant chains are called time-variant, and otherwise are called time-invariant. These codes can be constructed, e.g., using the lifting procedure or using edge-cutting vectors [31]. |

Tamo-Barg code | A family of \(q\)-ary polynomial evaluation codes that are optimal LRCs and for which \(q\) is comparable to \(n\). |

Tamo-Barg-Vladut code | Polynomial evaluation code on algebraic curves, such as Hermitain or Garcia-Stichtenoth curves, that is constructed to be an LRC code. Codes can be constructed to be be able to recover locally after one or more erasures as well as to tackle the availability problem. |

Tanner-Sridhara-Fuja (TSF) code | Array QC-LDPC code constructed from a cyclically shifted identity matrix; see [32; Exam. 21.6.5]. |

Tetracode | The \([4,2,3]_3\) self-dual MDS code that has connections to lattices [17]. |

Tornado code | Stub. |

\([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. |

\([2^m-1,m,2^{m-1}]\) simplex code | A member of the 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. The codewords form a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping. |

\([2^r-1,2^r-r-1,3]\) Hamming code | Member of an infinite family of perfect linear codes with parameters \([2^r-1,2^r-r-1, 3]\) for \(r \geq 2\). Their \(r \times (2^r-1) \) parity-check matrix \(H\) has all possible non-zero \(r\)-bit strings as its columns. Adding a parity check yields the \([2^r,2^r-r-1, 4]\) extended Hamming code. |

\([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. |

\([7,4,3]\) Hamming code | Second-smallest member of the Hamming code family. |

\(q\)-ary LDPC code | A \(q\)-ary linear code with a sparse parity-check matrix. Alternatively, a member of an infinite family of \([n,k,d]_q\) codes for which the number of nonzero entries in each row and column of the parity-check matrix are both bounded above by a constant as \(n\to\infty\). |

\(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 parity-check code | Also known as a sum-zero or zero-sum 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 protograph LDPC code | A \(q\)-ary LDPC code whose parity-check matrix is constructed using the lifting procedure applied to the incidence matrix of a sparse graph called, in this context, a protograph. An ability to assign non-binary edge weight called edge scaling can also be used in code construction. |

\(q\)-ary simplex code | An \([n,m,q^{m-1}]_q\) 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. |

## References

- [1]
- G. A. Margulis, “Explicit constructions of graphs without short cycles and low density codes”, Combinatorica 2, 71 (1982) DOI
- [2]
- C. A. Kelley, D. Sridhara, and J. Rosenthal, “Tree-Based Construction of LDPC Codes Having Good Pseudocodeword Weights”, IEEE Transactions on Information Theory 53, 1460 (2007) DOI
- [3]
- S. J. Johnson and S. R. Weller, “Regular low-density parity-check codes from combinatorial designs”, Proceedings 2001 IEEE Information Theory Workshop (Cat. No.01EX494) DOI
- [4]
- S. J. Johnson and S. R. Weller, “Construction of low-density parity-check codes from Kirkman triple systems”, GLOBECOM’01. IEEE Global Telecommunications Conference (Cat. No.01CH37270) DOI
- [5]
- S. J. Johnson and S. R. Weller, “Resolvable 2-designs for regular low-density parity-check codes”, IEEE Transactions on Communications 51, 1413 (2003) DOI
- [6]
- B. Vasic and O. Milenkovic, “Combinatorial Constructions of Low-Density Parity-Check Codes for Iterative Decoding”, IEEE Transactions on Information Theory 50, 1156 (2004) DOI
- [7]
- S. J. Johnson and S. R. Weller, “Codes for iterative decoding from partial geometries”, Proceedings IEEE International Symposium on Information Theory, DOI
- [8]
- P. O. Vontobel and R. M. Tanner, “Construction of codes based on finite generalized quadrangles for iterative decoding”, Proceedings. 2001 IEEE International Symposium on Information Theory (IEEE Cat. No.01CH37252) DOI
- [9]
- Z. Liu and D. A. Pados, “LDPC Codes From Generalized Polygons”, IEEE Transactions on Information Theory 51, 3890 (2005) DOI
- [10]
- Tanner, R. Michael, Deepak Sridhara, and Tom Fuja. "A class of group-structured LDPC codes." Proc. ISTA. 2001.
- [11]
- T. Mittelholzer, “Efficient encoding and minimum distance bounds of Reed-Solomon-type array codes”, Proceedings IEEE International Symposium on Information Theory, DOI
- [12]
- D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications”, Codes, Systems, and Graphical Models 113 (2001) DOI
- [13]
- S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
- [14]
- A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
- [15]
- G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
- [16]
- Heng Tang et al., “Codes on finite geometries”, IEEE Transactions on Information Theory 51, 572 (2005) DOI
- [17]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [18]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [19]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [20]
- J. H. Conway and N. J. A. Sloane, “Orbit and coset analysis of the Golay and related codes”, IEEE Transactions on Information Theory 36, 1038 (1990) DOI
- [21]
- W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
- [22]
- C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
- [23]
- 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
- [24]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [25]
- F. Lazebnik and V. A. Ustimenko, “Explicit construction of graphs with an arbitrary large girth and of large size”, Discrete Applied Mathematics 60, 275 (1995) DOI
- [26]
- K. KASAI and K. SAKANIWA, “Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A, 2161 (2011) arXiv:1102.4612 DOI
- [27]
- J. Rosenthal and P. O. Vontobel, “Constructions of regular and irregular LDPC codes using Ramanujan graphs and ideas from Margulis”, Proceedings. 2001 IEEE International Symposium on Information Theory (IEEE Cat. No.01CH37252) DOI
- [28]
- W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [29]
- I. E. Bocharova et al., “Searching for Voltage Graph-Based LDPC Tailbiting Codes With Large Girth”, IEEE Transactions on Information Theory 58, 2265 (2012) arXiv:1108.0840 DOI
- [30]
- Johnson, Sarah J. "Introducing low-density parity-check codes." University of Newcastle, Australia 1 (2006): 2006.
- [31]
- H. Esfahanizadeh, A. Hareedy, and L. Dolecek, “Finite-Length Construction of High Performance Spatially-Coupled Codes via Optimized Partitioning and Lifting”, IEEE Transactions on Communications 67, 3 (2019) DOI
- [32]
- C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI