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/9907418 · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics

Cascading parity-check error-correcting codes

Ido Kanter, David Saad

Published Feb 1, 2000• 27 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreve.61.2137

Related papers

TAP for Parity Check Error Correcting Codes

David Saad, Yoshiyuki Kabashima, Renato Vicente

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.

The MIT Press eBooks•Jun 8, 2001•1 citation

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

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

Statistical physics of irregular low-density parity-check codes

Renato Vicente, David Saad, Yoshyiuki Kabashima

Low-density parity-check codes with irregular constructions have recently been shown to outperform the most advanced error-correcting codes to date. In this paper we apply methods of statistical physics to study the typical properties of simple irregular codes. We use the replica method to find a phase transition which coincides with Shannon's coding bound when appropriate parameters are chosen. The decoding by belief propagation is also studied using statistical physics arguments; the theoretical solutions obtained are in good agreement with simulation results. We compare the performance of irregular codes with that of regular codes and discuss the factors that contribute to the improvement in performance.

arXiv:cond-mat/9908358•Journal of Physics A Mathematical and General•Sep 6, 2000•21 citations

Statistical mechanics of low-density parity check error-correcting codes over Galois fields

K Nakamura, Y Kabashima, David Saad

A variation of low-density parity check (LDPC) error-correcting codes defined over Galois fields ( GF ( q )) is investigated using statistical physics. A code of this type is characterised by a sparse random parity check matrix composed of C non-zero elements per column. We examine the dependence of the code performance on the value of q , for finite and infinite C values, both in terms of the thermodynamical transition point and the practical decoding phase characterised by the existence of a unique (ferromagnetic) solution. We find different q -dependence in the cases of C = 2 and C ⩾ 3; the analytical solutions are in agreement with simulation results, providing a quantitative measure to the improvement in performance obtained using non-binary alphabets.

arXiv:cond-mat/0010073•Europhysics Letters (EPL)•Nov 1, 2001•47 citations

On the effect of parity-check weights in iterative decoding

Nandakishore Santhi, Alexander Vardy

It is well-established "folk knowledge" that in order to be iteratively decodable, a code should have a sparse parity-check matrix, as it has some qualitative and quantitative properties for finite-length codes.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•10 citations
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.
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.
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.
Low-density parity-check codes with irregular constructions have recently been shown to outperform the most advanced error-correcting codes to date. In this paper we apply methods of statistical physics to study the typical properties of simple irregular codes. We use the replica method to find a phase transition which coincides with Shannon's coding bound when appropriate parameters are chosen. The decoding by belief propagation is also studied using statistical physics arguments; the theoretical solutions obtained are in good agreement with simulation results. We compare the performance of irregular codes with that of regular codes and discuss the factors that contribute to the improvement in performance.
A variation of low-density parity check (LDPC) error-correcting codes defined over Galois fields ( GF ( q )) is investigated using statistical physics. A code of this type is characterised by a sparse random parity check matrix composed of C non-zero elements per column. We examine the dependence of the code performance on the value of q , for finite and infinite C values, both in terms of the thermodynamical transition point and the practical decoding phase characterised by the existence of a unique (ferromagnetic) solution. We find different q -dependence in the cases of C = 2 and C ⩾ 3; the analytical solutions are in agreement with simulation results, providing a quantitative measure to the improvement in performance obtained using non-binary alphabets.