Viterbi algorithm: a standalone construct

Andrew J. Viterbi introduced the algorithm in 1967 as a decoding method for convolutional codes, a family of error-correcting codes used to send data reliably over a noisy channel (Viterbi, 1967). G. David Forney's 1973 review named it the Viterbi algorithm and recast it in general terms as an efficient solution to a broad class of estimation problems (Forney, 1973). The algorithm finds the single most likely sequence of hidden states that could have produced an observed sequence, where hidden means the states are never seen directly but only inferred from noisy outputs. It works by dynamic programming: it steps through the observations one at a time, keeps only the best-scoring path leading into each possible state, and discards the rest, so the work grows with the length of the sequence rather than exploding across every possible combination of states. This shared machinery is why the same procedure decodes convolutional codes in digital communication, aligns acoustic frames to words in speech recognition, and recovers state paths in hidden Markov models across bioinformatics and natural language processing.[1][2]

Unit

A decoding and estimation algorithm that returns one optimal state sequence for a given observation sequence

Recovery means

Not applicable

Measured by

Identified by its recursion: a best-path score is maintained for each state and updated across the sequence, then backtracking recovers the maximum-likelihood path