# Viterbi Decoding of Convolutional codes

Viterbi algorithm is utilized to decode the convolutional codes. Again the decoding can be done in two approaches. One approach is called hard decision decoding which uses Hamming distance as a metric to perform the decoding operation, whereas, the soft decision decoding uses Euclidean distance as a metric.

As stated in one of the previous posts the soft decision decoding improves the performance of the code to a significant extent compared to the hard decision decoding.

Viterbi Algorithm (VA) decoding involves three stages, namely,

**1) **Branch Metric Calculation

**2) **Path Metric Calculation

**3) **Trace back operation

### Branch Metric Calculation :

The pair of received bits (for (n=2) , if (n=3) then we call it triplets, etc.,) are compared with the corresponding branches in the trellis and the distance metrics are calculated. For hard decision decoding, Hamming distances are calculated. Suppose if the received pair of bits are ’11′ and the hamming distance to {’00′,’01′,’10′,’11′} outputs of the trellis are 2,1,1,0 respectively.

For soft decision decoding, see previous article

### Path Metric Calculation:

Path metrics are calculated using a procedure called ACS (Add-Compare-Select). This procedure is repeated for every encoder state.

**1. **Add – for a given state, we know two states on the previous step which can move to this state, and the output bit pairs that correspond to these transitions. To calculate new path metrics, we add the previous path metrics with the corresponding branch metrics.

**2. **Compare, select – we now have two paths, ending in a given state. One of them (with greater metric) is dropped.

### Trace back Operation :

Track back operation is needed in hardware that generally has memory limitations and if the transmitted message is of greater length compared to the memory available. It is also required to maintain a constant throughput at the output of the decoder.

Using soft decision decoding is recommended for Viterbi decoders, since it can give a gain of about 2 dB (that is, a system with a soft decision decoder can use 2 dB less transmitting power than a system with a hard decision decoder with the same error probability).

### Two Level Coding System:

Convolution codes with Viterbi decoding are not good at burst error correction, but they are good at random error correction.On the contrary, the Reed Solomon coding is good at burst error correction and not so good at random error correction. So the advantages of these two codes are exploited in many systems to provide good error correction capability against both random and burst errors.

In such systems, data are encoded firstly with a Reed-Solomon code, then they are processed by an interleaver (which places symbols from the same Reed-Solomon codeword far from each other), and then encoded with a convolutional code.

At the receiver, data are firstly processed by a Viterbi decoder. The bursts of errors from its output are then deinterleaved (with erroneous symbols from one burst getting into different Reed-Solomon codewords) and decoded with a Reed-Solomon decoder.

### Additional Resources:

[1] A graphical illustration of “How Viterbi Decoding works”

Pingback: Convolutional Coding | GaussianWaves