BCJR algorithm

The BCJR algorithm is a method for maximum a posteriori decoding of error correcting codes that are defined on trellises, principally convolutional codes, though it also applies to linear block codes. It was introduced in 1974 by Lalit R. Bahl, John Cocke, Frederick Jelinek and Josef Raviv, and the name is formed from their surnames. Instead of picking the single most likely path through the trellis, it makes a forward pass and a backward pass over it and combines the two, so that each transmitted symbol receives a posterior probability. Decoders built on it therefore provide soft outputs that express the relative probabilities of the possible symbol values, which is why they serve as component decoders in iterative turbo decoding. Several variants exist. Log-MAP performs the same calculations in the logarithmic domain, replacing multiplications of small probabilities with additions and avoiding numerical difficulties, and it is exactly equivalent to the probability-domain version. Max-Log-MAP approximates further by keeping only the largest exponent in a sum, which is cheaper but can reduce decoding accuracy. A windowed form processes the trellis in segments to cut memory use and latency on very long sequences, and a simplified Berrou-Glavieux-Thitimajshima form removes redundant divisions from the recursions. The method is closely related to the forward-backward algorithm.