Viterbi Algorithm

The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources and hidden Markov models.

The terms "Viterbi path" and "Viterbi algorithm" are also applied to related dynamic programming algorithms that discover the single most likely explanation for an observation. For example, in statistical parsing a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is sometimes called the "Viterbi parse".

The Viterbi algorithm was proposed by Andrew Viterbi in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links. The algorithm has found universal application in decoding the convolutional codes used in both CDMA and GSM digital cellular, dial-up modems, satellite, deep-space communications, and 802.11 wireless LANs. It is now also commonly used in speech recognition, keyword spotting, computational linguistics, and bioinformatics. For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.

Read more about Viterbi AlgorithmAlgorithm, Pseudocode, Example, Extensions

Other articles related to "viterbi algorithm, algorithm, viterbi":

Soft Output Viterbi Algorithm
... The soft output Viterbi algorithm (SOVA) is a variant of the classical Viterbi algorithm ... SOVA differs from the classical Viterbi algorithm in that it uses a modified path metric which takes into account the a priori probabilities of the input symbols, and produces a soft ... output measure of reliability of the hard bit decision of the Viterbi algorithm ...
Viterbi Algorithm - Extensions
... A generalization of the Viterbi algorithm, termed the max-sum algorithm (or max-product algorithm) can be used to find the most likely assignment of ... The general algorithm involves message passing and is substantially similar to the belief propagation algorithm (which is the generalization of the forward-backward algorithm) ... With the algorithm called iterative Viterbi decoding one can find the subsequence of an observation that matches best (on average) to a given HMM ...
Andrew Viterbi - Further Career
... Viterbi was later a professor of electrical engineering at UCLA and UCSD ... In 1967 he invented the Viterbi algorithm, which he used for decoding convolutionally encoded data ... On advice of a lawyer, Viterbi did not patent the algorithm ...