On the Number of Errors Correctable with Codes on Graphs

DOI10.1109/TIT.2010.2094812MaRDI QIDQ5281083zbMATH OpenFDO

Authors Alexander Barg, Arya Mazumdar

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.4522

Mathematics Subject Classification ID

Applications of graph theory (05C90) Hypergraphs (05C65) Combinatorial codes (94B25) Decoding (94B35) Synchronization error-correcting codes (94B50)

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.

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.)
• scientific article; zbMATH DE number 5953464 (Why is no real title available?)
• 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)