THE VITERBI ALGORITHM the single most likely path through time
Given a sequence of noisy observations and a model of hidden states, which one path of states most likely produced them? Viterbi answers it with dynamic programming on a trellis: keep, for each state at each time, the best score of any path ending there, plus a back-pointer. It decodes your phone calls, your DNA, and your speech.
THE TECHNIQUE best-path score into every state, over time
At time 1, each state’s score is its start probability times its emission for the first observation. At each later step, a state’s score is the max over predecessors of (their score × transition) × this state’s emission — and you remember which predecessor won. At the end, take the best final state and follow the back-pointers. Below: a 2-state weather/health model. live demo
HISTORY & CREDIT the inventor thought it was impractical
“Viterbi built the optimal decoder and named it” — he did neither. His 1967 paper calls it “clearly suboptimal”; the name and the “trellis” came from someone else. cited
1964 · Howard Yudkin (MIT thesis) had already derived the error bound Viterbi’s method was invented to demonstrate. 1967 · Andrew Viterbi introduces the algorithm only to prove a bound on convolutional codes — he considered it impractical and suboptimal. 1968–69 · Jim Omura shows it is just forward dynamic programming (Bellman, 1950s) on a trellis; his 1969 paper already titles it “the Viterbi decoding algorithm.” 1967 → 1973 · G. David Forney recognises it as an optimum trellis decoder and coins the word “trellis” in a 1967 NASA Ames report (the same year as Viterbi, before Omura), then proves ML-optimality and fixes the name in his canonical 1973 Proc. IEEE tutorial “The Viterbi Algorithm.”
The visual that carries its fame — the trellis — came from the man who proved it optimal, not from Viterbi. Viterbi 1967 / Forney 1973
RECOMMEND FOR I-13 a 2-D table that runs flattened
The trellis is a states×time table of best-scores; the recurrence is max, multiply, remember — and it runs on the compiler:
$ i13 run viterbi.i13 # obs [normal,cold,dizzy]
v2_H = 0.00588 v2_F = 0.01512 best = 0.01512 -> path Healthy,Healthy,Fever
Recommend: the DP itself has no wall — the grounded run reproduces the textbook decode exactly (best 0.01512, path H,H,F). The natural home is a 2-D array (states × time) — PS-004, the want named by knapsack (053), Smith-Waterman (054), Hungarian (064), PageRank (068) — but it runs today flattened into a 1-D array with index arithmetic t*S + s, exactly as those darts do. Note: the back-pointer table wants a parallel integer array; recovering the path is a walk backward through it — all bounded-array work.