Viterbi algorithm: Difference between revisions

Revision as of 03:36, 29 November 2005

Revision as of 15:51, 29 November 2005

Line 9:

== Overview ==

As a simplified 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, multiple sequences or paths can lead to it – but there will only be one that will be the most likely, called the "survivor path" to that state. This is a fundamental 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 algorithm 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 aan incremental metric, usually a number. This transition is computed from 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 possible previous state with the incremental metric of the transition due to the event and chooses the best. It should be noted here that the incremental metric associated with an event is dependant upon the transition possibility from the old state to the new state. For example in data communications, it may be possible to only transmit half the symbols from an odd numbered state and the other half from an even numbered state. Additionally, in many cases the state transition table is not fully connected. A simple example would be a car that has 3 states, forward, stop and reverse. A transition from forward to reverse is not allowed. It must first enter the stop state. After computing the combinations of incremental metric and state metric, only the best survives and all other paths are discarded.. 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 described 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.