BCJR algorithm

From Quire, the open reference·Error correction algorithm·2 min read

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.^[1]

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.^[2]

Algorithm#edit

The algorithm combines a forward pass and a backward pass through the trellis. Let ${\displaystyle S_{k$ denote the encoder state at time ${\displaystyle k}$ , and ${\displaystyle y_{1}^{N}=(y_{1},\ldots ,y_{N})}$ the received sequence. Its metrics are

${\displaystyle {\begin{aligned}\alpha _{k}(s)&=P(S_{k}=s,y_{1}^{k}),\\\beta _{k}(s)&=P(y_{k+1}^{N}\mid S_{k}=s),\\\gamma _{k}(s',s)&=P(S_{k}=s,y_{k&#12$

For continuous observations, the corresponding probability densities are used. The branch metric ${\displaystyle \gamma _{k$ incorporates the channel observation and the prior probability of the transition.

The forward and backward recursions are

${\displaystyle \alpha _{k}(s)=\sum _{s'}\alpha _{k-1}(s')\gamma _{k}(s',s),}$

${\displaystyle \beta _{k-1}(s')=\sum _{s}\gamma _{k}(s',s)\beta _{k}(s).}$

Initialisation reflects the available information about the encoder's initial and final states. The posterior probability of a transition is proportional to

${\displaystyle P(S_{k-1}=s',S_{k}=s\mid y_{1}^{N})\propto \alpha _{k-1}(s')\gamma _{k}(s',s)\beta _{k}(s).}$

Summing over transitions associated with a particular input symbol and normalising gives that symbol's posterior probability.^[3]

Steps involved#edit

Based on the trellis:

Compute forward probabilities ${\displaystyle \alpha }$
Compute backward probabilities ${\displaystyle \beta }$
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.^[3]

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.^[2]

The distinction is expressed by the identity

${\displaystyle \ln(e^{x}+e^{y})=\max(x,y)+\ln(1+e^{-|x-y|}).}$

Log-MAP retains the correction term ${\displaystyle \ln(1+e^{-|x-y|})}$ , whereas Max-Log-MAP omits it.^[4]

Windowed BCJR#edit

A modified version that processes the trellis in segments to reduce computational complexity and memory requirements. This approach is particularly useful for very long sequences where full trellis storage becomes impractical. The windowed version maintains near-optimal performance while significantly lowering latency and hardware resource utilization in implementations.^[5]

Implementations#edit

Susa framework implements BCJR algorithm for forward error correction codes and channel equalization in C++.

References#edit

^ 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.
^ a b Robertson, Patrick; Hoeher, Peter; Villebrun, Emmanuelle (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.
^ a b Wang, Sichun; Patenaude, François (2006). "A Systematic Approach to Modified BCJR MAP Algorithms for Convolutional Codes". EURASIP Journal on Applied Signal Processing. 2006: 1–15. doi:10.1155/ASP/2006/95360.
^ 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.
^ Viterbi, A.J. (1998). "An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes". IEEE Journal on Selected Areas in Communications. 16 (2): 260–264. Bibcode:1998IJSAC..16..260V. doi:10.1109/49.661114. ISSN 0733-8716.

External links#edit

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

Categories Error detection and correction Algorithms and data structures stubs

This article is mirrored from “BCJR algorithm” on English Wikipedia, revision 1379857475, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1379857475 · just now