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. |
| 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. |
| 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. |
| Block LDPC (B-LDPC) code | Member of a particular class of irregular QC-LDPC codes with efficient encoders. |
| 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 the points of \(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. |
| Griesmer code | A type of \(q\)-ary code whose parameters satisfy the Griesmer bound with equality. |
| 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 [17], and conformal field theory [18]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [19]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). |
| Hirschfeld code | A projective geometry code that is an example of an MDS code that is not an RS code; see [20; Exam. 7.6] for the description. |
| 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 [21] 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. |
| Linearized RS code | A linearized version of a skew RS code, i.e., an RS code constructed by evaluating skew polynomials [22,23]. |
| 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 \(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. |
| 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\) [24]. |
| 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 [25] utilize Ramanujan graphs [14,15]. |
| Maximum distance separable (MDS) code | A type of \(q\)-ary code whose parameters satisfy the Singleton bound with equality. |
| Multi-edge LDPC code | Irregular LDPC code whose construction generalizes those of the original examples of irregular LDPC as well as RA codes. |
| 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 \(GF(q)\). |
| Optimal LRC | An LRC whose parameters saturate a generalized Singleton bound. |
| Private information retrieval (PIR) code | A code used to obtain information from several servers privately, i.e., without the servers knowing what information was obtained. |
| 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. |
| 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. |
| Pyramid code | An LRC whose generator matrix is that of an RS code in standard form, but some of whose columns are split into multiple columns; see [26; Sec. 31.3.1.1] for an example. |
| 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 [27]. 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 coordinate from each codeword. |
| Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). |
| Regenerating code (RGC) | An \([n,k,d,\alpha,\beta,M]_q\) Regenerating Code \(\mathcal{C}\) is an erasure correcting code that encodes \(M\) symbols from \(GF(q)\) into an \(\alpha \times n\) matrix over \(GF(q)\), with each column of the matrix treated as a coordinate of a codeword. |
| 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 [28]. |
| 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. |
| 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 [29]. |
| 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 Hermitian or Garcia-Stichtenoth curves, that is constructed to be an LRC. 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 [30; Exam. 21.6.5]. |
| Tetracode | The \([4,2,3]_3\) self-dual MDS code that has connections to lattices [17]. |
| Tornado code | Linear binary code that is a precursor to fountain codes and whose encoding and decoding operations involve only XOR gates [31; Sec. 30.2]. |
| \([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. |
| \([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. |
| \(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 | 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]
- 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]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [20]
- S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
- [21]
- 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
- [22]
- D. Boucher and F. Ulmer, “Linear codes using skew polynomials with automorphisms and derivations”, Designs, Codes and Cryptography 70, 405 (2012) DOI
- [23]
- 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) (2015) DOI
- [24]
- 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
- [25]
- 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
- [26]
- V. Ramkumar, M. Vajha, S. B. Balaji, M. Nikhil Krishnan, B. Sasidharan, P. Vijay Kumar, "Codes for Distributed Storage." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [27]
- 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
- [28]
- Johnson, Sarah J. "Introducing low-density parity-check codes." University of Newcastle, Australia 1 (2006): 2006.
- [29]
- 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
- [30]
- C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [31]
- I. F. Blake, "Coding for Erasures and Fountain Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI