Lecture 8 min.
In 1967, Andrew Viterbi developed and analyzed a decoding algorithm based on the maximum likelihood principle. The algorithm is optimized by exploiting the structure of the particular code trellis. The advantage of Viterbi decoding over brute-force decoding is that the complexity of the Viterbi decoder is not a function of the number of symbols in the codeword sequence.
The algorithm involves computing a measure of similarity (or distance) between the signal received at time 
and all the trellis paths entering each state at time 
. The Viterbi algorithm does not consider those trellis paths that, according to the maximum likelihood principle, obviously cannot be optimal. If two paths enter the same state, the one with the better metric is chosen; such a path is called the survivor. The selection of survivor paths is performed for every state. In this way, the decoder goes deeper into the trellis, making decisions by eliminating less likely paths. Early rejection of unlikely paths simplifies the decoding process. In 1969, Jim Omura showed that the basis of the Viterbi algorithm is maximum likelihood estimation. Note that the problem of selecting optimal paths can be expressed as choosing the codeword with the maximum likelihood metric or the minimum distance metric.
The best decoding scheme for error-correcting codes is maximum likelihood decoding , in which the decoder determines a set of conditional probabilities 
, corresponding to all possible code vectors 
, and decides in favor of the codeword corresponding to the maximum . For a memoryless binary symmetric channel (a channel in which the probabilities of transmitting 0 and 1, as well as the probabilities of errors of the form 0 -> 1 and 1 -> 0, are equal, and errors in the j-th and i-th code symbols are independent), the maximum likelihood decoder reduces to a minimum Hamming distance decoder. The latter computes the Hamming distance between the received sequence r and all possible code vectors and decides in favor of the vector that turns out to be closest to the received one. Naturally, in the general case such a decoder is very complex and, for large code sizes 
and 
, practically unrealizable. The characteristic structure of convolutional codes (the repetition of the structure beyond a window of length ) makes it possible to build a maximum likelihood decoder of quite acceptable complexity.
A segment of the sequence 
of length 
, exceeding the code block length , arrives at the decoder input. Let us call the decoding window. Let us compare all the codewords of the given code (within the segment of length ) with the received word and choose the codeword closest to the received one. The first information frame of the chosen codeword is taken as the estimate of the information frame of the decoded word. After that, 
new symbols are fed into the decoder, and the oldest symbols entered earlier are discarded, and the process is repeated to determine the next information frame. Thus, the Viterbi decoder processes the data frame by frame, moving along a trellis similar to the one used by the encoder. At each moment in time, the decoder does not know which node the encoder is in, and does not try to decode it. Instead, the decoder uses the received sequence to determine the most likely path to each node and computes the distance between each such path and the received sequence. This distance is called the path divergence measure. The segment having the smallest divergence measure is chosen as the estimate of the received sequence. The path with the smallest divergence measure is called the survivor path.
Let us consider the operation of the Viterbi decoder on a simple example. Suppose that encoding is performed using a convolutional (7,5) code. Using the encoder's trellis diagram, let us try, having received some segment , to trace the most likely path of the encoder. For each section of the trellis diagram, we will note the path divergence measure to each of its nodes. Suppose that the transmitted code sequence is U = (00000000…), and the received sequence is r = (10001000…), that is, errors occurred in the first and third frames of the codeword. As we have already seen, the decoding procedure and result do not depend on the transmitted codeword and are determined only by the error contained in the received sequence. Therefore, it is simplest to assume that the zero sequence was transmitted, that is, U = (00000000…). Having received the first pair of symbols (10), the decoder determines the divergence measure for the first section of the trellis; having received the next pair of symbols (00), it does so for the second section, and so on. Of the paths entering each node, we keep the path with the smaller divergence, since a path with a currently larger divergence can no longer become shorter later. Note that in this example, starting from the fourth level, the metric (or divergence measure) of the zero path is smaller than any other metric. Since there were no more errors in the channel, it is clear that this path will ultimately be chosen as the answer. This example also shows that survivor paths can differ from each other for quite a long time. However, at the sixth or seventh level, the first seven edges of all survivor paths coincide. At this moment, according to the Viterbi algorithm, a decision on the transmitted symbols is made, since all survivor paths emerge from one vertex, that is, they correspond to a single information symbol.
The depth at which the survivor paths merge cannot be computed in advance; it is a random variable that depends on the multiplicity and probability of the errors occurring in the channel. Therefore, in practice one usually does not wait for the paths to merge, but sets a fixed decoding depth.
At step i) the difference between the metrics of the correct and incorrect paths is quite large ( 
, 
), so in this case the decoding depth could be limited to 
. But sometimes a path that is longer up to a given section may turn out to be the shortest in the end, so one should not get too carried away with reducing the size of the decoding window b in order to simplify the decoder. In practice, the decoding depth is usually chosen in the range 
, where 
is the number of errors the given code corrects. Despite the presence of two errors in the received fragment, its decoding occurred without error, and the transmitted zero sequence will be accepted as the answer.
A physical implementation of a Viterbi decoder will not yield an exact maximum likelihood stream because of quantization of the input signal, branch and path metrics, and the finite traceback length . Practical implementations come within 1 dB of the ideal.
At the output of a Viterbi decoder decoding a message corrupted by an additive Gaussian channel, errors are grouped into error bursts. Single-error-correcting codes alone cannot correct such bursts, so either the convolutional code and Viterbi decoder must be designed powerful enough to reduce the number of errors to an acceptable level, or burst-error-correcting codes must be used.
A hardware Viterbi decoder for punctured codes is usually implemented as follows:
One of the most time-consuming operations is the ACS butterfly, which is usually implemented in assembly language with appropriate instruction set extensions (such as SSE2 ) to speed up decoding.
The Viterbi decoding algorithm is widely used in the following areas:
Comments