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.
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.
Non-binary LDPC codes are promising error correcting 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.
Recently low-density parity check (LDPC) codes have been applied in more areas, and the research of non-binary LDPC codes has become more significant. In this paper, we establish a dynamic scheduling strategy to reduce complexity of non-binary LDPC codes decoding, and choose extended min-sum algorithm as the model. The dynamic scheduling strategy is based on the idea of nodes reliability. When decoding, we select a part of check nodes to update messages in real time according to the reliability rules, and only the variable nodes getting new messages can participate in the message propagation. Compared with usual standard flooding scheduling, this dynamic scheduling strategy can reduce decoding complexity effectively. We also optimize the message of variable nodes according to reliability, which ensure that the error correction performance of decoding algorithm is not affected. Our simulations over a BPSK-AWGN channel show that this dynamic scheduling strategy can reduce complexity in non-binary LDPC codes belief propagation decoding without affecting error correction performance.
In this work, iterative decoders for Low-Density Parity-Check (LDPC) codes are analyzed and optimized for low computational complexity. LDPC block codes are now widely used in industry standards such as Wi-Fi or 5G New Radio (NR). Hence, there is a strong need for decoder concepts suitable for hardware designs. In addition, terminated LDPC convolutional codes are promising candidates for next-generation communication systems. The main theme of this work is to investigate low-overhead strategies for reducing the computational complexity of iterative decoders. Two aspects are considered for fast decoding of the LDPC block codes in 5G NR. Firstly, an efficient but simple-to determine update schedule for the iterative decoding process, i.e., the sequence of updates on different parts of a codeword, is proposed. Secondly, Early Termination (ET), i.e., an option to stop decoding before a maximal number of iterations is exhausted, is improved in two ways: On the one hand, a partial evaluation of the code’s Parity-Check (PC) equations speeds up the detection of valid codewords. On the other hand, a novel criterion detects when the decoding process is unlikely to converge and stops the decoding before a lot of resources are wasted on futile iterations. The combination of all techniques results in a decoder with significant reduction of the computational complexity compared to a decoder without these methods. Still, only few additional residual decoding errors are produced. This work also contains an analysis of various aspects of a Windowed Decoder (WD), which is a specialized decoder design for LDPC convolutional codes. A WD can be configured in even more ways than a decoder for block codes. The analysis in this work assumes a normalization of the computational complexity to a certain maximal value. With this setup, it is shown that a larger size of the decoding window may be preferable over a smaller size to minimize the computational complexity. Furthermore, various window update strategies (determining in which way the code symbol reliabilities are updated in each window) and variations of ET are compared to identify a well-suited WD configuration. Lastly, strategies with Dynamic Scheduling (DS) are considered to further reduce the computational complexity. A novel fixed approach derived from several DS strategies performs well without actual dynamic knowledge of the decoder state. All in all, the optimized WD configuration halves the computational complexity of a block decoder while maintaining an acceptable loss in the decoding performance measured by the number of residual decoding errors. A comparison of systems with Hybrid Automatic Repeat reQuest (HARQ) expands the scope of this work into the domain of error control by retransmissions. The analyzed systems make use of the decoder output, e.g., the final code-symbol reliabilities, to assemble dynamic retransmissions that are as short as possible and contain specifically selected code symbols. These systems stand in contrast to contemporary implementations of HARQ that only use imprecise feedback messages. Still, some compatibility with existing systems is achieved by assuming a limited feedback channel, which requires clever compression of the feedback information. A novel HARQ system is proposed, which evaluates the code’s PC equations to avoid the computational overhead of soft-value processing. The throughput with the proposed system is found to be improved compared to a reference system that evaluates code-symbol reliabilities. Finally, approximations of the accurate message-update rules of the Sum–Product Algorithm (SPA) are analyzed. With fixed-point arithmetic, Look-Up Tables (LUTs) are a promising approach to approximate functions that are costly to compute. It is shown that an optimized LUT with just nine entries can be used in a fixed-point decoder such that the decoding performance is close to that of a floating-point decoder with accurate message updates.
After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area.
This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.
Recent advances in coding theory have uncovered the previously forgotten power of Low-Density Parity-Check (LDPC) codes. Their popularity can be related to their relatively simple iterative decoders and their potential to achieve high performance close to shannon limit. These make them an attractive candidate for error correcting application in communication systems. In this thesis, we focus our research on the iterative decoding algorithms for Low-Density Parity-Check codes and present an improved decoding algorithm. First, the graph structure of LDPC codes is studied and a graph-based search algorithm to find the shortest closed walk and shortest cycle for each node of the graph is proposed. Then, the Deterministic schedule is applied on nodes of the graph with the objective of preserving the optimality of the algorithms. Finally, Hybrid Switch-Type technique is applied on the improved algorithms to provide a desirable complexity/performance trade-off. Hybrid Technique and Deterministic schedule are combined for decoding regular and irregular LDPC codes. The performance and complexity of the decoder is studied for Sum-Product and Gallager A algorithms. The result is a flexible decoder for any available LDPC code and any combination of decoding algorithms based on the communication systems need. In this technique, we benefit the high performance of soft-decision algorithms and low complexity of hard-decision algorithms by changing the decoding rule after a few iterations. Hence, a desirable performance can be obtained with less average number of soft iterations. Moreover, all the nodes do not update messages in each iteration. As a result, the total number of computations is reduced considerably
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
…