From BCJR to turbo decoding: MAP algorithms made easier

• Type: Technical Report
• Date: 2004

Authors

Sílvio A. Abrantes (Author) FEUP

Scientific classification

CORDIS: Technological sciences > Engineering > Communication engineering

Other information

Resumo (PT): Em 1974 Bahl, Cocke, Jelinek e Raviv publicaram um algoritmo de descodificação de códigos baseado em probabilidades a posteriori. O algoritmo passou depois a ser conhecido como algoritmo BCJR (das iniciais dos autores), algoritmo MAP (de “maximum a posteriori”) ou ainda “forward-backward algorithm”. O procedimento pode ser aplicado a códigos de blocos ou a códigos convolucionais mas, como é bastante mais complexo que o algoritmo de Viterbi, durante cerca de vinte anos não foi usado na prática, situação que foi substancialmente alterada com o advento dos turbo-códigos em 1993. Nessa altura os seus inventores, Berrou, Glavieux e Thithimajshima, usaram uma versão modificada do algoritmo BCJR, que dessa forma renasceu com grande vigor. Existem diversas versões simplificativas do algoritmo MAP, nomeadamente as designadas como log-MAP e max-log-MAP. O propósito deste texto é mostrar, sem cálculos intermédios, como é que todos estes algoritmos funcionam e são aplicados na descodificação turbo. Os pormenores teóricos poderão ser consultados no Apêndice.

Abstract (EN): In 1974 Bahl, Cocke, Jelinek and Raviv published the decoding algorithm based on a posteriori probabilities later on known as the BCJR, Maximum a Posteriori (MAP) or forward-backward algorithm. The procedure can be applied to block or convolutional codes but, as it is more complex than the Viterbi algorithm, during about 20 years it was not used in practical implementations. The situation was dramatically changed with the advent of turbo codes in 1993. Their inventors, Berrou, Glavieux and Thithimajshima, used a modified version of the BCJR algorithm, which has reborn vigorously that way. There are several simplified versions of the MAP algorithm, namely the log-MAP and the max-log-MAP algorithms. The purpose of this tutorial text is to clearly show, without intermediate calculations, how all these algorithms work and are applied to turbo decoding. A complete worked out example is presented to illustrate the procedures. Theoretical details can be found in the Appendix.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 30