(cid:160)(cid:129) (cid:129)
`
`(cid:160) (cid:160)(cid:160)
`
`TDA Progress Report 42-120
`
`February 15, 1995
`
`Turbo Codes for Deep-Space Communications
`
`D. Divsalar and F. Pollara
`
`Communications Systems Research Section
`
`Turbo codes were recently proposed by Berrou, Glavieux, and Thitimajshima
`[2], and it has been claimed these codes achieve near-Shannon-limit error correction
`performance with relatively simple component codes and large interleavers. A re-
`quired Eb/No of 0.7 dB was reported for a bit error rate of 10−5, using a rate 1/2
`turbo code [2]. However, some important details that are necessary to reproduce
`these results were omitted. This article confirms the accuracy of these claims, and
`presents a complete description of an encoder/decoder pair that could be suitable
`for deep-space applications, where lower rate codes can be used. We describe a new
`simple method for trellis termination, analyze the effect of interleaver choice on the
`weight distribution of the code, and introduce the use of unequal rate component
`codes, which yields better performance.
`
`I. Introduction
`
`Turbo codes were recently proposed by Berrou, Glavieux, and Thitimajshima [2] as a remarkable step
`forward in high-gain, low-complexity coding. It has been claimed these codes achieve near-Shannon-limit
`error correction performance with relatively simple component codes and large interleavers. A required
`Eb/N0 of 0.7 dB was reported for a bit error rate (BER) of 10−5, using a rate 1/2 turbo code [2]. However,
`some important details that are necessary to reproduce these results were omitted. The purpose of this
`article is to shed some light on the accuracy of these claims and to present a complete description of an
`encoder/decoder pair that could be suitable for deep-space applications, where lower rate codes can be
`used. Two new contributions are reported in this article: a new, simple method for trellis termination
`and the use of unequal component codes, which results in better performance.
`
`II. Parallel Concatenation of Convolutional Codes
`
`The codes considered in this article consist of the parallel concatenation of two convolutional codes
`with a random interleaver between the encoders. Figure 1 illustrates a particular example that will
`be used in this article to verify the performance of these codes. The encoder contains two recursive
`binary convolutional encoders, with M1 and M2 memory cells, respectively. In general, the two compo-
`nent encoders may not be identical. The first component encoder operates directly on the information
`bit sequence u = (u1, · · · , uN ) of length N , producing the two output sequences x1i and x1p. The
`second component encoder operates on a reordered sequence of information bits, u′, produced by an
`interleaver of length N , and outputs the two sequences x2i and x2p. The interleaver is a pseudorandom
`block scrambler defined by a permutation of N elements with no repetitions: a complete block is read
`into the interleaver and read out in a specified permuted order. Figure 1 shows an example where
`a rate r = 1/n = 1/4 code is generated by two component codes with M1 = M2 = M = 4, producing the
`
`29
`
`

`
`(cid:129) (cid:129)
`
`(cid:160)(cid:160)(cid:160)
`
`u
`
`N-BIT INTERLEAVER
`
`u´
`
`D
`
`D
`
`D
`
`D
`
`ENCODER 1
`
`D
`
`D
`
`D
`
`D
`
`ENCODER 2
`
`Fig. 1. Example of an encoder.
`
`x1i
`
`x1p
`
`x2i
`
`x2p
`
`outputs x1i = u, x1p = u · ga/gb, x2i = u′, and x2p = u′ · ga/gb, where the generator polynomials ga and
`gb have an octal representation of 21 and 37, respectively. Note that various code rates can be obtained
`by puncturing the outputs.
`
`A. Trellis Termination
`
`We use the encoder in Fig. 1 to generate a (n(N + M ), N ) block code. Since the component encoders
`are recursive, it is not sufficient to set the last M information bits to zero in order to drive the encoder
`to the all-zero state, i.e., to terminate the trellis. The termination (tail) sequence depends on the state of
`each component encoder after N bits, which makes it impossible to terminate both component encoders
`with the same M bits. Fortunately, the simple stratagem illustrated in Fig. 2 is sufficient to terminate
`the trellis. Here the switch is in position “A” for the first N clock cycles and is in position “B” for M
`additional cycles, which will flush the encoders with zeros. The decoder does not assume knowledge of
`the M tail bits. The same termination method can be used for unequal rate and memory encoders.
`
`INPUT DATA
`
`B
`
`A
`
`D
`
`D
`
`D
`
`D
`
`xp
`
`xi
`
`30
`
`Fig. 2. Trellis termination.
`
`

`
`B. Weight Distribution
`
`In order to estimate the performance of a code, it is necessary to have information about its minimum
`distance, d, weight distribution, or actual code geometry, depending on the accuracy required for the
`bounds or approximations. The example of turbo code shown in Fig. 1 produces two sets of codewords,
`x1 = (x1i, x1p) and x2 = (x2i, x2p), whose weights can be easily computed. The challenge is in finding the
`pairing of codewords from each set, induced by a particular interleaver. Intuitively, we would like to avoid
`pairing low-weight codewords from one encoder with low-weight words from the other encoder. Many such
`pairings can be avoided by proper design of the interleaver. However, if the encoders are not recursive,
`the low-weight codeword generated by the input sequence u = (00 · · · 0000100 · · · 000) with a single “1”
`will always appear again in the second encoder, for any choice of interleaver. This motivates the use of
`recursive encoders, where the key ingredient is the recursiveness and not the fact that the encoders are
`systematic. For our example using a recursive encoder, the input sequence u = (00 · · · 0010000100 · · · 000)
`generates the minimum weight codeword (weight = 6). If the interleaver does not properly “break” this
`input pattern, the resulting minimum distance will be 12.
`
`However, the minimum distance is not the most important quantity of the code, except for its asymp-
`totic performance, at very high Eb/No. At moderate signal-to-noise ratios (SNRs), the weight distribution
`at the first several possible weights is necessary to compute the code performance. Estimating the com-
`plete weight distribution for a large N is still an open problem for these codes. We have investigated the
`effect of the interleaver on the weight distribution on a small-scale example where N = 16. This yields
`an (80,16) code whose weight distribution can be found by exhaustive enumeration. Some of our results
`are shown in Fig. 3(a), where it is apparent that a good choice of the interleaver can increase the mini-
`mum distance from 12 to 14, and, more importantly, can reduce the count of codewords at low weights.
`Figure 3(a) shows the weight distribution obtained by using no interleaver, a reverse permutation, and
`a 4 × 4 block interleaver, all with d = 12. Better weight distributions are obtained by the “random”
`permutation {2, 13, 0, 3, 11, 15, 6, 14, 8, 9, 10, 4, 12, 1, 7, 5} with d = 12, and by the best-found permutation
`{12, 3, 14, 15, 13, 11, 1, 5, 6, 0, 9, 7, 4, 2, 10, 8} with d = 14. For comparison, the binomial distribution is also
`shown. The best known (80,16) linear block code has a minimum distance of 28. For an interleaver length
`of N = 1024, we were only able to enumerate all codewords produced by input sequences with weights
`1, 2, and 3. This again confirmed the importance of the interleaver choice for reducing the number of
`low-weight codewords. Better weight distributions were obtained by using “random” permutations than
`by using structured permutations as block or reverse permutations.
`
`TURBO DECODING
`
`(b)
`
`U
`
`N I O
`
`N B
`
`O
`
`U
`
`N
`
`D
`
`MAXIMUM LIKELIHOOD
`
`10-1
`
`10-2
`
`10-3
`
`10-4
`
`10-5
`
`10-6
`
`BER
`
`BINOMIAL
`
`(a)
`
`NO INTERLEAVING
`
`REVERSE
`
`BLOCK
`
`RANDOM
`
`BEST FOUND
`
`105
`
`104
`
`103
`
`102
`
`101
`
`10
`
`NUMBER OF CODEWORDS (CUMULATIVE)
`
`12
`
`16
`
`20
`
`24
`28
`WEIGHT
`
`32
`
`36
`
`40
`
`0
`
`1
`
`2
`
`3
`4
`Eb/No, dB
`
`5
`
`6
`
`7
`
`Fig. 3. The (80, 16) code (a) weight distribution and (b) performance.
`
`31
`
`(cid:129) (cid:129) (cid:160)(cid:160)(cid:160)
`
`

`
`(cid:129) (cid:129)
`
`(cid:160) (cid:160)(cid:160)
`
`
`
`For the (80,16) code using the best-found permutation, we have compared the performance of a
`maximum-likelihood decoder (obtained by simulation) to that of a turbo decoder with 10 iterations, as
`described in Section 3, and to the union bound computed from the weight distribution, as shown in
`Fig. 3(b). As expected, the performance of the turbo decoder is slightly suboptimum.
`
`III. Turbo Decoding
`
`Let uk be a binary random variable taking values in {+1, −1}, representing the sequence of informa-
`tion bits. The maximum a posteriori (MAP) algorithm, summarized in the Appendix, provides the log
`likelihood ratio L(k) given the received symbols y:
`
`L(k) = log
`
`P (uk = +1|y)
`P (uk = −1|y)
`
`(1)
`
`The sign of L(k) is an estimate, ˆuk, of uk, and the magnitude |L(k)| is the reliability of this estimate, as
`suggested in [3].
`
`The channel model is shown in Fig. 4, where the n1ik’s and the n1pk’s are independent identically
`distributed (i.i.d.)
`
`zero-mean Gaussian random variables with unit variance, and ρ = p2Es/No =
`p2rEb/No is the SNR. A similar model applies for encoder 2.
`
`n1i
`
`
`
`
`
`u
`
`ENCODER 1
`
`ρ
`
`ρ
`
`y1i =ρ u + n1i
`
`y1p =ρ x1p + n1p
`
`n1p
`
`Fig. 4. The channel model.
`
`Given the turbo code structure in Fig. 1, the optimum decoding rule maximizes either P (uk|y1, y2)
`(minimum bit-error probability rule) or P (u|y1, y2) (maximum-likelihood sequence rule). Since this
`rule is obviously too complex to compute, we resort to a suboptimum decoding rule [2,3] that sep-
`arately uses the two observations y1 and y2, as shown in Fig. 5. Each decoder in Fig. 5 computes
`the a posteriori probabilities P (uk|yi, ˜ui), i = 1, 2 see Fig. 6(a), or equivalently the log-likelihood ra-
`tio Li(k) = log (P (uk = +1|yi, ˜ui)) / (P (uk = −1|yi, ˜ui)) where ˜u1 is provided by decoder 2 and ˜u2 is
`provided by decoder 1 (see Fig. 6(b)). The quantities ˜ui correspond to “new data estimates,” “innova-
`tions,” or “extrinsic information” provided by decoders 1 and 2, which can be used to generate a priori
`probabilities on the information sequence u for branch metric computation in each decoder.
`
`The question is how to generate the probabilities P (˜ui,k|uk) that should be used for computa-
`tion of the branch transition probabilities in MAP decoding.
`It can be shown that the probabilities
`P (uk|˜ui,k) or, equivalently, log (P (uk = +1|˜ui,k)) / (P (uk = −1|˜ui,k)), i = 1, 2 can be used instead of
`P (˜ui,k|uk) for branch metric computations in the decoders. When decoder 1 generates P (uk|˜u2,k) or
`log (P (uk = +1|˜u2,k)) / (P (uk = −1|˜u2,k)) for decoder 2, this quantity should not include the contribu-
`tion due to ˜u1,k, which has already been generated by decoder 2. Thus, we should have
`
`log
`
`P (uk = +1|˜u2,k)
`P (uk = −1|˜u2,k)
`
`= log
`
`P (uk = +1|y1, ˜u1,1, · · · , ˜u1,k−1, ˜u1,k+1, · · · , ˜u1,N )
`P (uk = −1|y1, ˜u1,1, · · · , ˜u1,k−1, ˜u1,k+1, · · · , ˜u1,N )
`
`(2)
`
`32
`
`

`
`(cid:129) (cid:129)
`
`(cid:160)(cid:160)(cid:160)
`
`FEEDBACK
`
`˜L1
`
`L1– ˜L1
`
`N-BIT
`INTERLEAVER
`
`˜L2
`
`L2 – ˜L2
`
`N-BIT
`DEINTERLEAVER
`
`DECODER
`1
`
`L1
`
`DECODER
`2
`
`N-BIT
`DEINTERLEAVER
`
`L2
`
`y1
`
`y2
`
`y1i
`
`y1p
`
`y2i
`
`y2p
`
`INPUTS FROM
`MATCHED
`FILTER
`
`(a)
`
`˜u1
`
`y1
`
`Fig. 5. The turbo decoder.
`
`˜L2 k( ) = log
`
`= log
`
`
`
`
`
`P uk = +1 ˜ u2,k
`
`
`
`
`
`
`P uk = –1 ˜u2,k
`
`
`
`P uk = +1 y1, ˜u1,1, ... , ˜u1,k–1, ˜u1,k+1, ... , ˜u1,N
`
`
`
`
`P uk = –1 y1, ˜u1,1, ... , ˜u1,k–1, ˜u1,k+1, ... , ˜u1,N
`
`
`
`
`
`
`
`
`
`(b)
`
`˜L1 k( )
`
`y1
`
`MAP
`DECODER 1
`
`MAP
`DECODER 1
`
`EXTRINSIC
`INFORMATION
`
`A POSTERIORI
`PROBABILITY
`
`(
`)
`P uk y1, ˜u1
`
`DECODED
`BITS
`
`
`
`˜L1 k( ) – ˜L1 k( )L1 k( )
`
`L1 k( )
`
`Fig. 6. Input/output of the MAP decoder: (a) a posteriori probability and (b) log-likelihood ratio.
`
`To compute log (P (uk = +1|˜u2,k)) / (P (uk = −1|˜u2,k)), we note [see Fig. 6(a)] that
`
`P (uk|y1, ˜u1) =
`
`P (uk|y1, ˜u1,1, · · · , ˜u1,k−1, ˜u1,k+1, · · · , ˜u1,N )P (˜u1,k|uk, y1, ˜u1,1, · · · , ˜u1,k−1, ˜u1,k+1, · · · , ˜u1,N )
`P (˜u1,k|y1, ˜u1,1, · · · , ˜u1,k−1, ˜u1,k+1, · · · , ˜u1,N )
`
`(3)
`
`Since ˜u1,k was generated by decoder 2 and deinterleaving is used, this quantity depends only weakly on
`y1 and ˜u1,j, j 6= k. Thus, we can have the following approximation:
`
`P (˜u1,k|uk, y1, ˜u1,1, · · · , ˜u1,k−1, ˜u1,k+1, · · · , ˜u1,N ) ≈ P (˜u1,k|uk) = 2P (uk|˜u1,k)P (˜u1,k)
`
`(4)
`
`Using Eq. (4) in Eq. (3), we obtain
`
`33
`
`

`
`(cid:129) (cid:129)
`
`(cid:160)(cid:160)(cid:160)
`
`
`
`P (uk|y1, ˜u1,1, · · · , ˜u1,k−1, ˜u1,k+1, · · · , ˜u1,N ) =
`
`P (uk|y1, ˜u1)P (˜u1,k|y1, ˜u1,1, · · · , ˜u1,k−1, ˜u1,k+1, · · · , ˜u1,N )
`2P (uk|˜u1,k)P (˜u1,k)
`
`(5)
`
`It is preferable to work with likelihood ratios to avoid computing probabilities not involving uk (see
`Fig. 6(b)). Define
`
`˜Li(k) = log
`
`P (uk = +1|˜ui,k)
`P (uk = −1|˜ui,k)
`
`,
`
`i = 1, 2
`
`(6)
`
`From Eqs. (2) and (5), we obtain ˜L(m)
`(k) = L(m)
`(k) − ˜L(m−1)
`(k) at the output of decoder 1, before
`2
`1
`1
`interleaving, for the mth iteration. Similarly, we can obtain ˜L(m)
`(k) = L(m)
`(k) − ˜L(m)
`(k) at the output
`1
`2
`2
`of decoder 2, after deinterleaving. Using the above definitions, the a priori probabilities can be computed
`as
`
`P (uk = +1|˜ui,k) =
`
`e ˜Li(k)
`1 + e ˜Li(k)
`
`= 1 − P (uk = −1|˜ui,k),
`
`i = 1, 2
`
`Then the update equation for the mth iteration of the decoder in Fig. 5 becomes
`
`˜L(m)
`1
`
`(k) = ˜L(m−1)
`1
`
`(k) − L(m)
`1
`
`2
`
`(k) + αmhL(m)
`(k)i , αm = 1
`This looks like the update equation of a steepest descent method, where hL(m)
`
`the rate of change of L(k) for a given uk, and αm is the step size.
`
`(k) − L(m)
`1
`
`2
`
`(7)
`
`(8)
`
`(k)i represents
`
`Figure 7 shows the probability density function of ˜L1(k) at the output of the second decoder in Fig. 1,
`after deinterleaving and given uk = +1. As shown in Fig. 7, this density function shifts to the right as
`the number of iterations, m, increases. The area under each density function to the left of the origin
`represents the BER if decoding stops after m iterations.
`
`At this point, certain observations can be made. Note that ˜L2(k′) at the input of decoder 2 includes
`an additive component 2ρy1ik, which contributes to the branch metric computations in decoder 2 at
`observation y2ik. This improves by 3 dB the SNR of the noisy information symbols at the input of
`decoder 2. Similar arguments hold for ˜L1(k). An apparently more powerful decoding structure can be
`considered, as shown in Fig. 8. However, the performances of the decoding structures in Figs. 8 and 5 are
`equivalent for a large number of iterations (the actual difference is one-half iteration). If the structure in
`Fig. 8 is used, then the log-likelihood ratio ˜L2(k) fed to decoder 2 should not depend on ˜u1k and y′
`1ik,
`and, similarly, ˜L1(k) should not depend on ˜u2k and y′
`2ik. Using analogous derivations based on Eqs. (2)
`through (5), we obtain
`
`˜L2(k) = L1(k) − ˜L1(k) − 2ρy′
`1ik
`
`˜L1(k) = L2(k) − ˜L2(k) − 2ρy′
`2ik
`
`where y′1i is the sum of y1i with the deinterleaved version of y2i and y′
`
`2i is the sum of y2i with the
`interleaved version of y1i. Thus, the net effect of the decoding structure in Fig. 8 is to explicitly pass to
`decoder 2 the information contained in y1i (and vice versa), but to remove the identical term from the
`input log-likelihood ratio.
`
`34
`
`

`
`m = 40
`
`Eb /No = 0.3 dB
`r =1/4
`
`N = 4096
`
`m = 1
`
`m = 5
`
`0.4
`
`0.3
`
`0.2
`
`0.1
`
`PROBABILITY DENSITY FUNCTION OF L˜L1k()
`
`0.0
`
`–10
`
`m = 20
`
`m = 10
`
`0
`
`10
`
`NOT RELIABLE
`
`RELIABILITY VALUE
`
`20
`˜L1 k( )
`
`30
`
`40
`
`RELIABLE
`
`DECODING ERROR
`
`CORRECT DECODING
`
`Fig. 7. The reliability function.
`
`FEEDBACK
`
`N-BIT
`INTERLEAVER
`
`N-BIT
`DEINTERLEAVER
`
`DECODER
`1
`
`y ´1i
`
`DECODER
`2
`
`y ´2i
`
`N-BIT
`DEINTERLEAVER
`
`y1i
`
`y1p
`
`y2i
`
`y2p
`
`INPUTS
`FROM
`MATCHED
`FILTER
`
`N-BIT
`DEINTERLEAVER
`
`N-BIT
`INTERLEAVER
`
`Fig. 8. An equivalent turbo decoder.
`
`DECODED
`OUTPUT BITS
`
`35
`
`

`
`(cid:129) (cid:129)
`
`(cid:160) (cid:160)
`
`IV. Performance
`
`The performance obtained by turbo decoding the code in Fig. 1 with random permutations of lengths
`N = 4096 and N = 16384 is compared in Fig. 9 to the capacity of a binary-input Gaussian channel for
`rate r = 1/4 and to the performance of a (15,1/4) convolutional code originally developed at JPL for
`the Galileo mission. At BER = 5 × 10−3, the turbo code is better than the (15,1/4) code by 0.25 dB for
`N = 4096 and by 0.4 dB for N = 16384.
`
`10–1
`
`N = 16,384, m = 20
`(TWO RATES)
`
`10–2
`
`(15,1/4) GALILEO CODE
`
`N = 4,096, m = 10
`
`N = 16,384, m = 20
`
`
`
`
`
`
`
`
`
`
`
`CAPACITY
`(BINARY
`INPUT,
`RATE =1/4)
`
`N = 4,096, m = 10
`(TWO RATES)
`
`10–3
`
`BER
`
`10–4
`
`10–5
`
`–1.5
`
`–1.0
`
`–0.5
`
`0.0
`
`0.5
`
`1.0
`
`1.5
`
`Eb/No, dB
`
`Fig. 9. Turbo codes performance, r = 1/4.
`
`So far we have considered only component codes with identical rates, as shown in Fig. 1. Now we
`propose to extend the results to encoders with unequal rates, as shown in Fig. 10. This structure improves
`the performance of the overall rate 1/4 code, as shown in Fig. 9. The gains at BER = 5 × 10−3 relative to
`the (15,1/4) code are 0.55 dB for N = 4096 and 0.7 dB for N = 16384. For both cases, the performance
`is within 1 dB of the Shannon limit at BER = 5 × 10−3, and the gap narrows to 0.7 dB for N = 16384
`at a low BER.
`
`V. Conclusions
`
`We have shown how turbo codes and decoders can be used to improve the coding gain for deep-space
`communications while decreasing the decoding complexity with respect to the large constraint-length
`convolutional codes currently in use. These are just preliminary results that require extensive further
`analysis. In particular, we need to improve our understanding of the influence of the interleaver choice
`on the code performance, to explore the sensitivity of the decoder performance to the precision with
`which we can estimate Eb/No, and to establish whether there might be a flattening of the performance
`curves at higher Eb/No, as it appears in one of the curves in Fig. 9. An interesting theoretical question
`is to determine how random these codes can be so as to draw conclusions on their performance based on
`comparison with random coding bounds.
`
`36
`
`

`
`(cid:160) (cid:160)
`
`In this article, we have explored turbo codes using only two encoders, but similar constructions can
`be used to build multiple-encoder turbo codes and generalize the turbo decoding concept to a truly
`distributed decoding system where each subdecoder works on a piece of the total observation and tentative
`estimates are shared among decoders until an acceptable degree of consensus is reached.
`
`u
`
`ENCODER 1
`
`D
`
`D
`
`D
`
`D
`
`N-BIT INTERLEAVER
`
`u´
`
`D
`
`D
`
`D
`
`D
`
`ENCODER 2
`
`Fig. 10. The two-rate encoder.
`
`Acknowledgments
`
`The authors are grateful to Sam Dolinar and Robert McEliece for their helpful
`comments.
`
`References
`
`[1] L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal Decoding of Linear Codes
`for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory,
`vol. 20, pp. 284–287, March 1974.
`
`[2] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit Error-
`Correcting Coding and Decoding: Turbo-Codes,” Proceedings of ICC ’93,
`Geneva, Switzerland, pp. 1064–1070, May 1993.
`
`x1i
`
`x1p
`
`x1p´
`
`x2p
`
`37
`
`

`
`(cid:129) (cid:129)
`
`(cid:160)(cid:160)(cid:160)
`
` (cid:160)
`
`[3] J. Hagenauer and P. Robertson, “Iterative (Turbo) Decoding of Systematic Con-
`volutional Codes With the MAP and SOVA Algorithms,” Proceedings of the ITG
`Conference on “Source and Channel Coding,” Frankfurt, Germany, pp. 1-9, Oc-
`tober 1994.
`
`[4] P. L. McAdam, L. R. Welch, and C. L. Weber, “M.A.P. Bit Decoding of Convolu-
`tional Codes” (Abstract), 1972 International Symposium on Information Theory,
`Asilomar, California, p. 91, May 1972.
`
`Appendix
`
`The MAP Algorithm
`
`Let uk be the information bit associated with the transition from time k − 1 to time k, and use s as
`an index for the states. The MAP algorithm [1,4] provides the log likelihood given the received symbols
`yk, as shown in Fig. A-1.
`
`y
`
`MAP ALGORITHM
`
`L (uk)
`
`k = 1, ..., N
`
`Fig. A-1. The MAP algorithm.
`
`L(k) = log
`
`P (uk = +1|y)
`P (uk = −1|y)
`
`= log PsPs′ γ+1(yk, s′, s)αk−1(s′)βk(s)
`PsPs′ γ−1(yk, s′, s)αk−1(s′)βk(s)
`
`(A-1)
`
`The estimate of the transmitted bits is then given by sign[L(k)] and their reliability by |L(k)|. In order
`to compute Eq. (A-1), we need the forward and backward recursions,
`
`αk(s) = Ps′ Pi=±1 γi(yk, s′, s)αk−1(s′)
`PsPs′ Pj=±1 γj(yk, s′, s)αk−1(s′)
`
`βk(s) = Ps′ Pi=±1 γi(yk+1, s, s′)βk+1(s′)
`PsPs′ Pj=±1 γj(yk+1, s′, s)αk(s′)
`
`(A-2)
`
`where
`
`38
`
`

`
`(cid:129) (cid:129)
`
`(cid:160)(cid:160)
`
`(cid:160)
`
`
`
`γi(yk, s′, s) = ½ ηkeρPn
`
`ν=1
`
`0
`
`yk,ν xk,ν (s′,i)
`
`if transition s′ → s is allowable for uk = i
`otherwise
`
`(A-3)
`
`ρ = p2(Es/N0), ηk = P (uk = ±1|˜uk), except for the first iteration in the first decoder, where ηk = 1/2,
`
`and xk,ν are code symbols. The operation of these recursions is shown in Fig. A-2. The evaluation of
`Eq. (A-1) can be organized as follows:
`
`Step 0: α0(0) = 1 α0(s) = 0, ∀s 6= 0
`
`βN (0) = 1 βN (s) = 0, ∀s 6= 0
`
`Step 1: Compute the γk’s using Eq. (A-3) for each received set of symbols yk.
`
`Step 2: Compute the αk’s using Eq. (A-2) for k = 1, · · · , N .
`
`Step 3: Use Eq. (A-2) and the results of Steps 1 and 2 to compute the βk’s for k = N, · · · , 1.
`
`Step 4: Compute L(k) using Eq. (A-1) for k = 1, · · · , N .
`
`αk–1(s´0)
`
`s´0
`
`βk+1(s˝0)
`
`s˝0
`
`γ
`i(s, s˝0)
`
`γ
`–i(s, s˝1)
`
`γ
`i0(s´0,s)
`
`γ
`i1(s´1, s)
`
`αk(s)
`
`s
`
`βk(s)
`
`k
`
`Fig. A-2. Forward and backward recursions.
`
`αk–1(s´1)
`
`s´1
`
`k – 1
`
`s˝1
`
`βk+1(s˝1)
`
`k + 1
`
`TIME
`
`39