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

International Conference on Innovative Research in Applied Science, Engineering and Technology (IRASET)

LDPC Decoding Based On Statistical Mechanics Of Spin-Glasses: A Study

Z. JADDI, Abdessalam Aït Madi, Mohammed Benbrahim

Published Apr 1, 2020• 0 citations
Publisher

Abstract

In this paper, the LDPC (Low Density Parity Check Codes) decoding algorithm has been investigated using statistical mechanics properties. The main advantage of LDPC codes is their performance that works in near Shannon limit, and the ability to use iterative decoding algorithms. In 1989 N. Sourlas showed that error-correcting codes can be considered as Spin-Glass systems thus making it possible to model LDPC codes as an Ising model, opening the way for information theorists to solve coding problems with the power of statistical mechanics. According to N. Sourlas, the decoding problem can be solved by finding the ground state of the corresponding spin-system Hamiltonian. The main goal of this paper is to review as simple as possible the statistical properties of LDPC codes, and how it is used especially facing the decoding problem.

DOI
10.1109/iraset48871.2020.9092331

Related papers

STATISTICAL MECHANICS APPROACH TO ERROR-CORRECTING CODES

Nicolas Sourlas

I will review the relationship between error-correction codes and certain mathematical models of spin glasses. I will show that there is a one to one relationship between error correcting codes and spin glass models. Minimum error probability decoding is equivalent to finding the magnetisation of the corresponding spin system. Convolutional codes correspond to one-dimensional spin systems and Viterbi’s decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. I will also show how the recently discovered (or rediscovered) capacity approaching codes (turbo codes and low density parity check codes) can be analysed using statistical mechanics. Turbo codes correspond to two coupled spin chains, while low density parity check codes are spin models on a diluted random graph. It is possible to show, using statistical mechanics, that these codes allow error-free communication for signal to noise ratio above a certain threshold. This threshold, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.

Solvay Conference on Physics•Aug 1, 2003•2 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•79 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

Magnetization Performance of LDPC Reduced-Complexity Decoding Algorithms

Manel Abdelhedi, Omessaad Hamdi, Ammar Bouallègue

Low-density parity-check (LDPC) codes are very efficient for communicating reliably through a noisy channel. N.Sourlas [1] showed that LDPC codes, which revolutionize the codes domain and used in many communications standards, can be mapped onto an Ising spin systems. Besides, it has been shown that the Belief-Propagation (BP) algorithm, the LDPC codes decoding algorithm, is equivalent to the Thouless- Anderson-Palmer (TAP) approach [2]. Unfortunately, no study has been made for the other decoding algorithms. In this paper, we develop the Log-Likelihood Ratios-Belief Propagation (LLR-BP) algorithm and its simplifications the BP-Based algorithm and the λ-min algorithm with the TAP approach. We present the performance of these decoding algorithms using statistical physics argument i.e., we present the performance as function of the magnetization.

International Journal of Communications Network and System Sciences•Jan 1, 2010•0 citations

Reduced-Comlexity Decoding 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 information theory. N. Sourlas was the first to point out that LDPC codes have a similarity with Ising spin systems of statistical physics. Besides, it has been shown that the Belief-Propagation algorithm, the LDPC codes decoding algorithm, is equivalent to the Thouless-Anderson-Palmer(TAP) approach. In this paper, we develop the log likelihood ratios-Belief Propagation (LLR-BP) algorithm and its simplifications the BP-Based algorithm and the λ-min algorithm with the TAP approach.

International Conference on Signal-Image Technology & Internet-Based Systems (SITIS)•Nov 1, 2009•0 citations

Linear-time encoding and decoding of low-density parity-check codes

Mikael Simberg

Low-density parity-check (LDPC) codes had a renaissance when they were rediscovered in the 1990’s. Since then LDPC codes have been an important part of the field of error-correcting codes, and have been shown to be able to approach the Shannon capacity, the limit at which we can reliably transmit information over noisy channels. Following this, many modern communications standards have adopted LDPC codes. Error-correction is equally important in protecting data from corruption on a hard-drive as it is in deep-space communications. It is most commonly used for example for reliable wireless transmission of data to mobile devices. For practical purposes, both encoding and decoding need to be of low complexity to achieve high throughput and low power consumption. This thesis provides a literature review of the current state-of-the-art in encoding and decoding of LDPC codes. Message- passing decoders are still capable of achieving the best error-correcting performance, while more recently considered bit-flipping decoders are providing a low-complexity alternative, albeit with some loss in error-correcting performance. An implementation of a low-complexity stochastic bit-flipping decoder is also presented. It is implemented for Graphics Processing Units (GPUs) in a parallel fashion, providing a peak throughput of 1.2 Gb/s, which is significantly higher than previous decoder implementations on GPUs. The error-correcting performance of a range of decoders has also been tested, showing that the stochastic bit-flipping decoder provides relatively good error-correcting performance with low complexity. Finally, a brief comparison of encoding complexities for two code ensembles is also presented.

•Jan 20, 2015•0 citations
In this paper, the LDPC (Low Density Parity Check Codes) decoding algorithm has been investigated using statistical mechanics properties. The main advantage of LDPC codes is their performance that works in near Shannon limit, and the ability to use iterative decoding algorithms. In 1989 N. Sourlas showed that error-correcting codes can be considered as Spin-Glass systems thus making it possible to model LDPC codes as an Ising model, opening the way for information theorists to solve coding problems with the power of statistical mechanics. According to N. Sourlas, the decoding problem can be solved by finding the ground state of the corresponding spin-system Hamiltonian. The main goal of this paper is to review as simple as possible the statistical properties of LDPC codes, and how it is used especially facing the decoding problem.
I will review the relationship between error-correction codes and certain mathematical models of spin glasses. I will show that there is a one to one relationship between error correcting codes and spin glass models. Minimum error probability decoding is equivalent to finding the magnetisation of the corresponding spin system. Convolutional codes correspond to one-dimensional spin systems and Viterbi’s decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. I will also show how the recently discovered (or rediscovered) capacity approaching codes (turbo codes and low density parity check codes) can be analysed using statistical mechanics. Turbo codes correspond to two coupled spin chains, while low density parity check codes are spin models on a diluted random graph. It is possible to show, using statistical mechanics, that these codes allow error-free communication for signal to noise ratio above a certain threshold. This threshold, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.
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.
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.
Low-density parity-check (LDPC) codes are very efficient for communicating reliably through a noisy channel. N.Sourlas [1] showed that LDPC codes, which revolutionize the codes domain and used in many communications standards, can be mapped onto an Ising spin systems. Besides, it has been shown that the Belief-Propagation (BP) algorithm, the LDPC codes decoding algorithm, is equivalent to the Thouless- Anderson-Palmer (TAP) approach [2]. Unfortunately, no study has been made for the other decoding algorithms. In this paper, we develop the Log-Likelihood Ratios-Belief Propagation (LLR-BP) algorithm and its simplifications the BP-Based algorithm and the λ-min algorithm with the TAP approach. We present the performance of these decoding algorithms using statistical physics argument i.e., we present the performance as function of the magnetization.
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 information theory. N. Sourlas was the first to point out that LDPC codes have a similarity with Ising spin systems of statistical physics. Besides, it has been shown that the Belief-Propagation algorithm, the LDPC codes decoding algorithm, is equivalent to the Thouless-Anderson-Palmer(TAP) approach. In this paper, we develop the log likelihood ratios-Belief Propagation (LLR-BP) algorithm and its simplifications the BP-Based algorithm and the λ-min algorithm with the TAP approach.
Low-density parity-check (LDPC) codes had a renaissance when they were rediscovered in the 1990’s. Since then LDPC codes have been an important part of the field of error-correcting codes, and have been shown to be able to approach the Shannon capacity, the limit at which we can reliably transmit information over noisy channels. Following this, many modern communications standards have adopted LDPC codes. Error-correction is equally important in protecting data from corruption on a hard-drive as it is in deep-space communications. It is most commonly used for example for reliable wireless transmission of data to mobile devices. For practical purposes, both encoding and decoding need to be of low complexity to achieve high throughput and low power consumption. This thesis provides a literature review of the current state-of-the-art in encoding and decoding of LDPC codes. Message- passing decoders are still capable of achieving the best error-correcting performance, while more recently considered bit-flipping decoders are providing a low-complexity alternative, albeit with some loss in error-correcting performance. An implementation of a low-complexity stochastic bit-flipping decoder is also presented. It is implemented for Graphics Processing Units (GPUs) in a parallel fashion, providing a peak throughput of 1.2 Gb/s, which is significantly higher than previous decoder implementations on GPUs. The error-correcting performance of a range of decoders has also been tested, showing that the stochastic bit-flipping decoder provides relatively good error-correcting performance with low complexity. Finally, a brief comparison of encoding complexities for two code ensembles is also presented.