Alternative names: Margulis-Gabber-Galil LDPC code.
Description
Member of a class of LDPC codes deterministically constructed from explicit sparse regular expander graphs. The underlying Margulis-Gabber-Galil graph family provides explicit expanders [1,2], yielding deterministic sparse parity-check matrices. Related explicit LDPC constructions [3] utilize Ramanujan graphs [4,5].Primary Hierarchy
Low-density parity-check (LDPC) code\(q\)-ary LDPC Tanner Linear \(q\)-ary LRC Distributed-storage ECC
Cycle LDPC code\(q\)-ary LDPC Tanner Projective geometry Linear \(q\)-ary Linear code over \(\mathbb{Z}_q\) LRC Distributed-storage ECC
Parents
Margulis LDPC codes are examples of cycle codes for particular large-girth graphs [6].
Algebraic LDPC code\(q\)-ary LDPC Tanner Linear \(q\)-ary Linear code over \(\mathbb{Z}_q\) LRC Distributed-storage ECC
Margulis LDPC code
References
- [1]
- G. A. Margulis, “Explicit constructions of graphs without short cycles and low density codes”, Combinatorica 2, 71 (1982) DOI
- [2]
- O. Gabber and Z. Galil, “Explicit constructions of linear-sized superconcentrators”, Journal of Computer and System Sciences 22, 407 (1981) DOI
- [3]
- 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) 4 DOI
- [4]
- A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
- [5]
- G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
- [6]
- 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