Viterbi Decoding Algorithm

The Viterbi algorithm (VA) is a coding method for mitigating the effect of noise at the receiver. The VA reduces the computational load and complexity by early rejecting the unlikely paths in the coding trellis. The Viterbi decoding algorithm was introduced and analyzed by Andrew J. Viterbi in 1967. Since then, other researchers have expanded on his work by finding good convolutional codes, exploring the performance limits of the technique, and varying decoder design parameters to optimize the implementation of the technique in hardware and software.

The VA is a popular method used to decode convolutionally coded messages. This algorithm tracks down the most likely state sequences of the encoder went through in decoding the message, and uses this information to determine the original message. Instead of estimating a message based on each individual sample in the signal, the convolutional encoding and Viterbi decoding process packages and encodes a message as sequence, providing a level of correlation between each sample in the signal (Davis et al. 2002).

The VA fits nicely into the streaming paradigm. For a 1/2 rate VD, a stream of two-bit digital elements is input into the VD, and a stream of one-bit element is returned. The decoding process involves two major steps: metric update and traceback. These two steps can be thought of as kernels. An illustration on how these two kernels might interconnect with input and output streams is shown in the following figure (the figure under contruction).

In this model, a stream consists of the coded message and injected noise is input into the VD. Within the decoder,  a Metric Update kernel is performed, which produces two streams; a state metric stream which contains the accumulated state metrics for all delay states, and a transition stream contains the optimal path chosen for each delay state. These two streams are passed to a traceback stream which traverses the state metric stream and employs the transition stream to find the optimal path through the trellis.

Why Viterbi Algorithm ?

The reasons for the selection of VA are:

• The VA is a binary decoding algorithm that is easier to implement in the VLSI hardware and software.
• The VA reduces computational load and decoding complexity by early rejection of the unlikely paths in the trellis code. The reduction of the computational load will increase the bit rate and the reduction of the decoding complexity lessens the power consumption.
• The complexity of VD is not a function of the number of symbols in the codeword sequence (Sklar 2001).

References:

1. Digital Communications: Fundamentals and Applications, Sklar B., Communication Engineering Services, Tarzana, California and University of California, Los Angeles, 2002.
2. VLSI Implementation of 1/2 Code Rate Viterbi Decoder For Ultra-Wideband Communication, Siswanto M., Master Thesis, Institute of Microengineering and Nanoelectronics, Universiti Kebangsaan Malaysia, Bangi, Selangor, Malaysia, 2008.
3. http://www.emeraldinsight.com/fig/160_10_1016_S1479-3601_05_06008-X.png (source of the picture)