28-12-2012, 04:40 PM
Viterbi Algorithm for Decoding of Convolutional Codes
1Viterbi Algorithm.pdf (Size: 282.48 KB / Downloads: 45)
Introduction
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 (with error probabilities of about
10−3 ). 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:
1. 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.
2. 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.
3. 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.
Convolutional Codes
Convolutional Encoders
Like any error-correcting code, a convolutional code works by adding some structured redundant
information to the user's data and then correcting errors using this information.
A convolutional encoder is a linear system.
A binary convolutional encoder can be represented as a shift register. The outputs of the encoder are
modulo 2 sums of the values in the certain register's cells. The input to the encoder is either the
unencoded sequence (for non-recursive codes) or the unencoded sequence added with the values of some register's cells (for recursive codes).
Convolutional codes can be systematic and non-systematic. Systematic codes are those where an
unencoded sequence is a part of the output sequence. Systematic codes are almost always recursive,
conversely, non-recursive codes are almost always non-systematic.
A combination of register's cells that forms one of the output streams (or that is added with the input
stream for recursive codes) is defined by a polynomial. Let m be the maximum degree of the
polynomials constituting a code, then K=m1 is a constraint length of the code.
Trellis Diagram
A convolutional encoder is often seen as a finite state machine. Each state corresponds to some
value of the encoder's register. Given the input bit value, from a certain state the encoder can move
to two other states. These state transitions constitute a diagram which is called a trellis diagram.
A trellis diagram for the code on the Figure 2 is depicted on the Figure 3. A solid line corresponds to
input 0, a dotted line – to input 1 (note that encoder states are designated in such a way that the
rightmost bit is the newest one).
Each path on the trellis diagram corresponds to a valid sequence from the encoder's output.
Conversely, any valid sequence from the encoder's output can be represented as a path on the trellis
diagram. One of the possible paths is denoted as red (as an example).
Note that each state transition on the diagram corresponds to a pair of output bits. There are only
two allowed transitions for every state, so there are two allowed pairs of output bits, and the two
other pairs are forbidden. If an error occurs, it is very likely that the receiver will get a set of
forbidden pairs, which don't constitute a path on the trellis diagram. So, the task of the decoder is to
find a path on the trellis diagram which is the closest match to the received sequence.
Implementation
A Viterbi algorithm consists of the following three major parts:
1. Branch metric calculation – calculation of a distance between the input pair of bits and the
four possible “ideal” pairs (“00”, “01”, “10”, “11”).
2. Path metric calculation – for every encoder state, calculate a metric for the survivor path
ending in this state (a survivor path is a path with the minimum metric).
3. Traceback – this step is necessary for hardware implementations that don't store full
information about the survivor paths, but store only one bit decision every time when one
survivor path is selected from the two.