On the Number of Errors Correctable with Codes on Graphs
From MaRDI portal
Publication:5281083
DOI10.1109/TIT.2010.2094812zbMATH Open1366.94737arXiv0911.4522MaRDI QIDQ5281083FDOQ5281083
Authors: Alexander Barg, Arya Mazumdar 
Publication date: 27 July 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: We study ensembles of codes on graphs (generalized low-density parity-check, or LDPC codes) constructed from random graphs and fixed local constrained codes, and their extension to codes on hypergraphs. It is known that the average minimum distance of codes in these ensembles grows linearly with the code length. We show that these codes can correct a linearly growing number of errors under simple iterative decoding algorithms. In particular, we show that this property extends to codes constructed by parallel concatenation of Hamming codes and other codes with small minimum distance. Previously known results that proved this property for graph codes relied on graph expansion and required the choice of local codes with large distance relative to their length.
Full work available at URL: https://arxiv.org/abs/0911.4522
Applications of graph theory (05C90) Hypergraphs (05C65) Combinatorial codes (94B25) Decoding (94B35) Synchronization error-correcting codes (94B50)
Cited In (9)
- Double and Triple Node-Erasure-Correcting Codes Over Complete Graphs
- Analysis of the relation between properties of LDPC codes and the Tanner graph
- Bounds on codes derived by counting components in Varshamov graphs
- The zero-error side information problem and chromatic numbers (Corresp.)
- Title not available (Why is that?)
- Decay of Correlations for Sparse Graph Error Correcting Codes
- Error-correcting codes from graphs
- On the multiple threshold decoding of LDPC codes over \(\mathrm{GF}(q)\)
- Error-correcting codes from \(k\)-resolving sets
This page was built for publication: On the Number of Errors Correctable with Codes on Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281083)
