BCJR algorithm

Error correction algorithm

The 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 α {\displaystyle \alpha }
  • Compute backward probabilities β {\displaystyle \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. ^ Bahl, L.; Cocke, J.; Jelinek, F.; Raviv, J. (March 1974). "Optimal Decoding of Linear Codes for minimizing symbol error rate". IEEE Transactions on Information Theory. 20 (2): 284–7. doi:10.1109/TIT.1974.1055186.
  2. ^ Wang, Sichun; Patenaude, François (2006). "A Systematic Approach to Modified BCJR MAP Algorithms for Convolutional Codes". EURASIP Journal on Applied Signal Processing. 2006: 95360. Bibcode:2006EJASP2006..242W. doi:10.1155/ASP/2006/95360.
  3. ^ Robertson, P.; Hoeher, P.; Villebrun, E. (1997). "Optimal and Sub-Optimal Maximum A Posteriori Algorithms Suitable for Turbo Decoding". European Transactions on Telecommunications. 8 (2): 119–125. doi:10.1002/ett.4460080202.

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
  • v
  • t
  • e