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

Belief revision and small loops in Gallager-type error-correcting codes

Doubez, M.

Published Jan 1, 2000• 0 citations
Publisher

Abstract

Gallager-type error-correcting codes are low density parity check codes (LDPC) which may in specific case nearly saturate Shannon’s bound. They are based on the construction of two very sparse matrices, various structures of which have been studied in recent years. We will mainly focus here on constructions that have recently been studied by Kanter and Saad. The aim of this project is to examine the performance of two different decoding LDPC algorithms, belief propagation and belief revision within this framework, as well as that of different coding methods (MN vs. Gallager codes).We will also look at the effect of removing small loops in the matrices on the code’s performance.

DOI
10.48780/publications.aston.ac.uk.00021452

Related papers

Good error-correcting codes based on very sparse matrices

David Mackay

We report theoretical and empirical properties of Gallager's (1963) low density parity check codes on Gaussian channels. It can be proved that, given an optimal decoder, these codes asymptotically approach the Shannon limit. With a practical 'belief propagation' decoder, performance substantially better than that of standard convolutional and concatenated codes can be achieved; indeed the performance is almost as close to the Shannon limit as that of turbo codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 22, 2002•183 citations

Typical Performance of Gallager-Type Error-Correcting Codes

Yoshiyuki Kabashima, Tatsuto Murayama, David Saad

The performance of Gallager's error-correcting code is investigated via methods of statistical physics. In this approach, the transmitted codeword comprises products of the original message bits selected by two randomly constructed sparse matrices; the number of nonzero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity is saturated for many of the codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the Thouless-Anderson-Palmer approach which is identical to the commonly used belief-propagation-based decoding.

arXiv:cond-mat/9908104•Physical Review Letters•Feb 7, 2000•109 citations

A comprehensive Study of Decoding Algorithms for Low Density Parity-Check(LDPC)

C S Anil Kumar, M Vedhashri, L Vanditha +2 more

The near-capacity performance and effective decoding algorithms of Low-Density Parity-Check (LDPC) codes have made them a mainstay of contemporary error correction. With an emphasis on iterative techniques like the Belief Propagation (BP) algorithm, the Min-Sum algorithm, and their variations, this paper offers a thorough analysis of decoding algorithms for LDPC codes. We investigate the trade-offs between various algorithmic techniques’ computational complexity, decoding latency, and error correction performance. Particular focus is placed on new methods and hardware-friendly algorithms that are tailored for next-generation communication systems, such 5 G and beyond.

International Conference on Knowledge Engineering and Communication Systems (ICKECS)•Apr 28, 2025•0 citations

Regular and Irregular Gallager-zype Error-Correcting Codes

Yoshiyuki Kabashima, Tatsuto Murayama, David Saad +1 more

The performance of regular and irregular Gallager-type error-correcting code is investigated via methods of statistical physics. The transmitted codeword comprises products of the original message bits selected by two randomly-constructed sparse matrices; the number of non-zero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity may be saturated in equilibrium for many of the regular codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding. We show that irregular codes may saturate Shannon's capacity but with improved dynamical properties.

neural information processing systems•Nov 29, 1999•1 citation

Capacity-Approaching Low-Density Parity-Check Codes

Pierre J. Garrigues

The class of low-density parity-check (LDPC) codes was introduced by Gallager in his thesis in 1961 [2]. Until the invention of turbo codes, they were largely neglected, but received a lot of interest lately, due to the possibility of designing LDPC codes within 0.0045 dB of the Shannon limit. We review in this project techniques used to analyze the performance of LDPC codes under a message-passing decoding algorithm, namely belief propagation (BP) [4][5]. This analysis gives us the tools to design good LDPC codes. We will first take the simpler example of transmission over the class of binary erasure channels (BEC). We will then see how it is possible to extend the results for the BEC to the much more general class of symmetric channels.

•Jan 1, 2005•0 citations

Advanced decoding technics for law density parity check codes decoding

Allaoui, Y.

Error-correcting codes based on very sparse matrices provide the best performance to date. We will focus on improving the decoding of Low Density Parity Checks Codes by examining a new variant of belief propagation for this problem. This new variant is based on techniques such as time averaging and prior biasing. Results obtained by extensive simulations show that, well combined, these techniques bring a modest improvement to BP decoding performance. We also studied the possibility of parallelism, which consists of breaking the algorithm in independent pieces that can be solved simultaneously on different computer nodes. But the time spent in inter-communication between the different machines slows the process and prevent the parallelisation to be as fast as expected.

•Jan 1, 2004•0 citations
Gallager-type error-correcting codes are low density parity check codes (LDPC) which may in specific case nearly saturate Shannon’s bound. They are based on the construction of two very sparse matrices, various structures of which have been studied in recent years. We will mainly focus here on constructions that have recently been studied by Kanter and Saad. The aim of this project is to examine the performance of two different decoding LDPC algorithms, belief propagation and belief revision within this framework, as well as that of different coding methods (MN vs. Gallager codes).We will also look at the effect of removing small loops in the matrices on the code’s performance.
The performance of Gallager's error-correcting code is investigated via methods of statistical physics. In this approach, the transmitted codeword comprises products of the original message bits selected by two randomly constructed sparse matrices; the number of nonzero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity is saturated for many of the codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the Thouless-Anderson-Palmer approach which is identical to the commonly used belief-propagation-based decoding.
The near-capacity performance and effective decoding algorithms of Low-Density Parity-Check (LDPC) codes have made them a mainstay of contemporary error correction. With an emphasis on iterative techniques like the Belief Propagation (BP) algorithm, the Min-Sum algorithm, and their variations, this paper offers a thorough analysis of decoding algorithms for LDPC codes. We investigate the trade-offs between various algorithmic techniques’ computational complexity, decoding latency, and error correction performance. Particular focus is placed on new methods and hardware-friendly algorithms that are tailored for next-generation communication systems, such 5 G and beyond.
The performance of regular and irregular Gallager-type error-correcting code is investigated via methods of statistical physics. The transmitted codeword comprises products of the original message bits selected by two randomly-constructed sparse matrices; the number of non-zero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity may be saturated in equilibrium for many of the regular codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding. We show that irregular codes may saturate Shannon's capacity but with improved dynamical properties.
The class of low-density parity-check (LDPC) codes was introduced by Gallager in his thesis in 1961 [2]. Until the invention of turbo codes, they were largely neglected, but received a lot of interest lately, due to the possibility of designing LDPC codes within 0.0045 dB of the Shannon limit. We review in this project techniques used to analyze the performance of LDPC codes under a message-passing decoding algorithm, namely belief propagation (BP) [4][5]. This analysis gives us the tools to design good LDPC codes. We will first take the simpler example of transmission over the class of binary erasure channels (BEC). We will then see how it is possible to extend the results for the BEC to the much more general class of symmetric channels.
Error-correcting codes based on very sparse matrices provide the best performance to date. We will focus on improving the decoding of Low Density Parity Checks Codes by examining a new variant of belief propagation for this problem. This new variant is based on techniques such as time averaging and prior biasing. Results obtained by extensive simulations show that, well combined, these techniques bring a modest improvement to BP decoding performance. We also studied the possibility of parallelism, which consists of breaking the algorithm in independent pieces that can be solved simultaneously on different computer nodes. But the time spent in inter-communication between the different machines slows the process and prevent the parallelisation to be as fast as expected.