IEEE Transactions on Communications

Stochastic Decoding of LDPC Codes over GF(q)

Gabi Sarkis, Saied Hemati, Shie Mannor, Warren J. Gross

Published Feb 6, 2013• 27 citations

Abstract

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.

DOI: 10.1109/tcomm.2013.012913.110340

Related papers

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 ComputingSep 1, 20105 citations

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.

GlobecomNov 1, 200920 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 ApplicationsApr 18, 20140 citations

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

Gabi Sarkis, Warren J. Gross

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.

IEEE Communications LettersJan 4, 201221 citations

Design of Low-Density Parity-Check Codes and Their Decoding Algorithms

조성혜

In this thesis, we propose low-complexity designing algorithms for non-binary low-density parity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding algorithms for binary LDPC codes. We first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q) based on message-passing algorithms. Short cycles in an NB-LDPC code may be even more harmful to its performance if they do not satisfy the so-called full rank condition (FRC). This is because they may induce low-weight codewords or absorbing sets in that case. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as the number of short cycles for analyzing the performance of an NB-LDPC code. In order to count those cycles, we first develop a novel message-passing algorithm and identify how it is related to the FRC.We then propose a low-complexity algorithmfor counting the number of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short cycles. The proposed algorithm is not only theoretically validated, but its computational and storage complexities are also computed. It does not require cycle enumeration with high complexity, and therefore is still feasible even in the case of large code length, say ≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal rule to choose a nonzero element for a given edge and propose a low-complexity algorithm for designing an NB-LDPC code with low error floor. Furthermore, several design examples are presented to verify the validity of the proposed design algorithm. Secondly, we propose a low-complexity decoding algorithm for binary LDPC codes over the binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding algorithm for binary LDPC codes and has lower computational complexity than the sum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it has performance degradation. Furthermore, reducing the number of bits for representing messages to two in a decoding algorithm for further reducing computational and storage complexities, causes significant performance losses. In order to minimize the performance degradation and computational and storage complexities, we propose a low-complexity decoding algorithm which uses several decoders with two-bit precision for binary LDPC codes over the BSC. The proposed algorithm adaptively changes decoders according to the number of unsatisfied check nodes at each iteration. Compared with the SPA using floating-point operations, the proposed decoding algorithm greatly reduces computational and storage complexities with negligible performance losses. Numerical results show that the proposed decoding algorithm has similar performance to the SPA with floating-point operations over the BSC. In the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes for the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms …

Jan 1, 20180 citations

A Novel Stochastic Decoding of LDPC Codes with Quantitative Guarantees

Nima Noorshams, Aravind Raghava Iyengar

Low-density parity-check codes, a class of capacity-approaching linear codes, are particularly recognized for their efficient decoding scheme. The decoding scheme, known as the sum-product, is an iterative algorithm consisting of passing messages between variable and check nodes of the factor graph. The sum-product algorithm is fully parallelizable, owing to the fact that all messages can be update concurrently. However, since it requires extensive number of highly interconnected wires, the fully-parallel implementation of the sum-product on chips is exceedingly challenging. Stochastic decoding algorithms, which exchange binary messages, are of great interest for mitigating this challenge and have been the focus of extensive research over the past decade. They significantly reduce the required wiring and computational complexity of the message-passing algorithm. Even though stochastic decoders have been shown extremely effective in practice, the theoretical aspect and understanding of such algorithms remains limited at large. Our main objective in this paper is to address this issue. We first propose a novel algorithm referred to as the Markov based stochastic decoding. Then, we provide concrete quantitative guarantees on its performance for tree-structured as well as general factor graphs. More specifically, we provide upper-bounds on the first and second moments of the error, illustrating that the proposed algorithm is an asymptotically consistent estimate of the sum-product algorithm. We also validate our theoretical predictions with experimental results, showing we achieve comparable performance to other practical stochastic decoders.

arXiv:1405.6353May 25, 20140 citations