This contribution deals with the comparison of the sum-product algorithm (SPA) and its log-domain version (log-SPA) for decoding LDPC (low density parity check) codes over general binary extension fields. For both algorithms, we determine their computational complexity based on the number of real-valued operations and investigate their sensitivity to quantization effects. Whereas the log-SPA yields the shorter decoding time in the case of binary LDPC codes, we point out that increasing the field size tends to favor the SPA, especially when a multiplication takes only slightly more time than an addition. Further, we show that log-SPA requires fewer quantization levels and suffers less from a quantization induced error-floor.
This contribution deals with the comparison of the sum-product algorithm (SPA) and its log-domain version (log-SPA) for decoding LDPC (low density parity check) codes over general binary extension fields. For both algorithms, we determine their computational complexity based on the number of real-valued operations and investigate their sensitivity to quantization effects. Whereas the log-SPA yields the shorter decoding time in the case of binary LDPC codes, we point out that increasing the field size tends to favor the SPA, especially when a multiplication takes only slightly more time than an addition. Further, we show that log-SPA requires fewer quantization levels and suffers less from a quantization induced error-floor.
An efficient implementation of the Sum-Product algorithm(SPA) in the log-likelihood ratio (LLR) domain is presented in [1]. In this paper, We modify a formula in [1] such that SPA can be implemented by using two small look-up tables. With this modification, all the calculations involved in this implementation involve only additions, subtractions, comparisons and table looking-ups, which leads to low computation complexity and facility in hardware implementation. Based on this modified implementation, various quantization schemes of SPA for decoding low-density parity-check (LDPC) codes are investigated. And the issues related to quantization, such as clipping levels and variables quantization, are also investigated. Simulation results show that the performance of the uniform quantization scheme is very close to that of the non-quantizaiton over the AWGN channel. Moreover, it can obtain the same performance as that of non-quantization at high SNRs.
Efficient implementations of the sum-product algorithm (SPA) are presented for decoding low-density parity-check (LDPC) codes using log-likelihood ratios (LLR) as messages between symbol and parity-check nodes. Various reduced-complexity derivatives of the LLR-SPA are proposed. Both serial and parallel implementations are investigated, leading to trellis and tree topologies, respectively. Furthermore, by exploiting the inherent robustness of LLRs, it is shown, via simulations, that coarse quantization tables are sufficient to implement complex core operations with negligible or no loss in performance. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency and computational complexity perspective.
It is generally known that the log sum-product-algorithm (log-SPA) for non-binary low-density parity-check (NB-LDPC) codes requires a high decoding complexity. The complexity grows exponentially fast and becomes prohibitive as the check node degree and/or the field size increase. In this work, we propose a quantum-assisted decoding (QD) for NB-LDPC codes to resolve the complexity issue associated with the log-SPA. We utilize the quantum amplitude estimation algorithm (QAEA) to calculate the check node messages in the form of log-likelihood ratio vector (LLRV). This work realizes the QAEA with the following two blocks, 1) state preparation and 2) amplitude estimation (AE). In particular, the state preparation provides the AE with the input state. It will be shown that the proposed QD achieves a significant complexity reduction, which becomes more distinctive as the check node degree and/or the field size grows.
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.
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
…
A simplified decoding algorithm for low-density parity-check (LDPC) codes over high order Galois field is proposed to reduce the complexity of traditional sum-product algorithm (SPA). There are only addition operation and comparison operation in this algorithm, without complex multiplication operation. The computation complexity of proposed algorithm is much smaller than the SPA. The signal-to-noise power ratio (SNR) isn't needed in this algorithm, so the process of SNR estimation can also be removed. The simulation results show that the bit error rate (BER) performance of proposed algorithm degrades only about 0.5 dB than the SPA, so the proposed algorithm is an efficient simplified algorithm in engineering.