BCJR 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 $\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++.

gollark: It would be important to make it reasonably easy to add and update packages.

gollark: Well, it would be less useful if there wasn't a good central repo too.

gollark: "Search packages" is `pacman -Ss [whatever]`, "install" is `pacman -S [whatever]`, "update repos and update all packages" (it is apparently unsafe to update only individual packages) is `pacman -Syu`.

gollark: You pick a "subcommand" with a capital-letter flag like `-S` (sync, which seems to be a fancy word for "Install packages"), `-Q` (query information aboud stuff) and then pass extra flags to configure how that works.

gollark: > what's a pacman-like CLI?Arch Linux (btw I use that) has a neat package manager called `pacman`.> what counts as package updating support?Updating packages without breaking things horribly, including not overwriting user-edited (config) files.> and library interface as in an API you can use from scripts?Precisely.

References

L.Bahl, J.Cocke, F.Jelinek, and J.Raviv, "Optimal Decoding of Linear Codes for minimizing symbol error rate", IEEE Transactions on Information Theory, vol. IT-20(2), pp. 284-287, March 1974.
Sichun Wang and François Patenaude, "A Systematic Approach to Modified BCJR MAP Algorithms for Convolutional Codes," EURASIP Journal on Applied Signal Processing, vol. 2006, Article ID 95360, 15 pages, 2006. doi:10.1155/ASP/2006/95360
P. Robertson, P. Hoeher and E. Villebrun, "Optimal and Sub-Optimal Maximum A Posteriori Algorithms Suitable for Turbo Decoding", European Transactions on Telecommunications, Vol. 8, 1997.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[bcjr-1] L.Bahl, J.Cocke, F.Jelinek, and J.Raviv, "Optimal Decoding of Linear Codes for minimizing symbol error rate", IEEE Transactions on Information Theory, vol. IT-20(2), pp. 284-287, March 1974.

[2] Sichun Wang and François Patenaude, "A Systematic Approach to Modified BCJR MAP Algorithms for Convolutional Codes," EURASIP Journal on Applied Signal Processing, vol. 2006, Article ID 95360, 15 pages, 2006. doi:10.1155/ASP/2006/95360

[3] P. Robertson, P. Hoeher and E. Villebrun, "Optimal and Sub-Optimal Maximum A Posteriori Algorithms Suitable for Turbo Decoding", European Transactions on Telecommunications, Vol. 8, 1997.