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 Conference on Communications

Stochastic Decoding of LDPC Codes over GF(q)

Gabi Sarkis, Shie Mannor, Warren J. Gross

Published Jun 1, 2009• 32 citations
Publisher

Abstract

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.

DOI
10.1109/icc.2009.5199493

Related papers

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

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

Architecture of a low-complexity non-binary LDPC decoder for high order fields

Adrian Voicila, François S. Verdier, David Declercq +2 more

In this paper, we propose a hardware implementation of the EMS decoding algorithm for non-binary LDPC codes, presented in [10]. To the knowledge of the authors this is the first implementation of a GF(q) LDPC decoder for high order fields (q ges 64). The originality of the proposed architecture is that it takes into account the memory problem of the non-binary LDPC decoders, together with a significant complexity reduction per decoding iteration which becomes independent from the field order. We present the estimation of the non-binary decoder implementation and key metrics including throughput and hardware complexity. The error decoding performance of the low complexity algorithm with proper compensation has been obtained through computer simulations. The frame error rate results are quite good with respect to the important complexity reduction. The results show also that an implementation of a non-binary LDPC decoder is now feasible and the extra complexity of the decoder is balanced by the superior performance of this class of codes. With their foreseen simple architectures and good-error correcting performances, non-binary LDPC codes provide a promising vehicle for real-life efficient coding system implementations.

International Symposium on Communications and Information Technologies•Oct 1, 2007•61 citations

Decoding Algorithms for Nonbinary LDPC Codes Over GF$(q)$

David Declercq, M.P.C. Fossorier

In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes

IEEE Transactions on Communications•Apr 1, 2007•724 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

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
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.
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.
In this paper, we propose a hardware implementation of the EMS decoding algorithm for non-binary LDPC codes, presented in [10]. To the knowledge of the authors this is the first implementation of a GF(q) LDPC decoder for high order fields (q ges 64). The originality of the proposed architecture is that it takes into account the memory problem of the non-binary LDPC decoders, together with a significant complexity reduction per decoding iteration which becomes independent from the field order. We present the estimation of the non-binary decoder implementation and key metrics including throughput and hardware complexity. The error decoding performance of the low complexity algorithm with proper compensation has been obtained through computer simulations. The frame error rate results are quite good with respect to the important complexity reduction. The results show also that an implementation of a non-binary LDPC decoder is now feasible and the extra complexity of the decoder is balanced by the superior performance of this class of codes. With their foreseen simple architectures and good-error correcting performances, non-binary LDPC codes provide a promising vehicle for real-life efficient coding system implementations.
Decoding Algorithms for Nonbinary LDPC Codes Over GF(q)(q)(q)
In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes
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.
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.