Content deleted Content added
No edit summary |
No edit summary |
||
Line 6:
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 stochastic [[parser|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".
== Overview ==
As a simplifed description, we need to understand the assumptions listed above. First, we need to understand that the Viterbi algorithm operates on a state machine assumption. That is there are a finite number of states, however large, that can be listed. At each state, or if you prefer node, only one sequence or path can lead to it. This is a fundemental assumption of the algorithm because the algorithm will examine all possible paths leading to a state and only keep the one most likely. This way the algortihm does not have to keep track of multiple paths, only one per state. A second key assumption is that a transition from a previous state to a new state is marked by a incremental metric, usually a number. This transition is the event. The third key assumption is that the events are cumulative over a path in some sense, usually additive. So the crux of the algorithm is to keep a number for each state. Then when an event happens, the algorithm examines moving forward to a new set of states by combining the metric of a previous state with the incremental metric of the event. So at each possible new state, the algorithm combines a possible old state with the new incremental metric and chooses the best. All other path backwards are discarded and only the best survives. This is the crux of the algorithm. There are modifications to the basic algorithm which allow for a forward search in addition to the backwards one presented here.
Path history must be stored. In some cases, the search history is finite because the state machine at the encoder starts in a known state and there is sufficient memory to keep all the paths. In some other cases, one example is convolutional encoding, the decoder must truncate the history at a depth large enough to keep performance to an acceptable level. Although, the Viterbi algorithm is very efficient, there are modifications that reduce the computational load; the memory requirements tend to remain constant.
==A concrete example==
| |||