Non-binary LDPC codes are promising error correcting techniques with very good performance, especially for high order fields. Using higher order fields enhances performance but, at the same time, increases decoding complexity. Several methods have been proposed to reduce this complexity, such as sub-optimal decoding algorithms or techniques aiming at reducing the number of iterations. In this paper, a technique for selective check nodes update is presented enabling a complexity reduction at the level of iteration in the non-binary case. More than 35% of complex updates can be saved in a large SNR region, with parameters that can be tuned according to the desired complexity/performance ratio.
Non-binary LDPC codes are promising error correcting techniques with very good performance, especially for high order fields. Using higher order fields enhances performance but, at the same time, increases decoding complexity. Several methods have been proposed to reduce this complexity, such as sub-optimal decoding algorithms or techniques aiming at reducing the number of iterations. In this paper, a technique for selective check nodes update is presented enabling a complexity reduction at the level of iteration in the non-binary case. More than 35% of complex updates can be saved in a large SNR region, with parameters that can be tuned according to the desired complexity/performance ratio.
In this paper, we introduce a computationally efficient selective node update algorithm for the decoding of low-density parity check codes. Unlike the standard sum-product algorithm, where all bit and check nodes are updated at each decoding iteration, the developed algorithm only updates unreliable check and bit nodes. A simple reliability criteria is developed to determine the active bit and check nodes per decoding iteration. Based on the developed technique, significant computation reductions are achieved with very little or no loss in the BER performance of the LDPC codes. At a WER of 10-5, 91.8% and 72.7% check node and 80% and 41% bit node computation reductions are obtained for a (96, 48) and a (504, 252) LDPC code, respectively. The proposed method can be implemented with a slight modification to the standard sum-product decoding algorithm with negligible additional hardware complexity. From a hardware point of view, the proposed algorithm offers power reductions proportional to the computation savings and it leads to higher decoding speeds in serial implementations by decreasing the number of required memory accesses
Low-density parity-check (LDPC) codes defined over non-binary (NB) finite field GF(2q)(q >1) achieve better error-correcting performance than binary LDPC codes when the codeword length is moderate. The decoder complexity increases very fast with the order of the field, 2q, although the error-correcting performance also improves. To reduce the complexity for practical applications, NB-LDPC codes over lower-order finite fields are of great interest. Previous designs have been focusing on decoders over either the smallest NB field GF (4) or much larger fields, such as GF (32) or higher. Prior optimization techniques are either not applicable or do not lead to efficient designs for codes over GF (8) or other lower-order fields. In this paper, an efficient architecture is developed for the check node processing, which is the most complicated step in NB-LDPC decoding, for the Min-max algorithm over lower-order fields. By utilizing the properties of finite field elements, the max/min comparison results are shared and the number of comparators needed is reduced significantly. Compared to the best prior design, the proposed check node processing has 18.5% smaller area and shorter critical path for an example code over GF (8).
Non-binary LDPC codes are promising error cor- recting codes for short and moderate block lengths. These codes demonstrate interesting performances in high order fields, though are more complex to decode. As for binary LDPC codes, decoding scheduling can be optimized to improve performance. In this paper, a simulation-based approach is used for different scheduling policies in the non-binary case in order to point out possible performance gains for these codes. An optimization of decoding scheduling is also proposed and exhibits about 20% complexity reduction in error-floor region, thus promising interesting gains if combined with advanced dynamic scheduling strategies. I. INTRODUCTION Channel coding has seen important developments over the last two decades. Thanks to the introduction of advanced error- correcting codes, initiated by Turbo-codes in the early 90's, and to the use of iterative decoding techniques, Shannnon- limit performance has been closely approached. Low-Density Parity-Check (LDPC) codes, first introduced by Gallager (1) in the 60's, were rediscovered by Mackay and Neal (2) in 1996. Excellent error-correcting performance for long block lengths (3) position LDPC codes as an important candidate for advanced communication systems, already adopted in different standards, such as DVB-S2, IEEE 802.16 and 802.11n. How- ever, as codewords become shorter, LDPC performance gains are generally less satisfying. Non-binary LDPC codes, though more complex, proved to significantly improve performance for moderate and short blocklengths (4), (5). The use of a high order alphabet also suggests matching it with the modulation alphabet: LDPC codes over a 16�elements Galois field for example can be naturally mapped in 16�QAM modulated symbols. This would avoid the bit-to-symbol performance loss, especially when having a frequency selective channel, as non- binary encoding can reduce channel memory effect (6). This use of non-binary LDPC codes is thus very promising for high data rate communications, especially when complexity reduc- tion techniques are adopted, either for decoding update rules or scheduling policy. Previous work on scheduling strategies for the binary case can be found in (7). In this paper, we will first address a brief overview of decoding techniques for LDPC codes over high order extension fields. Then, scheduling strategies and effects will be compared for the non-binary case. A simulation-based approach will also be detailed to suggest new scheduling policies, and results from an optimized scheduling will be presented. The paper will be concluded by some remarks and suggestions towards future works.
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.
Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.
A novel adaptive binary decoding algorithm for LDPC codes is proposed, which reduces the decoding complexity while having a comparable or even better performance than corresponding non-adaptive alternatives. In each iteration the variable node decoders use the binary check node decoders multiple times; each single use is referred to as a sub-iteration. To process the sequences of binary messages in each iteration, the variable node decoders employ pre-computed look-up tables. These look-up tables as well as the number of sub-iterations per iteration are dynamically adapted during the decoding process based on the decoder state, represented by the mutual information between the current messages and the syndrome bits. The look-up tables and the number of sub-iterations per iteration are determined and optimized using density evolution. The performance and the complexity of the proposed adaptive decoding algorithm is exemplified by simulations.