Other modifications of the VA

  1. SOVA Soft Output Viterbi Algorithm

  The Soft-Output Viterbi Algorithm (SOVA) is a variation of the Viterbi algorithm. This algorithm has two modifications [Vit98] over the classical Viterbi algorithm. First, the path metrics used to select the maximum likelihood path through the trellis are modified to take account of a-priori information. Second, the algorithm is modified to provide a soft output for each decoded bit.

Consider the operation of a Viterbi algorithm. At some time t , each surviving path in the trellis denotes a series of add/compare/select operations, each resulting in the selection of a value for an information bit or symbol. Hagenauer and Hoeher noted that the probability that a given value is correct is proportional to how close the algorithm came to selecting the other value (or values). Let's assume here that the code in question is binary and the decoding depth for the decoder is D. The SOVA algorithm proceeds as follows.

The algorithm traverses the entire trellis, thereby tracing the ML path (the most probable).

Next the algorithm traces back from time t along the ML path, noting all path metric comparisons that could have changed the ML information bit value selected at time t-D. From among these comparisons that comparison is selected in which the difference between the compared partial path metrics is the smallest one. Thus the minimization is carried out only for those paths merging with the ML path which would have given a different value for the bit at time t-D if they had been selected as the survivor. Let be the difference between these two partial path metrics. Likelihood of the decision can be expressed as We have to normalize the probabilities so that (in binary case) P(1;O)+P(0;O)=1.

Operation of the SOVA algorithm is illustrated in Fig. 1.


Fig. 1. Example of the trellis for a binary code with SOVA decoding

The SOVA algorithm selects minimum among the following values . The paths merging the ML path and rejected at time instants t-D, t-D+1, , t-1, t have the information bit u t-D equal 1.

The SOVA approximation of the probability P(u;O) is quite good except at very low SNR's, at which point the estimate becomes too optimistic.