TMCnet News
Modified Decoding Algorithm of LLR-SPA [Sensors & Transducers (Canada)](Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: In wireless sensor networks, the energy consumption is mainly occurred in the stage of information transmission. The Low Density Parity Check code can make full use of the channel information to save energy. Because of the widely used decoding algorithm of the Low Density Parity Check code, this paper proposes a new decoding algorithm which is based on the LLR-SPA (Sum-Product Algorithm in Log-Likelihood-domain) to improve the accuracy of the decoding algorithm. In the modified algorithm, a piecewise linear function is used to approximate the complicated Jacobi correction term in LLR-SPA decoding algorithm. Construct the tangent by the tangency point to the function of Jacobi correction term, which is based on the first order Taylor Series. In this way, the proposed piecewise linear approximation offers almost a perfect match to the function of Jacobi correction term. Meanwhile, the proposed piecewise linear approximation could avoid the operation of logarithmic which is more suitable for practical application. The simulation results show that the proposed algorithm could improve the decoding accuracy greatly without noticeable variation of the computational complexity. Copyright © 2014IFSA Publishing, S. L. Keywords: LDPC codes, LLR-SPA, Taylor series, Piecewise linear approximation, Decoding algorithm. (ProQuest: ... denotes formulae omitted.) 1. Introduction Low Density Parity Check (LDPC) code has attracted much attention in recent years, its Bit Error Rate (BER) performance approaching Shannon limit [1], With the improvement of codec algorithm, LDPC codes have been proven a kind of practical code [2-6]. Because of the LDPC code could achieve parallel decoding completely, it has been widely adopted by current communication standards [7-9]. In wireless sensor networks, LDPC codes could reduce energy consumption in information transmission. LDPC codes could be represented by the parity check matrix and the tanner graph, and they are shown in Fig. 1. From Fig. 1, the H; ; matrix can be equivalently represented by a tanner graph, which is a bipartite graph with the check nodes on one partite and the variable nodes on the other. The low complicated LDPC codes can be achieved by various iterative decoding algorithms. The decoding algorithm of LDPC codes are based on Belief Propagation (BP) in no cycle tanner graph. Due to the algorithm involves large numbers of addition and multiplication computations, therefore, the BP decoding algorithm is also called SumProduct (SPA) algorithm. The multiplication in BP algorithm not only consumes vast of operation time but also it is not suitable for quantization implementation [10-11]. The message of probability can be expressed by Log-Likelihood Ratio (LLR), and the multiplication can be replaced by the addition. The LLR-SPA (Log Likelihood Ratio Sum-Product Algorithm, LLR - SPA) is based on the principle. In order to make the LDPC code more suitable for practical application, many scholars have made many contributions on reducing the decoding complexity. To reduce the complexity of the LDPC decoding algorithm, MS (min-sum) algorithm is proposed in [12]. Although the algorithm reduces the complexity of the LLR-SPA algorithm, and the MS algorithm could reduce the complexity of the LLRSPA algorithm, but the decoding performance is relatively poor. So it is difficult to meet the decoding requirements of high performance. Another two lowcomplexity decoding algorithms have been proposed in [13-16], OMS (offset min-sum) algorithm and NMS (normalized min-sum) algorithm. The two algorithms can provide higher decoding accuracy, but the related offset parameters and the correction factor should be set according to the practical situation. It not only increases the decoding complexity, but also increases the difficulty of hardware implementation. Two simplified decoding algorithms have been proposed based on the first-term McLaren series and the first-term Taylor series in [17, 18]. The two methods could reduce the decoding complexity effectively at the expense of the decoding accuracy. To solve the problem, an efficient algorithm is proposed in this paper. In this algorithm, a piecewise linear function which is based on Taylor series is used to approximate the correction term of the Jacobi logarithm in LLR-SPA decoding algorithm. The simulation has been shown that the modified decoding algorithm can improve the decoding accuracy greatly without noticeable variation of the computational complexity. 2. Decoding Algorithm of LDPC Codes In LDPC codes, the decoding process is based on exchanging message which between check nodes and variable nodes along edges. And the two nodes are connected in an iterative manner. Since the loglikehood-ration was introduced, the multiplication was replaced by addition in LLR-SPA algorithm. The BP algorithm could be simplified in the way, and it is more suitable for practical application. 2.1. LLR-SPA Decoding Algorithm In the decoding algorithm of LLR-SPA, the decoding process is based on the parity-check matrix , the transmitted codeword X, the received codeword y and the modulated codeword C. Assuming that: ... (1) ... (2) ... (3) The encoded bits are binary phase shift keying (BPSK) modulated and transmitted over the additive white Gaussian noise (AWGN) channel. Assuming the AWGN channel is with noise variance G2, the posteriori likelihood ratio of each variable node isL(xn). Its computation equation is summarized as follows: ... (4) Thus, the decoding process in [19] can be summarized as follows: Step 1. Initialization: the initial information transmitted from variable node to check node is z"^m(x") and the initial information transmitted from check node to variable node is L (x ). The calculation formulas are as follows: ... (5) ... (6) Step 2. Update check nodes: For each m, ns N(m) and N(m) denote the set of variable nodes that connected to the check nodes. n = N(m) \ n and N(m)\n represent exclusion of n from the set N(m). Lm^n (xn ) is given by: ... (7) Step 3. Update variable nodes: For each n, mG M(n) and denote the set of check nodes that connected to the variable nodes, m =M(n)\m and M(n)\m represent exclusion of m from the set M(n). Zn^m(xn) is given by: ... (8) Step 4. Calculate the hard decision information of all variable nodes, and make the decision according to the decoded codeword c : ... (9) ... (10) Stop the iterative computation if Hcr = 0 or the iterative number reached the maximum number, otherwise, go to step 2, then ended the decoding process. The decoding process flow diagram is shown in Fig. 2. Compared with the BP decoding algorithm, the LLR-SPA algorithm reduces the decoding complexity greatly. But the nonlinear function which is in LLR-SPA algorithm limits its further application. So modified the nonlinear function is essential for practical application. 2.2. The Modified Decoding Algorithm The proposed algorithm in this paper used a piecewise linear function based on Taylor series to approximate the correction term of the Jacobi logarithm of LLR-SPA decoding algorithm. Here is focused on simplifying the check node update. Using the core operation in [20] to deal with the tanh operation in formula (7), then can obtain the equation of (11). The two non-linear logarithmic function is Jacobi correction term in (11). ... (11) where U and V are the statistically independent binary random variables with log likelihood ratio values of L{U) and L{v), respectively. © represents modulo 2 operation. The outgoing message from check node m becomes: ... (12) where f. and b. are the sets of auxiliary binary random variables, dc represents the check degrees of the parity-check matrix H . Using (11) repeatedly to do recursive computation, and could obtained ¿(4) and L(bt). Using the parity-check node constraint as follows: ... (13) Then we can obtain the following equation by the (13): ... (14) where i e {2,3,..., dc -1}. Complete to update the check nodes with the forward-backward recursion operation In this paper, it uses the Taylor series expansion and omits greater orders which is high than the first order to approximate the correction term. g(x) expresses the correction term as follows: ... (15) Using the first order Taylor series to expand the function of g(x) at the tangency point of XQ. Where x0 represents tangency point of g (x). The approximate function curve is obtained by the following steps. First of all, make the graph of g(x). The second, draw the tangent point of g(x). The third, after construct the tangent by the tangency point x0, the adjacent tangents intersected at one point (For example, the point of M in Fig. 3). The distance between the adjacent of two intersections is the interval of the piecewise approximation function, that is |x|. Finally, connect the point of tangency and the point of intersection in tum. The line is the curve of approximation. The experiment has been shown that, when the segmentation step length is set to 0.75, the proposed algorithm has the best comprehensive performance. The piecewise linear functions is based on the first order Taylor series and its intervals are shown in Table 1. At the same time, their curves are shown in Fig. 3. As can be seen in Fig. 3, the proposed piecewise linear approximation offers almost a perfect match to the function of correction term in practice. It can also effectively reduce the error that x = 0 and g(x) = 0 which is in the literature of [18]. And the experiment verification of the proposed algorithm will be given in the next section. Compared to the LLR-SPA algorithm, the proposed algorithm could avoid the look-up table operation (non-linear logarithmic operation), and the BER (Bit Error Rate) performance almost have no loss. The new algorithm can reduce the decoding complexity. Compared with two modified (OMS and NMS) decoding algorithm, the algorithm that this paper proposed does not need to set up the offset parameter and the correction factor. So it is better for practical application. 3. The Results of Simulation The paper make the contrast from the following aspects: one is the maximum error which compared with the original curve, another one is the BER performance. The encoded bits are binary phase shift keying (BPSK) modulated and transmitted over an AWGN (Additive White Gaussian Noise) channel. Two randomly constructed regular LDPC codes are used. It means that, the block sizes is (504, 3, 6) and (6000, 3, 6). The maximum iterations are set to 40 and 80, respectively. The author in [18] uses the first term Taylor series to approximate the correction term. The proposed algorithm in this paper uses a piecewise linear function which is based on Taylor series to approximate the correction term. From Table 2, we can obtain the maximum error by comparing the two kinds of approximation with the original curve. As it is showed in the Table 2, the proposed algorithm has lower maximum error, and the piecewise linear function is more close to the original curve. Using the regular LDPC codes (504, 3, 6) and (6000, 3, 6) which code rates are 1/2 as the experimental codes. The maximum iterations are set to 40 and 80, respectively. The BER performance of the proposed algorithm, the LLR-SPA algorithm, the first order of Taylor series algorithm in [18] and the Min-Sum algorithm are shown in Fig. 4 and Fig. 5. From Fig. 4, we can observe that, at the bit error rate of 10-4, the proposed algorithm is better 0.15 dB and 0.35 dB respectively than the first term Taylor series method and the Min-Sum algorithm. Compared to the optimal algorithm of LLR-SPA, the BER performance of the proposed algorithm has only about 0.05 dB performance loss. The accuracy of the proposed decoding algorithm improved greatly. Fig. 5 depicts that, at the bit error rate of 10"1, the proposed algorithm is superior about 0.2 dB, 0.55 dB respectively than the first term Taylor series method and the MS algorithm. The proposed algorithm is superior about 0.22 dB and 0.6 dB respectively than the first term Taylor series method and the MS algorithm when they at the bit error rate of 10~5. Compared to the optimal algorithm of LLR-SPA, the BER performance of the proposed algorithm almost has no loss. As can be seen from Fig. 4 and Fig. 5, the proposed algorithm has more advantages on matter what the block size is. This paper has done a lot of jobs to improve the decoding accuracy. But to some extent, increases a little decoding complexity. The proposed algorithm needs further improvement, such as the number of approximation's segments. 4. Conclusion This paper proposes a modified algorithm, and it is mainly to improve the accuracy of LDPC codes decoding algorithm. It uses a piecewise linear function based on Taylor series to approximate the correction term of the Jacobi logarithm which is in the LLR-SPA decoding algorithm. The modified decoding algorithm can improve the decoding accuracy greatly under the condition of the computational complexity almost unchanged. It could be achieve the optimal LLR-SPA performance, and it can be avoided the calculation of non-linear logarithmic function, which is more suitable for practical application. At the same time it increased the application prospect of LDPC codes in wireless sensor networks. Acknowledgements This work was supported by the scientific and technological projects of Shandong province (2012J0030009). References [1]. R. G. Gallager, Low density parity check codes, IRE Transactions on Information Theory, Vol. 8, Issue 1, 1962, pp. 21-28. [2]. Qiu Peng Wen, Bai Peng, Li Ming Yang, Design of dynamically reconfigurable LDPC encoder based on FPGA according to CCSDS criteria, Video Engineering, Vol. 36, Issue 21, 2012, pp. 59-62. [3]. Chen Zi Qiang, Ou Yang Shan, Xiao Hai Lin, Cooperative LDPC codes design for decode-andforward half-duplex relay channels, Journal of Electronics & Information Technology, Vol. 33, Issue 11,2011, pp. 2610-2615. [4]. Wang Xiu Min, Shen Jian Ming, Zhang Yang, Fu Juan, Design of WIMAX LDPC codec based on FPGA, Journal of Zhejiang University, Vol. 39, Issue 1,2012, pp. 112-116. [5]. Shen Xue Mei, LDPC decoding algorithm in the next generation wireless LAN, Bulletin of Science and Technology, Vol. 29, Issue 2,2013, pp. 127-129. [6]. So-Jin Lee, Joo-Yul Park, Ki-Seok Chung, Memory efficient multi-rate regular LDPC decoder for CMMB, IEEE Transactions on Consumer Electronics, Vol. 55, Issue 4, 2009, pp. 1866-1874. [7]. Wang Kai Yao, Xiao Yang, Kiseon Kim, Construction of time-frequency codes based on protograph LDPC codes in OFDM communication systems, Journal of Systems Engineering and Electronics, Vol. 3, Issue 23,2012, pp. 335-341. [8]. Ma Piming, Yuan Dongfeng, Yang Xiumei, Wu Dalei, LDPC coded OFDM wireless communication system based on IEEE 802.11a standard, Systems Engineering and Electronics, Vol. 27, Issue 1, 2005, pp. 163-166. [9]. Zhu Lianxiang, Xing Yanhui, Li Xiang, Dai Gairong, Wang Zhaozhang, Joint LDPC codes and network coding cooperative communication technology, Journal of Chongqing University of Posts and Telecommunications, Vol. 23, Issue 3, 2011, pp. 262-265. [10]. Wu Bin, Yang Bo, Ye Ming, The hardware implementation of bits selection in data quantization and its performance simulation of LDPC codes, Information & Communications, Vol. 118, Issue 2, 2012, pp. 26-28. [11]. Liang Wei, Liu Liang, Shen Xu, Ye Fan, Ren Jun Yan, LDPC decoder architecture with dynamic quantization, Computer Engineering and Applications, Vol. 47, Issue 10, 2011, pp. 106-109. [12]. Chen Xu Can, Liu Dong Pei, Modified decoding algorithm of LDPC codes, Journal of University of Electronic Science and Technology of China, Vol. 39, Issue 2,2010, pp. 219-222. [13]. Wang Chungli, Chen Xiaoheng, Li Zongwang, Yang Shaohua, A simplified min-sum decoding algorithm for non-binary LDPC codes, IEEE Transactions on Communications, Vol. 61, Issue 1,2013, pp. 24-32. [14]. Gottfried Lechner and Jossy Sayir, Improved summin decoding of LDPC codes, in Proceedings of the International Symposium on Information Theory and its Applications, (ISITA'04), Parma, Italy, 2004, pp. 10-13. [15]. Wu Qiong, Mei Jinjie, Research on LDPC decoding based on modified min-sum algorithm, Radio Communications Technology, Vol. 38, Issue 2, 2012, pp. 27-29. [16]. Hu Xiaoyu, Eleftheriou Evangelos, Arnold Dieter-Michael et al, Efficient implementations of the sumproduct algorithm for decoding LDPC codes, in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM'01), 2001, pp. 1036-1036. [17]. S. Papaharalabos, P. T. Mathiopoulos, Simplified sum-product algorithm for decoding LDPC codes with optimal performance, Electronics Letters, Vol. 45, Issue 2,2009,pp. 116-117. [18]. Hu Shu Kai, Wang Xin Mei, Simplified decoding algorithm for LDPC over GF(q), Journal of Xidian University, Vol. 38, Issue 2,2011, pp. 8-12. [19]. Yuan Dong Feng, Zhang Hai Gang, The theory and application of LDPC codes, Liu Yang, Posts & Telecom Press, 2008. [20]. Chen Jing-Hu, Dholakia Ajay, Eleftheriou Evangelos et al, Reduced-complexity decoding of LDPC codes, IEEE Transactions on Communications, Vol. 53, Issue 8,2005, pp. 1288-1299. 1 Zhongxun Wang,1 Yan Wang,1 Tiantian Tang,1 Weiyun Liu and 1 Xinglong Gao 1 Institute of Science and Technology for Opto-Electronics Information, Yantai University, Yantai, Shandong, 264005, China 1 Tel.: 15063831774 1 E-mail: [email protected] Received: 25 April 2014 /Accepted: 29 August 2014 /Published: 30 September 2014 (c) 2014 IFSA Publishing, S.L. |