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 Symposium on Communications and Information Technologies

Modified fast Hadamard transform based belief propagation decoding algorithm

Xueqin Jiang, Moon Ho Lee

Published Sep 1, 2009• 0 citations
Publisher

Abstract

In this paper, we propose a new fast Hadamard transform based the belief-propagation (BP) decoding algorithm over GF (2p) with a modification of the permutations between the check nodes and variable nodes. This scheme is mathematically equivalent to the conventional BP decoding algorithm, but complexity of the proposed scheme is lower. We show by simulation that the non-binary regular and irregular LDPC codes in GF (2p) have good performance with our proposed modified BP decoding algorithm.

DOI
10.1109/iscit.2009.5341135

Related papers

Fast decoding algorithm for LDPC over GF(2/sup q/)

Loïc Barnault, David Declercq

We present a modification of belief propagation that enables us to decode LDPC codes defined on high order Galois fields with a complexity that scales as p log/sub 2/ (p), p being the field order. With this low complexity algorithm, we are able to decode GF(2/sup q/) LDPC codes up to a field order value of 256. We show by simulation that ultra-sparse regular LDPC codes in GF(64) and GF(256) exhibit very good performance.

IEEE Information Theory Workshop (ITW)•Mar 2, 2004•268 citations

Fast decoding of low density parity check codes

Nassib Laouini, Larbi Ben Hadj Slama, Ammar Bouallègue

The Layered Belief Propagation L-BP algorithm is is a modified Belief Propagation BP algorithm, where the check nodes are divided in subgroups called layers and each iteration is broken into multiple sub-iterations. In this paper, we consider layered belief propagation decoding and propose an efficient variable node layering for decoding LDPC codes that performs well. We compare the performance of the first introduced LDPC decoding algorithm BP and Layered BP using check node layering with Layered BP using variable node layering in terms of bit error rate (BER). We show that the convergence for decoding LDPC codes is increasing by using a simple and efficient layering strategy.

International Symposium on High-capacity Optical Networks and Enabling Technologies•Dec 1, 2012•5 citations

Fast convergence decoding scheme tor regular LDPC codes

Jaebum Kim, Nam-Sik Kim, Hyuncheol Park

We propose a new belief propagation (BP) decoding algorithm for fast convergence decoding of regular LDPC codes. The fast convergence is achieved by grouping and scheduling updates of nodes on a bipartite-graph without additional computations or approximations. For this reason, the proposed algorithm can be applied to a serially constructed decoder, and can reduce the power consumption and decoding delay of the decoder. Simulation results show that the convergence speed of the proposed algorithm depends on the degree, d/sub v/, of the variable-nodes of the bipartite-graph, and the average number of iterations of the decoder can be reduced to (d/sub v/-1)/d/sub v/ by using the proposed algorithm without performance degradation or additional computation.

International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)•Jun 15, 2005•1 citation

A proof of the hadamard transform decoding of the belief propagation algorithm for LDPCC over GF(q)

Xiangming Li, Mohammad Soleymani

The LDPCC (low-density parity-check codes) belief propagation decoding algorithm uses a bipartite graph and sends belief messages between the variable symbols and the checks in an iterative process. The message that a check sends to a variable symbol can be calculated using a Hadamard transform, as introduced by T.J. Richardson and R.L. Urbanke (see IEEE Trans. Inform. Theory, vol.IT-47, p.599-618, 2001). However, the explicit proof of the correctness of the FHT (fast Hadamard transform) implementation of the decoding algorithm has not, so far, been seen in the literature. We give a proof for the FHT implementation of the decoding algorithm for LDPC codes over GF(q).

IEEE Vehicular Technology Conference•Apr 12, 2005•17 citations

Reduced complexity and improved performance decoding algorithm for nonbinary LDPC codes over GF(q)

Xin Chen, Aidong Men

Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.

IEEE International Conference on Communication Technology (ICCT)•Nov 1, 2008•6 citations

Check-Belief Propagation Decoding of LDPC Codes

Wu Guan, Liping Liang

Variant belief propagation (BP) algorithms are applied to low-density parity-check (LDPC) codes. However, conventional decoders suffer from a large resource consumption due to gathering messages from all the neighbour variable-nodes and/or check-nodes through cumulative calculations. In this paper, a check-belief propagation (CBP) decoding algorithm is proposed. Check-belief is used as the probability that the corresponding parity-check is satisfied. All check-beliefs are iteratively enlarged in a sequential recursive order, and successful decoding will be achieved after the check-beliefs are all big enough. Compared to previous algorithms employing a large number of cumulative calculations to gather all the neighbour messages, CBP decoding can renew each check-belief by propagating it from one check-node to another through only one variable-node, resulting in a low complexity decoding with no cumulative calculations. The simulation results and analyses show that the CBP algorithm provides little error-rate performance loss in contrast with the previous BP algorithms, but consumes much fewer calculations and memories than them. It earns a big benefit in terms of complexity.

arXiv:2305.05286•IEEE Transactions on Communications•Aug 24, 2023•16 citations
In this paper, we propose a new fast Hadamard transform based the belief-propagation (BP) decoding algorithm over GF (2p) with a modification of the permutations between the check nodes and variable nodes. This scheme is mathematically equivalent to the conventional BP decoding algorithm, but complexity of the proposed scheme is lower. We show by simulation that the non-binary regular and irregular LDPC codes in GF (2p) have good performance with our proposed modified BP decoding algorithm.
The Layered Belief Propagation L-BP algorithm is is a modified Belief Propagation BP algorithm, where the check nodes are divided in subgroups called layers and each iteration is broken into multiple sub-iterations. In this paper, we consider layered belief propagation decoding and propose an efficient variable node layering for decoding LDPC codes that performs well. We compare the performance of the first introduced LDPC decoding algorithm BP and Layered BP using check node layering with Layered BP using variable node layering in terms of bit error rate (BER). We show that the convergence for decoding LDPC codes is increasing by using a simple and efficient layering strategy.
We propose a new belief propagation (BP) decoding algorithm for fast convergence decoding of regular LDPC codes. The fast convergence is achieved by grouping and scheduling updates of nodes on a bipartite-graph without additional computations or approximations. For this reason, the proposed algorithm can be applied to a serially constructed decoder, and can reduce the power consumption and decoding delay of the decoder. Simulation results show that the convergence speed of the proposed algorithm depends on the degree, d/sub v/, of the variable-nodes of the bipartite-graph, and the average number of iterations of the decoder can be reduced to (d/sub v/-1)/d/sub v/ by using the proposed algorithm without performance degradation or additional computation.
The LDPCC (low-density parity-check codes) belief propagation decoding algorithm uses a bipartite graph and sends belief messages between the variable symbols and the checks in an iterative process. The message that a check sends to a variable symbol can be calculated using a Hadamard transform, as introduced by T.J. Richardson and R.L. Urbanke (see IEEE Trans. Inform. Theory, vol.IT-47, p.599-618, 2001). However, the explicit proof of the correctness of the FHT (fast Hadamard transform) implementation of the decoding algorithm has not, so far, been seen in the literature. We give a proof for the FHT implementation of the decoding algorithm for LDPC codes over GF(q).
Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.
Variant belief propagation (BP) algorithms are applied to low-density parity-check (LDPC) codes. However, conventional decoders suffer from a large resource consumption due to gathering messages from all the neighbour variable-nodes and/or check-nodes through cumulative calculations. In this paper, a check-belief propagation (CBP) decoding algorithm is proposed. Check-belief is used as the probability that the corresponding parity-check is satisfied. All check-beliefs are iteratively enlarged in a sequential recursive order, and successful decoding will be achieved after the check-beliefs are all big enough. Compared to previous algorithms employing a large number of cumulative calculations to gather all the neighbour messages, CBP decoding can renew each check-belief by propagating it from one check-node to another through only one variable-node, resulting in a low complexity decoding with no cumulative calculations. The simulation results and analyses show that the CBP algorithm provides little error-rate performance loss in contrast with the previous BP algorithms, but consumes much fewer calculations and memories than them. It earns a big benefit in terms of complexity.