aqora

Codes on hypergraphs

Alexander Barg, Gilles Zémor

A generalization of codes on regular bipartite graphs is given by a family of codes on hypergraphs. We derive the average weight distribution and estimate the minimum distance of codes in the random ensemble of hypergraph codes. We also propose an iterative decoding algorithm of hypergraph codes that corrects a larger proportion of errors than known previously for this code family.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20083 citations

Sufficient Conditions for a Regular LDPC Code Better than an Irregular LDPC Code

MiyamotoShinya, KasaiKenta, SakaniwaKohichi

Decoding performance of LDPC (Low-Density Parity-Check) codes is highly dependent on the degree distributions of the Tanner graphs which define the LDPC codes. We compare two LDPC code ensembles, o...

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesFeb 1, 20070 citations

On Graph Constructions for LDPC Codes by Quasi-Cyclic Extension

R. Michael Tanner

Springer eBooksJan 1, 200210 citations

On the Number of Errors Correctable with Codes on Graphs

Alexander Barg, Arya Mazumdar

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.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.

arXiv:0911.4522IEEE Transactions on Information TheoryJan 21, 201112 citations

The Block Error Probability of Detailedly Represented Irregular LDPC Code Ensembles Under Maximum Likelihood Decoding

健太笠井, Kenta Kasai

Mar 1, 20060 citations

On the Error Correction of Iterative Bounded Distance Decoding of Generalized LDPC Codes

David Burshtein

Consider an ensemble of regular generalized LDPC (GLDPC) codes and assume that the same component code is associated with each parity check node. To decode a GLDPC code from the ensemble, we use the bit flipping bounded distance decoding algorithm, which is an extension of the bit flipping algorithm for LDPC codes. Previous work has shown conditions, under which, for a typical code in the ensemble with blocklength sufficiently large, a positive constant fraction of worst case errors can be corrected. In this work we first show that these requirements can be relaxed for ensembles with small left degrees. While previous work on GLDPC codes has considered expander graph arguments, our analysis formulates a necessary condition that the Tanner graph needs to satisfy for a failure event and then shows that the probability of this event vanishes for a sufficiently large blocklength. We then extend the analysis to random error correction and derive a lower bound on the fraction of random errors that can be corrected asymptotically. We discuss the extension of our results to non-binary GLDPC codes and present numerical examples.Consider an ensemble of regular generalized LDPC (GLDPC) codes and assume that the same component code is associated with each parity check node. To decode a GLDPC code from the ensemble, we use the bit flipping bounded distance decoding algorithm, which is an extension of the bit flipping algorithm for LDPC codes. Previous work has shown conditions, under which, for a typical code in the ensemble with blocklength sufficiently large, a positive constant fraction of worst case errors can be corrected. In this work we first show that these requirements can be relaxed for ensembles with small left degrees. While previous work on GLDPC codes has considered expander graph arguments, our analysis formulates a necessary condition that the Tanner graph needs to satisfy for a failure event and then shows that the probability of this event vanishes for a sufficiently large blocklength. We then extend the analysis to random error correction and derive a lower bound on the fraction of random errors that can be corrected asymptotically. We discuss the extension of our results to non-binary GLDPC codes and present numerical examples.

arXiv:2507.12073IEEE Transactions on Information TheorySep 16, 20250 citations

On the number of errors correctable with codes on graphs

Abstract

Related papers

On the number of errors correctable with codes on graphs

Abstract

Related papers