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 Symposium on Electrical & Electronics Engineering

A low-complexity algorithm for decoding of M-ary LDPC codes

Baomao Pang, Haoshan Shi, Guanghua He

Published Jun 1, 2012• 0 citations
Publisher

Abstract

M-ary LDPC codes provide higher performances than their binary counterpart but suffer from highest decoding complexity. The use of stochastic decoding algorithm can reduce the decoding complexity, but the computational complexity of probability generation is very high. A simple method to fast generate the probability especially in high-order modulation schemes is proposed in this paper. Simulation results show the proposed algorithm causes negligible performance degradation with reduction in computational complexity, which gives some advantages in hardware implementation of the decoders.

DOI
10.1109/eeesym.2012.6258660

Related papers

Low-complexity probability generation algorithm for stochastic decoding of non-binary LDPC codes

Guanghua He, Baoming Bai

Non-binary LDPC codes offer higher performances than their binary counterpart but suffer from highest decoding complexity. A solution to reduce the decoding complexity is the use of stochastic decoding algorithm, but the computational complexity of probability generation in the first step is very high. In this paper, we propose a simple method to fast generate the probability especially in high-order modulation schemes. Simulation results show that the proposed algorithm causes negligible performance degradation with reduction in computational complexity for stochastic decoding of non-binary LDPC codes, which gives some advantages in hardware implementation of the decoders.

International ICST Conference on Communications and Networking in China•Aug 1, 2011•0 citations

Efficient algorithms for stochastic decoding of LDPC codes

Kuo-Lun Huang

The expanding demand for high-speed communications has resulted in development of high-throughput error-correcting techniques required by emerging communication standards. Low-Density Parity-Check (LDPC) codes are a class of linear block codes that achieve near-capacity performance and have been selected as part of many digital communication standards. Stochastic computation has been proposed as a hardware efficient approach for decoding LDPC codes. Using stochastic computation, all messages in the iterative decoding process are represented by Bernoulli sequences. Computations on these sequences are performed bit-by-bit using simple logic operations. Furthermore, serial messages used in stochastic decoders help alleviate routing congestion in hardware implementation of decoder. These factors make stochastic decoding a low complexity alternative to implement LDPC decoders. In this dissertation, we analyze the characteristics of stochastic decoding and propose reduced-latency designs for stochastic LDPC decoders to achieve improved performance on various channel models.

•Jan 1, 2016•2 citations

Reduced-latency stochastic decoding of LDPC codes over GF(q)

Gabi Sarkis, Warren J. Gross

Non-binary LDPC codes have excellent error-correcting performance but have not yet been widely adopted due to the high decoder implementation complexity. Stochastic decoding has been proposed as a low-complexity decoding algorithm for non-binary LDPC codes. In this paper we present a new stochastic decoding algorithm for non-binary LDPC codes using tracking forecast memories that has higher throughput and lower latency than previous stochastic decoders.

European Wireless Conference•Jan 1, 2010•12 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

Stochastic Decoding of LDPC Codes over GF(q)

Gabi Sarkis, Shie Mannor, Warren J. Gross

Non-binary LDPC codes have been shown to outperform currently used codes for magnetic recording and several other channels. Currently proposed nonbinary decoder architectures have very high complexity for high-throughput implementations and sacrifice error-correction performance to maintain realizable complexity. In this paper, we present an alternative decoding algorithm based on stochastic computation that has a very simple implementation and minimal performance loss when compared to the sum-product algorithm. We demonstrate the performance of the algorithm when applied to a GF(16) code and provide details of the hardware resources required for an implementation.

International Conference on Communications•Jun 1, 2009•32 citations

A message-passing decoding algorithm for q-ary LDPC codes with low-complexity

Chao‐Yu Chen, Qin Huang, Chi-chao Chao +1 more

This paper presents a novel low-complexity iterative reliability-based decoding algorithm for LDPC codes over q-ary finite fields. This proposed algorithm has low complexity and hence provides an effective trade-off between error performance and decoding complexity compared to q-ary sum product algorithm. This decoding algorithm is devised based on simple orthogonal concept of one-step majority-logic decoding for q-ary linear block codes. It requires only integer and finite field operations and converges very fast in decoding. It is particularly effective for decoding LDPC codes constructed based on finite geometries and finite fields.

International Symposium on Information Theory and its Applications•Oct 1, 2010•0 citations
M-ary LDPC codes provide higher performances than their binary counterpart but suffer from highest decoding complexity. The use of stochastic decoding algorithm can reduce the decoding complexity, but the computational complexity of probability generation is very high. A simple method to fast generate the probability especially in high-order modulation schemes is proposed in this paper. Simulation results show the proposed algorithm causes negligible performance degradation with reduction in computational complexity, which gives some advantages in hardware implementation of the decoders.
Non-binary LDPC codes offer higher performances than their binary counterpart but suffer from highest decoding complexity. A solution to reduce the decoding complexity is the use of stochastic decoding algorithm, but the computational complexity of probability generation in the first step is very high. In this paper, we propose a simple method to fast generate the probability especially in high-order modulation schemes. Simulation results show that the proposed algorithm causes negligible performance degradation with reduction in computational complexity for stochastic decoding of non-binary LDPC codes, which gives some advantages in hardware implementation of the decoders.
The expanding demand for high-speed communications has resulted in development of high-throughput error-correcting techniques required by emerging communication standards. Low-Density Parity-Check (LDPC) codes are a class of linear block codes that achieve near-capacity performance and have been selected as part of many digital communication standards. Stochastic computation has been proposed as a hardware efficient approach for decoding LDPC codes. Using stochastic computation, all messages in the iterative decoding process are represented by Bernoulli sequences. Computations on these sequences are performed bit-by-bit using simple logic operations. Furthermore, serial messages used in stochastic decoders help alleviate routing congestion in hardware implementation of decoder. These factors make stochastic decoding a low complexity alternative to implement LDPC decoders. In this dissertation, we analyze the characteristics of stochastic decoding and propose reduced-latency designs for stochastic LDPC decoders to achieve improved performance on various channel models.
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.
Non-binary LDPC codes have been shown to outperform currently used codes for magnetic recording and several other channels. Currently proposed nonbinary decoder architectures have very high complexity for high-throughput implementations and sacrifice error-correction performance to maintain realizable complexity. In this paper, we present an alternative decoding algorithm based on stochastic computation that has a very simple implementation and minimal performance loss when compared to the sum-product algorithm. We demonstrate the performance of the algorithm when applied to a GF(16) code and provide details of the hardware resources required for an implementation.
This paper presents a novel low-complexity iterative reliability-based decoding algorithm for LDPC codes over q-ary finite fields. This proposed algorithm has low complexity and hence provides an effective trade-off between error performance and decoding complexity compared to q-ary sum product algorithm. This decoding algorithm is devised based on simple orthogonal concept of one-step majority-logic decoding for q-ary linear block codes. It requires only integer and finite field operations and converges very fast in decoding. It is particularly effective for decoding LDPC codes constructed based on finite geometries and finite fields.