GeezerVison

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]

The algorithm combines a forward pass and a backward pass through the trellis. Let $S_k$ denote the encoder state at time $k$, and $y_1^N=(y_1,\dots ,y_N)$ the received sequence. Its metrics are

$\begin{array}{cc}{\alpha }_k\left(s\right)& =P(S_k=s,y_1^k),\\ {\beta }_k\left(s\right)& =P(y_{k+1}^N\mid S_k=s),\\ {\gamma }_k(s^{\prime },s)& =P(S_k=s,y_k\mid S_{k-1}=s^{\prime }).\end{array}$

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

The forward and backward recursions are

${\alpha }_k\left(s\right)=\sum _{s^{\prime }}{\alpha }_{k-1}\left(s^{\prime }\right){\gamma }_k(s^{\prime },s),$

${\beta }_{k-1}\left(s^{\prime }\right)=\sum _s{\gamma }_k(s^{\prime },s){\beta }_k\left(s\right).$

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

$P(S_{k-1}=s^{\prime },S_k=s\mid y_1^N)\propto {\alpha }_{k-1}\left(s^{\prime }\right){\gamma }_k(s^{\prime },s){\beta }_k\left(s\right).$

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

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)

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]

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

• Forward–backward algorithm
• Maximum a posteriori (MAP) estimation
• Hidden Markov model

• 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 adding missing information.

• v
• t
• e