Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Codes on hypergraphs

Alexander Barg, Gilles Zémor

Published Jul 1, 2008• 3 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2008.4594967

Related papers

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.

arXiv:0911.4522•IEEE Transactions on Information Theory•Jan 21, 2011•12 citations

On the number of errors correctable with codes on graphs

Alexander Barg, Arya Mazumdar

We estimate the number of errors corrected by two different ensembles of codes on graphs (generalized LDPC codes), namely codes on regular bipartite graphs and their extension to hypergraphs.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•0 citations

Improved low-density parity-check codes using irregular graphs and belief propagation

Michael G. Luby, M. Amin Shokrolloahi, M. Mizenmacher +1 more

We construct new families of low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct more errors than previously known low-density codes. Our improved performance comes from using codes based on irregular random bipartite graphs, based on the work of Luby et al. (1997). Previously studied low-density codes have been derived from regular bipartite graphs. Initial experimental results for our irregular codes suggest that, with improvements, irregular codes may be able to match turbo code performance.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•142 citations

Multilevel expander codes

Alexander Barg, Gilles Zémor

We define multilevel codes on bipartite graphs that have properties analogous to multilevel serial concatenations. A decoding algorithm is described that corrects a proportion of errors equal to half the Blokh-Zyablov bound on the minimum distance. The error probability of this algorithm has exponent similar to that of serially concatenated multilevel codes.

arXiv:cs/0502079•Feb 19, 2005•0 citations

Graph-based codes and iterative decoding

Aamod Khandekar

The field of error correcting codes was revolutionized by the introduction of turbo codes [7] in 1993. These codes demonstrated dramatic performance improvements over any previously known codes, with significantly lower complexity. Since then, much progress has been made towards understanding the performance of these codes, as well as in using this understanding to design even better codes. This thesis takes a few more steps in both these directions. We develop a new technique, called the typical set bound, for analyzing the asymptotic performance of code ensembles based on their weight enumerators. This technique yields very tight bounds on the maximum-likelihood decoding threshold of code ensembles, and is powerful enough to reproduce Shannon's noisy coding theorem for the class of binary-input symmetric channels. We also introduce a new class of codes called irregular repeat-accumulate~(IRA) codes, which are adapted from the previously known class of repeat-accumulate~(RA) codes. These codes are competitive in terms of decoding performance with the class of irregular low-density parity-check~(LDPC) codes, which are arguably the best class of codes known today, at least for long block lengths. In addition, IRA codes have a significant advantage over irregular LDPC codes in terms of encoding complexity. We also derive an analytical bound regarding iterative decoding thresholds of code ensembles on general binary-input symmetric channels, an area in which theoretical results are currently lacking

•Jan 1, 2003•53 citations

Ensemble Weight Enumerators for Protograph LDPC Codes

D. Divsalar

Recently, LDPC codes with projected graph, or protograph structures have been proposed. In this paper, finite length ensemble weight enumerators for LDPC codes with protograph structures are obtained. Asymptotic results are derived as the block size goes to infinity. In particular, we are interested in obtaining ensemble average weight enumerators for protograph LDPC codes which have typical minimum distance that grows linearly with block size. As with irregular ensembles, linear minimum distance property is sensitive to the proportion of degree-2 variable nodes. In this paper, the derived results on ensemble weight enumerators show that linear minimum distance condition on degree distribution of unstructured irregular LDPC codes is a sufficient but not a necessary condition for protograph LDPC codes

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•67 citations
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.
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 construct new families of low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct more errors than previously known low-density codes. Our improved performance comes from using codes based on irregular random bipartite graphs, based on the work of Luby et al. (1997). Previously studied low-density codes have been derived from regular bipartite graphs. Initial experimental results for our irregular codes suggest that, with improvements, irregular codes may be able to match turbo code performance.
The field of error correcting codes was revolutionized by the introduction of turbo codes [7] in 1993. These codes demonstrated dramatic performance improvements over any previously known codes, with significantly lower complexity. Since then, much progress has been made towards understanding the performance of these codes, as well as in using this understanding to design even better codes. This thesis takes a few more steps in both these directions. We develop a new technique, called the typical set bound, for analyzing the asymptotic performance of code ensembles based on their weight enumerators. This technique yields very tight bounds on the maximum-likelihood decoding threshold of code ensembles, and is powerful enough to reproduce Shannon's noisy coding theorem for the class of binary-input symmetric channels. We also introduce a new class of codes called irregular repeat-accumulate~(IRA) codes, which are adapted from the previously known class of repeat-accumulate~(RA) codes. These codes are competitive in terms of decoding performance with the class of irregular low-density parity-check~(LDPC) codes, which are arguably the best class of codes known today, at least for long block lengths. In addition, IRA codes have a significant advantage over irregular LDPC codes in terms of encoding complexity. We also derive an analytical bound regarding iterative decoding thresholds of code ensembles on general binary-input symmetric channels, an area in which theoretical results are currently lacking
Recently, LDPC codes with projected graph, or protograph structures have been proposed. In this paper, finite length ensemble weight enumerators for LDPC codes with protograph structures are obtained. Asymptotic results are derived as the block size goes to infinity. In particular, we are interested in obtaining ensemble average weight enumerators for protograph LDPC codes which have typical minimum distance that grows linearly with block size. As with irregular ensembles, linear minimum distance property is sensitive to the proportion of degree-2 variable nodes. In this paper, the derived results on ensemble weight enumerators show that linear minimum distance condition on degree distribution of unstructured irregular LDPC codes is a sufficient but not a necessary condition for protograph LDPC codes