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

IEEE Communications Letters

Efficient Stochastic Decoding of Non-Binary LDPC Codes with Degree-Two Variable Nodes

Gabi Sarkis, Warren J. Gross

Published Jan 4, 2012• 21 citations
Publisher

Abstract

In this letter, we present an optimized version of the relaxed half-stochastic (RHS) algorithm targeted at non-binary LDPC codes with a variable node degree equal to two. The new algorithm has significantly fewer multiplications while maintaining an error-correction performance and a decoding iteration count identical to those of the original.

DOI
10.1109/lcomm.2011.122211.111737

Related papers

A Relaxed Half-Stochastic Iterative Decoder for LDPC Codes

François Leduc-Primeau, Saied Hemati, Warren J. Gross +1 more

This paper presents a Relaxed Half-Stochastic (RHS) low-density parity-check (LDPC) decoding algorithm that uses some elements of the sum-product algorithm (SPA) in its variable nodes, but maintains the low-complexity interleaver and check node structures characteristic of stochastic decoders. The algorithm relies on the principle of successive relaxation to convert binary stochastic streams to a log-likelihood ratio (LLR) representation. Simulations of a (2048, 1723) RS-LDPC code show that the RHS algorithm can outperform 100-iterations floating-point SPA decoding. We describe approaches for low-complexity implementation of the RHS algorithm. Furthermore, we show how the stochastic nature of the belief representation can be exploited to lower the error floor.

Globecom•Nov 1, 2009•20 citations

Stochastic Decoding of LDPC Codes over GF(q)

Gabi Sarkis, Saied Hemati, Shie Mannor +1 more

Despite the outstanding performance of non-binary low-density parity-check (LDPC) codes over many communication channels, they are not in widespread use yet. This is due to the high implementation complexity of their decoding algorithms, even those that compromise performance for the sake of simplicity. In this paper, we present three algorithms based on stochastic computation to reduce the decoding complexity. The first is a purely stochastic algorithm with error-correcting performance matching that of the sum-product algorithm (SPA) for LDPC codes over Galois fields with low order and a small variable node degree. We also present a modified version which reduces the number of decoding iterations required while remaining purely stochastic and having a low per-iteration complexity. The second algorithm, relaxed half-stochastic (RHS) decoding, combines elements of the SPA and the stochastic decoder and uses successive relaxation to match the error-correcting performance of the SPA. Furthermore, it uses fewer iterations than the purely stochastic algorithm and does not have limitations on the field order and variable node degree of the codes it can decode. The third algorithm, NoX, is a fully stochastic specialization of RHS for codes with a variable node degree 2 that offers similar performance, but at a significantly lower computational complexity. We study the performance and complexity of the algorithms; noting that all have lower per-iteration complexity than SPA and that RHS can have comparable average per-codeword computational complexity, and NoX a lower one.

IEEE Transactions on Communications•Feb 6, 2013•27 citations

Modification in the Construction of Non-Binary LDPC Decoder using Stochastic Computation

R. Kalaiarasan, M. Anbuselvi

Low-Density Parity Check (LDPC) codes are linear block codes which perform closer to Shannon"s limit.It is defined by the parity check matrix (PCM) which contains only a few ones in comparison to the number of zeros (sparsity).Stochastic based computation is a method to design lowprecision digital circuits.In stochastic computing, probabilities are encoded by random sequences of bits.In this paper, we focus on the design of Relaxed Half Stochastic (RHS) based algorithm for Non-Binary LDPC decoder, with reduced hardware complexity and optimal decoding performance.Here Sum Product Algorithm (SPA) based variable nodes and stochastic based check nodes are integrated.Thereby the convergence speed of the algorithm is improved.The limitation of the complete stochastic decoder is based on the field order and the degree of variable node.This could be overcome by the method of RHS algorithm.The PCM (Parity Check Matrix) which defines the strength of the LDPC codes contains the non-zero elements.Increasing the sparsity of the PCM, helps in reducing the computation complexity.We propose two modifications in the PCM namely, LDM (Lower Diagonal Matrix) and DDM (Doubly Diagonal Matrix).Decoding performance measured in terms of bit error rate shows that non binary LDPC decoder outperforms than binary LDPC decoder.

International Journal of Computer Applications•Apr 18, 2014•0 citations

Relaxed half-stochastic decoding of LDPC codes over GF(q)

Gabi Sarkis, Saied Hemati, Shie Mannor +1 more

The error-correcting performance of non-binary LDPC codes has been shown to be better than most codes currently used for a variety of applications. However, due to the very high complexity of decoding these codes, they are not ubiquitously used. Moreover, an SPA decoder is so prohibitively complex, that a fully parallel implementation is not feasible even with simplified algorithms. In this paper we present a new algorithm which approaches the low complexity of stochastic decoding with the high performance of SPA decoding by combining elements from both algorithms and applying successive relaxation. We study its performance using a number of codes and show that it matches that of the SPA. We also analyze its complexity compared to the SPA and conclude that it has lower per iteration complexity and can have comparable average complexity per codeword. Due to the lower per iteration complexity, RHS has the potential of being implemented as a parallel, or partially parallel, decoder that is faster than a feasible SPA decoder.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2010•5 citations

Relaxed Half-Stochastic Belief Propagation

François Leduc-Primeau, Saied Hemati, Shie Mannor +1 more

Low-density parity-check codes are attractive for high throughput applications because of their low decoding complexity per bit, but also because all the codeword bits can be decoded in parallel. However, achieving this in a circuit implementation is complicated by the number of wires required to exchange messages between processing nodes. Decoding algorithms that exchange binary messages are interesting for fully-parallel implementations because they can reduce the number and the length of the wires, and increase logic density. This paper introduces the Relaxed Half-Stochastic (RHS) decoding algorithm, a binary message belief propagation (BP) algorithm that achieves a coding gain comparable to the best known BP algorithms that use real-valued messages. We derive the RHS algorithm by starting from the well-known Sum-Product algorithm, and then derive a low-complexity version suitable for circuit implementation. We present extensive simulation results on two standardized codes having different rates and constructions, including low bit error rate results. These simulations show that RHS can be an advantageous replacement for the existing state-of-the-art decoding algorithms when targeting fully-parallel implementations.

arXiv:1205.2428•May 11, 2012•1 citation

Relaxed Half-Stochastic Belief Propagation

François Leduc-Primeau, Saied Hemati, Shie Mannor +1 more

Low-density parity-check codes are attractive for high throughput applications because of their low decoding complexity per bit, but also because all the codeword bits can be decoded in parallel. However, achieving this in a circuit implementation is complicated by the number of wires required to exchange messages between processing nodes. Decoding algorithms that exchange binary messages are interesting for fully-parallel implementations because they can reduce the number and the length of the wires, and increase logic density. This paper introduces the Relaxed Half-Stochastic (RHS) decoding algorithm, a binary message belief propagation (BP) algorithm that achieves a coding gain comparable to the best known BP algorithms that use real-valued messages. We derive the RHS algorithm by starting from the well-known Sum-Product algorithm, and then derive a low-complexity version suitable for circuit implementation. We present extensive simulation results on two standardized codes having different rates and constructions, including low bit error rate results. These simulations show that RHS can converge faster on average than existing state-of-the-art decoding algorithms, leading to improvements in throughput and energy efficiency.

IEEE Transactions on Communications•Feb 22, 2013•13 citations
In this letter, we present an optimized version of the relaxed half-stochastic (RHS) algorithm targeted at non-binary LDPC codes with a variable node degree equal to two. The new algorithm has significantly fewer multiplications while maintaining an error-correction performance and a decoding iteration count identical to those of the original.
This paper presents a Relaxed Half-Stochastic (RHS) low-density parity-check (LDPC) decoding algorithm that uses some elements of the sum-product algorithm (SPA) in its variable nodes, but maintains the low-complexity interleaver and check node structures characteristic of stochastic decoders. The algorithm relies on the principle of successive relaxation to convert binary stochastic streams to a log-likelihood ratio (LLR) representation. Simulations of a (2048, 1723) RS-LDPC code show that the RHS algorithm can outperform 100-iterations floating-point SPA decoding. We describe approaches for low-complexity implementation of the RHS algorithm. Furthermore, we show how the stochastic nature of the belief representation can be exploited to lower the error floor.
Despite the outstanding performance of non-binary low-density parity-check (LDPC) codes over many communication channels, they are not in widespread use yet. This is due to the high implementation complexity of their decoding algorithms, even those that compromise performance for the sake of simplicity. In this paper, we present three algorithms based on stochastic computation to reduce the decoding complexity. The first is a purely stochastic algorithm with error-correcting performance matching that of the sum-product algorithm (SPA) for LDPC codes over Galois fields with low order and a small variable node degree. We also present a modified version which reduces the number of decoding iterations required while remaining purely stochastic and having a low per-iteration complexity. The second algorithm, relaxed half-stochastic (RHS) decoding, combines elements of the SPA and the stochastic decoder and uses successive relaxation to match the error-correcting performance of the SPA. Furthermore, it uses fewer iterations than the purely stochastic algorithm and does not have limitations on the field order and variable node degree of the codes it can decode. The third algorithm, NoX, is a fully stochastic specialization of RHS for codes with a variable node degree 2 that offers similar performance, but at a significantly lower computational complexity. We study the performance and complexity of the algorithms; noting that all have lower per-iteration complexity than SPA and that RHS can have comparable average per-codeword computational complexity, and NoX a lower one.
Low-Density Parity Check (LDPC) codes are linear block codes which perform closer to Shannon"s limit.It is defined by the parity check matrix (PCM) which contains only a few ones in comparison to the number of zeros (sparsity).Stochastic based computation is a method to design lowprecision digital circuits.In stochastic computing, probabilities are encoded by random sequences of bits.In this paper, we focus on the design of Relaxed Half Stochastic (RHS) based algorithm for Non-Binary LDPC decoder, with reduced hardware complexity and optimal decoding performance.Here Sum Product Algorithm (SPA) based variable nodes and stochastic based check nodes are integrated.Thereby the convergence speed of the algorithm is improved.The limitation of the complete stochastic decoder is based on the field order and the degree of variable node.This could be overcome by the method of RHS algorithm.The PCM (Parity Check Matrix) which defines the strength of the LDPC codes contains the non-zero elements.Increasing the sparsity of the PCM, helps in reducing the computation complexity.We propose two modifications in the PCM namely, LDM (Lower Diagonal Matrix) and DDM (Doubly Diagonal Matrix).Decoding performance measured in terms of bit error rate shows that non binary LDPC decoder outperforms than binary LDPC decoder.
The error-correcting performance of non-binary LDPC codes has been shown to be better than most codes currently used for a variety of applications. However, due to the very high complexity of decoding these codes, they are not ubiquitously used. Moreover, an SPA decoder is so prohibitively complex, that a fully parallel implementation is not feasible even with simplified algorithms. In this paper we present a new algorithm which approaches the low complexity of stochastic decoding with the high performance of SPA decoding by combining elements from both algorithms and applying successive relaxation. We study its performance using a number of codes and show that it matches that of the SPA. We also analyze its complexity compared to the SPA and conclude that it has lower per iteration complexity and can have comparable average complexity per codeword. Due to the lower per iteration complexity, RHS has the potential of being implemented as a parallel, or partially parallel, decoder that is faster than a feasible SPA decoder.
Low-density parity-check codes are attractive for high throughput applications because of their low decoding complexity per bit, but also because all the codeword bits can be decoded in parallel. However, achieving this in a circuit implementation is complicated by the number of wires required to exchange messages between processing nodes. Decoding algorithms that exchange binary messages are interesting for fully-parallel implementations because they can reduce the number and the length of the wires, and increase logic density. This paper introduces the Relaxed Half-Stochastic (RHS) decoding algorithm, a binary message belief propagation (BP) algorithm that achieves a coding gain comparable to the best known BP algorithms that use real-valued messages. We derive the RHS algorithm by starting from the well-known Sum-Product algorithm, and then derive a low-complexity version suitable for circuit implementation. We present extensive simulation results on two standardized codes having different rates and constructions, including low bit error rate results. These simulations show that RHS can be an advantageous replacement for the existing state-of-the-art decoding algorithms when targeting fully-parallel implementations.
Low-density parity-check codes are attractive for high throughput applications because of their low decoding complexity per bit, but also because all the codeword bits can be decoded in parallel. However, achieving this in a circuit implementation is complicated by the number of wires required to exchange messages between processing nodes. Decoding algorithms that exchange binary messages are interesting for fully-parallel implementations because they can reduce the number and the length of the wires, and increase logic density. This paper introduces the Relaxed Half-Stochastic (RHS) decoding algorithm, a binary message belief propagation (BP) algorithm that achieves a coding gain comparable to the best known BP algorithms that use real-valued messages. We derive the RHS algorithm by starting from the well-known Sum-Product algorithm, and then derive a low-complexity version suitable for circuit implementation. We present extensive simulation results on two standardized codes having different rates and constructions, including low bit error rate results. These simulations show that RHS can converge faster on average than existing state-of-the-art decoding algorithms, leading to improvements in throughput and energy efficiency.