Field Guide · algorithm

Also known as: BCJR algorithm, MAP decoder, forward-backward algorithm, Bahl-Cocke-Jelinek-Raviv

The BCJR algorithm is a soft-output trellis decoder that computes, for every information bit, the maximum a posteriori (MAP) probability that the bit was 0 or 1 given the entire received sequence.1 It does this with a forward–backward sweep over the code’s trellis and reports each decision as a log-likelihood ratio (LLR) — a signed confidence value rather than a hard 0/1.2 That soft output is exactly what makes iterative decoders like turbo codes work, and it is the main way BCJR differs from the Viterbi algorithm, which finds one most-likely sequence.

forward α backward β LLR(bit) = log P(bit=1) − log P(bit=0), from α · γ · β at each stage
BCJR combines a forward pass (α), a backward pass (β), and branch metrics (γ) to give a soft reliability for every bit, not just one winning path.

How it works

BCJR treats the encoder as a Markov process moving through trellis states and asks, for each information bit, how probable each value is after weighing all paths consistent with the received signal — not just the single best one. It computes three quantities:

  • γ (gamma) — a branch metric for each trellis transition, from the channel likelihood of the received symbol plus any prior information about the bit.
  • α (alpha) — a forward recursion accumulating the probability of reaching each state from the start of the block.
  • β (beta) — a backward recursion accumulating the probability of reaching the end from each state.

Multiplying α, γ, and β for the transitions that carry a given bit value, and summing over states, gives the total probability of that value. The LLR is the log of the ratio between the two totals. In practice the recursions are done in the log domain (log-MAP, or the lower-complexity max-log-MAP approximation) to replace multiplications with additions and avoid underflow.

The crucial output is not the hard bit but the magnitude and sign of the LLR: sign is the decision, magnitude is the confidence.

BCJR vs Viterbi

Both run on the same trellis, but they optimise different things. Viterbi is a maximum-likelihood sequence decoder — it returns the single most probable path and, in its classic form, a hard bit stream. BCJR is a bit-wise MAP decoder — it minimises the per-bit error probability and emits soft reliabilities. Viterbi is cheaper (one forward pass, survivor selection); BCJR costs a forward and a backward pass plus more arithmetic. You pay that cost when you need soft output to feed another decoder, which is precisely the turbo setting. (A soft-output Viterbi variant, SOVA, is a cheaper approximation that also yields LLRs.)

Relevance to SDR

BCJR is the component decoder inside turbo codes, which carry the data channels of 3G/4G cellular and many deep-space links; iterating two BCJR decoders that exchange extrinsic LLRs is what gets those systems close to the Shannon limit. It is a forward error correction algorithm for the convolutional-code family and a cousin of the belief-propagation decoding used for LDPC codes. The land-mobile and aviation formats GopherTrunk targets use block and plain convolutional codes rather than turbo codes, so GT does not run a BCJR decoder; it belongs to the broader cellular/space FEC world and is included here for context alongside Viterbi.

Sources

  1. BCJR algorithm — Wikipedia, for the MAP forward–backward soft-output decoder. ↩

  2. Optimal decoding of linear codes for minimizing symbol error rate — Bahl, Cocke, Jelinek, Raviv, IEEE Trans. Information Theory (1974), the original MAP algorithm. ↩

See also