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:0710.5501

Discriminated Belief Propagation

Uli Sorger

Published Oct 29, 2007• 6 citations
arXivHTMLPDF

Abstract

Near optimal decoding of good error control codes is generally a difficult task. However, for a certain type of (sufficiently) good codes an efficient decoding algorithm with near optimal performance exists. These codes are defined via a combination of constituent codes with low complexity trellis representations. Their decoding algorithm is an instance of (loopy) belief propagation and is based on an iterative transfer of constituent beliefs. The beliefs are thereby given by the symbol probabilities computed in the constituent trellises. Even though weak constituent codes are employed close to optimal performance is obtained, i.e., the encoder/decoder pair (almost) achieves the information theoretic capacity. However, (loopy) belief propagation only performs well for a rather specific set of codes, which limits its applicability. In this paper a generalisation of iterative decoding is presented. It is proposed to transfer more values than just the constituent beliefs. This is achieved by the transfer of beliefs obtained by independently investigating parts of the code space. This leads to the concept of discriminators, which are used to improve the decoder resolution within certain areas and defines discriminated symbol beliefs. It is shown that these beliefs approximate the overall symbol probabilities. This leads to an iteration rule that (below channel capacity) typically only admits the solution of the overall decoding problem. Via a Gauss approximation a low complexity version of this algorithm is derived. Moreover, the approach may then be applied to a wide range of channel maps without significant complexity increase.

DOI
10.48550/arxiv.0710.5501

Related papers

A novel Encoding/Decoding scheme with Belief Propagation and LDPC code

Prashnatita Pal, Bikash Chandra Sahana, Jayanta Poray

Encoding/decoding plays an important role in the reliability and success of modern data communication, as this becomes an integral part of our daily lives. However, by its inherent nature, the data communication systems are most vulnerable to errors. In communication, the errors mainly occur across the channels and its effect is very severe at times. Depending on the type of error, the code word transmitted across the channel can be partially or totally changed. So, the information transmitted can be lost permanently due to error. The concept of error correction is to introduce redundant data in the information during the transfer of data. The receiver can check the redundant data in the received message and can determine the consistency of the sent message. It can also check the redundant data to detect the transmitted errors in the message and can correct the errors if any. In this context, the principle of loopy Belief Propagation has been used by the Low-Density Parity Check (LDPC) codes. This code comes with an excellent error correction performance. The goal of this paper is to set up a framework to describe the LDPC code constraints, compute probabilities in trellises and finally generate transfer vectors for Loopy Belief Propagation model.

Routledge eBooks•Jun 14, 2022•0 citations

Iterative decoding beyond belief propagation

Shiva Kumar Planjery, Shashi Kiran Chilappagari, Bane V. Vasic +2 more

At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity. However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications. This paper introduces this new paradigm.

Information Theory and Applications Workshop (ITA)•Jan 1, 2010•17 citations

Principles and applications of iterative decoding

K.C. Chew

This thesis presents the newly discovered technique to decode a Turbo code. This technique is known to the artificial intelligence community as belief propagation developed by Judea Pearl, but is relatively unknown to the information theorists. It was only recently that researchers found that turbo decoding, or equivalently iterative decoding, is an instance of Pearl's belief propagation algorithm. Literatures have shown that Pearl's algorithm can be used to derive effective iterative decoding algorithms for a number of error control systems like Gallager's low-density parity-check codes, the low-density generator matrix codes, serially concatenated codes and product codes. Belief propagation provides an attractive general method for devising low-complexity iterative decoding algorithms for hybrid systems because of the simplicity in Bayesian network representations of these systems. Coincidentally, the performance of Turbo codes has attained to a level where it is difficult to improvement any much further. More viable is the challenge to devise low-complexity codes that could achieve near capacity performance. Therefore, the study of making used of single-parity check-based tree (SPCT) codes and belief propagation algorithm was motivated. The recently introduced low-complexity "zigzag" codes can be viewed as a subclass of SPCT codes, whose Bayesian networks have the most unbalanced tree structures. This thesis involves preliminary study of other subclasses of SPCT codes. Interesting observations suggest that performance improvement without increasing decoding complexity is theoretically possible.

•Jan 1, 2000•0 citations

Reduced complexity iterative decoding of low-density parity check codes based on belief propagation

M.P.C. Fossorier, Miodrag J. Mihaljević, Hirotaka Imai

Two simplified versions of the belief propagation algorithm for fast iterative decoding of low-density parity check codes on the additive white Gaussian noise channel are proposed. Both versions are implemented with real additions only, which greatly simplifies the decoding complexity of belief propagation in which products of probabilities have to be computed. Also, these two algorithms do not require any knowledge about the channel characteristics. Both algorithms yield a good performance-complexity trade-off and can be efficiently implemented in software as well as in hardware, with possibly quantized received values.

IEEE Transactions on Communications•May 1, 1999•1,065 citations

Performance of Iterative Algebraic Decoding of Codes Defined on Graphs: An Initial Investigation

Xiangyu Tang, R. Koetter

We investigate iterative algebraic decoding of codes defined on graphs. Practical codes that can achieve the Shannon limit are codes defined on graphs with its associated iterative decoding algorithms. Yet, the complexity of these algorithms is high, especially for long codes that attain capacity. For the foreseeable future, algebraic decoding will still be a standard in industry. We aim to harness the power of iterative processes and the low complexity of algebraic techniques by decoding codes on graphs using iterative algebraic techniques. We study the performance of codes on graphs decoded with this method taking into account the case of undetected errors. More specifically, we examine the threshold under which decoding is successful for the BEC and the BSC and compare these with that of certain LDPC codes. Our initial investigation shows that although a significant loss of performance is incurred on the BEC when compared to belief propagation decoding, for transmission over the BSC the threshold value is somewhat close to belief propagation. Especially for high rate codes iterative algebraic decoding could have good performance while maintaining low decoding complexity.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•9 citations

Iterative Decoding Beyond Belief Propagation of Low-Density Parity-Check Codes

Shiva Kumar Planjery

The recent renaissance of one particular class of error-correcting codes called low-density parity-check (LDPC) codes has revolutionized the area of communications leading to the so-called field of modern coding theory. At the heart of this theory lies the fact that LDPC codes can be efficiently decoded by an iterative inference algorithm known as belief propagation (BP) which operates on a graphical model of a code. With BP decoding, LDPC codes are able to achieve an exceptionally good error-rate performance as they can asymptotically approach Shannon's capacity. However, LDPC codes under BP decoding suffer from the error floor phenomenon, an abrupt degradation in the error-rate performance of the code in the high signal-to-noise ratio region, which prevents the decoder from achieving very low error-rates. It arises mainly due to the sub-optimality of BP decoding on finite-length loopy graphs. Moreover, the effects of finite precision that stem from hardware realizations of BP decoding can further worsen the error floor phenomenon. Over the past few years, the error floor problem has emerged as one of the most important problems in coding theory with applications now requiring very low error rates and faster processing speeds. Further, addressing the error floor problem while taking finite precision into account in the decoder design has remained a challenge. In this dissertation, we introduce a new paradigm for finite precision iterative decoding of LDPC codes over the binary symmetric channel (BSC). These novel decoders, referred to as finite alphabet iterative decoders (FAIDs), are capable of surpassing the BP in the error floor region at a much lower complexity and memory usage than BP without any compromise in decoding latency. The messages propagated by FAIDs are not quantized probabilities or log-likelihoods, and the variable node update functions do not mimic the BP decoder. Rather, the update functions are simple maps designed to ensure a higher guaranteed error correction capability which improves the error floor performance. We provide a methodology for the design of FAIDs on column-weight-three codes. Using this methodology, we design 3-bit precision FAIDs that can surpass the BP (floating-point) in the error floor region on several column-weight-three codes of practical interest. While the proposed FAIDs are able to outperform the BP decoder with low precision, the analysis of FAIDs still proves to be a difficult issue. Furthermore, their achievable guaranteed error correction capability is still far from what is achievable by the optimal maximum-likelihood (ML) decoding. In order to address these two issues, we propose another novel class of decoders called decimation-enhanced FAIDs for LDPC codes. For this class of decoders, the technique of decimation is incorporated into the variable node update function of FAIDs. Decimation, which involves fixing certain bits of the code to a particular value during decoding, can significantly reduce the number of iterations required to correct a fixed number of errors while maintaining the good performance of a FAID, thereby making such decoders more amenable to analysis. We illustrate this for 3-bit precision FAIDs on column-weight-three codes and provide insights into the analysis of such decoders. We also show how decimation can be used adaptively to further enhance the guaranteed error correction capability of FAIDs that are already good on a given code. The new adaptive decimation scheme proposed has marginally added complexity but can significantly increase the slope of the error floor in the error-rate performance of a particular FAID. On certain high-rate column-weight-three codes of practical interest, we show that adaptive decimation-enhanced FAIDs can achieve a guaranteed error-correction capability that is close to the theoretical limit achieved by ML decoding.

•Jan 1, 2013•0 citations
Near optimal decoding of good error control codes is generally a difficult task. However, for a certain type of (sufficiently) good codes an efficient decoding algorithm with near optimal performance exists. These codes are defined via a combination of constituent codes with low complexity trellis representations. Their decoding algorithm is an instance of (loopy) belief propagation and is based on an iterative transfer of constituent beliefs. The beliefs are thereby given by the symbol probabilities computed in the constituent trellises. Even though weak constituent codes are employed close to optimal performance is obtained, i.e., the encoder/decoder pair (almost) achieves the information theoretic capacity. However, (loopy) belief propagation only performs well for a rather specific set of codes, which limits its applicability. In this paper a generalisation of iterative decoding is presented. It is proposed to transfer more values than just the constituent beliefs. This is achieved by the transfer of beliefs obtained by independently investigating parts of the code space. This leads to the concept of discriminators, which are used to improve the decoder resolution within certain areas and defines discriminated symbol beliefs. It is shown that these beliefs approximate the overall symbol probabilities. This leads to an iteration rule that (below channel capacity) typically only admits the solution of the overall decoding problem. Via a Gauss approximation a low complexity version of this algorithm is derived. Moreover, the approach may then be applied to a wide range of channel maps without significant complexity increase.
Encoding/decoding plays an important role in the reliability and success of modern data communication, as this becomes an integral part of our daily lives. However, by its inherent nature, the data communication systems are most vulnerable to errors. In communication, the errors mainly occur across the channels and its effect is very severe at times. Depending on the type of error, the code word transmitted across the channel can be partially or totally changed. So, the information transmitted can be lost permanently due to error. The concept of error correction is to introduce redundant data in the information during the transfer of data. The receiver can check the redundant data in the received message and can determine the consistency of the sent message. It can also check the redundant data to detect the transmitted errors in the message and can correct the errors if any. In this context, the principle of loopy Belief Propagation has been used by the Low-Density Parity Check (LDPC) codes. This code comes with an excellent error correction performance. The goal of this paper is to set up a framework to describe the LDPC code constraints, compute probabilities in trellises and finally generate transfer vectors for Loopy Belief Propagation model.
At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity. However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications. This paper introduces this new paradigm.
This thesis presents the newly discovered technique to decode a Turbo code. This technique is known to the artificial intelligence community as belief propagation developed by Judea Pearl, but is relatively unknown to the information theorists. It was only recently that researchers found that turbo decoding, or equivalently iterative decoding, is an instance of Pearl's belief propagation algorithm. Literatures have shown that Pearl's algorithm can be used to derive effective iterative decoding algorithms for a number of error control systems like Gallager's low-density parity-check codes, the low-density generator matrix codes, serially concatenated codes and product codes. Belief propagation provides an attractive general method for devising low-complexity iterative decoding algorithms for hybrid systems because of the simplicity in Bayesian network representations of these systems. Coincidentally, the performance of Turbo codes has attained to a level where it is difficult to improvement any much further. More viable is the challenge to devise low-complexity codes that could achieve near capacity performance. Therefore, the study of making used of single-parity check-based tree (SPCT) codes and belief propagation algorithm was motivated. The recently introduced low-complexity "zigzag" codes can be viewed as a subclass of SPCT codes, whose Bayesian networks have the most unbalanced tree structures. This thesis involves preliminary study of other subclasses of SPCT codes. Interesting observations suggest that performance improvement without increasing decoding complexity is theoretically possible.
Two simplified versions of the belief propagation algorithm for fast iterative decoding of low-density parity check codes on the additive white Gaussian noise channel are proposed. Both versions are implemented with real additions only, which greatly simplifies the decoding complexity of belief propagation in which products of probabilities have to be computed. Also, these two algorithms do not require any knowledge about the channel characteristics. Both algorithms yield a good performance-complexity trade-off and can be efficiently implemented in software as well as in hardware, with possibly quantized received values.
We investigate iterative algebraic decoding of codes defined on graphs. Practical codes that can achieve the Shannon limit are codes defined on graphs with its associated iterative decoding algorithms. Yet, the complexity of these algorithms is high, especially for long codes that attain capacity. For the foreseeable future, algebraic decoding will still be a standard in industry. We aim to harness the power of iterative processes and the low complexity of algebraic techniques by decoding codes on graphs using iterative algebraic techniques. We study the performance of codes on graphs decoded with this method taking into account the case of undetected errors. More specifically, we examine the threshold under which decoding is successful for the BEC and the BSC and compare these with that of certain LDPC codes. Our initial investigation shows that although a significant loss of performance is incurred on the BEC when compared to belief propagation decoding, for transmission over the BSC the threshold value is somewhat close to belief propagation. Especially for high rate codes iterative algebraic decoding could have good performance while maintaining low decoding complexity.
The recent renaissance of one particular class of error-correcting codes called low-density parity-check (LDPC) codes has revolutionized the area of communications leading to the so-called field of modern coding theory. At the heart of this theory lies the fact that LDPC codes can be efficiently decoded by an iterative inference algorithm known as belief propagation (BP) which operates on a graphical model of a code. With BP decoding, LDPC codes are able to achieve an exceptionally good error-rate performance as they can asymptotically approach Shannon's capacity. However, LDPC codes under BP decoding suffer from the error floor phenomenon, an abrupt degradation in the error-rate performance of the code in the high signal-to-noise ratio region, which prevents the decoder from achieving very low error-rates. It arises mainly due to the sub-optimality of BP decoding on finite-length loopy graphs. Moreover, the effects of finite precision that stem from hardware realizations of BP decoding can further worsen the error floor phenomenon. Over the past few years, the error floor problem has emerged as one of the most important problems in coding theory with applications now requiring very low error rates and faster processing speeds. Further, addressing the error floor problem while taking finite precision into account in the decoder design has remained a challenge. In this dissertation, we introduce a new paradigm for finite precision iterative decoding of LDPC codes over the binary symmetric channel (BSC). These novel decoders, referred to as finite alphabet iterative decoders (FAIDs), are capable of surpassing the BP in the error floor region at a much lower complexity and memory usage than BP without any compromise in decoding latency. The messages propagated by FAIDs are not quantized probabilities or log-likelihoods, and the variable node update functions do not mimic the BP decoder. Rather, the update functions are simple maps designed to ensure a higher guaranteed error correction capability which improves the error floor performance. We provide a methodology for the design of FAIDs on column-weight-three codes. Using this methodology, we design 3-bit precision FAIDs that can surpass the BP (floating-point) in the error floor region on several column-weight-three codes of practical interest. While the proposed FAIDs are able to outperform the BP decoder with low precision, the analysis of FAIDs still proves to be a difficult issue. Furthermore, their achievable guaranteed error correction capability is still far from what is achievable by the optimal maximum-likelihood (ML) decoding. In order to address these two issues, we propose another novel class of decoders called decimation-enhanced FAIDs for LDPC codes. For this class of decoders, the technique of decimation is incorporated into the variable node update function of FAIDs. Decimation, which involves fixing certain bits of the code to a particular value during decoding, can significantly reduce the number of iterations required to correct a fixed number of errors while maintaining the good performance of a FAID, thereby making such decoders more amenable to analysis. We illustrate this for 3-bit precision FAIDs on column-weight-three codes and provide insights into the analysis of such decoders. We also show how decimation can be used adaptively to further enhance the guaranteed error correction capability of FAIDs that are already good on a given code. The new adaptive decimation scheme proposed has marginally added complexity but can significantly increase the slope of the error floor in the error-rate performance of a particular FAID. On certain high-rate column-weight-three codes of practical interest, we show that adaptive decimation-enhanced FAIDs can achieve a guaranteed error-correction capability that is close to the theoretical limit achieved by ML decoding.