Description
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], a generalized polygon [8,9], or a Latin square [10–12]. The extra structure and/or symmetry [13] of these codes can often be used to gain a better understanding of their properties.Cousins
- Combinatorial design— Combinatorial designs can be used to construct explicit LDPC codes [3–5].
- Protograph LDPC code— Some deterministic protograph LDPC codes [14] can be obtained from the theory of voltage graphs [15,16].
- Quantum LDPC (QLDPC) code— Algebraic LDPC codes made from Latin squares can be used to make QLDPC codes [17; Ch. 15].
Primary Hierarchy
Low-density parity-check (LDPC) code\(q\)-ary LDPC Tanner Linear \(q\)-ary LRC Distributed-storage ECC
Parents
Algebraic LDPC code
Children
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]
- O. Milenkovic and S. Laendner, “Analysis of the cycle-structure of LDPC codes based on Latin squares”, 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577) 777 (2004) DOI
- [11]
- S. Laendner and O. Milenkovic, “LDPC Codes Based on Latin Squares: Cycle Structure, Stopping Set, and Trapping Set Analysis”, IEEE Transactions on Communications 55, 303 (2007) DOI
- [12]
- L. Zhang, Q. Huang, S. Lin, K. Abdel-Ghaffar, and I. F. Blake, “Quasi-Cyclic LDPC Codes: An Algebraic Construction, Rank Analysis, and Codes on Latin Squares”, IEEE Transactions on Communications 58, 3126 (2010) DOI
- [13]
- Tanner, R. Michael, Deepak Sridhara, and Tom Fuja. "A class of group-structured LDPC codes." Proc. ISTA. 2001.
- [14]
- C. A. Kelley, “On codes designed via algebraic lifts of graphs”, 2008 46th Annual Allerton Conference on Communication, Control, and Computing (2008) DOI
- [15]
- C. A. Kelley and J. L. Walker, “LDPC codes from voltage graphs”, 2008 IEEE International Symposium on Information Theory (2008) DOI
- [16]
- L. W. Beineke, R. J. Wilson, J. L. Gross, and T. W. Tucker, editors , Topics in Topological Graph Theory (Cambridge University Press, 2009) DOI
- [17]
- S. A. Aly, “On Quantum and Classical Error Control Codes: Constructions and Applications”, (2008) arXiv:0812.5104
Page edit log
- Victor V. Albert (2023-05-09) — most recent
Cite as:
“Algebraic LDPC code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/algebraic_ldpc