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

arXiv:cond-mat/0203159 · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics

Critical noise levels for low-density parity check decoding

Jort van Mourik, David Saad, Yoshiyuki Kabashima

Published Aug 28, 2002• 12 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreve.66.026705

Related papers

Magnetization enumerator for LDPC codes - a statistical physics approach

Jort van Mourik, David Saad, Yoshiyuki Kabashima

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•4 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

低密度パリティ検査符号の統計力学的解析(修士論文(1998年度))

Tatsuto Murayama

The performance of low-density parity-check codes is investigated via methods of statistical mechanics. Low-density parity-check codes is first invented by Gallager, which was abandoned shortly after its introduction due to the limited computational abilities and recently rediscovered by MacKay and Neal as MN codes. In these codes, a message is encoded to the codeword which comprises products of the message bits selected by two randomly-constructed sparse matrices. The typical case analysis of statistical mechanics indicates a practical property of the particular family of the codes, which could not be found within the framework of worst case analysis. Further, decoding aspects are considered by investigating solutions obtained by a mean field approach, which is identical to the commonly used belief propagation.

•Sep 20, 1999•0 citations

Low-density Parity-Check decoding Algorithms

Florent Pirou

Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.

•Jan 1, 2004•0 citations

Typical performance of regular low-density parity-check codes over general symmetric channels

Toshiyuki Tanaka, David Saad

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. Relationship between the free energy in statistical-mechanics approach and the mutual information used in the information-theory literature is established within a general framework; Gallager and MacKay–Neal codes are studied as specific examples of LDPC codes. It is shown that basic properties of these codes known for particular channels, including their potential to saturate Shannon's bound, hold for general symmetric channels. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel models.

arXiv:cond-mat/0204554•Journal of Physics A Mathematical and General•Oct 15, 2003•17 citations
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 codes is investigated via methods of statistical mechanics. Low-density parity-check codes is first invented by Gallager, which was abandoned shortly after its introduction due to the limited computational abilities and recently rediscovered by MacKay and Neal as MN codes. In these codes, a message is encoded to the codeword which comprises products of the message bits selected by two randomly-constructed sparse matrices. The typical case analysis of statistical mechanics indicates a practical property of the particular family of the codes, which could not be found within the framework of worst case analysis. Further, decoding aspects are considered by investigating solutions obtained by a mean field approach, which is identical to the commonly used belief propagation.
Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.
Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. Relationship between the free energy in statistical-mechanics approach and the mutual information used in the information-theory literature is established within a general framework; Gallager and MacKay–Neal codes are studied as specific examples of LDPC codes. It is shown that basic properties of these codes known for particular channels, including their potential to saturate Shannon's bound, hold for general symmetric channels. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel models.