Margulis LDPC code[1]
Description
Member of a class of LDPC codes deterministically constructed using a class of regular graphs with no short cycles. Related explicit LDPC constructions [2] utilize Ramanujan graphs [3,4].
Encoding
Efficient encoder improving over the original Gallager encoder [1].
Parents
- Cycle LDPC code — Margulis LDPC codes are examples of cycle codes for particular large-girth graphs [5].
- Algebraic LDPC code
References
- [1]
- G. A. Margulis, “Explicit constructions of graphs without short cycles and low density codes”, Combinatorica 2, 71 (1982) DOI
- [2]
- 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
- [3]
- A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
- [4]
- G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
- [5]
- G. Zémor, “On Cayley Graphs, Surface Codes, and the Limits of Homological Coding for Quantum Error Correction”, Lecture Notes in Computer Science 259 (2009) DOI
Page edit log
- Victor V. Albert (2023-05-04) — most recent
Cite as:
“Margulis LDPC code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/margulis_ldpc