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)

Magnetization enumerator for LDPC codes - a statistical physics approach

Jort van Mourik, David Saad, Yoshiyuki Kabashima

Published Jun 25, 2003• 4 citations
Publisher

Abstract

We propose a method based on the magnetization enumerator to determine the critical noise level for Gallager type low density parity check error correcting codes (LDPC). Our method provides an appealingly simple interpretation to the relation between different decoding schemes, and provides more optimistic critical noise levels than those reported in the information theory literature.

DOI
10.1109/isit.2002.1023528

Related papers

Critical noise levels for low-density parity check decoding

Jort van Mourik, David Saad, Yoshiyuki Kabashima

We determine the critical noise level for decoding low-density parity check error-correcting codes based on the magnetization enumerator (M), rather than on the weight enumerator (W) employed in the information theory literature. The interpretation of our method is appealingly simple, and the relation between the different decoding schemes such as typical pairs decoding, MAP, and finite temperature decoding (MPM) becomes clear. In addition, our analysis provides an explanation for the difference in performance between MN and Gallager codes. Our results are more optimistic than those derived using the methods of information theory and are in excellent agreement with recent results from another statistical physics approach.

arXiv:cond-mat/0203159•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Aug 28, 2002•12 citations

Statistical mechanics of low-density parity-check codes

Yoshiyuki Kabashima, David Saad

We review recent theoretical progress on the statistical mechanics of error correcting codes, focusing on low-density parity-check (LDPC) codes in general, and on Gallager and MacKay–Neal codes in particular. By exploiting the relation between LDPC codes and Ising spin systems with multi-spin interactions, one can carry out a statistical mechanics based analysis that determines the practical and theoretical limitations of various code constructions, corresponding to dynamical and thermodynamical transitions, respectively, as well as the behaviour of error-exponents averaged over the corresponding code ensemble as a function of channel noise. We also contrast the results obtained using methods of statistical mechanics with those derived in the information theory literature, and show how these methods can be generalized to include other channel types and related communication problems.

Journal of Physics A Mathematical and General•Jan 28, 2004•84 citations

Tighter decoding reliability bound for Gallager’s error-correcting code

Yoshiyuki Kabashima, Naoya Sazuka A, Kazutaka Nakamura +1 more

Statistical physics is employed to evaluate the performance of error-correcting codes in the case of finite message length for an ensemble of Gallager's error correcting codes. We follow Gallager's approach of upper bounding the average decoding error rate, but invoke the replica method to reproduce the tightest general bound to date, and to improve on the most accurate zero-error noise level threshold reported in the literature. The relation between the methods used and those presented in the information theory literature are explored.

arXiv:cond-mat/0010173•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Sep 21, 2001•28 citations

Evaluating zero error noise thresholds by the replica method for Gallager code ensembles

Yoshiyuki Kabashima, Naoya Sazuka A, K. Nakamura +1 more

The replica method, developed in statistical physics, is employed in conjunction with Gallager's methodology to accurately evaluate zero error noise thresholds for Gallager code ensembles. Our approach generally provides more optimistic evaluations than those reported in the information theory literature for sparse matrices; the difference vanishes as the parity check matrix becomes dense.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•4 citations

Performance Evaluation Of Low Density Parity Check Codes

Othman Omran Khalifa, Sheroz Khan, Mohamad Zaid +1 more

This paper mainly about the study on one of the widely used error correcting codes that is Low parity check Codes (LDPC). In this paper, the Regular LDPC code has been discussed The LDPC codes explained in this paper is about the Regular Binary LDPC codes or the Gallager.

•Nov 24, 2007•15 citations

Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

Hua Xiao, Amir H. Banihashemi

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

IEEE Transactions on Communications•Jun 1, 2009•35 citations
We propose a method based on the magnetization enumerator to determine the critical noise level for Gallager type low density parity check error correcting codes (LDPC). Our method provides an appealingly simple interpretation to the relation between different decoding schemes, and provides more optimistic critical noise levels than those reported in the information theory literature.
We determine the critical noise level for decoding low-density parity check error-correcting codes based on the magnetization enumerator (M), rather than on the weight enumerator (W) employed in the information theory literature. The interpretation of our method is appealingly simple, and the relation between the different decoding schemes such as typical pairs decoding, MAP, and finite temperature decoding (MPM) becomes clear. In addition, our analysis provides an explanation for the difference in performance between MN and Gallager codes. Our results are more optimistic than those derived using the methods of information theory and are in excellent agreement with recent results from another statistical physics approach.
We review recent theoretical progress on the statistical mechanics of error correcting codes, focusing on low-density parity-check (LDPC) codes in general, and on Gallager and MacKay–Neal codes in particular. By exploiting the relation between LDPC codes and Ising spin systems with multi-spin interactions, one can carry out a statistical mechanics based analysis that determines the practical and theoretical limitations of various code constructions, corresponding to dynamical and thermodynamical transitions, respectively, as well as the behaviour of error-exponents averaged over the corresponding code ensemble as a function of channel noise. We also contrast the results obtained using methods of statistical mechanics with those derived in the information theory literature, and show how these methods can be generalized to include other channel types and related communication problems.
Statistical physics is employed to evaluate the performance of error-correcting codes in the case of finite message length for an ensemble of Gallager's error correcting codes. We follow Gallager's approach of upper bounding the average decoding error rate, but invoke the replica method to reproduce the tightest general bound to date, and to improve on the most accurate zero-error noise level threshold reported in the literature. The relation between the methods used and those presented in the information theory literature are explored.
The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.