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

Electronics Letters

Combined linear programming/belief propagation decoder

Michael Lunglmayr, Jens Berkmann, Mario Huemer

Published Jun 3, 2008• 3 citations
Publisher

Abstract

For decoding of LDPC codes two types of algorithms are frequently discussed in the literature. One type is based on belief propagation (BP) the other is based on linear programming (LP). Especially for short LDPC codes it has been observed that BP decoding often performs better at low SNR ranges, whereas LP decoding performs better at high SNR levels. A combined linear programming and belief propagation decoder is presented, which significantly outperforms both a pure LP and a pure BP decoder throughout the whole SNR range.

DOI
10.1049/el:20081200

Related papers

Evaluation of LDPC decoder with standardized codes

Jun Zhao

Low density parity check (LDPC) codes are one of the most popular channel codes.Based on traditional sum-product and max-product algorithms, various modified algorithms are tried to improve the performance of LDPC codes in terms of error rate, complexity and latency.Uniformly rweighted belief propagation (URW-BP) algorithm can offer better performance than traditional algorithm especially for regular LDPC codes.linear programming (LP) decoder is also competitive to traditional message passing algorithm.We describe two traditional message passing decoders, four reweighted message passing decoders based on URW-BP and LP decoder in this paper.Reweighted decoders can outperform traditional decoders especially when iteration number is limited.Considering complexity and latency, reweighted max product decoder of version 2 (R-MPD-II) is the most promising decoder.CONTENTS 4.3 Short regular LDPC codes . . . . . . . .

•Jan 1, 2012•0 citations

A high‐performance belief propagation decoding algorithm for codes with short cycles

Ali Karimi-lenji, Monireh Houshmand, Fahimeh Zarmehi

Summary The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.

International Journal of Communication Systems•Feb 28, 2017•2 citations

4 The ADMM penalized decoder for LDPC codes∗

Xishuo Liu, Stark Christiaan Draper

Linear programming (LP) decoding for low-density parity-check codes was introduced by Feldman et al. and has been shown to have theoretical guarantees in several regimes. Furthermore, it has been reported in the literature-via simulation and via instanton analysis-that LP decoding displays better error rate performance at high signal-to-noise ratios (SNR) than does belief propagation (BP) decoding. However, at low SNRs, LP decoding is observed to have worse performance than BP. In this paper, we seek to improve LP decoding at low SNRs while maintaining LP decoding's high SNR performance. Our main contribution is a new class of decoders obtained by applying the alternating direction method of multipliers (ADMM) algorithm to a set of non-convex optimization problems. These non-convex problems are constructed by adding a penalty term to the objective of LP decoding. The goal of the penalty is to make pseudocodewords, which are non-integer vertices of the LP relaxation, more costly. We name this class of decoders-ADMM penalized decoders. For low and moderate SNRs, we simulate ADMM penalized decoding with ℓ 1 and ℓ 2 penalties. We find that these decoders can outperform both BP and LP decoding. For high SNRs, where it is difficult to obtain data via simulation, we use an instanton analysis and find that, asymptotically, ADMM penalized decoding performs better than BP but not as well as LP. Unfortunately, since ADMM penalized decoding is not a convex program, we have not been successful in developing theoretical guarantees. However, the non-convex program can be approximated using a sequence of linear programs; an approach that yields a reweighted LP decoder. We show that a two-round reweighted LP decoder has an improved theoretical recovery threshold when compared with LP decoding. In addition, we find via simulation that reweighted LP decoding significantly attains lower error rates than LP decoding at low SNRs.

•Jan 1, 2014•49 citations

ML vs. BP decoding of binary and non-binary LDPC codes

Stefan Scholl, Frank Kienle, Michael Helmling +1 more

It has been shown that non-binary LDPC codes have a better error correction performance than binary codes for short block lengths. However, this advantage was up to now only shown under belief propagation decoding. To gain new insights, we investigate binary and non-binary codes under ML decoding. Our analysis includes different modulation schemes and decoding algorithms. For ML decoding under different modulation schemes a flexible integer programming formulation is presented. In this paper, we show that with respect to ML decoding short non-binary LDPC codes are not necessarily superior to binary codes. The decoding gain observed under BP decoding originates mainly in the more powerful non-binary decoding algorithm.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2012•8 citations

Suppressing pseudocodewords by penalizing the objective of LP decoding

Xishuo Liu, Stark Christiaan Draper, Benjamin Recht

In this paper, we present a new class of decoders for low density parity check (LDPC) codes. We are motivated by the observation that the linear programming (LP) decoder has worse error performance than belief propagation (BP) decoders at low SNRs. We base our new decoders on the alternating direction method of multipliers (ADMM) decomposition technique for LP decoding. The ADMM not only efficiently solves the LP decoding problem, but also makes it possible to explore other decoding algorithms. In particular, we add various penalty terms to the linear objective of LP decoding with the goal of suppressing pseudocodewords. Simulation results show that the new decoders achieve much better error performance compared to LP decoder at low SNRs. What is more, similar to the LP decoder, no error floor is observed at high SNRs.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•26 citations

Fast Linear-Programming decoding of LDPC codes over GF(2 m )

Junya Honda, H. Yamamoto

Recently Linear Programming (LP) decoding is attracting much attention as an alternative to Belief Propagation (BP) decoding for LDPC codes. It is well known for the BP decoding that nonbinary LDPC codes can improve the decoding error probability considerably. On the other hand, Flanagan et al. proposed an LP decoding scheme for LDPC codes over finite rings. Although their scheme is applicable to LDPC codes over finite fields, the number of variables in the LP grows rapidly and hence, its implementation becomes harder as the field size increases. To overcome this defect we propose a new LP decoding scheme for GF(2m), in which the number of variables increases linearly in the field size. Although our scheme relaxes a maximum likelihood decoding problem more loosely to an LP problem than their scheme, the deterioration of the decoding error probability is small.

International Symposium on Information Theory and its Applications•Oct 1, 2012•10 citations
For decoding of LDPC codes two types of algorithms are frequently discussed in the literature. One type is based on belief propagation (BP) the other is based on linear programming (LP). Especially for short LDPC codes it has been observed that BP decoding often performs better at low SNR ranges, whereas LP decoding performs better at high SNR levels. A combined linear programming and belief propagation decoder is presented, which significantly outperforms both a pure LP and a pure BP decoder throughout the whole SNR range.
Low density parity check (LDPC) codes are one of the most popular channel codes.Based on traditional sum-product and max-product algorithms, various modified algorithms are tried to improve the performance of LDPC codes in terms of error rate, complexity and latency.Uniformly rweighted belief propagation (URW-BP) algorithm can offer better performance than traditional algorithm especially for regular LDPC codes.linear programming (LP) decoder is also competitive to traditional message passing algorithm.We describe two traditional message passing decoders, four reweighted message passing decoders based on URW-BP and LP decoder in this paper.Reweighted decoders can outperform traditional decoders especially when iteration number is limited.Considering complexity and latency, reweighted max product decoder of version 2 (R-MPD-II) is the most promising decoder.CONTENTS 4.3 Short regular LDPC codes . . . . . . . .
Summary The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.
Linear programming (LP) decoding for low-density parity-check codes was introduced by Feldman et al. and has been shown to have theoretical guarantees in several regimes. Furthermore, it has been reported in the literature-via simulation and via instanton analysis-that LP decoding displays better error rate performance at high signal-to-noise ratios (SNR) than does belief propagation (BP) decoding. However, at low SNRs, LP decoding is observed to have worse performance than BP. In this paper, we seek to improve LP decoding at low SNRs while maintaining LP decoding's high SNR performance. Our main contribution is a new class of decoders obtained by applying the alternating direction method of multipliers (ADMM) algorithm to a set of non-convex optimization problems. These non-convex problems are constructed by adding a penalty term to the objective of LP decoding. The goal of the penalty is to make pseudocodewords, which are non-integer vertices of the LP relaxation, more costly. We name this class of decoders-ADMM penalized decoders. For low and moderate SNRs, we simulate ADMM penalized decoding with ℓ 1 and ℓ 2 penalties. We find that these decoders can outperform both BP and LP decoding. For high SNRs, where it is difficult to obtain data via simulation, we use an instanton analysis and find that, asymptotically, ADMM penalized decoding performs better than BP but not as well as LP. Unfortunately, since ADMM penalized decoding is not a convex program, we have not been successful in developing theoretical guarantees. However, the non-convex program can be approximated using a sequence of linear programs; an approach that yields a reweighted LP decoder. We show that a two-round reweighted LP decoder has an improved theoretical recovery threshold when compared with LP decoding. In addition, we find via simulation that reweighted LP decoding significantly attains lower error rates than LP decoding at low SNRs.
It has been shown that non-binary LDPC codes have a better error correction performance than binary codes for short block lengths. However, this advantage was up to now only shown under belief propagation decoding. To gain new insights, we investigate binary and non-binary codes under ML decoding. Our analysis includes different modulation schemes and decoding algorithms. For ML decoding under different modulation schemes a flexible integer programming formulation is presented. In this paper, we show that with respect to ML decoding short non-binary LDPC codes are not necessarily superior to binary codes. The decoding gain observed under BP decoding originates mainly in the more powerful non-binary decoding algorithm.
In this paper, we present a new class of decoders for low density parity check (LDPC) codes. We are motivated by the observation that the linear programming (LP) decoder has worse error performance than belief propagation (BP) decoders at low SNRs. We base our new decoders on the alternating direction method of multipliers (ADMM) decomposition technique for LP decoding. The ADMM not only efficiently solves the LP decoding problem, but also makes it possible to explore other decoding algorithms. In particular, we add various penalty terms to the linear objective of LP decoding with the goal of suppressing pseudocodewords. Simulation results show that the new decoders achieve much better error performance compared to LP decoder at low SNRs. What is more, similar to the LP decoder, no error floor is observed at high SNRs.
Recently Linear Programming (LP) decoding is attracting much attention as an alternative to Belief Propagation (BP) decoding for LDPC codes. It is well known for the BP decoding that nonbinary LDPC codes can improve the decoding error probability considerably. On the other hand, Flanagan et al. proposed an LP decoding scheme for LDPC codes over finite rings. Although their scheme is applicable to LDPC codes over finite fields, the number of variables in the LP grows rapidly and hence, its implementation becomes harder as the field size increases. To overcome this defect we propose a new LP decoding scheme for GF(2m), in which the number of variables increases linearly in the field size. Although our scheme relaxes a maximum likelihood decoding problem more loosely to an LP problem than their scheme, the deterioration of the decoding error probability is small.