International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013

ISSN 2229-5518

3015

Iterative Decoding of Turbo Codes

Miss.Rupinder Kaur, Mr.Shakti Raj Chopra. Lovely Professional University,Jalandhar

Abstract— In this paper through analysis of results we have shown that by using the Max-Log-MAP and Log-MAP algorithms the two stopping criterions namely PCS and HDA have the same performances, for the complex AW GN channel and for Rayleigh Fading channel with BPSK modulation. Since the HDA stopping criteria compares only the systematic bits from two constituent decoders which does not need to check with parity bits and re-encode the systematic bits ,it is proved to be simpler then the PCS stopping criteria.

Index Terms— APP(a-posteriori-probability),AW GN(Additive white Gaussian noise), BLER(block error rate), HDA(Hard Decision Aided),Iterative Decoding, LLR(Log likelihood ratio),MAP(Maximum-a-posteriori-probability), PCS(Parity Check Criterion),SISO(Soft input soft output),RSC(Recursive Systematic Convolutional Encoder),SNR(Signal to noise Ratio)

——————————  ——————————

1 INTRODUCTION

1.1Turbo Codes

In the recent years, Turbo Codes that achieve the near Shannon limit performance have attracted great interest and have been chosen for third mobile communication standard (IMT-2000/3GPP).
The basic turbo codes are made up with two parallel concatenated and identical recursive systematic convolutional (RSC) encoders, separated by an interleaver. The RSC encoders generate the systematic codeword which consists the parity bits (xk1,xk2)followed by the information bit(xks). A typical structure of the turbo encoder with the coding rate (R) of 1/2 (with puncturing) or with the rate R of 1/3 is shown in Fig.1.The constituent encoders are generally used to the identical component codes which are the same constraint length and the generator polynomial [7],[11].

Fig. 1. Turbo Encoder block diagram[11].
Let uk, k {1,…,n} be the information bits, whose code bits are BPSK modulated and transmitted through a channel. At the turbo decoder,(yks,yk1,yk2)are signals corresponding to uk,Where yks is the systematic signal, (yk1,yk2) are the parity signals for a RSC1 and a RSC2 encoder, respectively. The first encoder encodes the input bit uk and the second encoder, encodes the interleaved input bit un. The codeword output can be punctured to change the overall code rate. We denote by
GD=[g1,g2] the parallel concatenated turbo code with RSC encoders g1 and g2 Where g1 is terminated. Note that in general g1 and g2 get the same component codes. The RSC encoders are denoted by (FBoct ,FFoct), where FBoct and FFoct are the feedback and the feed forward encoding polynomials, respectively. The feed-forward polynomial and the feedback polynomial of the generator polynomial for a RSC encoder are relatively prime. The feedback polynomial of the generator polynomial for a RSC encoder should be primitive to improve the BER performance of a turbo code [11].

1.2 Stopping Criterias

Techniques for early stopping of iterative decoding of Turbo codes are of interest for many reasons, such as increasing average decoder throughput or reducing the average decoder power-consumption
Various early stopping methods have been proposed(1-8) earlier, and they can be categorized into two classes[6].One class is based on soft-bit decisions such as CE(Cross Entropy),absolute log-likelihood ratio (LLR) measurement, mean estimation (ME),and a priori LLR measurement. The other class is based on hard-bit decisions, such as sign-change ratio (SCR), hard decision-aided (HDA), and sign-difference ratio (SDR). In addition, some methods are based on extra checking policies, such as CRC(cyclic redundancy check)[11].Most stopping criterias cannot terminate the decoding process at half the iteration, so the minimum controllable number of iterations is 1.
PARITY-CHECK stopping (PCS) scheme for iterative
turbo decoding is proposed in [14], where each soft-input and soft-output (SISO) decoder outputs both the estimated systematic bits and parity bits. The systematic bits from one SISO decoder are interleaved and encoded with the constituent encoder, then the parity bits from the encoder are compared with the parity bits from another SISO decoder. If
the two sets of parity bits are matched bit by bit, the iterative decoding stops[13].
Another well-known stopping criterion named hard decision-aided (HDA) has been proposed in [15], which

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013

ISSN 2229-5518

3016

compares decisions from the same SISO on successive full- iterations. An improved HDA (IHDA) was proposed in [16] which requires less storage than HDA with similar performance in terms of bit error rate (BER) and average number of iterations. A general HDA approach was first introduced in [4]. This HDA approach compares hard decisions of the systematic bits between SISO1 and SISO2, and can stop the iterative decoding after either SISO, which is currently the best HDA approach. HDA has very good performance with enhanced max-log-MAP algorithm (i.e., with scaled extrinsic information feedback). In digital communication systems, HDA is a well known rule that attempts to detect the unreliable decoded sequences by evaluating the tentative decoded bits (hard bit decisions)at the end of each iteration in comparison with the previous iteration.

2 ITERATIVE DECODING

2.1 Iterative Turbo Decoding

Iterative Turbo Decoding achieves a good performance as the number of the iterations increases along with the decoding process. However too many iterations cause computational burden and latency. Stopping rules treat this problem by finding an acceptable compromise between performance and complexity through reducing the number of iterations.

2.2 Turbo Decoding Algos

The effectiveness of the Turbo decoding scheme is based on iterating the MAP algorithm applied to each constituent code. In general, MAP algorithm is implemented by means of SISO decoder, which computes the APP, i.e. the reliability value, for each received information symbol .However this computation is extremely complex owing to the multiplications and exponential operations needed for forward and backward recursions in the trellis diagram. To reduce the decoding complexity of MAP algorithm, researchers have developed other SISO decoders, which are less complex and can be used instead of MAP algorithm. Two of such algorithms are Max- Log-MAP and the Log-MAP algorithms.

2.3 Log-MAP algorithm

The Log-MAP algorithm was proposed by Robertson et al.[10],which corrected the approximation used in the Max- Log-MAP algorithm and hence attain a performance identical to the MAP algorithm at a fraction of its complexity. In Log- MAP algorithms for the component decoders is suitable for the hardware implementation, due to its relative simplicity compared with the original MAP algorithm and has better performance than the Max-Log-MAP algorithm. The Log- MAP algorithm, which is suitable for the iterative decoding and has less complex hardware implementation without multiplication by using of ―Log‖ operation, is adopted as SISO decoding algorithm[11].
Each Log-MAP decoder calculates the LLR for the input bits using the Log-MAP criterion. After defining the number

of decoding iterations, the hard decisions are estimated from the LLR. The procedure of the Log-MAP algorithm is as follows. The branch metrics Γ are calculated from the received signals and the soft output of the previous Log-MAP decoder according to equation (1), where LC is the channel reliability
The back-ward state metrics B, the forward state metrics and the LLR are calculated in the following order using equations (2), (3) and (4) , and then the soft output is obtained.

Where y, sand s are the received symbol sequence, the previous state and the present state of the trellis. After completing the final iteration process, the decoded hard decision data is obtained from the de-interleaved LLR sequence of the second Log-MAP decoder. In a Log-MAP turbo decoder, each component decoder make the forward recursion to compute the metric A, then make the backward recursion to compute the metric B . With metrics A, B and the branch transition metrics Γ, each component decoder produces the extrinsic information Le for the other component decoder.
As the decoding proceeds, a SISO turbo decoder plays an important role in determining the decoding quality. The SISO Turbo decoder computes the APP, i.e. the reliability value, for each received information symbol. In a Soft-In-Soft- Out decoding algorithm (Log-MAP decoding), the output LLR of the component decoder can be modeled with an independent Gaussian random variable, where the variance of the LLR corresponds to the variance of the AWGN channel, and its mean value to the transmitted systematic bit. That is the sign of LLR determines the binary symbol, negative for 0 and positive for 1, and the magnitude quantify the decision certainty. Hence, when values of LLR are close to zero, the decoder decision is ambiguous.
The basic iterative decoding structure is depicted in Fig.2.

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013

ISSN 2229-5518

3017

the situation of equal path metrics),

sˆk

and

pˆ k

must come
from the same path in the trellis. In the PCS scheme, there are
two parity-check flags to stop the iteration, as shown in Fig. 4:

(a)
S1 of the i-th iteration is interleaved and encoded with the
2nd recursive systematic convolutional encoder (RSC2), and

then compared with

P2 . If the two sequences are totally

Fig. 2. Turbo Decoder block diagram[11].
As shown, One SISO decoder takes the systematic sequence yKS and the parity sequence yK1 (or yK2) as input and computes
the log-likelihood ratio (LLR) of each information bit based on
matched, the iteration is terminated.
(b) Sˆ2 of the i-th iteration is de-interleaved and encoded with
RSC1, and then compared with Pˆ . If the two sequences are totally matched, the iteration is terminated.
The process of (a) and (b) are similar. For convenience, we
take (a) at i-th iteration as an example to explain the equivalence
between the PCS and the HDA criteria. As described in the

the trellis structure of the RSC.
above, for SISO2 decoder, the systematic bits S 2

and the parity
bits

P2 are in the same ML path in the encoding trellis. So it is

Unlike the max-log-MAP and SOVA algorithms which only
look at two paths per step, the log-MAP algorithm always
easy to deduce that Pˆ
is also the encoded result of Sˆ2 , with the
takes all paths into calculation, but splits them into two sets (s=1, s=0), which may change from step to step. The information bits output from the log-MAP decoder do not certainly constitute a whole path in the trellis. Thus we cannot get a certain relationship between the systematic bits and
encoder of RSC2. As we know, the RSC encoding is a one-to-one
mapping process (assuming a rate 1/2 RSC code), which means that one information sequence can only give rise to one unique parity sequence, and one parity sequence can only arise from one

ˆ ' Pˆ ,

parity bits output from a log-MAP decoder. This means that
unique information sequence. So if

P 2 is the same as 2

ˆ and

ˆ are not certainly the encoding results of

ˆ and

ˆ must be the same as Sˆ2

. On the other hand, if Sˆ
is the same

Sˆ2

respectively. However, since log-MAP algorithm and max-
as Sˆ2
,after encoding with RSC2, they must get the same parity
log-MAP with a proper scaling factor on the extrinsic information have similar performance we expect that using

bits. So the PCS criterion is equivalent to comparing Sˆ
and Sˆ2 ,
log- MAP decoding, the PCS has similar performance with HAD in most scenarios in terms of average iteration number and block error rate[13].

2.4 Max-Log-MAP algorithm

It has been proved in [6] that, the max-log-MAP algorithm is equivalent to the soft-output Viterbi algorithm (SOVA), and the max-log-MAP algorithm makes the same hard decisions as the Viterbi algorithm (assuming no tied path metrics). In the decoding process, the max-log-MAP looks at two paths per step in the trellis, the best with bit zero and the best with bit one, and outputs the difference of the log-likelihoods of the two paths. From step to step, one of these paths may change, but one will always be the maximum-likelihood (ML) path. That means, for the max-log-MAP decoding, the hard decision of the output always comes from the ML path because the ML path always has the largest path metrics (again, assuming no tied path metrics). From (5) and (6), we can see that, the decoding processes are quite similar for the systematic bits and parity bits. The difference is the path set of bit zero and the path set of one. However, in max-log-MAP decoding, the output of hard decision bits always come from the ML path, which is valid for both systematic bits and parity bits. Since there is only one ML path in the trellis (without considering
which is actually the HDA criterion shown in Fig. 5. Similar to
the proof of (a), it’s easy to prove that (b) is also equivalent to the
HDA criterion[13].

2.5 Comparison between PCS and HDA Criteria

In the PCS scheme, each SISO decoder outputs log-like lihoodratio (LLR) (as shown in Fig. 3) of the systematic bits sk and the parity bits pk, which can be expressed as follows,
Fig. 3. Turbo Decoding of systematic and parity bits[13].

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013

ISSN 2229-5518

3018

(5)

where α, β and γ denote the forward recursive, backward
recursive and branch transition probabilities, respectively. For
max-log-MAP decoding, we can rewrite (5) as:

(6) where A, B and Γ are logarithms of α, β and γ, respectively. Then the hard decisions (HD) of sk and pk are based on the

sign of L(sk) and L(pk) respectively:

sˆk =1, if L(sk)>0; else sˆk =0,
stopping criterias (PCS and HDA), In terms of Block-error-rate and average number of iterations as a function of Eb/No, Where Eb is the energy per information bit and NO the noise power spectral density.
The simulations are conducted over complex AWGN Channel and Rayleigh Fading Channel, with BPSK modulation. Worked with Turbo codes of rate=1/2,generator polynomial(6,4)in octal, with a random interleaver. The maximum numbers of the iterations allowed were fixed to 8.
Relationship between SNR and Eb/N0 in a BPSK system is SNR(dB) = Eb/N0(dB) − 10 lg(1/R). where R is Turbo code rate 1/2 in our scheme. Information length is 1600. In high SNR conditions, it is expected that the decoder decodes successfully, and it can stop operating at early stages without further iterations . On the other hand, the decoder should stop operating for unnecessary iterations in low SNR conditions when there is an unsolvable situation. Based on iterative decoding, the input a priori LLR of one component decoder comes from the output extrinsic LLR of the other component decoder. The observation of the LLRs of one component decoder can characterize the convergence of the Turbo decoder towards final decoded frame.

pˆ k =1 ,if L(pk)>0; else

pˆ k = 0.

Fig. 4. The PCS criterion for iterative Turbo Decoding[13].
Fig. 5. The HDA criterion for iterative Turbo Decoding[13].

3 Simulation Results

In this section we investigated the comparisons of two

Fig. 6.The error performance of the log-MAP algorithm with different stopping criterias, information length = 1600,with Rayleigh Fading channel.

Fig .7.The error performance of the log-MAP algorithm with different stopping criteria, information length1600,with complex AWGN channel.

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013

ISSN 2229-5518

3019

Fig.8.The error performance of the Max-log-MAP algorithm with different stopping criterias, information length = 1600,with Rayleigh Fading channel.

Fig.9. The error performance of the Max-log-MAP algorithm with different stopping criterias, information length = 1600,with complex AWGN channel.

4.CONCLUSION

In this paper through analysis of results we have shown that by using the Max-Log-MAP and Log-MAP algorithms, the two stopping criterions namely PCS and HDA have the same performances for the complex AWGN channel and for Rayleigh Fading channel with BPSK modulation. Since the HDA stopping criteria compares only the systematic bits from two constituent decoders which does not need to check with parity bits and re-encode the systematic bits, it is proved to be simpler then the PCS stopping criteria

References.

[1] F. Li, A. Wu, ―On the New Stopping Criteria of Iterative Tu rbo Decoding by Using Decoding Threshold,‖ IEEE Trans Signal Process, vol. 55, pp. 5506–5516, November 2007.

[2] A. Hunt, S. Crozier, K. Gracie, J. Lodge. ―A completely safe

earlystopping criterion for max-log turbo code decoding‖. 4th international symposium on turbo codes & related topics, M unich, Germany. April3-7 2006.

[3] M. Zheng. et al., ―A joint early detection-early stopping scheme for

short-frame turbo decoding‖. Int J Electron Commun vol. 65, pp. 37 –43

2011.

[4] L. Erl-Huei, L. Yi-Nan, H. Wei-Wen, ―Improvement of turbo decoding using cross-entropy‖. Computer Communications vol. 32, pp. 1034 -1038,

2009.

[5] F. Li, A. Wu, ―A new stopping criterion for efficient early termination in turbo decoder designs‖, Proceedings of the IEEE Int Symposium on Intelligent Signal Processing and Communication Systems, pp. 585 - 588, Hong Kong, December 13-16, 2005.

[6] A. Matache, S. Dolinar, F. Pollara, ―Stopping rules for turbo

decoders.‖Jet Propulsion Lab., Pasadena, CA, JPL Progress Rep. 42-142, 15

August, 2000.

[7] S. Byoung-Sup, P. Hyoung-Keun, K. Sun-Youb, R. Yu-Chan, ―An

efficient iteration decoding stopping criterion for turbo codes.‖ ICCSA'07

Proceedings of the International Conference on

Computational Science and its Applications, Kuala Lumpur, Malaysia, Part II, pp. 104-112, August 2007.

[8] R. Shao, S. Lin, MCP. Fossorier, ―Two simple stopping criteria for

turbo decoding.‖ IEEE Trans Commun vol. 47, pp. 1117-1120, 1999.

[9] Z.Wu, M.Peng, and W.Wang,―A new parity-check stopping crite-rion

for turbo decoding,‖ IEEE Commun. Lett., vol. 12, no. 4, pp. 304 –306,Apr.

2008.

[10] P. Robertson, E. Villebrun, P. Hoeher, ―A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain‖.Proceeding IEEE International Conference on Communications ICC, Seattle, WA, USA, pp. 1009-13, 1995.

[11] Imed Amamra, Nadir Derouiche, ―A Stopping criteria for turbo decoding based on the LLR histogram‖, IEEE Trans, 978-1-4673-0784-0/12. [12] M. P. C. Fossorier, F. Burkert, S. Lin, and J. Hagenauer COn the equivalence between SOVA and max-log-MAP decodings,‖ IEEE Commun.Lett., vol. 2, no. 5, May 1998.

[13] Yuejun Wei, Yuhang Yang, Lili Wei, Member, IEEE, and Wen Chen,

Senior Member, IEEE, ―Comments on―A New Parity-Check Stopping Criterion for Turbo Decoding‖, IEEE COMMUNICATIONS LETTERS, VOL. 16, NO. 10, OCTOBER 2012

[14] Z. Wu, M. Peng, and W. Wang, ―A new parity-check stopping

criterion for turbo decoding,‖ IEEE Commun. Lett., vol. 12, no. 4, pp. 304 –

306, Apr. 2008.

[15] R. Y. Shao, M. Fossorier, and S. Lin, ―Two simple stopping criteria for iterative decoding,‖ in Proc. 1998 International Symposium on Information

Theory, pp. 279, Aug. 1998.

[16] T. Ngatched and F. Takawira, ―Simple stopping criterion for turbo decoding,‖ Electron. Lett., vol. 37, pp. 1350–351, Oct. 2000.

http://www.ijser.org