BCJR algorithm: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 21:11, 21 June 2024

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++.

References

^ 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.
^ 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.
^ 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

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

[bcjr-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.

[sichun2006-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.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
 {{short description|Error correction algorithm}}
-The '''BCJR algorithm''' is an [[algorithm]] for [[maximum a posteriori]] decoding of [[error correcting code]]s defined on 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 code]]s and [[low-density parity-check code]]s.
+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]].
 ==Steps involved==
@@ Line 12: / Line 12: @@
 ===SBGT BCJR===
-Berrou, Glavieux and Thitimajshima simplification.<ref>{{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>
+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>
 ===Log-Map BCJR===