BCJR algorithm

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.{{cite journal |first1=L. |last1=Bahl |first2=J. |last2=Cocke |first3=F. |last3=Jelinek |first4=J. |last4=Raviv |title=Optimal Decoding of Linear Codes for minimizing symbol error rate |journal=IEEE Transactions on Information Theory |volume=20 |issue=2 |pages=284–7 |date=March 1974 |doi=10.1109/TIT.1974.1055186 }} 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.{{cite journal |first1=Sichun |last1=Wang |first2=François |last2=Patenaude |title=A Systematic Approach to Modified BCJR MAP Algorithms for Convolutional Codes |journal=EURASIP Journal on Applied Signal Processing |volume=2006 |issue= |pages=95360 |date= 2006|doi=10.1155/ASP/2006/95360 |bibcode=2006EJASP2006..242W |doi-access=free }}

=Log-Map BCJR=

{{cite journal |first1=P. |last1=Robertson |first2=P. |last2=Hoeher |first3=E. |last3=Villebrun |title=Optimal and Sub-Optimal Maximum A Posteriori Algorithms Suitable for Turbo Decoding |journal=European Transactions on Telecommunications |volume=8 |issue=2 |pages=119–125 |date=1997 |doi=10.1002/ett.4460080202 |doi-access=free }}

Implementations

[http://libsusa.org/ Susa] framework implements BCJR algorithm for forward error correction codes and channel equalization in C++.

References

External links

[http://www.inference.phy.cam.ac.uk/mackay/itila/ The online textbook: Information Theory, Inference, and Learning Algorithms], by David J.C. MacKay, discusses the BCJR algorithm in chapter 25.
[https://github.com/behrooza/susa/blob/master/inc/susa/channel.h#L360 The implementation of BCJR algorithm in Susa signal processing framework]

Category:Error detection and correction