Abstract: Because of the excellent error- correcting capability and optional error correct code, Low-Density Parity-Check (LDPC) codes have received great attention recently. LDPC codes can be decoded by an iterative decoding algorithm as Belief Propagation Algorithm or Message Passing Algorithm. In this paper, the extended analysis of Sum-Product algorithm (SPA) and Min-Sum algorithm (MSA) using Stopping node method is introduced. This method based on SPA using stopping node to reduce the computing complexity on LDPC code is presented, and it has also been proposed to be applied to MSA. Moreover, how to remove the effect of short cycles to improve the quality of LDPC decoder and how to make early decisions on the next iteration to reduce the number of calculations are presented in this paper. Simulations show that the stopping node algorithm not only offers a better performance but also decreases processing time by factor of 5 times under BPSK scheme and nearly 10 times under QPSK scheme by comparison with standard MSA and SPA.
INTRODUCTION
Low-Density Parity-Check (LDPC) codes were first introduced by Gallager (1962). Due to the complexity of Decoding Algorithm that requires large volume of calculations and because of the technology was not mature enough for their practical implementation, they were forgotten until the 1990s. LDPC codes were reintroduced by MacKay and Neal (1996). Then with the development of computing technology in processing and data storage, the problem of LDPC had been solved.
LDPC codes are among the known codes achieving close to the Shannon limit performance, can achieve very low bit error rates for low signal to noise ratio (SNR) application (MacKay and Neal, 1996). Comparing the Turbo codes decoding algorithm, LDPC decoding algorithm has low implementation complexity, as well as no error- floor at high SNRs. So that, LDPC codes have received great attention by their excellent error- correcting capability and optional error correct coding schemes by many standards have been adopted.
LDPC codes are a special class of linear codes with a low density check matrix which means that it has just few ones in each column and row. LDPC codes can be decoded by an iterative decoding algorithm as Belief Propagation Algorithm (MacKay, 1999) or so call Message Passing Algorithm in which the calculations are done in probability domain. To achieve the better BER performance and reduce computational complexity by decreasing the number of iterations, Sum-Product Algorithm (SPA) and Min-Sum Algorithm (MSA) were introduced and they are done in log domain. The SPA presents the highest BER performance but it is dependent on the noise variance estimation. In contrast, MSA aims for reducing computational complexity, it cause certain degradation in decoding performance but it is simpler to implement and independent on noise variance estimation.
In “Sleeping node decoder” method presented by Bresnan (2004), the reached nodes can make early decisions on the next iteration to reduce the number of calculations. Lin and Ku (2009) had presented the Elimination Node method to make node stops according to Log likelihood. In addition, modifications using Early Stopping (ES) based on Cross Entropy (CE) coefficient (Hagenauer et al., 1996) or based on Hard Decision Aided (HDA) (Shao et al., 1999) and follow Sign- Change-Ratio (SCR) for Turbo codes have also been proposed to be applied to LDPC decoder.
This study presented a comparison between the standard SPA, standard MSA and SPA using stopping node (SPA-SN), MSA using stopping node (MSA-SN) to apply in LDPC decode.
SUM-PRODUCT ALGORITHM AND MIN-SUM ALGORITHM
LDPC codes: LDPC code is defined by a sparse parity check matrix H of size MxN that consist of M = N-K rows and N column of the parity check matrix. The code rate is represented by K/N.
LDPC code can be represented by the bilateral Tanner graph (Tanner, 1981). A graph contains two kinds of node: Bit nodes and check nodes. Bit nodes are associated with a column of H, check nodes are associated with a row of H. In the Tanner graph, a single bit node can be connected to check nodes where the elements of a column are “1” in the parity check matrix H and a single check node can be connected to bit nodes where the elements of a row are “1” in the parity check matrix H.
Sum-product algorithm: Let L(rji) be the messages are sent from check nodes j to bit node i; Let L(qij) be the messages are sent from bit node i to check nodes j. The SPA steps can be summarized as following:
*Initialization: For the domain of Log-likelihood and for all bit nodes vi (i=1, 2…, n) the LLR value Li is:
| (1) |
*Phase 1: For all check nodes cj (j = 1, 2…, m), in the corresponding position (I, j), Hij =1, in the γth iterations, calculates L(γ)(rji) with the following equation:
| (2) |
where:
| (3) |
*Phase 2: Calculates L(γ)(qij) for all bit nodes vi (i = 1, 2…, n), for position (i,j), Hij =1, uses the Eq. 4:
| (4) |
Exploration: Computing likelihood ratio for bit nodes vi (i = 1, 2,…, n):
| (5) |
For the exploration codeword
| (6) |
where the exploration codeword
| (7) |
When the number of iterations achieves the maximum value the iteration stops. Otherwise repeat from phase 1.
Min-sum algorithm: MSA is a simplified version of the SPA. There are only two differences between MSA and SPA. In MSA, the initialization of the input LLR is:
| (8) |
Where: Set γ = 1 and γmax be the maximum number iteration.
And in phase 1, L(γ)(rji) is calculated by Eq. 9:
| (9) |
The approximation leads to both computation reductions, MSA may cause certain degradation in decoding performance. The performance of the Min-Sum decoder can be improved in a number ways. In particular, the application of a correction factor and an offset in the check node output messages (Jiang et al., 2006) may have beneficial effect on the decoder performance. Using stopping node to make early decisions on the next iteration is one of the methods to improve the performance of the MSA.
STOPPING NODE ALGORITHM
Firstly, set a group of bit nodes as V(s)=[vi(s)] then the hard decision of codeword in the γth iterations is C(γ)=(c1(γ),c2(γ),…cn(γ)) that correspond respectively to bit nodes (v1, v2,...vn).
Definition: The Stopping nodes (SN) are a collection of bit nodes V(s) = [vi(s)] when sign of LLR (Log Likelihood Ratio) corresponding bit codes remain unchanged.
Considering regression decoding algorithms, the SN node is determined by comparing the sign of c1(γ) under iterations. If ci(γ)= ci(γ-1)=…=ci(γ-L) where L is the number of bits observed, vi(s) are nodes SN, then:
| (10) |
When determining a stop node, the calculation process iteration at node SN, Eq. 2 (in SPA or Eq. 9 in MSA) and Eq. (4), Eq. (5) does not need to perform calculations and only receives the value of the γ'th iteration by:
| (11) |
| (12) |
| (13) |
So L(qij) and L(rji) matrix are not updated at SN nodes, the amount of decoder computation can be reduced in every iteration γ>γ’.
When using the stopping node method, if all nodes are SN bit nodes, the Early Stopping (ES) can be used to reduce the number of iteration. So a new target of implementing ES is:
| (14) |
LDPC decoding algorithm modified SPA, MSA using stopping node by checking sign the bit code is called Sum-Product Stopping node Algorithm (SPA-SN) and Min-Sum Stopping node Algorithm (MSA-SN).
In the decoding process, with a certain code, the quality achieved depends on the number of iterations performed. The decoding processing time and the quality increase when the number of iterations increases. But this relationship is not linear. When performing building code in random or structure mode it cannot avoid the appearance of finite cycles. That means that when decoding on the graph, node inter-messages transmission depends solely on the time taken by message depending nodes, but updating information at any node depends on the node itself. Error floor appears when the quality graph of the code is in regression.
The decoding quality of LDPC iterative decoding algorithm having finite length is limited by the short cycles on bilateral tanner graph. In iterative decoding algorithms, when transmitting messages from bit node to check node and contrary, often error handling appear within short period. So when building codes, the case of short cycles must be avoided, especially in case of 4 cycles. Using Stopping Node method can improve the quality of LDPC decoder iteration by removing the effect of short cycles.
Using stop node to remove the effect of short cycles is described in Fig. 1.
| Fig. 1: | Excluding the impact of short-cycle by stopping node |
The shortest cycles of the code is 4 because of the set of nodes v3, c2, v5 and c4. If v5 is the stop node at certain iteration, it do not need to perform calculation at node v5, the shortest of code will increase to 6 by the set of nodes v1, c3, v4, c4, v3 and c1.
SIMULATION RESULTS
Using Monte-Carlo simulation techniques, assuming that the modulation and demodulation is ideal BPSK and QPSK, the additive noise in AWGN channel is with zero mean and variance is σ2 = N0/2 (N0 is the power spectrum density bilateral). Effectiveness evaluation of the decoding LDPC algorithm using Stopping node methods can achieved with four parameters: Bit error rate, iterations average number, Stopping Node rate (the number of SN at the last iteration of the bit node) and processing time simulation at different values of bit energy rate on the noise power spectral density Eb/N0.
MathWorks MATLAB software installed in a computer equipped with Intel(R) Core(TM) 2 Duo CPU T5670@ 1.80 GHz and 3 GB physical memory was been used to run simulations of the SPA, MSA, SPA-SN, MSA-SN algorithms.
In this study, LDPC encoding with code rate of 1/2 is set, the block size (204.102) and (504.252) have been chosen. According to experience, the value of L can be selected to L = 9. The maximum number of iterations of LDPC decoding algorithm was set to γmax = 30.
Decoder using SPA-SN, MSA-SN and common SPA, MSA where, codewords error number corresponds to Eb /N0 = 1 dB, 1 dB<Eb/N0= 2 dB, Eb/N0>2 dB are, respectively 300, 200 and 100.
This paper had achieved the following results:
Figure 2-5 show BER performance comparisons between the SPA-SN, MSA-SN and common SPA, MSA under BPSK scheme and QPSK scheme in the (204,102) LDPC code and (504.252) LDPC code.
With BPSK scheme when Eb/N0>2 dB, BER quality of the SPA-SN losses are insignificant for the (204,102) LDPC code and about 0, 1 dB for (504,252) LDPC code compared with the SPA.
| Fig. 2: | BER performance under BPSK scheme comparison for (204,102) LDPC code with maximum iteration = 30 |
| Fig. 3: | BER performance under BPSK scheme comparison for (504.252) LDPC code with maximum iteration =30 |
But when Eb/N0>3 dB, SPA-SN have a BER quality 60% higher than SPA for (504,252) LDPC code. In contrast, MSA-SN has 0,1 dB to 0,3 dB BER lower than common MSA in both (204,102) LDPC code and (504,252) LDPC code.
Using SPA-SN and MSA-SN under QPSK scheme can achieve the better BER quality compared with SPA SN and MSA-SN under BPSK scheme for the (204, 102) LDPC code and (504, 252) LDPC code.
| Fig. 4: | BER performance under QPSK scheme comparison for (204,102) LDPC code with maximum iteration = 30 |
| Fig. 5: | BER performance under QPSK scheme comparison for (504.252) LDPC code with maximum iteration =30 |
Evaluating the decoding algorithm’s complexity is done by comparing processing time to assess BER on the same computer for the same codewords error number and the same values of Eb/N0.
| Fig. 6: | Running time comparison under BPSK scheme comparison for (204, 102) LDPC code, max iteration = 30 |
| Fig. 7: | Running time comparison under BPSK scheme comparison for (504.252) LDPC code, max iteration=30 |
| Fig. 8: | Running time comparison under QPSK scheme comparison for (204,102) LDPC code, max iteration = 30 |
| Table 1: | Comparisons of processing time with maximum iteration =30 |
| Fig. 9: | Running time comparison under QPSK scheme comparison for (504.252) LDPC code, max iteration= 30 |
The processing time within SPA-SN, MSA-SN compared to SPA, MSA are significantly decreased in all values of Eb/N0. Figure 6 to 9 shows full processing resulting time for SPA, MSA, SPA-SN and MSA-SN together under BPSK scheme and QPSK scheme. Table 1 shows the comparisons of processing time for (204,102) LDPC code and (504,252) LDPC code which is used SPA, MSA, SPA-SN and MSA-SN for decode LDPC.
Means that using the BPSK scheme, SPA-SN, MSA-SN decreases processing time by factor of 5 times compared to the common SPA, MSA algorithm and nearly 10 times under QPSK scheme.
CONCLUSION
An enhanced and more efficient algorithm for decoding LDPC codes using Stopping node method has been proposed. The performance of simulation shows that computation time of this proposed method is significantly reduced, about 5 times than the conventional algorithms under BPSK scheme and nearly 10 times than the conventional algorithms under QPSK scheme. Moreover, the proposed method has a 0.3 dB BER lower than common MSA for MSA-SN under QPSK scheme for (504.252) LDPC code, with maintaining processing quality where losses are insignificant and acceptable for SPA-SN. Therefore, the proposed algorithm can save power, reduce transmission delay and processing cost.