Turbo Codes

9.1 Turbo Encoder

  • Turbo Encoder: consists of the parallel concatenation of two or more (usually identical, rate-1/2) recursive systematic convolutional (RSC) encoders and a pseudorandom interleaver.

Recursive Systematic Convolutional (RSC) encoders : different from the non-recursive convolutional encoder discussed in earlier classes. Realized in systematic feedback form.

  • Parallel concatenation: two encoders operate on the same set of input bits, rather than one encoding the output of the other.
  • Interleaver: to permute the input bits such that the two encoders are operating on the same set of input bits, but different input sequences.
  • The input bits are grouped into finite-length sequences whose length, N, equals the size of the interleaver.
  • Since both the encoders are systematic and operate on the same set of input bits, it is only necessary to transmit the input bits once. As a result, the overall code rate is 1/3.
  • In order to increase the overall code rate to ½, the two parity sequences v(1)v(2) can be punctured by alternately deleting v(1)v(2).
  • Notation: A (h0, h1, N) Turbo code means that

h0, h1 : parity-check polynomials of the two encoders.

N: length of the interleaver.

Example: A (1+X+X2, X, 16) Turbo code

Each constituent encoder is a (2,1,2) RSC encoder with parity-check polynomials h0(X)= 1+X+X2 and h1(X)=X.

Interleaver size N = 16 with permutation 16={15, 10, 1, 12, 2, 0, 13, 9, 5, 3, 8, 11, 7, 4, 14, 6} which implies u’0=u15, u’1=u10, and so on.

Structure of the RSC encoder:

If the input sequence is

u={u0, …, u15} = {1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0},

then the permutated input to the second encoder is:

u’={u’0, …, u’15} = {0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,0}.

The corresponding un-punctured parity sequences are

v(1)={v(1)0,…,v(1)15}={0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0}

v(2)={v(2)0,…,v(2)15}={0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1}

Without puncturing, the resultant codeword sequence is

u0, v(1)0, v(2)0, u1, v(1)1, v(2)1, …, u15, v(1)15, v(2)15

Code Rate = 1/3.

Hamming weight of the resultant codeword:

d=w(u)+w(v(1))+w(v(2)=4+3+3=10

If puncturing starts from v(1)0, the punctured codeword sequence becomes

u0, v(2)0, u1, v(1)1, u2, v(2)2, …, u15, v(1)15

Code Rate = ½

Hamming weight of the resultant codeword:

d= 4+3+2=9

If puncturing starts from v(2)0, the punctured codeword sequence becomes

u0, v(1)0, u1, v(2)1, u2, v(1)2, …, u15, v(2)15

Code Rate = ½

Hamming weight of the resultant codeword:

d= 4+0+1=5

9.2 Features of Turbo Codes

  • Finding the free distance of a Turbo code is complicated by the fact that Turbo encoders are time varying due to the interleaver.

If (where D is the delay operator, this means that the input sequence has one-bit delay),

={0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0} .

The first zero is due to the delay.

Output of the interleaver is

={1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0}.

The second parity sequence then becomes

v(2)={v(2)0,…,v(2)15}={0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0}.

Thus, time-shifting the input bits results in codewords that differ in both bit position and overall Hamming weight! The variation in the weights of codewords corresponding to time-shifted input sequences is magnified by puncturing.

  • As the pseudo-random interleaver permutes the input bits, the two input sequences u and u’ are almost always different, though of the same weight. The two encoders will (with high probability) produce parity sequences of different weights.
  • It is common that the first encoder is forced to return to the all-zero state. With a pseudo-random interleaver, it is highly unlikely that both encoders will be returned to the all-zero state at the end of the codeword even when the last v bits of the input sequence u are chosen to force the first encoder back to the all-zero state.

9.3 Iterative Decoding of Turbo Codes

  • The state-space of Turbo codes is too large to perform optimal decoding. To overcome this problem, the discoverers of Turbo codes proposed a novel iterative decoder based on the maximum a posteriori (MAP) decoding algorithm.
  • A MAP decoder computes the a posteriori probability P(ur=u|y) conditioned on the received sequence y.

After some calculations,

where the first term is the extrinsic information from the mth decoder. The second term is the a priori log-likelihood ratio of the systematic bit ur. The last term is the log-likelihood ratio of the a posteriori probabilities of the systematic bit.

Block diagram of an iterative Turbo decoder

  • Each MAP decoder corresponds to a constituent encoder. The interleavers are identical to the interleavers in the Turbo encoder and are used to reorder the sequences so that each decoder is properly synchronized.
  • Each iteration of the iterative decoding is executed in two phases. The a posteriori probabilities of one phase are used as the a priori information for the following phase.
  • The first MAP decoder passes the extrinsic information to the second one. The latter then feed back the information to the first decoder. This is somewhat resembles the principle behind the turbo engine. Therefore this class of codes is called Turbo Codes.
  • The iterative decoding process continues until a desired performance is achieved. For a (37, 21, 65536) Turbo code, the performance with iterative decoding continues to improve up to 18 iterations.

9.4 References

  • Trellis Coding, Christian Schlegel, IEEE Press, 1997, Chapter 8
  • Error-Control Coding for Data Networks, I.S. Reed and X Chen, Kluwer Academic Publishers, 1999, Chapter 12.3

1