BCJR算法

BCJR算法的名稱是由4個發明人名字的首字母命名的。4個發明人分別是Bahl,Cocke Jelinek和Raviv。這是數字通信的最廣泛的兩個算法之一（另一個是維特比算法）。

這個算法在1974年提出後，直到20年後才得以廣泛套用。當時的4位發明人均是IBM的員工，在IBM研究實驗室工作。IBM將它列為IBM對人類最大的貢獻之一。並把貼在加洲阿莫頓實驗室（Amanden Research Labs）。

基本介紹

• 中文名：BCJR算法
• 外文名：BCJRAlgorithm
• 分類：計算機算法
• 用途：用於卷積編碼
• 提出時間：1974年
• 提出人：Bahl、Cocke、Jelinek 和 Raviv

算法定義

BCJR算法是一種定義在格線圖上的用來最大化糾錯編碼的後驗機率的算法，主要用於卷積編碼。這種算法以它的發明者的名字命名，分別是Bahl, Cocke,Jelinek 和 Raviv。這個算法對於疊代的糾錯編碼來說是非常重要的，其中包括Turbo碼和低密度部分檢錯編碼。

算法步驟

基於格型結構：

計算前向機率

計算後向機率

基於其他信息（例如高斯白噪聲的方差，二進制對稱信道的位交叉機率）計算出平滑的機率。

衍生算法

SBGT BCJR：

Berrou, Glavieux and Thitimajshima Simplification.

Log-Map BCJR：

Max-Log-Map BCJR

相關算法

前向後向算法，最大後驗機率估計，隱馬爾科夫模型

參考文獻

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

擴展閱讀

The on-line textbook:資訊理論，推理和學習算法 Information Theory, Inference, and Learning Algorithms, byDavid J.C. MacKay, discusses the BCJR algorithm in chapter 25.