http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=BCJR_algorithmBCJR algorithm - Revision history2026-10-26T02:58:38ZRevision history for this page on the wikiMediaWiki 1.43.1http://debianws.lexgopc.com/wiki143/index.php?title=BCJR_algorithm&diff=4047305&oldid=previmported>Fluxjupyter: Added full name and trellis link2024-06-21T21:11:48Z<p>Added full name and trellis link</p>
<p><b>New page</b></p><div>{{short description|Error correction algorithm}}<br />
The '''Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm''' is an [[algorithm]] for [[maximum a posteriori]] decoding of [[error correcting code]]s defined on [[Trellis_(graph)|trellises]] (principally [[convolutional code]]s). The algorithm is named after its inventors: Bahl, Cocke, [[Frederick Jelinek|Jelinek]] and Raviv.<ref name="bcjr">{{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 }}</ref> This algorithm is critical to modern iteratively-decoded error-correcting codes, including [[turbo codes]] and [[low-density parity-check codes]].<br />
<br />
==Steps involved==<br />
Based on the [[convolutional code|trellis]]:<br />
<br />
* Compute forward probabilities <math>\alpha</math><br />
* Compute backward probabilities <math>\beta</math><br />
* Compute smoothed probabilities based on other information (i.e. [[noise variance]] for [[AWGN]], [[bit crossover probability]] for [[binary symmetric channel]])<br />
<br />
==Variations==<br />
<br />
===SBGT BCJR===<br />
Berrou, Glavieux and Thitimajshima simplification.<ref name="sichun2006">{{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 }}</ref><br />
<br />
===Log-Map BCJR===<br />
{{Expand section|date=September 2022}}<br />
<ref>{{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 }}<br />
</ref><br />
<br />
==Implementations==<br />
* [http://libsusa.org/ Susa] framework implements BCJR algorithm for [[forward error correction]] codes and channel equalization in C++.<br />
<br />
==See also==<br />
* [[Forward-backward algorithm]]<br />
* [[Maximum a posteriori|Maximum a posteriori (MAP) estimation]]<br />
* [[Hidden Markov model]]<br />
<br />
==References==<br />
<references/><br />
<br />
==External links==<br />
* [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.<br />
* [https://github.com/behrooza/susa/blob/master/inc/susa/channel.h#L360 The implementation of BCJR algorithm in Susa signal processing framework]<br />
<br />
{{DEFAULTSORT:Bcjr Algorithm}}<br />
[[Category:Error detection and correction]]<br />
<br />
{{algorithm-stub}}</div>imported>Fluxjupyter