International Journal of Computer Applications

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

R. Kalaiarasan, M. Anbuselvi

Published Apr 18, 2014• 0 citations

Abstract

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.

DOI: 10.5120/16105-5337

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 CommunicationsFeb 6, 201327 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

LOW COMPLEXITY DESIGN OF NON-BINARY LDPC DECODER USING EXTENDED MIN-SUM ALGORITHM

C.S.Elamaran

Low Density Parity Check (LDPC) codes, is a linear block code having the decoding performance closer to Shannon's limit.Nonbinary LDPC is the class of binary LDPC, which works on the higher order Galois field.The decoding performance of non-binary (NB) LDPC is better than binary LDPC for moderate code lengths.The increased computation with the increased order of field is the major challenge in hardware realization of NB-LDPC.The extension of conventional sum-product algorithm, known as extended Min-Sum (EMS) algorithm, with reduced computational complexity is used in this paper.However, a tradeoff exists between computational complexity and decoding performance. This paper aims at reducing the computational complexity by focusing on the Parity Check Matrix (PCM) modifications. The bottleneck of the design is large memory requirement and more computation intensive. The modification in the EMS algorithm can be incorporated to design low complexity hardware architecture of NB-LDPC decoder.

International Journal of Research in Engineering and TechnologyApr 25, 20151 citation

Analysis of a Code Construction Method for Non-Binary Quasi-Cyclic Irregular Low Density Parity Check Decoder

M. Anbuselvi, P. Saravanan, S. Joseph Gladwin

Non-binary LDPC codes is a class of linear block code outperform in the short and moderate block length, closer to Shannon's limit. The numerical strength of the decoder is proportional to the sparsity of the parity check matrix. A Hierarchically Diagonal Parity Check Matrix (HDPCM) with better sparseness is constructed to optimize the computation complexity and decoding performance. The decoder based on the proposed matrix using FFT-SP decoding algorithm is analyzed, with different modulation schemes and channel environment. The positive impact of the constructed matrix is elaborated, concludes with the suitability of the HDPCM structure in AWGN channel and BPSK modulation environment.

Journal of Computational and Theoretical NanoscienceJan 19, 20181 citation

Optimized Min-Sum Decoding Algorithm for Low Density Parity Check Codes

Mohammad Rakibul, Dewan Siam Shafiullah, Muhammad Mostafa +1 more

Low Density Parity Check (LDPC) code approaches Shannon–limit performance for binary field and long code lengths. However, performance of binary LDPC code is degraded when the code word length is small. An optimized min-sum algorithm for LDPC code is proposed in this paper. In this algorithm unlike other decoding methods, an optimization factor has been introduced in both check node and bit node of the Min-sum algorithm. The optimization factor is obtained before decoding program, and the same factor is multiplied twice in one cycle. So the increased complexity is fairly low. Simulation results show that the proposed Optimized Min-Sum decoding algorithm performs very close to the Sum-Product decoding while preserving the main features of the Min-Sum decoding, that is low complexity and independence with respect to noise variance estimation errors.

International Journal of Advanced Computer Science and ApplicationsJan 1, 201119 citations

Optimized Min-Sum Decoding Algorithm for Low Density Parity Check Codes

Mohammad Rakibul Islam, Dewan Siam Shafiullah, Muhammad Mostafa +2 more

Abstract ― Low Density Parity Check (LDPC) code approaches Shannon–limit performance for binary field and long code lengths. However, performance of binary LDPC code is degraded when the code word length is small. An optimized min-sum algorithm for LDPC code is proposed in this paper. In this algorithm unlike other decoding methods, an optimization factor has been introduced in both check node and bit node of the Min-sum algorithm. The optimization factor is obtained before decoding program, and the same factor is multiplied twice in one cycle. So the increased complexity is fairly low. Simulation results show that the proposed Optimized Min-Sum decoding algorithm performs very close to the Sum-Product decoding while preserving the main features of the Min-Sum decoding, that is low complexity and independence with respect to noise variance estimation errors.

Oct 31, 20152 citations