Fano algorithm (sequential decoding)

Also known as: Fano algorithm, Fano sequential decoding, sequential decoding

The Fano algorithm is a sequential decoding method for convolutional codes: it explores the code’s decision tree one path at a time, moving forward while a running score stays above a moving threshold and backing up to try alternatives when the score drops.¹ Introduced by Robert Fano in 1963, it was for years the practical way to decode the long-constraint-length codes used on deep-space and early data links, before the Viterbi algorithm became dominant for short codes.

Fano's decoder advances along one tree path while its Fano metric stays above a threshold, and backtracks to explore siblings when the metric drops.

How it works

A convolutional encoder can be viewed as walking a binary tree: each information bit chooses a branch, and each branch emits a block of coded bits. Decoding is the search for the tree path whose emitted bits best match the received sequence. The optimal search would examine the whole tree, but that is exponential in message length. Sequential decoding instead follows a single best-guess path, guided by the Fano metric — a per-branch score that rewards agreement with the received symbols and subtracts a bias so that longer paths are not automatically penalised against shorter ones. The bias makes the metric of the correct path tend to rise with depth while wrong paths tend to fall.

The Fano algorithm turns this into a low-memory procedure driven by a single running threshold T:

Move forward to the better branch while the accumulated metric stays at or above T. When it comfortably clears T, tighten T upward by a step Δ.
Back up when every branch ahead drops below T: retreat toward the root, trying not-yet-explored siblings.
If backing up also fails (the whole neighbourhood is below T), lower T by Δ and try again, admitting paths that were previously rejected.

Because it keeps only the current path and the threshold — not a full trellis — the Fano algorithm needs very little memory, which is precisely why it scaled to constraint lengths far beyond what a Viterbi decoder could afford in the 1960s–70s.

Variants

The stack (or ZJ) algorithm is the other classic sequential decoder: it keeps an ordered stack of partial paths and always extends the best one, avoiding repeated back-and-forth but demanding memory to hold the stack. Fano’s method trades that memory for occasional re-traversal of the same branches. Both share the same statistical behaviour, including the defining weakness below.

In practice

Sequential decoding’s effort is variable and data-dependent. On a clean channel the correct path clears every threshold and the decoder races to the end with almost no backtracking. As the signal-to-noise ratio falls toward the computational cutoff rate R₀, the number of tree nodes visited per decoded bit follows a heavy-tailed (Pareto) distribution: a single bad noise burst can trigger an avalanche of backtracking whose expected work is unbounded. Real systems therefore cap the computation and declare an erasure or request a retransmit when the budget is exhausted. This unpredictable, bursty workload — versus Viterbi’s fixed, constraint-length-bounded cost — is the central engineering trade-off between the two, and the main reason short-constraint-length codes migrated to Viterbi while sequential decoding survived where long codes and large coding gains mattered more than latency.

Relevance to SDR

Fano-style sequential decoding was the workhorse of early deep-space telemetry (the Pioneer missions used long convolutional codes decoded sequentially) and appeared in HF and satellite data modems where its large coding gain justified the variable latency. In modern trunked-radio and consumer wireless links, the short-constraint-length convolutional codes in P25, DMR, Wi-Fi and LTE are decoded with the fixed-cost Viterbi algorithm instead, so GopherTrunk does not run a Fano decoder in its own chain. The algorithm remains important as the conceptual bridge between brute-force tree search and the maximum-likelihood sequence estimation that Viterbi made tractable, and it is the historical answer to “how do you decode a code too long to trellis?”

Sources

Sequential decoding — Wikipedia, for the Fano algorithm, the Fano metric, the running threshold, the stack algorithm, and the computational-cutoff-rate behaviour. ↩