Field Guide · algorithm

Also known as: Viterbi algorithm, Viterbi, Viterbi decoder

The Viterbi algorithm efficiently finds the most likely sequence of states through a trellis, given a stream of noisy observations.1 It is the standard maximum-likelihood way to decode convolutional codes, and it is named for Andrew Viterbi, who published it in 1967. The same dynamic-programming idea also underlies maximum-likelihood sequence estimation for channels with memory and appears far outside radio, from speech recognition to bioinformatics.

most-likely path through the trellis
The Viterbi algorithm finds the most-likely sequence through a trellis, decoding convolutional codes.

How it works

The code’s memory defines a set of trellis states (2^(K−1) of them for constraint length K), and each received symbol advances the trellis one step. At every step the decoder computes a branch metric — how well each possible transition matches the received symbol — and runs an add–compare–select (ACS) operation for each destination state: it adds each incoming branch metric to the running path metric, compares the competing paths, and selects the single best one, discarding the rest. Because only one survivor path is kept per state, the search cost stays linear in the message length instead of exploding exponentially, yet the surviving global path is provably the maximum-likelihood sequence.

Once enough steps have accumulated, a traceback walks the stored survivor decisions backward from the best final state to reconstruct the decoded bits. Practical decoders trace back over a fixed window of roughly five times the constraint length rather than waiting for the whole message, which bounds latency and memory with negligible loss.

Variants

  • Hard-decision decoding feeds the ACS unit sliced bits and uses Hamming distance as the metric — simple, but it throws away confidence information.
  • Soft-decision decoding feeds it the demodulator’s real-valued (or quantised) samples and uses a Euclidean-style metric, buying roughly 2 dB of coding gain for the same code. This is why radios keep soft symbols as far into the pipeline as they can.
  • Contrast with the BCJR algorithm: Viterbi minimises the sequence error probability and emits hard bit decisions, whereas BCJR is a MAP decoder that computes the a-posteriori probability of each individual bit — the soft output that iterative turbo and LDPC decoders need. Viterbi is cheaper; BCJR gives the soft information.

In practice

The regular, replicated ACS structure maps cleanly onto hardware, so Viterbi decoders are routinely built as dedicated blocks in FPGAs and baseband ASICs; software radios implement the same recursion, often with SIMD to parallelise the butterfly of ACS updates.

Relevance to SDR

Viterbi decoding appears wherever convolutional codes do: GSM, IS-95/CDMA, satellite and deep-space links, 802.11a/g, and, in the scanner world, systems such as M17 and various trunked-radio signalling paths. GopherTrunk applies Viterbi decoding on convolutionally coded fields to drive down the error rate before framing.

Sources

  1. Viterbi algorithm — Wikipedia, for the maximum-likelihood trellis decoder and its origin. See also Viterbi decoder for add-compare-select and traceback hardware. ↩

See also

Learn it step by step

From the blog