Branch : Computer Science and Engineering
Subject : Wireless Communication
Unit : Cellular System Design
The Viterbi Algorithm
Introduction:
There are a number of techniques for decoding convolutional codes. Themost important of these methods is the Viterbi algorithm which performs maximumlikelihood decoding of convolutional codes.Viterbi algorithm reconstructs the maximum-likelihood path given the input sequence
Algorithm:
The Viterbi algorithm can be described as follows:
- Let the trellis node corresponding to state Sj at time i be denoted Sj,i
- Each node in the trellis is to be assigned a value V (Sj ,i)based on a metric. The node values are computed in the following manner.
- Set V(S _{0,0})=0 and i=1 (see figure 6.3)
- At time i compute the partial path metrics for all paths entering each node.
- Set V(Sj,i) equal to the smallest partial path metric entering the node corresponding to state Sj at time i. Ties can be broken by previous node choosing a path randomly. The non-surviving branches are deleted from the trellis. In this manner, a group of minimum paths is created from S_{0,0}.
- If i < L m, where L is the number of input code segments (k bits for each segment) and m is the length of the longest shift register in the encoder, let i= i 1 andgobacktostep2
State Diagrams For Viterbi algorithm and Maximum Likelihood Path
- Each state has one survivor path which is the most likely path
- The Viterbi algorithm takes advantage of this structure by discarding all paths entering a given node except the path with the largest partial path metric up to that node. The path that is not discarded is called the survivor path.
- The Viterbi algorithm must keep track of 2k (K−1) surviving paths and their corresponding metrics
- At each stage, 2k metrics must be computed for each node to determine the surviving path, corresponding to the 2k paths entering each node.