Here is a list of LDPC 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. |
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. |
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 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. |
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 [17] of known girth and relatively large stopping sets. |
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\) [18]. |
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 [19] utilize Ramanujan graphs [14,15]. |
Multi-edge LDPC code | Irregular LDPC code whose construction generalizes those of the original examples of irregular LDPC as well as RA codes. |
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. |
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 [20]. Their simple structure makes them useful for several wireless communication standards. |
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 [21]. |
Repeat-accumulate-accumulate (RAA) code | Generalization of the RA code in which two accumulators and permutations are used. |
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 [22]. |
Tanner-Sridhara-Fuja (TSF) code | Array QC-LDPC code constructed from a cyclically shifted identity matrix; see [23; Exam. 21.6.5]. |
Tornado code | Linear binary code that is a precursor to fountain codes and whose encoding and decoding operations involve only XOR gates [24; Sec. 30.2]. |
\(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 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. |
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]
- 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
- [18]
- 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
- [19]
- 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
- [20]
- 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
- [21]
- Johnson, Sarah J. "Introducing low-density parity-check codes." University of Newcastle, Australia 1 (2006): 2006.
- [22]
- 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
- [23]
- C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [24]
- I. F. Blake, "Coding for Erasures and Fountain Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI