UNB ECE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Convolutional Coding - Viterbi Decoding

The technique of convolutional coding transforms a binary message into a sequence of symbols to be transmitted. Upon reception, the received information must be related back to the original message bits. If there are no errors, the process of decoding is readily accomplished. It has already been shown that single bit errors can be corrected by simple inspection of the received symbols.

In general, convolutional coding techniques are applied to very long messages, such as the continuous stream of data from a satellite television transmiter. A fast approach to applying bit correction dynamically during reception is required. The method of Viterbi Decoding is widely used to decode and to correct errors in convolutionally encoded data.


A Convolutional Coder

The circuit below illustrates a simple convolutional coder suitable for incorporating forward error correction into a transmitted message.

In this section, it is assumed that a data stream has passed through the above circuit to yield a series of two bit (dibit) symbols representing the data. It is now necessary to examine the incoming bits and to extract the original data. Of course, the symbols received may not be exactly the same as those which were originally transmitted.


Error Correction Example

With the aid of the trellis diagram, a received message can be related back to the original bitstream even if the received data contains errors. Assume the circuit starts at 00, and the following short symbol stream is received.
The original data bits were 11101100 and there are now errors in two adjacent bits spanning two symbols, as shown highlighted below. Of course, this fact is not yet known to the decoder... 11 01 11 11 00 01 01 11

The problem is clear if the symbols are simply accepted as received, as shown below. While the original symbols defined a continuous path through the trellis, the presence of errors means that now there is no obvious continuous path through the trellis. The message bits (?) cannot be determined until such a path has been found. It is expected that the path found will exactly match the original despite the errors which have occured.

Viterbi
Decoding

It is necessary to reconstruct a continuous path from the above information. The "best fit" path will be the one which best matches the above data, deviating only as required to establish continuity. The available resources to establish this path are the four possible symbols and the corresponding eight possible state transitions:

trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis
Available elements to establish a continuous path

Proceeding by trial and error to find the "missing symbols" presupposes that the location of the bad symbols was known and greatly oversimplifies the decoding process. Perhaps the symbols leading up to the "obvious" break in the path are themselves incorrect. In general, the exact location of any bad symbols cannot be known in advance. In practice, a systematic approach to identifying the best path through the trellis can be employed to correct errors automatically as they occur.


Viterbi Decoding

The properties of the convolutionally coded signal make possible an efficient approach in which all possible paths through the trellis are explored, but only the best paths are pursued. The best path is defined as the one which is closest (Hamming distance) to the received symbols, or which has the fewest number of bits which differ from the received symbols. It is assumed that each bit which is different resulted from a transmission error which can now be corrected.

At each time interval, the (5,7) encoding circuit can have only four possible states (00,01,10,11), although many alternate paths may have led to those four states. Each state in the circuit can lead to one of two states in the next time interval. Conversely, a given state can be arrived at from one of exactly two states from the previous time interval.

In other words, exactly two incoming paths always lead to each of the four states. In general, one of those two incoming paths will have the lowest error up to that point in the trellis. By choosing the 'best path so far' and moving on to the next stage, the overall best path will be the one with the smallest 'cumulative error' at it traverses the trellis.


Viterbi Decoding Algorithm

As above, the following message is received with two errors:

11 01 11 11 00 01 01 11

Step 1 - The process begins at the start of the path, where it is always assumed the circuit begins at state 00. From here, only two paths are possible. Since the first received symbol is ' 11', the lower path (11) involves an error of 0, while the upper path (00) involves an error of 2 bits. These two values are recorded on the trellis for the next step. Any further progress along either path will add to these errors. Stage One

Step 2 - Four paths are defined leading to the next stage, two from each of the incoming states from Step 1. The error associated with a given path segment depends on the actual symbol ' 01' received, as compared to the symbol defined for that segment. Here, the corresponding dibits are shown superimposed on each candidate path segment, and the cumulative error is shown for each endpoint. Any further progress along a path will include and possibly add to the errors recorded here on the trellis. The best path so far appears to be the lower path which still has zero error. Stage Two

Step 3 - Eight paths are defined leading to the next stage, two from each of the four incoming states. The error associated with a given path segment depends on the actual symbol '11' received, as compared to the symbol defined for that segment. Each path segment is shown with its corresponding dibits, and the cumulative error for each path is computed; however, where two paths arrive at the same state, only the one with the lowest cumulative error is retained, and the other is discarded. For example, the topmost path arrives at state 00 with a cumulative error of 5, but another path leads to this same state with a cumulative error of 2. The second path is retained and 2 is recorded, representing the best path to arrive at this state. The best overall path is uncertain at this point since there are two states with error 1 (of course, an error in the received data has just occurred). This problem is expected to be resolved as the decoding continues. Stage Three

Continuing... - At each successive stage, the four best path errors are kept, four non-productive paths are discarded, and the overall correct path is expected to emerge from the computations...

Viterbi Decoding

At the far end of the trellis there is one path which gives the lowest cumulative error (2), and which corresponds to the correct data. The value (2) reflects the fact that two bit errors were corrected along this path. This path can then be traced back and is shown highlighted. Paths to each of the possible endpoints can also be traced by inspection of the above trellis.

Note that a better path seemed to be emerging at stages 'E' and 'F' when the uppermost path had a cumulative error of 1. This potential path eventually lost out to the best path, but there was no clear winner until stage 'I'. The final path cannot be traced until all possible paths have been explored.

Occasionally, two paths may arrive at the same state with equal weights, and it is impossible to choose one over the other. Note that in stage 'F' two paths arrive with weight 3 at state 11. The result is two equally-likely paths which may be followed to reach this point. The same happens at state 01. In practice, one line or the other can be chosen randomly and the resulting path might eventually die anyway (as in this example), but if the best path through the trellis is uncertain, there will likely be an error in the recovered message bits.


The EE4253 Online Viterbi Decoder is available to explore bit correction in short messages using Viterbi decoding.


The Viterbi Decoding algorithm chooses the best-fit path through the trellis, correcting for multiple bit errors as the received data arrives.


Mon Mar 4 13:57:15 AST 2024
Last Updated: 15 NOV 2004
Richard Tervo [ tervo@unb.ca ] Back to the course homepage...