Weaknesses of Margulis and Ramanujan-Margulis low-density parity-check cCodes
By David John Cameron MacKay, Michael S. Postol. MFCSIT, 2003
339 citations recorded by the source corpus.
Abstract We report weaknesses in two algebraic constructions of low-density parity-check codes based on expander graphs. The Margulis construction gives a code with near-codewords, which cause problems for the sum-product decoder; The Ramanujan-Margulis construction gives a code with low-weight codewords, which produce an error-floor.
Subfields: Artificial Intelligence, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/a1bc36f0f53c5398ea62b4d75212d68055157b83
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Marc P. C. Fossorier
- T. Richardson
- Graeme J. Mitchison
- David John Cameron MacKay
- P. L. Mcfadden
- Pavel Panteleev
- Gleb Kalachev
In Computer Networks and Communications
- Marc P. C. Fossorier
- David John Cameron MacKay
- Graeme J. Mitchison
- P. L. Mcfadden
- T. Richardson
- David Declercq
- Jinghu Chen
- Evangelos Eleftheriou
Citations in the corpus
- Error Floors of LDPC Codes (2003, background): “The source of the problem is identified in [2] as certain “near codewords” in the graph.”
- Sparse-graph codes for quantum error correction (2003, background): “A small value of corresponds to a quite-probable error pattern, while the small value of indicates that only a few check-sums are affected by these error patterns [21], [24].”
- Quasicyclic low-density parity-check codes from circulant permutation matrices (2004, background): “These simple results suggest that when constructing families of LDPC codes, either relatively large girth (i.e., g > 12), or additional constraints such as large minimum distance, a large number of redundant check sums, or appropriate coset weight distribution (see [26] ) have to be considered.”