The encyclopedia · Engineering & Operations · Technical decision · 1967
Viterbi's algorithm made every mobile phone decode its own signal
In 1967 Viterbi found the most likely path through a trellis, the decoder hidden in almost every cellphone.
Qualcomm · UCLA
the move
Digital communication over a wireless link is a battle against noise, which can corrupt the bits an antenna receives. The obvious fix is to add error-correcting code, but decoding it requires a way to work out, from a noisy received stream, which message was actually sent.
Viterbi's 1967 algorithm did exactly that. A convolutional encoder constrains the transmitter to move through a finite set of states, and the receiver keeps a trellis of those states; at each step it keeps only the cheapest path into each state, so by the end it has found the single most likely message rather than choosing each bit independently.
By making practical, short constraint-length codes workable, the algorithm made forward error correction cheap enough to deploy in real radios. It turned a vague 'what was the message?' into a clean dynamic-programming search, and it is now used to separate voice and data from background noise.
why it works
- Keeping only the single cheapest path into each state makes the search take time linear in the message length.
- It recovers the maximum-likelihood sequence from noisy data without per-bit guesswork.
- Convolutional codes gain real error-correction power only when decoded this way.
what transfers
When a signal is too noisy to read directly, reconstruct the single most likely sequence it could have come from; the structure you added makes that search nearly effortless.
what came after
The Viterbi algorithm is used in the vast majority of mobile phones worldwide and in satellite receivers, magnetic recording, speech recognition and DNA analysis; Viterbi went on to co-found Qualcomm in 1985, and the algorithm helped make CDMA and digital cellular telephony workable.
references
spotted an error? The archive wants to know.