BCJR algorithm explained

The Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm is an algorithm for maximum a posteriori decoding of error correcting codes defined on trellises (principally convolutional codes). The algorithm is named after its inventors: Bahl, Cocke, Jelinek and Raviv.^[1] This algorithm is critical to modern iteratively-decoded error-correcting codes, including turbo codes and low-density parity-check codes.

Steps involved

Based on the trellis:

• Compute forward probabilities

\alpha

• Compute backward probabilities

\beta

• Compute smoothed probabilities based on other information (i.e. noise variance for AWGN, bit crossover probability for binary symmetric channel)

Variations

SBGT BCJR

Berrou, Glavieux and Thitimajshima simplification.^[2]

Log-Map BCJR

^[3]

Implementations

• Susa framework implements BCJR algorithm for forward error correction codes and channel equalization in C++.

See also

• Forward-backward algorithm
• Maximum a posteriori (MAP) estimation
• Hidden Markov model

References

1. L. . Bahl . J. . Cocke . F. . Jelinek . J. . Raviv . Optimal Decoding of Linear Codes for minimizing symbol error rate . IEEE Transactions on Information Theory . 20 . 2 . 284–7 . March 1974 . 10.1109/TIT.1974.1055186 .
2. Sichun . Wang . François . Patenaude . A Systematic Approach to Modified BCJR MAP Algorithms for Convolutional Codes . EURASIP Journal on Applied Signal Processing . 2006 . 95360 . 2006. 10.1155/ASP/2006/95360 . 2006EJASP2006..242W . free .
3. P. . Robertson . P. . Hoeher . E. . Villebrun . Optimal and Sub-Optimal Maximum A Posteriori Algorithms Suitable for Turbo Decoding . European Transactions on Telecommunications . 8 . 2 . 119–125 . 1997 . 10.1002/ett.4460080202 . free .

External links

• The online textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses the BCJR algorithm in chapter 25.
• The implementation of BCJR algorithm in Susa signal processing framework