Turbo code

From Wikipedia, the free encyclopedia
Jump to: navigation, search





In 1993, turbo codes were introduced by Berrou, Glavieux, and Thitimajshima (from Télécom Bretagne, former ENST Bretagne, France) in their paper: "Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes" published in the Proceedings of IEEE International Communications Conference.[1] In a later paper, Berrou gave credit to the "intuition" of "G. Battail, J. Hagenauer and P. Hoeher, who, in the late 80s, highlighted the interest of probabilistic processing." He adds "R. Gallager and M. Tanner had already imagined coding and decoding techniques whose general principles are closely related," although the necessary calculations were impractical at that time.[2]

The first class of turbo code was the parallel concatenated convolutional code (PCCC). Since the introduction of the original parallel turbo codes in 1993, many other classes of turbo code have been discovered, including serial versions and repeat-accumulate codes. Iterative turbo decoding methods have also been applied to more conventional FEC systems, including Reed-Solomon corrected convolutional codes.

Turbo Codes were first patented in US Patent 5,446,747. This patent expired August 29, 2013.

An example encoder[edit]




Turbo encoder.svg


  ~R_1 &= \frac{n_1 + n_2}{2n_1 + n_2}\\
  ~R_2 &= \frac{n_1 + n_2}{n_1 + 2n_2}

The decoder[edit]

The decoder is built in a similar way to the above encoder. Two elementary decoders are interconnected to each other, but in serial way, not in parallel. The \scriptstyle DEC_1 decoder operates on lower speed (i.e., \scriptstyle R_1), thus, it is intended for the \scriptstyle C_1 encoder, and \scriptstyle DEC_2 is for \scriptstyle C_2 correspondingly. \scriptstyle DEC_1 yields a soft decision which causes \scriptstyle L_1 delay. The same delay is caused by the delay line in the encoder. The \scriptstyle DEC_2's operation causes \scriptstyle L_2 delay.

Turbo decoder.svg

An interleaver installed between the two decoders is used here to scatter error bursts coming from \scriptstyle DEC_1 output. DI block is a demultiplexing and insertion module. It works as a switch, redirecting input bits to \scriptstyle DEC_1 at one moment and to \scriptstyle DEC_2 at another. In OFF state, it feeds both \scriptstyle y_{1k} and \scriptstyle y_{2k} inputs with padding bits (zeros).


  ~x_k &=  (2d_k - 1) + a_k\\
  ~y_k &= 2( Y_k - 1) + b_k

where \scriptstyle a_k and \scriptstyle b_k are independent noise components having the same variance \scriptstyle \sigma^2. \scriptstyle Y_k is a k-th bit from \scriptstyle y_k encoder output.

Redundant information is demultiplexed and sent through DI to \scriptstyle DEC_1 (when \scriptstyle y_k \;=\; y_{1k}) and to \scriptstyle DEC_2 (when \scriptstyle y_k \;=\; y_{2k}).

\scriptstyle DEC_1 yields a soft decision; i.e.:

\Lambda(d_k) = \log\frac{p(d_k = 1)}{p(d_k = 0)}

and delivers it to \scriptstyle DEC_2. \scriptstyle \Lambda(d_k) is called the logarithm of the likelihood ratio (LLR). \scriptstyle p(d_k \;=\; i),\, i \,\in\, \{0,\, 1\} is the a posteriori probability (APP) of the \scriptstyle d_k data bit which shows the probability of interpreting a received \scriptstyle d_k bit as \scriptstyle i. Taking the LLR into account, \scriptstyle DEC_2 yields a hard decision; i.e., a decoded bit.

It is known that the Viterbi algorithm is unable to calculate APP, thus it cannot be used in \scriptstyle DEC_1. Instead of that, a modified BCJR algorithm is used. For \scriptstyle DEC_2, the Viterbi algorithm is an appropriate one.

However, the depicted structure is not an optimal one, because \scriptstyle DEC_1 uses only a proper fraction of the available redundant information. In order to improve the structure, a feedback loop is used (see the dotted line on the figure).

Soft decision approach[edit]


  • −127 means "certainly 0"
  • −100 means "very likely 0"
  • 0 means "it could be either 0 or 1"
  • 100 means "very likely 1"
  • 127 means "certainly 1"
  • etc.




Solving hypotheses to find bits[edit]





Practical applications using turbo codes[edit]


Bayesian formulation[edit]


See also[edit]


  1. ^ Berrou, Claude; Glavieux, Alain; Thitimajshima, Punya, Near Shannon Limit Error – Correcting, retrieved 11 February 2010 
  2. ^ Berrou, Claude, The ten-year-old turbo codes are entering into service, Bretagne, France, retrieved 11 February 2010 
  4. ^ McEliece, Robert J.; MacKay, David J. C.; Cheng, Jung-Fu (1998), "Turbo decoding as an instance of Pearl's “belief propagation” algorithm", IEEE Journal on Selected Areas in Communications 16 (2): 140–152, doi:10.1109/49.661103, ISSN 0733-8716. 

External links[edit]