Low-Complexity Decoding Algorithms for Non-Binary Low-Density Parity-Check Codes

Abstract

In this thesis, we propose low-complexity decoding algorithms for non-binary low-density parity-check (NB-LDPC) codes over GF($q$), which achieve gains of computational complexity, latency, convergence, or performance.

We first propose a low-complexity low-latency decoding algorithm for NB-LDPC codes over GF($q$). The extended min-sum (EMS) and improved EMS (I-EMS) algorithms for NB-LDPC codes over GF($q$) significantly reduce the decoding complexity with an acceptable performance degradation, but they suffer from high latency due to many serial computations including a sorting process. On the other hand, the trellis-based EMS (T-EMS) algorithm can greatly reduce the latency, but it does not solve the complexity problem in high order fields ($q\geq 64$). To improve the latency problem with low-complexity advantages, we propose heap-based EMS (H-EMS) and heap-based I-EMS (HI-EMS) algorithms which are modifications of the EMS and I-EMS algorithms, respectively. We also propose double H-EMS and double HI-EMS algorithms trading off the latency against the performance by heaping messages twice. Numerical results show that the H-EMS algorithm has 2.74 to 9.52 times lower latency than the EMS algorithm with a negligible performance degradation over a wide range of code rates, while the HI-EMS algorithm has 1.20 to 1.62 times lower latency than the I-EMS algorithm. Furthermore, the proposed algorithms may be employed regardless of the decoding schedules.

Secondly, an adaptive version of the I-EMS algorithm is proposed. The I-EMS algorithm for decoding NB-LDPC codes over GF($q$) significantly reduces the decoding complexity by truncating each message into a message of effective length $n_m$. The number of effectively dominant components in each truncated message may gradually decrease with the number of iterations. Based on this observation, we propose a novel adaptive EMS algorithm, called the two-length EMS (TL-EMS) algorithm. It chooses one of two candidates as the effective message length $n_m$ for each message. By reflecting the concept called {\em message separation}, the proposed algorithm can effectively determine the proper value of $n_m$ between two candidates for each message. Numerical results show that it can significantly reduce the computational complexity with little performance degradation as the number of iterations increases.

We next propose novel decoding schedules for NB-LDPC codes over GF($q$). Informed dynamic schedules (IDSs) such as the residual belief-propagation (RBP) are employed for decoding of binary LDPC codes in order to accelerate convergence speed. But they require tremendous additional computations when they are simply extended to nonbinary LDPC codes over GF($q$). On the other hand, some probabilistic approaches have been proposed for decoding of nonbinary codes, based on the $q$-ary sum-product algorithm (QSPA). In order to enhance convergence speed with an acceptable computational complexity, we propose novel IDSs for nonbinary LDPC decoders using the log-domain QSPA or the I-EMS algorithm. The proposed schedules, called weighted message-approximated RBPs (WMA-RBPs), efficiently perform IDS without a drastic increase of computational complexity. Numerical results show that the WMA-RBP has a much faster convergence speed than traditional schedules. Moreover, it significantly reduces computational complexity, while maintaining almost the same convergence speed, compared with a nonbinary-extended version of the RBP.

Fourthly, hybrid decoders for NB-LDPC codes over GF($q$), which achieve both high performance and low complexity, are proposed. Two novel hybrid decoders for NB-LDPC codes are proposed. By taking the trellis-based extended min-sum (T-EMS) algorithm and the multiple-vote symbol-flipping (MV-SF) algorithm as their component decoders, the proposed decoders have a significant performance gain, while maintaining low complexity. Numerical results show that they outperform the T-EMS and the MV-SF algorithms. Moreover, one of them has a negligible increase of complexity, compared with the MV-SF algorithm, and the other has almost the same complexity as the T-EMS algorithm.

In the last part of this thesis, a low-complexity decoding scheme of LDPC codes for the layered-division multiplexing (LDM) systems in ATSC 3.0 is proposed. Based on the unique characteristic of the LDM and the special structure of a parity-check matrix (PCM) for the core layer, the proposed scheme applies the sum-product algorithm (SPA) to only a part of the PCM. For this reason, it is referred to as `the partial SPA', compared with the conventional scheme, denoted by `the full SPA'. Clearly, it has a significantly lower complexity than `the full SPA'. Furthermore, we propose hybrid decoders employing both the full SPA and the partial SPA to achieve a better performance, while maintaining its complexity low. Numerical results show that the proposed schemes have a good performance enough to perform successive interference cancellation for the enhanced layer of the LDM systems in ATSC 3.0 as well as they have a low-complexity merit depending on system parameters. Since they only schedule the decoding procedure without modifying the decoder structure, they also have a benefit in the implementation of decoders.