# BCJR algorithm

From BitcoinWiki

This is the approved revision of this page, as well as being the most recent.

The **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. This algorithm is critical to modern iteratively-decoded error-correcting codes including turbo codes and low-density parity-check codes.

## Contents

## Steps involved[edit]

Based on the trellis:

- Compute forward probabilities <math>\alpha</math>
- Compute backward probabilities <math>\beta</math>
- Compute smoothed probabilities based on other information (i.e. noise variance for AWGN, bit crossover probability for binary symmetric channel)

## Variations[edit]

### SBGT BCJR[edit]

Berrou, Glavieux and Thitimajshima simplification.

### Log-Map BCJR[edit]

### Max-Log-Map BCJR[edit]

## Implementations[edit]

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

## See Also on BitcoinWiki[edit]

## 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

## Source[edit]