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 was introduced in 1974 by Lalit R. Bahl, John Cocke, Frederick Jelinek and Josef Raviv, whose surnames give it its name. It applies to both linear block codes and convolutional codes.

BCJR-based decoders provide soft outputs, which express the relative probabilities of possible symbol values. They are used as component decoders in iterative turbo decoding.

k, and γk incorporates the channel observation and the prior probability of the transition.

The forward and backward recursions are

β

Compute smoothed probabilities based on other information (i.e. noise variance for AWGN, bit crossover probability for binary symmetric channel)

Variations

edit

SBGT

edit

The simplified Berrou-Glavieux-Thitimajshima (SBGT) algorithm retains the structure of the BGT formulation while removing redundant divisions from its forward and backward recursions.

Log-MAP and Max-Log-MAP

edit

The Log-MAP algorithm performs the BCJR calculations in the logarithmic domain. This replaces probability multiplications with additions and reduces numerical difficulties associated with very small probabilities. When evaluated exactly, Log-MAP is equivalent to the probability-domain MAP algorithm. Max-Log-MAP simplifies the calculations further by approximating a logarithm of a sum of exponentials with the largest exponent; this approximation can reduce decoding accuracy.

The distinction is expressed by the identity

1. ↑ Bahl, L. R.; 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–287. doi:10.1109/TIT.1974.1055186.
2. 1 2 Robertson, P.; Villebrun, E.; Hoeher, P. (1995). "A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain" (PDF). Proceedings of the IEEE International Conference on Communications. pp. 1009–1013.
3. ↑