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

The MIT Press eBooks

TAP for Parity Check Error Correcting Codes

David Saad, Yoshiyuki Kabashima, Renato Vicente

Published Jun 8, 2001• 1 citation
Publisher

Abstract

We employ the methods presented in the previous chapter for decoding corrupted codewords, encoded using sparse parity check error correcting codes. We show the similarity between the equations derived from the TAP approach and those obtained from belief propagation, and examine their performance as practical decoding methods.
DOI
10.7551/mitpress/1100.003.0010

Related papers

Cascading parity-check error-correcting codes

Ido Kanter, David Saad

A method for improving the performance of sparse-matrix based parity check codes is proposed, based on insight gained from methods of statistical physics. The advantages of this approach are demonstrated on an existing encoding/decoding paradigm suggested by Sourlas. We also discuss the application of the same method to more advanced codes of a similar type.

arXiv:cond-mat/9907418•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Feb 1, 2000•27 citations

Iterative decoding algorithms of LDPC codes using TAP approach

Manel Abdelhedi, Omessaad Hamdi, Ammar Bouallègue

Low-density parity-check (LDPC) codes are based on random construction. Because of this randomness, it is not easy to analyze them with the traditional methods of communication theory. N.Sourlas [6] was the first to point out that LDPC codes have a similarity to Ising spin systems in statistical physics. Besides, it has been shown that the Belief-Propagation algorithm, the decoding algorithm of LDPC codes, is equivalent to the Thouless-Anderson-Palmer(TAP) [9] approach. In this paper, we develop the log-likelihood ratios-Belief Propagation (LLR-BP) and the BP-Based decoding algorithms with the TAP approach.

Global Information Infrastructure and Networking Symposium•Jun 1, 2009•1 citation

Iterative Decoding of Low-Density Parity Check Codes

Venkatesan Guruswami

Much progress has been made on decoding algorithms for error-correcting codes in the last decade. In this article, we give an introduction to some fundamental results on iterative, message-passing algorithms for low-density parity check codes. For certain important stochastic channels, this line of work has enabled getting very close to Shannon capacity with algorithms that are extremely ecient (both in theory and practice).

Bulletin of the European Association for Theoretical Computer Science•Jan 1, 2006•12 citations

Statistical physics of regular low-density parity-check error-correcting codes

Tatsuto Murayama, Yoshiyuki Kabashima, David Saad +1 more

A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.

arXiv:cond-mat/0003121•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Aug 1, 2000•91 citations

Lowering Error Floor of Irregular LDPC Codes by CRC and OSD Algorithm

Satoshi Gounai

Irregular Low-Density Parity-Check (LDPC) codes generally achieve better performance than regular LDPC codes at low E b /N 0 values. They have, however, higher error floors than regular LDPC codes. With respect to the construction of the irregular LDPC code, it can achieve the trade-off between the performance degradation of low E b /N 0 region and lowering error floor. It is known that a decoding algorithm can achieve very good performance if it combines the Ordered Statistic Decoding (OSD) algorithm and the Log Likelihood Ratio-Belief Propagation (LLR-BP) decoding algorithm. Unfortunately, all the codewords obtained by the OSD algorithm satisfy the parity check equation of the LDPC code. While we can not use the parity check equation of the LDPC code to stop the decoding process, the wrong codeword that satisfies the parity check equation raises the error floor. Once a codeword that satisfies the parity check equation is generated by the LLR-BP decoding algorithm, we regard that codeword as the final estimate and halt decoding; the OSD algorithm is not performed. In this paper, we propose a new encoding/decoding scheme to lower the error floor created by irregular LDPC codes. The proposed encoding scheme encodes information bits by Cyclic Redundancy Check (CRC) and LDPC code. The proposed decoding scheme, which consists of the LLR-BP decoding, CRC check, and OSD decoding, detects errors in the codewords obtained by the LLR-BP decoding algorithm and the OSD decoding algorithm using the parity check equations of LDPC codes and CRC. Computer simulations show that the proposed encoding/decoding scheme can lower the error floor of irregular LDPC codes.

IEICE Transactions on Communications•Jan 1, 2006•6 citations

An overview of some efficient encoding and decoding algorithms for Low-Density Parity-Check Codes

Enrico Paolini, Gianluigi Liva, Marco Chiani

•Oct 10, 2003•0 citations
Low-density parity-check (LDPC) codes are based on random construction. Because of this randomness, it is not easy to analyze them with the traditional methods of communication theory. N.Sourlas [6] was the first to point out that LDPC codes have a similarity to Ising spin systems in statistical physics. Besides, it has been shown that the Belief-Propagation algorithm, the decoding algorithm of LDPC codes, is equivalent to the Thouless-Anderson-Palmer(TAP) [9] approach. In this paper, we develop the log-likelihood ratios-Belief Propagation (LLR-BP) and the BP-Based decoding algorithms with the TAP approach.
A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.
Irregular Low-Density Parity-Check (LDPC) codes generally achieve better performance than regular LDPC codes at low E b /N 0 values. They have, however, higher error floors than regular LDPC codes. With respect to the construction of the irregular LDPC code, it can achieve the trade-off between the performance degradation of low E b /N 0 region and lowering error floor. It is known that a decoding algorithm can achieve very good performance if it combines the Ordered Statistic Decoding (OSD) algorithm and the Log Likelihood Ratio-Belief Propagation (LLR-BP) decoding algorithm. Unfortunately, all the codewords obtained by the OSD algorithm satisfy the parity check equation of the LDPC code. While we can not use the parity check equation of the LDPC code to stop the decoding process, the wrong codeword that satisfies the parity check equation raises the error floor. Once a codeword that satisfies the parity check equation is generated by the LLR-BP decoding algorithm, we regard that codeword as the final estimate and halt decoding; the OSD algorithm is not performed. In this paper, we propose a new encoding/decoding scheme to lower the error floor created by irregular LDPC codes. The proposed encoding scheme encodes information bits by Cyclic Redundancy Check (CRC) and LDPC code. The proposed decoding scheme, which consists of the LLR-BP decoding, CRC check, and OSD decoding, detects errors in the codewords obtained by the LLR-BP decoding algorithm and the OSD decoding algorithm using the parity check equations of LDPC codes and CRC. Computer simulations show that the proposed encoding/decoding scheme can lower the error floor of irregular LDPC codes.