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:0902.3287 · IEEE International Symposium on Information Theory (ISIT)

Adaptive decoding of LDPC codes with binary messages

Ingmar Land, Gottfried Lechner, Lars Kildehoj Rasmussen

Published Jun 1, 2009• 0 citations
arXivHTMLPDF

Abstract

A novel adaptive binary decoding algorithm for LDPC codes is proposed, which reduces the decoding complexity while having a comparable or even better performance than corresponding non-adaptive alternatives. In each iteration the variable node decoders use the binary check node decoders multiple times; each single use is referred to as a sub-iteration. To process the sequences of binary messages in each iteration, the variable node decoders employ pre-computed look-up tables. These look-up tables as well as the number of sub-iterations per iteration are dynamically adapted during the decoding process based on the decoder state, represented by the mutual information between the current messages and the syndrome bits. The look-up tables and the number of sub-iterations per iteration are determined and optimized using density evolution. The performance and the complexity of the proposed adaptive decoding algorithm is exemplified by simulations.

DOI
10.1109/isit.2009.5205782

Related papers

Decoding of LDPC codes with binary vector messages and scalable complexity

Gottfried Lechner, Ingmar Land, Lars Kildehoj Rasmussen

In this paper, an iterative decoder for LDPC codes, suitable for high-speed processing, is proposed and analyzed. The messages exchanged between the nodes are binary vectors, where the information is conveyed by the number of ones rather than their positions in the vector. Regarding this aspect, the approach exhibits some similarities to stochastic decoding techniques. The check node decoders perform simple bit-wise modulo-2 additions, whereas the variable node decoders perform more complex processing tasks, making the resulting structure attractive for high-speed hardware implementation. By selecting the length of the binary vector messages between one and infinity, the complexity and the performance of the decoder can be scaled between that of the original binary message passing algorithm and that of the sum-product algorithm. Density evolution is developed for the proposed decoding algorithm, and decoding thresholds are determined as functions of the length of the binary vector messages. Simulation results exemplify the performance for finite-length codes.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•4 citations

Adaptive Extended Min-Sum Algorithm for Nonbinary LDPC Decoding

Xuan Guan, Yunsi Fei

Low Density Parity Check (LDPC) codes over a Galois Field GF(q) can provide significantly better error- correcting quality than binary LDPC codes with moderate code length. However, the computational complexity and memory requirement of nonbinary codes are much higher, limiting the application of non- binary LDPC codes. In this paper, we propose an adaptive message truncation algorithm for non-binary LDPC decoding, guided by the estimated code error rates. Compared to the previous fixed message truncation method, it can cut the messages adaptively, and therefore provide better decoding quality and computation complexity reduction. To further reduce the computation, we propose another adaptive check node update algorithm, simplifying the decoding by reducing the number of check nodes updating. Our simulation results demonstrate that by combining these two algorithms together, the average message size can be reduced greatly and good decoding quality is achieved, at a little cost of iterations. Compared to the existing truncation algorithms, our approach can reduce the order of complexity to O(nalog2(na)) (where nais messages size), with less performance degradation.

Globecom•Dec 1, 2011•7 citations

Adaptive decoding of LDPC codes based on cross-entropy

Tso-Cho Chen

An adaptive decoding scheme for low-density parity-check (LDPC) codes is proposed for accelerating the convergence of message-passing algorithms. The evolution of adaptive weighting factor with the number of decoding iterations and stopping criterion are based on the cross-entropy between two consecutive a posteriori probabilities distribution of the soft output of decoder. Information-theoretic support and extensive simulations are provided to demonstrate the efficiency of the proposed algorithm for LDPC decoding. The proposed adaptive decoding algorithm can reduce significantly the average number of iterations of decoder while having a comparable or even better performance than conventional message-passing algorithms.

Cross Strait Radio Science and Wireless Technology Conference (CSRSWTC)•Jul 1, 2011•0 citations

Efficient EMS decoding for non-binary LDPC codes

Leixin Zhou, Jin Sha, Zhongfeng Wang

Non-binary low-density parity-check (NB-LDPC) codes are an extension of binary LDPC codes with significantly better performance when the code length is moderate. Previously, forward-backward schemes are used to implement check node processing, which need large memory. In this paper, a novel approach is proposed for EMS NB-LDPC decoding. Compared to EMS decoding algorithm, the message memory and the average number of iterations have been reduced. Also, the overall decoder architecture is proposed.

International SoC Design Conference•Nov 1, 2012•9 citations

An Adaptive Method to Improve the Iteration Efficiency for Non-binary LDPC Decoding

Jin Xu, Jun Xu, Hai Tian +2 more

Non-binary low density parity check codes can achieve better err-correcting performance than binary LDPC codes when the code length is moderate at the cost of higher decoding complexity. Min-Max decoding algorithm is one of the low-complexity quasi-optimal iterative algorithms. However, a problem of the Min-Max decoding algorithm is iteration inefficient in the case of low SNR. In this paper, an adaptive method is proposed based on the Min-Max decoding algorithm. By comparing the correlation among each iteration output, setting an appropriate threshold to determine whether ahead of the end of iteration, which makes the adaptive Min-Max decoding algorithm very attractive for practical purposes

DEStech Transactions on Computer Science and Engineering•May 5, 2017•0 citations

Decoding of Non-Binary LDPC Codes using the Information Bottleneck Method

Maximilian Stark, Gerhard Bauch, Jan Lewandowsky +1 more

Recently, a novel lookup table based decoding method for binary low-density parity-check codes has attracted considerable attention. In this approach, mutual-information-maximizing lookup tables replace the conventional operations of the variable nodes and the check nodes in message passing decoding. Moreover, the exchanged messages are represented by integers with very small bit width. A machine learning framework termed the information bottleneck method is used to design the corresponding lookup tables. In this paper, we extend this decoding principle from binary to non-binary codes. This is not a straightforward extension but requires a more sophisticated lookup table design to cope with the arithmetic in higher order Galois fields. Provided bit error rate simulations show that our proposed scheme outperforms the log-max decoding algorithm and operates close to sum-product decoding.

arXiv:1810.08921•International Conference on Communications•May 1, 2019•6 citations
A novel adaptive binary decoding algorithm for LDPC codes is proposed, which reduces the decoding complexity while having a comparable or even better performance than corresponding non-adaptive alternatives. In each iteration the variable node decoders use the binary check node decoders multiple times; each single use is referred to as a sub-iteration. To process the sequences of binary messages in each iteration, the variable node decoders employ pre-computed look-up tables. These look-up tables as well as the number of sub-iterations per iteration are dynamically adapted during the decoding process based on the decoder state, represented by the mutual information between the current messages and the syndrome bits. The look-up tables and the number of sub-iterations per iteration are determined and optimized using density evolution. The performance and the complexity of the proposed adaptive decoding algorithm is exemplified by simulations.
In this paper, an iterative decoder for LDPC codes, suitable for high-speed processing, is proposed and analyzed. The messages exchanged between the nodes are binary vectors, where the information is conveyed by the number of ones rather than their positions in the vector. Regarding this aspect, the approach exhibits some similarities to stochastic decoding techniques. The check node decoders perform simple bit-wise modulo-2 additions, whereas the variable node decoders perform more complex processing tasks, making the resulting structure attractive for high-speed hardware implementation. By selecting the length of the binary vector messages between one and infinity, the complexity and the performance of the decoder can be scaled between that of the original binary message passing algorithm and that of the sum-product algorithm. Density evolution is developed for the proposed decoding algorithm, and decoding thresholds are determined as functions of the length of the binary vector messages. Simulation results exemplify the performance for finite-length codes.
Low Density Parity Check (LDPC) codes over a Galois Field GF(q) can provide significantly better error- correcting quality than binary LDPC codes with moderate code length. However, the computational complexity and memory requirement of nonbinary codes are much higher, limiting the application of non- binary LDPC codes. In this paper, we propose an adaptive message truncation algorithm for non-binary LDPC decoding, guided by the estimated code error rates. Compared to the previous fixed message truncation method, it can cut the messages adaptively, and therefore provide better decoding quality and computation complexity reduction. To further reduce the computation, we propose another adaptive check node update algorithm, simplifying the decoding by reducing the number of check nodes updating. Our simulation results demonstrate that by combining these two algorithms together, the average message size can be reduced greatly and good decoding quality is achieved, at a little cost of iterations. Compared to the existing truncation algorithms, our approach can reduce the order of complexity to O(nalog2(na)) (where nais messages size), with less performance degradation.
An adaptive decoding scheme for low-density parity-check (LDPC) codes is proposed for accelerating the convergence of message-passing algorithms. The evolution of adaptive weighting factor with the number of decoding iterations and stopping criterion are based on the cross-entropy between two consecutive a posteriori probabilities distribution of the soft output of decoder. Information-theoretic support and extensive simulations are provided to demonstrate the efficiency of the proposed algorithm for LDPC decoding. The proposed adaptive decoding algorithm can reduce significantly the average number of iterations of decoder while having a comparable or even better performance than conventional message-passing algorithms.
Non-binary low-density parity-check (NB-LDPC) codes are an extension of binary LDPC codes with significantly better performance when the code length is moderate. Previously, forward-backward schemes are used to implement check node processing, which need large memory. In this paper, a novel approach is proposed for EMS NB-LDPC decoding. Compared to EMS decoding algorithm, the message memory and the average number of iterations have been reduced. Also, the overall decoder architecture is proposed.
Non-binary low density parity check codes can achieve better err-correcting performance than binary LDPC codes when the code length is moderate at the cost of higher decoding complexity. Min-Max decoding algorithm is one of the low-complexity quasi-optimal iterative algorithms. However, a problem of the Min-Max decoding algorithm is iteration inefficient in the case of low SNR. In this paper, an adaptive method is proposed based on the Min-Max decoding algorithm. By comparing the correlation among each iteration output, setting an appropriate threshold to determine whether ahead of the end of iteration, which makes the adaptive Min-Max decoding algorithm very attractive for practical purposes
Recently, a novel lookup table based decoding method for binary low-density parity-check codes has attracted considerable attention. In this approach, mutual-information-maximizing lookup tables replace the conventional operations of the variable nodes and the check nodes in message passing decoding. Moreover, the exchanged messages are represented by integers with very small bit width. A machine learning framework termed the information bottleneck method is used to design the corresponding lookup tables. In this paper, we extend this decoding principle from binary to non-binary codes. This is not a straightforward extension but requires a more sophisticated lookup table design to cope with the arithmetic in higher order Galois fields. Provided bit error rate simulations show that our proposed scheme outperforms the log-max decoding algorithm and operates close to sum-product decoding.