Viterbi Algorithm for Decoding of Convolutional Codes

Company: 1-CORE Technologies

Convolutional codes are frequently used to correct errors in noisy channels. They have rather good correcting capability and perform well even on very bad channels. Convolutional codes are extensively used in satellite communications.

Although convolutional encoding is a simple procedure, decoding of a convolutional code is much more complex task. Several classes of algorithms exist for this purpose:

Threshold decoding is the simplest of them, but it can be successfully applied only to the specific classes of convolutional codes. It is also far from optimal. Sequential decoding is a class of algorithms performing much better than threshold algorithms. Their serious advantage is that decoding complexity is virtually independent from the length of the particular code. Although sequential algorithms are also suboptimal, they are successfully used with very long codes, where no other algorithm can be acceptable. The main drawback of sequential decoding is unpredictable decoding latency. Viterbi decoding is an optimal (in a maximum-likelihood sense) algorithm for decoding of a convolutional code. Its main drawback is that the decoding complexity grows exponentially with the code length. So, it can be utilized only for relatively short codes.

There are also soft-output algorithms, like SOVA (Soft Output Viterbi Algorithm) or MAP algorithm, which provide not only a decision, but also an estimate of its reliability. They are used primarily in the decoders of turbo codes and are not discussed in this article.

In this article the Viterbi algorithm is described using the approach suitable both for hardware and software implementations.

Reprinted from SOCcentral.com, your first stop for ASIC, FPGA, EDA, and IP news and design information.
Copyright 2002 - 2011 Tech Pro Communications, 1209 Colts Circle, Lawrenceville, NJ 08648