Advanced
Formulation of Joint Iterative Decoding for Raptor Codes
Formulation of Joint Iterative Decoding for Raptor Codes
Journal of Korea Multimedia Society. 2014. Aug, 17(8): 961-967
Copyright © 2014, Korea Multimedia Society
  • Received : June 13, 2014
  • Accepted : July 21, 2014
  • Published : August 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
M. Zhang
Div. of Electronics Eng., Chonbuk National University
S. Kim
Div. of Electronics Eng., Chonbuk National University
W.Y. Kim
Comesta, Inc.
Y.H. Cho
Comesta, Inc.

Abstract
Raptor codes are a class of rateless codes originally designed for binary erasure channels. This paper presents a compact set of mathematical expressions for iterative soft decoding of raptor codes. In addition, an early termination scheme is employed, and it is embedded in a single algorithm with the formula. In the proposed algorithm, the performance is enhanced by adopting iterative decoding, both in each inner and outer code and in the concatenated code itself between the inner and outer codes. At the same time, the complexity is reduced by applying an efficient early termination scheme. Simulation results show that our proposed method can achieve better performance with reduced decoding complexity compared to the conventional schemes.
Keywords
1. INTRODUCTION
Luby transform (LT) codes were first proposed as rateless codes, and were designed to obtain capacity-achieving performance for a binary erasure channel (BEC) without knowing the erasure conditions [1] . The decoding complexity of LT codes is generally infeasible when the length of the code is long. Raptor codes were designed to solve this problem, as an extension of LT codes [2] . A raptor code is a concatenated code of an LT code as an inner code and a precode as an outer code, and generally, a low density parity check (LDPC) code is used for a precode.
In earlier stages, these rateless codes have almost exclusively been investigated on erasure channels with a hard decision decoding method, and later soft iterative decoding algorithms for LT codes were attempted [3] . By using the soft information produced by both components codes of raptor codes, joint iterative decoding algorithms for raptor codes were proposed [4 - 6] . Efficient resource management is very important in wireless communication systems due to rapidly increasing traffic demands [7] . Utilization of joint iterative decoding algorithms for raptor codes may play important role to reduce the amount wireless traffic by decreasing unnecessary retransmissions. However, there was no clear mathematical expression of how soft information passes through the decoders.
Motivated by these prior works, an enhanced version of the joint iterative soft decoding for raptor codes is proposed, and all detailed mathematical formulas for soft information exchange across the decoders are provided. In addition, we adopt efficient stopping criteria to eliminate redundant iterations at the decoder.
2. SOFT JOINT ITERATIVE DECODING FOR RATPOR CODES
- 2.1 System Model
Fig. 1 shows the transmission flow using a raptor code. At the transmission part, information I with length k ′ is encoded to of length k by the outer LDPC code using a parity check matrix H, and u is encoded to c by the inner LT encoder with a predetermined degree distribution ρ [1 , 2] . Then, c is modulated and transmitted through the channel.
PPT Slide
Lager Image
Transmission flow with a raptor code with soft decoding.
At the receiver part, the receiver starts the demodulation and decoding process if a sufficient number of received symbols are collected. The LT decoder takes the demodulated soft information r of length n as priori information, and produces soft information v of length k . Then, the LDPC decoder utilizes v as soft input, and iteratively estimates soft output
PPT Slide
Lager Image
. For joint iterative decoding,
PPT Slide
Lager Image
from the LDPC decoder is passed back to the LT decoder, and the decoding is repeated. The ACK signal will be sent to the transmitter if the decoding is successful. Otherwise, more received symbols will be collected for the next decoding attempt.
- 2.2 Soft inputs and soft outputs
Fig. 2 shows the concept of the joint soft decoding for raptor codes. There are three soft-input-soft-output (SISO) iterative loops in the decoder, one in the inner LT decoder, another one in the outer LDPC decoder, and finally, the last one between the LT and LDPC decoders. The soft iterative decoding of the LT and LDPC codes is performed by using the belief propagation algorithm for each code [3 , 8] . In each of the codes, the estimation of the log likelihood ratio (LLR) between the nodes is performed iteratively.
PPT Slide
Lager Image
The concept of joint iterative decoding for raptor codes.
Before the LT decoder, soft input of the joint decoder, ri , is estimated by a soft demodulator. Then, soft iterative decoding is performed by alternatively estimating LLRs between the encoding node, j , and information node, i , where 1 ≤ j n and 1 ≤ i k . L (η,α) ( tj,i ) is the LLR estimated from encoding node j to information node i , while L (η,α) ( hj,i ) is the one from information node i to encoding node j , where η and α are the indices for iteration numbers of the joint and LT decoders. The decoding process is first started by initialization of L (η,α) ( hi,j ) and finished by the estimation of soft output information, vi (η,α) . If the iterative process inside the LT decoder is finished, then the final soft output for the information nodes is passed to the LDPC decoder and utilized as a priori information.
Afterwards, the LDPC decoder updates the LLRs messages between the bit and check nodes alternatively.
PPT Slide
Lager Image
is the LLR from bit node i to check node t , while
PPT Slide
Lager Image
is the LLR from check node t to bit node i , where β is the index for iteration numbers of the LDPC decoder. Subsequently, the soft output on bit nodes
PPT Slide
Lager Image
is estimated and parity check equation is examined. After the LDPC decoding process, the final estimation vector on bit nodes is passed back to the LT decoder and utilized as a priori information for the next joint iteration.
3. FORMULATION OF JOINT ITERATIVE DECODING
- 3.1 Conventional approach
In the conventional approach, the final soft estimation
PPT Slide
Lager Image
from the LDPC decoder was added to the incoming LLRs from the encoding node, which were obtained in the previous LT iteration [5] . It can represented by the following equation:
PPT Slide
Lager Image
where α max is the maximum iteration number for the LT decoder. By this way, the information passed from the LDPC decoder cannot be utilized, because the decoding of the LT code should be started with the calculation of LLRs from encoding node to information node, L (η,α) ( tj,i ), with a priori information from the channel, ri and LLRs from information node to encoding node, L (η,α) ( hi,j ) [6] .
- 3.2 Exchanging of soft information
After receiving ri from the soft demodulator and initializing, soft iterative decoding is performed alternatively using a belief propagation algorithm for both of the component decoders. At the first joint iteration, i.e., η = 1, all L (1,0) ( hi,j ) = 0 and from the second joint iteration, the soft output from the LDPC decoder will be used as initial values of L (η,0) ( hi,j ). We note that this initialization enables efficient utilization of extrinsic information from the LDPC decoder. With these initial values, L (η,α) ( tj,i ) is estimated as follows:
PPT Slide
Lager Image
where Nj is the index set of the neighborhood information nodes of encoding node, j . Next, L (η,α) ( hi,j ) is updated as follows, using the result in (2).
PPT Slide
Lager Image
where εi is the index set of encoding nodes connected with information node i . By increasing the iteration number, α , by 1, L (η,α) ( tj,i ) can be re-updated as in (2) using the result in (3).
The soft output information is then calculated by:
PPT Slide
Lager Image
This iterative process is continued until we reach α = α max , or using a stopping criterion which will be explained later.
If the iterative process inside the LT decoder is finished, then the final soft output for the information nodes is passed to the LDPC decoder and utilized as a priori information in the form of the following initialization.
PPT Slide
Lager Image
where Ri is the index set of the neighborhood check nodes of bit node i , and αn is the number of iterations made at the LT decoder.
Afterwards, the LDPC decoder updates the messages between the bit and check nodes alternatively using the following equations [8] :
PPT Slide
Lager Image
PPT Slide
Lager Image
where β is the index for the iteration number of the LDPC decoder,
( a . b )= sign ( a ) sign ( b ) min(| a |,| b |)+ LUTg ( a , b ),
LUTg ( a , b )=log(1+ e -|a+b| )-log(1- e -|a-b| ) and Ct is the index set of neighbourhood bit nodes of check node t , where 1 ≤ t k - k ′. Subsequently, the soft output on bit nodes is estimated by:
PPT Slide
Lager Image
The iterative calculations from (6) to (8) are continued until we reach the maximum number of iterations set for LDPC decoder, β max , or the parity check equation is satisfied.
After the LDPC decoding process, the final estimation vector on bit nodes is passed back to the LT decoder and utilized as a priori information in the form of the following initialization:
PPT Slide
Lager Image
where βn is the number of iterations made at the LDPC decoder.
- 3.3 Stopping criterion
In addition to this joint soft iterative decoding on three loops, we adaptively regulate αn and βn by using an efficient stopping criterion. In order to reduce the complexity of the joint iterative decoding, we modify the stopping criterion of iterative decoding proposed previously [9] , and utilize it to exit the iterative decoding process of the joint as well as LT decoding. In our method, if the signs of of vi (η,α–1) and vi (η,α) are the same, then LT decoding is terminated with αn = α , and vi (η,αη) is passed to the LDPC decoder using (5). In addition, if the signs of vi (η,1) and vi (η,2) are the same, then the joint iterative decoding is also terminated after the LDPC decoding process, finishing the whole decoding process. This is because no sign changes at an earlier stage generally means there was almost no valid soft input from the previous LDPC decoding process, and thus, further iteration may be meaningless [10] .
4. SIMULATION RESULTS
We simulate the performance of the proposed soft joint decoding with early termination algorithms for raptor codes on an additive white Gaussian noise (AWGN) channel. We used a degree distribution previously designed for LT codes [11 , 12] , and used the (1176, 1078) size compatible (SC)-Array LDPC codes [13] . The maximum number of iterations for joint, LT, and LDPC decoders, ( η max , α max , β max ) are shown in the performance graphs. The binary phase shift keying (BPSK) modulation scheme is used in all of the simulations.
If η max =1, the decoder can be considered as a tandem decoder without any joint iterative operation. On the other hand, if α max = β max =1, then the decoder utilizes only outer-loop without any iterations inside of LT and LDPC decoders. If we assume that the complexity of the LT and LDPC decoders are the same, then the same η max ( α max + β max ) would result the same decoding complexity and delay. Therefore, we set η max ( α max + β max )=200 in all of the simulations, and tried various combinations of ( η max , α max , β max ).
Fig. 3 shows the bit error rate (BER) performance comparisons of the conventional method in [5] with our proposed method according to R –1 when ES / N 0 =0 dB and the decoder iterates until it reaches the maximum number of iterations. The performance comparison in this figure shows that the proposed method outperforms the conventional method in [5] for any parameter combinations, on the condition that both of the methods are iterated. Fig. 4 shows the BER performance comparisons of the reduced search using the proposed stopping criterion with the fully iterated decoder. In Fig. 4 , BER performance of our proposed method with the reduced research can approximate to that of the full search for all the parameter combinations.
PPT Slide
Lager Image
BER performance comparisons for the conventional and proposed methods with the full search.
PPT Slide
Lager Image
BER performance comparisons of the proposed method with an early stopping criterion.
The BER performances in Fig. 3 and 4 show that the proposed soft joint iterative decoding methods produce much better performance than the conventional method [5] . It also demonstrates that with the same η max ( α max + β max ) values, the proposed methods can produce the better performance by allocating more iterations at the outer joint loop for ordinary joint iterative decoding, i.e., η max > 1, α max > 1, and β max > 1. For example, both of the full search and reduced search with (20,5,5) produce better performance than those with (5,20,20) do. The proposed method with reduced search using the same iteration numbers has almost the same performance as the full search method.
Fig. 5 presents the decoding complexity in terms of the total number of iterations made at the LT decoder,
PPT Slide
Lager Image
As shown in Fig. 5 , the complexity of our proposed method with the early stopping criterion is highly reduced compared with that of the method in [5] . For the reduced search method, the complexity with ( η max , α max , β max )=(20,5,5) is much less than with ( η max , α max , β max )=(5,20,20). This implies that more iterations at the outer joint loop in the proposed scheme can produce better performance with less complexity, i.e., smaller NLT , for ordinary joint iterative decoding, i.e., η max > 1, α max > 1, and β max > 1..
PPT Slide
Lager Image
Complexity comparison for various decoding algorithmsl.
4. CONCLUSION
This paper presents a compact set of equations for an efficient joint iterative soft decoding with an early termination algorithm for raptor codes. The simulation results demonstrated that the proposed scheme produces better performance than the conventional approach. In addition, adoption of the early termination algorithm produces almost the same performance as the full search method with highly reduced decoding complexity. We also demonstrate that with our proposed method, we can further enhance the performance by allocating more iterations at the outer joint loop, and fewer iterations at the inner LT and LDPC decoder loops, resulting in a reduced complexity.
BIO
Meixiang Zhang
She received the BE degree from South-Central Univ. for Nationalities, China, and MS degree from Chonbuk National Univ., Korea in 2008 and 2010, respectively. She is currently pursuing her PhD degree at Chonbuk National Univ.. Her research interests include satellite and digital communications, channel coding theory, soft detection, and rateless codes.
Sooyoung Kim
She received the B.S degree in electrical and electronics eng. from KAIST, Korea, in 1990. After having worked ETRI, Korea from Feb. 1990 to Sep. 1991, she received the M.Sc and Ph. D degree in electrical and electronics eng. from Univ. of Surrey, U.K in 1992 and 1995, respectively. From Nov. 1994 to Jun. 1996 she was employed as a research fellow at the Centre for Satellite Engineering Research, Univ. of Surrey, U.K. In 1996 she re-joined ETRI, Korea, and worked as a team leader until Feb. 2004. She is now a professor in Chonbuk National University. Her research interests include coded MIMO schemes and iterative soft detection and decoding for wireless communication systems.
Won-Yong Kim
He received the B.S and M.Sc degree in electronics eng. from Chonnam National Univ., Korea in 1995 and 1997, respectively. From Mar. 1997 to Aug. 1999 he was employed as a research fellow at ETRI, Korea. From Aug. 1999 to Dec. 2002 he worked as a team leader to develop satellite modem system for military radio communication. Now He is a CTO in Comesta Inc. His research interests include synchronization, equalization and efficient transmission techniques for digital communication systems.
Yong-Hoon Cho
He received the B.S and M.Sc degree in electrical eng. Yonsei Univ., Korea in 1986 and 1988, respectively. He received the Ph. D degree in electrical and electronics eng. in 2001. From Sep. 1989 to Aug. 2002 he was employed as a team leader at ETRI, Korea. From Sep. 2002 to Dec. 2011 he was a invited professor in Jeonju Univ.. Now He is the CEO in Comesta Inc. His research interests include error correction coding schemes, mobile and satellite communications, and data links.
References
Luby M. 2002 “LT Codes” Proceeding of the 43rd Annual IEEE Symposium on the Foundations of Computer Science 271 - 280
Shokrollahi A. 2006 “Raptor Codes” IEEE Transaction on Information Theory 52 (6) 2551 - 2567    DOI : 10.1109/TIT.2006.874390
Jenka H. , Mayer T. , Stockhammer T. , Xu W. 2005 “Soft Decoding of LT-codes for Wireless Broadcast” Proceeding of IST Mobile Summit
Venkiah A. , Poulliat C. , Declercq D. 2007 “Analysis and Design of Raptor Codes for Joint Decoding using Information Content Evolution” Proceeding of IEEE International Symposium on Information Theory 421 - 425
Huang W. , Li H. , Dill J. 2010 “Digital Fountain Codes System Model and Performance over AWGN and Rayleigh Fading Channels” Proceeding of International Conference on Computing, Communications and Control
Zhang M. , Kim S. , Jiang X. 2013 “Joint Iterative Soft Decoding for Raptor Codes” Proceeding of IEEE 17th International Symposium on Consumer Electronics 25 - 26
Lee S. , Lee M. 2010 “Packet Scheduling Algorithm of Increasing of Fairness According to Traffic Characteristics in HSDPA’‘ Journal of Korea Multimedia Society 13 (11) 1667 - 1676
Eroz M. , Sun F. , Lee L. 2004 “DVB-S2 Low Density Parity Check Codes with Near Shannon Limit Performance” International Journal of Satellite Communications and Networking 22 (3) 269 - 279    DOI : 10.1002/sat.787
Hagenauer J. , Offer E. , Papke L. 1996 “Iterative Decoding of Binary Block and Convolutional Codes” IEEE Transactions on Information Theory 42 (2) 429 - 445    DOI : 10.1109/18.485714
Zhang M. , Kim S. , Kim W.Y. , Cho Y.H. 2014 “Soft Decoding for Raptor Codes with an Efficient Early Termination Algorithm” Proceeding of IEEE 18th International Symposium on Consumer Electronics 160 - 161
Hu K. , Castura J. , Mao Y. 2007 “Performance-Complexity Tradeoffs of Raptor Codes over Gaussian Channels” IEEE Communication Letters 11 (4) 343 - 345    DOI : 10.1109/LCOM.2007.348295
Orozco V. , Yousefi S. 2010 “Trapping Sets of Fountain Codes” IEEE Communication Letters 14 (8) 755 - 757    DOI : 10.1109/LCOMM.2010.08.100548
Abematsu D. , Ohtsuki T. , Jarot S. , Kashima T. 2007 “Size Compatible (SC)-Array LDPC Codes” Proceeding of IEEE 66th Vehicular Technology Conference 1147 - 1151