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 | A \(q\)-ary LDPC code whose parity-check matrix has weight-two columns. Non-binary cycle LDPC codes for \(q\geq 32\) exihibit good performance [12–14]. |
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 [15]. |
Expander code | LDPC code whose parity-check matrix is derived from the adjacency matrix of bipartite expander graph [16] such as a Ramanujan graph or a Cayley graph of a projective special linear group over a finite field [17,18]. 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 [19]. |
Gallager (GL) code | The first LDPC code construction. 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. For example, the parity-check matrix \begin{align} \begin{pmatrix} 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \end{pmatrix} \tag*{(1)}\end{align} contains two subsets, each consisting of two rows, and the last two rows are obtained from the first two by exchanging the second and third columns. |
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. |
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 [20] 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\) [21]. |
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 [22] utilize Ramanujan graphs [17,18]. |
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 | LDPC code whose parity-check matrix is constructed using the lifting procedure (defined below) applied to the incident matrix of a sparse graph called, in this context, a protograph. 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 [23]. 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 [24]. |
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 [25]. |
Tanner-Sridhara-Fuja (TSF) code | Array QC-LDPC code constructed from a cyclically shifted identity matrix; see [26; Exam. 21.6.5]. |
Tornado code | Stub. |
\(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 | \(q\)-ary LDPC code whose parity-check matrix is constructed using the lifting procedure as well as using edge scaling, i.e., the ability to assign non-binary edge weights. |
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]
- X.-Yu. Hu and E. Eleftheriou, “Binary representation of cycle Tanner-graph GF(2/sup b/) codes”, 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577) (2004) DOI
- [13]
- R.-H. Peng and R.-R. Chen, “Design of Nonbinary Quasi-Cyclic LDPC Cycle Codes”, 2007 IEEE Information Theory Workshop (2007) DOI
- [14]
- C. Poulliat, M. Fossorier, and D. Declercq, “Design of regular (2,d/sub c/)-LDPC codes over GF(q) using their binary images”, IEEE Transactions on Communications 56, 1626 (2008) DOI
- [15]
- 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
- [16]
- S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
- [17]
- A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
- [18]
- G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
- [19]
- Heng Tang et al., “Codes on finite geometries”, IEEE Transactions on Information Theory 51, 572 (2005) DOI
- [20]
- 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
- [21]
- 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
- [22]
- 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
- [23]
- 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
- [24]
- Johnson, Sarah J. "Introducing low-density parity-check codes." University of Newcastle, Australia 1 (2006): 2006.
- [25]
- 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
- [26]
- C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI