Path Measure

• Definition:
  Path and branch measures are integral to the inner-working of the Viterbi algorithm. The Viterbi algorithm attempts to find the maximum likelihood path through the trellis which corresponds to the maximum likelihood codeword. It does this in an incremental fashion by computing the partial path measures for paths ending in intermediate states. The path measures of states in subsequent trellis sections are found as combinations of the path measures of the states in the previous trellis section and the branch measures that connect a state with its previous state.
  
• Theory:
  There are two possible ways to find the maximum likelihood path through the trellis. In the Workshop these two ways are named Probability and Metric.

  The Probability method is the most intuitive. The path measure of a state is calculated by the following three step process:

  • First, find the probability of the received codeword given the hypothesis codeword associated with the branches entering a state. This is called the branch measure.
  • Second, find the combined probability of the branch and the state it came from. This joint probability is simply the product of the previous state's path measure and the branch measure because the probabilities are independent since we assume a memoryless channel.
  • After these joint probabilities are calculated for each branch entering a state, the third step is to pick the best partial path measure. This amounts to picking one surviving branch out of those entering the state, and assigning the partial path measure calculated with this branch to this state. This probability is what is referred to as the path measure of the state. For this method, "best", means the highest probability.

  Using a Metric path measure to find the maximum-likelihood path is really just a simplification of the first method. We take the negative log of the joint probability of the branch measure and the previous state's path measure. This is equivalent to taking the sum of the negative log's of the measures. The best measure is then chosen as the smallest combined value.

  These two methods are equivalent and will always give the same results. So why even bother with the -log method? The answer is you shouldn't bother with it when using a BSC channel because you have to do multiplies, logarithms, and an addition instead of simply multiplies. However, when using an AWGN channel, using the second method provides a significant reduction in the amount of calculation required. Since the branch measure is the product of the Gaussian probabilities of the bits of the received word, taking the natural log reduces the expression from a product of exponentials to the sum of their exponents. The sum of these exponents is the squared Euclidean distance between the received word and the branch hypothesis word. So, now calculation of the branch and path measures only requires additions which can done much faster than exponentiation and multiplies.

• Examples:
  The best way to see an example of how this works is to step through the algorithm in the Workshop "By Branch". Try all four possible combinations of channel model and path measure style.