Turbo Code and Soft Decoding Algorithm
Turbo Encoder
A typical parallel concatenated convolutional (PCC) turbo encoder consists of two (or more) simple constituent recursive convolutional encoders linked by an interleaver (or different interleavers). A block diagram of such an encoder is shown in Fig. 6.13. The interleavers can be random, nonrandom, or semirandom.
Figure 6.13. Typical turbo encoder.
The turbo encoder works as follows. Suppose that all
constituent encoders start from the zero state and the first constituent encoder
terminates in the zero state. For user k, the
frame of input binary information bits, denoted by dk =
[dk[0],
..., dk[I – 1], is encoded by the constituent encoders, where
I is the size of the information bit frame. Let
xk[i] = [
]
denote the systematic bit and output parity bits of the constituent encoders,
corresponding to dk[i], where 
[i] is the systematic bit; 
[i], j
0, is the parity bit generated by the jth constituent encoder; and J is the number of constituent encoders. To generate a
desired code rate k0/n0, {xk[i]}
is punctured. The punctured bits are
BPSK mapped and then transmitted serially. The output bit frame is denoted by
bk = [bk[0], ..., bk[M – 1]], where M is the
size of the code-bit frame. To terminate the first constituent encoder in the
zero state, the last n bits of dk are
termination bits, where n is the number of shift
registers in the first encoder.
Soft Turbo Decoder
Corresponding to the turbo encoder in Fig. 6.13, the block diagram of an iterative soft turbo
decoder is shown in Fig. 6.14. The turbo
decoder consists of J MAP decoders. Each MAP
decoder is a slight modification of the MAP decoding algorithm for multiple
turbo codes given in [29, 100]. The signal flow is shown in Fig. 6.14. The deinterleaved LLRs {l1(bk[i])}i of the
kth user's code bits delivered by the SISO
multiuser detector are distributed to the J MAP
decoders as follows. The LLRs of the systematic bits, {l1([i])}i, are
sent to all MAP decoders after going through different interleavers. The LLRs of
the jth parity bits, {l1 (
)}, are
sent to the jth MAP decoder. Note that for a
punctured bit , we let l1 () = 0,
since no information is obtained by the soft multiuser detector for this
bit.
Figure 6.14. Soft turbo decoder.
The soft turbo decoder is itself an iterative algorithm. The
jth MAP decoder in the turbo decoder computes the
partial extrinsic information for the systematic bit and the jth parity bit, 
([i]) and (), based on the code constraints, the input LLRs given by the SISO
multiuser detector, and the partial extrinsic information given by other
modified MAP decoders. This partial extrinsic information is then sent to the
other modified MAP decoders for the next iteration within a soft turbo decoding
stage. After some iterations, the combined partial extrinsic information, which
is the sum of all J modified MAP decoders'
partial extrinsic information, is sent to the SISO multiuser detector as the
a priori information for the next iteration of
turbo multiuser detection. A more detailed description of the soft turbo decoder
is as follows.
Denote the LLR of a code bit at the jth MAP decoder as
where 
and 
denote the
sets of state transition pairs (s', s) such that
the code bit 
[i] is +1 and –1, respectively.
Define
as the partial extrinsic information of bit [i] delivered by the jth
MAP decoder.
As before, ai(s) and bi-1(s) can be computed by the following forward and backward recursions, respectively:
where S is the set of all 2n constituent encoder states. The quantity gi is defined as
Note that, by definition,
Then for b 
{+1, –1}, we have
where (6.176) follows
from the fact that b {+1, –1}. Using (6.177) in (6.173), we obtain
Substituting (6.178) into (6.169), we have
where the term 
(
[i]) is the partial extrinsic information obtained by
the jth MAP decoder which will be sent to the
other MAP decoders, as shown in Fig.
6.14; after some iterations within the turbo decoder, the total extrinsic
information, l2([i]),
is sent to the soft multiuser detector as the a
priori information about [i],
if (i) is not unpunctured. At the end of
the turbo multiuser receiver iteration, a hard decision is made on each
information bit dk[i] = [i] according to
For numerical stability, (6.179) and (6.180) should be scaled as computation proceeds, in a manner similar to that discussed in Section 6.3.3.