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 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 ${\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

SBGT BCJR

Berrou, Glavieux and Thitimajshima simplification.^[2]

Log-Map BCJR

^[3]

Windowed BCJR

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

Implementations

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

See also

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