Viterbi convolutional decoding algorithm
The Viterbi algorithm essentially performs maximum likelihood decoding; however, it reduces the computational complexity load by taking advantage of the special structure in the code trellis. The advantage of Viterbi coding is that the complexity of a Viterbi decoder is not a function of the number of symbols in the codeword sequence.
The algorithm involves calculating trellis paths that could not possibly be candidate for maximum likelihood choice. When two path enter the same state, the one having the best metric is chose; this path is called the surviving path. This selection of surviving path is performed for all the states. The decoder continues in this way to advance deeper into the trellis, making decision by eliminating the least likely path. The early rejection of the unlikely path reduces the complexity.
Decoder trellis diagram