Andrew Viterbi

Life and career

Andrew Viterbi has said, in various tellings, that the algorithm bearing his name was invented as a teaching device. He was preparing lectures on convolutional codes and found the existing treatment of sequential decoding too complicated to explain to students, so he constructed a simpler, obviously-correct alternative to present in class. That simpler alternative turned out to be optimal, and it now runs, in one form or another, in every mobile phone on the planet. It is one of the more agreeable origin stories in engineering: the pedagogical simplification that ate the field.

He was born Andrea Viterbi in Bergamo, Italy, in 1935. His family, Italian Jews, fled the Fascist racial laws in 1939 and settled in Boston, where he grew up and became Andrew. He went to MIT on a scholarship, taking bachelor's and master's degrees in electrical engineering in 1957, then joined the Jet Propulsion Laboratory in Pasadena, where he worked on telemetry and phase-locked loops for the earliest American space probes — real deep-space communication problems, where the signal is faint, the power budget is fixed, and every decibel of coding gain is worth millions of dollars in transmitter mass.

He took his PhD at the University of Southern California in 1962 and joined the faculty at UCLA, where he taught through the 1960s and early 1970s and where the 1967 paper was written. Alongside academic work he co-founded, with Irwin Jacobs and others, the consulting firm Linkabit in 1968, an unusual hybrid of research shop and defense contractor that became a training ground for a generation of San Diego communications engineers.

In 1985 Viterbi and Jacobs founded Qualcomm. The company's central bet was CDMA — code-division multiple access, in which many users share a frequency band simultaneously by using orthogonal spreading codes rather than being separated into time slots or channels. This was contrarian; the prevailing standards used TDMA, and established players argued CDMA could not work at scale. It won, becoming the basis of the 3G standards and, with its descendants, the foundation of modern cellular networks. Viterbi served as vice chairman and chief technical officer.

He has been an unusually generous benefactor: USC's engineering school is the Viterbi School of Engineering, and he has endowed positions and programs at several institutions including in Israel and Italy. His honors include the IEEE Alexander Graham Bell Medal, the Marconi Prize, the National Medal of Science (2007), and the IEEE Medal of Honor (2010). He has also been consistent about crediting others — he has repeatedly noted that David Forney established the optimality of the algorithm and that Jim Omura connected it to dynamic programming, and that the name attached to him partly by accident of who wrote which survey.

Key contributions

**The Viterbi algorithm (1967).** The setting is a finite-state Markov process observed through noise. In the original application, a convolutional encoder's state is the contents of its shift register; the encoder emits parity symbols determined by the state and the incoming bit; the channel corrupts them. The receiver's job is to recover the most likely transmitted sequence.

The naive approach is hopeless: with *L* input bits there are 2^*L* candidate sequences. Viterbi's observation is that the state sequence forms a **trellis** — states arrayed vertically, time horizontally, with edges for permitted transitions — and that the best path arriving at a given state at time *t* can be computed from the best paths arriving at each predecessor state at time *t*−1, because any optimal path through a state must have an optimal prefix reaching that state. This is Bellman's principle of optimality, and it collapses the exponential search to *O*(*L* · *S*²) for *S* states: at each node you compare a handful of incoming path metrics and keep only the survivor.

Two things make the result more than a clever trick. First, it is **exact**. Unlike beam search or sequential decoding, it does not approximate; Forney's later analysis showed it performs true maximum-likelihood sequence estimation. Second, the computation and memory per step are constant in the message length, so the decoder can run in real time in hardware. The combination — optimality plus streaming implementability — is why it took over.

For a machine learning audience the reach is what matters. Any hidden Markov model decoding problem is the same computation. Part-of-speech tagging with an HMM, gene finding in DNA sequences, phoneme decoding in speech recognizers, the Viterbi step in a conditional random field, the max-product algorithm on a chain in graphical model terms — all of these are the same recursion with different emission models. The forward algorithm sums where Viterbi maximizes; they are the same dynamic program in different semirings. If you have written a max-product message passing routine, you have written Viterbi.

**Convolutional codes and coding practice.** Viterbi's work on the performance analysis of convolutional codes — error bounds, the relationship between constraint length and coding gain — made the design of practical coded systems a quantitative engineering discipline. Deep space missions adopted convolutional codes with Viterbi decoding as standard, and the concatenation of a convolutional inner code with a Reed–Solomon outer code became the workhorse of satellite communication for decades.

**CDMA and spread spectrum.** The Qualcomm work is a different kind of contribution: taking spread-spectrum techniques with military origins and showing they could support commercial cellular telephony at higher capacity than the alternatives, then executing the standards and silicon to prove it. His book *CDMA: Principles of Spread Spectrum Communication* (1995) is the standard technical treatment.

In battle

Viterbi carries a mean of 30.1 with six dominant scores and, like Jelinek, one perfect 100 — and it is the same kind of 100, a problem that is not analogous to his work but *is* his work.

**Decode the hidden path** (P038) at 100 is the 1967 paper. The problem asks for exact recovery of a hidden state sequence from noisy observations, in time linear in sequence length, and every element of the setting — the noisy channel, the Markov state structure, the demand for exactness with efficiency — is what he built the method for. He then pushed it into real receivers at Qualcomm, which the problem also describes.

His dominant band is the reach of that single algorithm across domains. **Label every word** (P085) at 91 is HMM part-of-speech tagging: same trellis, different emissions. **Words from waveforms** (P073) at 88 and **A thousand words, connected speech** (P236) at 88 are speech recognition, where Viterbi decoding is the runtime inference step in every classical recognizer. **The parallel text is the teacher** (P256) at 88 is statistical MT, where decoding the alignment is again a dynamic program over hidden structure. **The scratch on the disc** (P169) at 82 is error correction on physical media — his home territory. **The noisy channel's limit** (P035) at 78 and **Correct the corrupted block** (P036) at 78 are Shannon capacity and block coding, where he is a leading practitioner rather than the originator, which is why those sit below his peak.

His `information` mean of 50.1 across sixteen problems and `perception` mean of 35.1 across fifteen tell the story: he is an information theorist whose algorithm turned out to be the inference engine for sequential perception. The `search` mean of 58.0 is high but rests on only two problems, and reflects dynamic programming rather than heuristic search.

The losses map a boundary that is worth naming precisely, because it is not "he's an engineer, so he loses at statistics." He scores 10 on **The eigenvalues are lying** (P282, random matrix effects in covariance estimation), 9 on **Small tools, loosely joined** (P246, the Unix philosophy), 8 on **Even approximating is hard** (P160, hardness of approximation), 8 on **Choose the first hundred believers** (P270, submodular influence maximization), 8 on **Unroll the swiss roll** (P284, manifold learning), and 6 on **The p-value reckoning** (P125), his floor. His `high-dim` mean is 9.0, `systems` 10.5, `experimental-design` 11.0.

The pattern: Viterbi's toolkit is exact inference over a *chain* with a small state space. It has nothing to say about high-dimensional geometry, nonlinear manifolds, computational complexity theory, software architecture, or the sociology and methodology of statistical inference. Even inside his own strength there is a hard edge that the game respects — the trellis is efficient only when the state space is small. Once the number of hidden states grows large, or the dependency structure is a general graph rather than a chain, the exact algorithm becomes intractable and approximate methods take over. On problems that turn on that explosion, he is beaten by people whose methods scale where his cannot.

Play Viterbi on anything sequential with hidden state: decoding, tagging, alignment, speech, error correction. Do not play him on anything that requires reasoning about a dataset rather than a signal.