Recognised by John Wozencraft, sequential decoding is a limited memory technique for decoding tree codes.
This approach may not be as accurate as the Viterbi algorithm but can save a substantial amount of computer memory.
It was used to decode a convolutional code in 1968 Pioneer 9 mission.
Sequential decoding explores the tree code in such a way to try to minimise the computational cost and memory requirements to store the tree.
There is a range of sequential decoding approaches based on the choice of metric and algorithm.
This metric is optimal given no other constraints (e.g. memory).
For a binary symmetric channel (with error probability
) the Fano metric can be derived via Bayes theorem.
Using the language of probability and Bayes theorem we want to choose the maximum over
of: We now introduce the following notation: We express the likelihood
(by using the binary symmetric channel likelihood for the first
in terms of the number of branch choices one has made,
The important point to see is that we have two terms here: one based on the number of wrong bits and one based on the number of right bits.
We can therefore update the Fano metric simply by adding
For sequential decoding to be a good choice of decoding algorithm, the number of states explored should remain small (otherwise an algorithm which deliberately explores all states, e.g. the Viterbi algorithm, may be more suitable).
For a particular noise level there is a maximum coding rate
called the computational cutoff rate where there is a finite backtracking limit.
The famous Fano algorithm (named after Robert Fano) has a very low memory requirement and hence is suited to hardware implementations.
This algorithm explores backwards and forward from a single point on the tree.