Advanced
LDPC Decoding by Failed Check Nodes for Serial Concatenated Code
LDPC Decoding by Failed Check Nodes for Serial Concatenated Code
ETRI Journal. 2015. Feb, 37(1): 54-60
Copyright © 2015, Electronics and Telecommunications Research Institute(ETRI)
  • Received : November 23, 2014
  • Accepted : November 04, 2014
  • Published : February 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Seog Kun Yu
Eon Kyeong Joo

Abstract
The use of serial concatenated codes is an effective technique for alleviating the error floor phenomenon of low-density parity-check (LDPC) codes. An enhanced sum–product algorithm (SPA) for LDPC codes, which is suitable for serial concatenated codes, is proposed in this paper. The proposed algorithm minimizes the number of errors by using the failed check nodes (FCNs) in LDPC decoding. Hence, the error-correcting capability of the serial concatenated code can be improved. The number of FCNs is simply obtained by the syndrome test, which is performed during the SPA. Hence, the decoding procedure of the proposed algorithm is similar to that of the conventional algorithm. The error performance of the proposed algorithm is analyzed and compared with that of the conventional algorithm. As a result, a gain of 1.4 dB can be obtained by the proposed algorithm at a bit error rate of 10 −8 . In addition, the error performance of the proposed algorithm with just 30 iterations is shown to be superior to that of the conventional algorithm with 100 iterations.
Keywords
I. Introduction
High-quality and throughput services are necessary for next-generation communication systems. It is expected that a bit error rate (BER) below 10 −15 and a high code rate of over 0.8 will be required to guarantee transmission quality and throughput. Turbo [1] and low-density parity-check code (LDPC) [2] [3] codes have recently received considerable attention from many researchers because of their excellent error performance. However, the error floor phenomenon occurs in turbo and LDPC decoding [1] , [4] [5] . Hence, the error floor phenomenon is a serious impediment to the application of turbo and LDPC codes in such systems. Therefore, reduction or elimination of the error floor phenomenon is very important.
Serial concatenation has been proposed to reduce the error floor phenomenon in turbo codes [4] . Moreover, a well-designed LPDC code with a low error floor [6] and serial concatenation [7] have been proposed. However, the decoding process of turbo codes is more complex than that of LDPC codes. In addition, a high code rate is relatively difficult to obtain with turbo codes as compared to LDPC codes. Hence, LDPC codes may be more suitable for next-generation systems. Therefore, an error-floor lowering technique for LDPC codes is investigated in this paper.
An LDPC code is defined by a parity-check matrix. A well-structured parity-check matrix is the most efficient solution against trapping sets [8] for LDPC codes. However, a high code rate is difficult to obtain because of the small row size of the parity-check matrix. A serial concatenation has no limitation on the code rate. Moreover, the additional decoding complexity can be minimized because a simple, high outer-code code rate, such as that of the Bose–Chaudhuri–Hocquenghem (BCH) code, is sufficient. However, it may be difficult to achieve an error performance with high efficiency because of the low error-correcting capability of the outer code and the characteristics of the errors of the trapping sets. It is expected that the low error-correcting capability of the outer code is sufficient for correcting the remaining errors of the inner LDPC decoding if the adverse effect of the trapping sets is minimized. Therefore, a simple but efficient decoding algorithm for LDPC codes, which is suitable for serial concatenated codes with a high-rate outer code, is proposed and analyzed in this paper.
The rest of this paper is organized as follows. First, the characteristics of errors due to trapping sets are analyzed in Section II. The key idea of the proposed algorithm is introduced and an enhanced Sum–product algorithm (SPA) is proposed in Section III. The error performance of BCH-LDPC codes with a conventional SPA decoder and the proposed SPA decoder are analyzed and compared in Section IV. Finally, our conclusions are stated in Section V.
II. Characteristics of Errors due to Trapping Sets
Many studies on LDPC decoding errors have been performed during the last 10 years [4] [12] . The types of bit probability transition and their distribution on the basis of the signal-to-noise ratio (SNR) were analyzed in [10] . The discovered types are shown in Fig. 1 . Bit probability transition can be roughly classified into two types; namely, convergence and oscillation.
PPT Slide
Lager Image
Types of bit probability transition of errors: (a) convergence type and (b) oscillation type.
In addition, the patterns of the number of errors by the trapping sets were analyzed in [11] . An example of the three patterns of the number of errors that are affected by the trapping sets with respect to iteration number during the SPA is shown in Fig. 2 . In the figure, the red dotted line signifies the error-correcting capability of the outer code.
PPT Slide
Lager Image
Three patterns of number of errors due to trapping sets: (a) saturation pattern, (b) propagation pattern, and (c) periodic pattern.
It may be easily recognized that the saturation or propagation pattern can occur only if the type of probability transition of each bit error within a trapping set is of the convergence type. This is because each error within a trapping set cannot be corrected. This is especially the case if the propagation patterns are of the convergence type with a long convergence time after a number of previous short oscillations. The periodic pattern is affected by the oscillation type. The error locations with respect to the number of iterations in a periodic pattern are shown in Fig. 3 . Note that a red dot signifies a bit error. It can be confirmed from Fig. 3 that the bit error probability transition is of the oscillation type.
PPT Slide
Lager Image
Relationship between bit number of the bit errors and iteration numbers.
An example of the number of errors after LDPC decoding with a periodic pattern is presented in Table 1 . In this case, the LDPC code rate is 0.8222; the codeword length is 16,200 bits; E b / N 0 is set to 3.3 dB; and the maximum number of iterations is set to 100. It can be seen that there is a large variation in the number of errors.
Number of errors at the maximum iteration number with a periodic pattern.
Codeword number Number of errors
1 7
2 205
3 8
4 13
5 4,760
In general, the error performance of LDPC codes can be improved by increasing the number of iterations. However, it can be affirmed from Fig. 2 and Table 1 that the number of errors can increase despite the increase in the number of iterations if the errors are due to trapping sets. The errors of the saturation pattern can be corrected by the outer code when the error floor phenomenon occurs, but those of the propagation pattern cannot be corrected. The periodic pattern errors can either be corrected or not corrected by the outer code according to the number of errors at the end of decoding. Therefore, the error-performance efficiency of a serial concatenated code with a high outer-code code rate may be reduced. However, the errors after LDPC decoding can be corrected by the outer code if the message block of the LDPC code can be obtained when the number of errors is minimized in the propagation and periodic pattern. Therefore, a technique to estimate the number of errors with respect to the iteration number is required.
Figure 4 shows a part of a Tanner graph containing a (3, 1) trapping set [8] , [12] . In the figure, a check node of the parity-check matrix is represented by a square, while a variable node is denoted by a circle. Moreover, i is the check node index and j is the variable node index. The members of the (3, 1) trapping set are shown by the colored parts.
PPT Slide
Lager Image
Part of Tanner graph containing (3, 1) trapping set.
A check node detects odd errors in the connected variable nodes if the value of the check node is “1” during the syndrome test. This kind of check node is called a failed check node (FCN). Hence, a close relationship between the numbers of errors and FCNs is expected. For example, node i +2 is an FCN if variable nodes j +1, j +2, and j +4 are in error. This is because check nodes i +1, i +3, and i +4 are connected to an even number of error variable nodes, but check node i +2 is connected to an odd number of error variable nodes. In addition, the three nodes i , i +2, and i +4 are FCNs if variable nodes j +1, j +2, j +4, and j +5 are in error. Therefore, as the number of errors increases, generally the number of FCNs also increases.
To confirm the relationship between the numbers of errors and FCNs, three patterns are simulated. The results are shown in Fig. 5 . As expected, the number of FCNs follows a pattern similar to that obtained for the number of errors.
PPT Slide
Lager Image
Three patterns of the numbers of errors and FCNs: (a) saturation pattern, (b) propagation pattern, and (c) periodic pattern.
III. Enhanced SPA for Serial Concatenated Codes
It was confirmed in the previous section that the pattern of the number of FCNs is similar to that of the number of errors. Hence, it is possible to obtain the decoded message at the iteration number with the minimum number of errors by simply counting the number of FCNs during the SPA. Therefore, it is expected that the error performance of the serial concatenated code can be improved because it is possible to minimize the number of errors in the three patterns of the trapping sets by the inner LDPC code.
Figure 6 shows the flow chart for the proposed serial concatenated code. The portion of the flowchart that is included inside the dotted box is added to a conventional SPA decoder. The colored box is the inner decoder. At first, the minimum number of FCNs, N min , is initialized as M , which is the total number of check nodes. When the SPA is used, the number of FCNs at the i th iteration,
N i FCN
, is counted. If
N i FCN
is smaller than N min , then N min is updated, and the decoded message at the i th iteration is stored in the memory. Finally, LDPC decoding is completed after loading the decoded message with the minimum number of FCNs. This decoded message is input to the outer decoder.
PPT Slide
Lager Image
Flow chart of proposed algorithm.
Hence, the error performance of the proposed decoding algorithm can be improved as it minimizes the errors from the trapping set. Therefore, the outer decoder can correct most of the errors that remain after inner LDPC decoding. In addition, the proposed algorithm has a complexity, in terms of computation and implementation, similar to that of a conventional decoder. The additional circuitry consists of only a counter and a memory for storing the message with the minimum number of errors.
IV. Performance Analysis
The Digital Video Broadcasting–Second Generation Terrestrial LDPC codes with a codeword length of n = 16,200 bits [7] were used in this study. However, the bit interleaver was not used. The maximum number of iterations was set to 100 to obtain sufficient error performance for the LDPC codes. Binary phase-shift keying modulation with an additive white Gaussian noise channel is assumed. In general, the error floor phenomenon appears at a relatively high BER region if the code rate is high. Hence, the code rate of the inner LDPC code was set to R = 37/45 (about 0.8222), which is the highest code rate with n = 16,200, to simplify the analysis. The error-correcting capability of the outer BCH code was set to 12 bits. The number of information bits for the BCH code is 13,152, and the codeword length is 13,320 bits. Therefore, the total code rate of the BCH-LDPC code is about R = 0.8118.
The error performance of the BCH-LDPC code is shown in Fig. 7 . The BCH-LDPC code with the proposed algorithm shows a far-improved BER performance. A gain of around 1.4 dB is obtained by the proposed algorithm over the conventional BCH-LDPC code at a BER of 10 −8 . The error performance of the conventional BCH-LDPC code is better than that of the conventional single LDPC code, but the difference is very small.
PPT Slide
Lager Image
Error performances of the LDPC and BCH-LDPC codes: (a) BER and (b) CER.
To verify the reasons for the differences in error performance in the error floor region, the number of errors for each uncorrected codeword after LDPC decoding with the conventional and proposed algorithm at an E b / N 0 of 3.3 dB is presented in Table 2 . In this case, the most dominant pattern of the number of errors is the periodic pattern. It was confirmed that the variation in the number of errors is tremendous for each uncorrected codeword after conventional SPA decoding. Hence, some errors can be corrected by the outer BCH code, but the number of corrected errors is relatively small. Therefore, the BER performance of the BCH-LDPC code with the conventional SPA is similar to that for the single LDPC code. It was also confirmed that most of the errors can be corrected by the BCH code with the proposed algorithm as the inner LDPC code minimizes the number of errors.
Number of errors after LDPC decoding (LDPC code rate: 0.8222,Eb/N0= 3.3 dB).
Uncorrected codeword number Conventional decoding Proposed decoding
1 7 4
2 205 2
3 8 3
4 13 13
5 4,760 5
The codeword error rate (CER) performance was found to be similar to the BER performance. However, the single LDPC code with the proposed algorithm shows the same CER for the single LDPC code with the conventional SPA because the proposed algorithm does not correct all the errors; rather, in only minimizes them. In addition, the BCH-LDPC code with the conventional SPA shows better performance than the single LDPC code because it allows correction of parts of the uncorrected codewords
Figure 8 shows the error performance of the BCH-LDPC code with the proposed and conventional algorithm with respect to the number of iterations at E b / N 0 = 3.2 dB. The proposed BCH-LDPC code at 30 iterations shows much better performance than the conventional BCH-LDPC code at 100 iterations.
PPT Slide
Lager Image
Error performance of BCH-LDPC code with respect to iteration number: (a) BER and (b) CER.
It was confirmed that the BER and CER performance of the proposed algorithm were saturated after 50 iterations. Therefore, a higher reduction in the maximum number of iterations can be obtained using the proposed algorithms as compared to the conventional algorithm. As a result, the latency with iterative decoding is also reduced.
In addition, the proposed algorithm was compared with the conventional one at various code rates. The inner code rate is varied from 4/9 (about 0.4444) to 37/45 (about 0.8222). The results of this analysis are shown in Fig. 9 .
PPT Slide
Lager Image
Error performance of BCH-LDPC codes for different code rates: (a) BER and (b) CER.
A relatively improved error performance is obtained using the proposed algorithm. Note that the gain of the BCH-LDPC code with a high rate is much more than that for a low-rate code, because the number of uncorrected codewords, which occurs form the trapping sets, is greater for high-rate codes.
V. Conclusion
The error floor phenomenon of LDPC codes is an obstacle for future communication systems with LDPC codes. A serial concatenated code can be used to overcome this obstacle. However, the error performance of the serial concatenated code with conventional SPA may be unsatisfactory because of the error characteristics of trapping sets. Hence, an enhanced decoding scheme for LDPC codes, which is suitable for a serial concatenated code, is proposed in this paper. The proposed algorithm uses the relationship between the number of errors and FCNs in the syndrome test. The error performance of BCH-LDPC codes with that of the proposed algorithm was compared with the conventional decoding algorithm in terms of the E b / N 0 and number of iterations.
As a result, the BCH-LDPC code with the proposed algorithm showed better error performance as compared to the BCH-LDPC code with conventional SPA for the same code rate. The BER for the proposed algorithm is only 1/10,000 of that for the conventional algorithm, while the E b / N 0 is 3.6 dB for a code rate of 0.8118. A gain of around 1.4 dB is obtained by the proposed algorithm as compared to conventional BCH-LDPC decoding at a BER of 10 −8 . In addition, it is possible to decrease the latency as the proposed algorithm requires a smaller number of iterations. A counter and memory, of a size equal to the message length, are sufficient additions to the conventional SPA for the proposed algorithm. Hence, computation and implementation complexity for the proposed algorithm are not expected to increase by much. Therefore, the proposed algorithm is considered to be suitable for LDPC decoding in a serial concatenated code for next-generation communication systems.
This research was supported by Kyungpook National University Research Fund, 2012.
BIO
amatess@ee.knu.ac.kr
Seog Kun Yu received his BS and MS degrees in electronics engineering from Kyungpook National University, Daegu, Rep of Korea, in 2004 and 2007, respectively. He is currently working toward his PhD degree in electronics engineering at Kyungpook National University. His research interests include coding and decoding and signal processing for communication.
Corresponding Author  ekjoo@ee.knu.ac.kr
Eon Kyeong Joo received his BS degree in electronics engineering from Seoul National University, Seoul, Rep. of Korea, in 1976 and his MS and PhD degree in electrical engineering from Ohio State University, Columbus, OH, USA, in 1984 and 1987, respectively. From 1976 to 1979, he was an officer of communication and electronics in the Republic of Korea Navy. From 1979 to 1982, he worked for the Korea Institute of Science and Technology, Seoul, Rep. of Korea, as a researcher. In 1987, he joined the faculty of the Department of Electronic Engineering, Kyungpook National University, Daegu, Rep. of Korea, where he is currently a professor in the School of Electronics Engineering. His research interests include digital communications; coding and decoding; modulation and demodulation; and signal processing for communications.
References
Garello R. “On Error Floor and Free Distance of Turbo Codes,” IEEE Int. Conf. Commun. Helsinki, Finland June 11–14, 2001 1 45 - 49    DOI : 10.1109/ICC.2001.936270
Gallager R.G. 1962 “Low-Density Parity-Check Code,” IRE Trans. Inf. Theory 8 (1) 21 - 28
MacKay D.J.C. , Neal R.M. 1997 “Near Shannon Limit Performance of Low-Density Parity-Check Codes,” Electron. Lett. 33 (6) 457 - 458    DOI : 10.1049/el:19970362
Lee S.H. , Seok J.A. , Joo E.K. “Serial Concatenation of LDPC and Turbo Code for the Next Generation Mobile Communications,” Wireless Opt. Commun. Netw. Dubai, UAE Mar. 6–8, 2005 425 - 427    DOI : 10.1109/WOCN.2005.1436061
Richardson T. “Error Floors of LDPC Codes,” Annu. Conf. Commun. Contr. Comput. Monticello, IL, USA Sept. 2003 1426 - 1435
Hu X.-Y. , Eleftheriou E. , Arnold D.M. 2005 “Regular and Irregular Progressive Edge-Growth Tanner Graphs,” IEEE Trans. Inf. Theory 51 (1) 386 - 398    DOI : 10.1109/TIT.2004.839541
2009 ETSI EN 302 755 v1.1.1, Digital Video Broadcasting (DVB); Frame Sturcture Channel Coding and Modulation for a Second Generation Digital Terrestrial Television Broadcasting System (DVB-T2)
Cavus E. , Daneshrad B. “A Performance Improvement and Error Floor Avoidance Technique for Belief Propagation Decoding of LDPC Codes,” Pers. Indoor Mobile Radio Commun. Berlin, Germany Sept. 11–14, 2005 4 2386 - 2390    DOI : 10.1109/PIMRC.2005.1651870
Yu S.-K. , Kang S.-G. , Joo E.-K. 2010 “A Modified Sum-Product Algorithm for Error-Floor Reduction in LDPC Codes,” J. KICS 35 (5) 423 - 431
Lee S.H. “Bit Probability Transition Characteristics of LDPC Code,” IEEE Int. Conf. Telecommun. Tahiti, French Polynesia Feb. 23–Mar. 1, 2003 1 553 - 557
Landner S. , Milenkovic O. 2005 “Algorithmic and Combinatorial Analysis of Trapping Sets in Structured LDPC Codes,” Wireless Netw., Commun. Mobile Comput. Maui, HI, USA 1 630 - 635
Han Y. , Ryan W.E. 2009 “Low-Floor Decoders for LDPC Codes,” IEEE Trans. Commun. 57 (6) 1663 - 1673    DOI : 10.1109/TCOMM.2009.06.070325