Also known as: Andrew Viterbi
Andrew Viterbi (born 1935) is an American electrical engineer who devised the Viterbi algorithm for maximum-likelihood decoding of convolutional codes, and co-founded Qualcomm, the company that put CDMA into the world’s cellphones.1
Life and work
Andrew James Viterbi was born Andrea Viterbi in Bergamo, Italy, in 1935; his Jewish family fled Mussolini’s racial laws in 1939 and settled in Boston, where he became a naturalised American. He studied electrical engineering at MIT, taking bachelor’s and master’s degrees, worked on telemetry and phase-locked loops at the Jet Propulsion Laboratory during the early space age, and earned a PhD from the University of Southern California in 1962. He then joined the faculty at UCLA, where he taught digital communications and co-wrote an influential textbook on the subject. It was as a professor, working through the theory of coding for deep-space links, that he found the algorithm that bears his name.
Viterbi was also a builder of companies. With his colleague Irwin Jacobs he co-founded Linkabit in 1968 and then, in 1985, Qualcomm — firms that turned academic coding and spread-spectrum theory into the silicon that runs modern cellular networks.
Contribution
Viterbi introduced his algorithm in a 1967 paper as a way to decode convolutional codes. A convolutional encoder has memory, so its output can be pictured as a path through a trellis of possible encoder states over time. The decoder’s job is to find the path that best matches the noisy received sequence — the maximum-likelihood estimate — but the number of possible paths grows exponentially with message length, so brute force is hopeless. Viterbi’s insight was that at each stage only the single best surviving path into each state need be kept; all others can be discarded because they can never become part of the eventual best path. This dynamic-programming pruning makes the cost grow only linearly with message length, turning an intractable search into a practical, low-cost computation.2 It also accepts soft-decision inputs, using the demodulator’s confidence in each symbol rather than hard 0/1 bits, which buys a further couple of decibels of coding gain.
The same trellis method reaches beyond error correction: it is the standard tool for maximum-likelihood sequence estimation in equalisers, for hidden-Markov-model decoding in speech recognition and bioinformatics, and for demodulating signals with memory such as continuous-phase modulation.
Legacy
The Viterbi algorithm became one of the most widely deployed algorithms in engineering. It decodes the convolutional codes in GSM, in satellite and deep-space links, in Wi-Fi, in digital video broadcasting, and in countless two-way radio systems, letting receivers pull correct data out of signals buried near the noise. It sits alongside the broader coding theory of Viterbi’s mentor Robert Gallager and reaches back toward the limit Claude Shannon defined. For land-mobile radio the connection is direct: P25 and many digital-voice modes protect their traffic with convolutional or trellis-coded schemes, so a decoder such as GopherTrunk relies on Viterbi’s method — the same maximum-likelihood trellis search — to recover frames cleanly at low SNR. Viterbi’s fortune from Qualcomm later funded, among much else, the USC Viterbi School of Engineering, which bears his name.
Sources
-
Andrew Viterbi — Wikipedia, for biography and his algorithm for decoding convolutional codes. ↩
-
Andrew J. Viterbi — Engineering and Technology History Wiki (IEEE), for the Viterbi algorithm and the founding of Qualcomm. ↩