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

Convolutional Coding - 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 will be shown that simple bit errors can be corrected by inspection of the received symbols. A more systematic approach based on a 'best fit' path through the trellis diagram will then be developed.


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.


Decoding Example

If there are no errors, the received message can easily be related back to the bitstream which led to that message. Let the following symbol stream represent the received data.

11 10 11 11 01 10 01 00 01 01 11

Assume the circuit starts at 00, and recall the table defining the behavior of the encoding circuit:

THIS  -------------> NEXT    
STATE                STATE   
BA -C--> CBA=(XY) next BA    
-------------------------
00 -0--> 000=(00) ===> 00  
00 -1--> 100=(11) ===> 10
-------------------------
01 -0--> 001=(11) ===> 00 
01 -1--> 101=(00) ===> 10
-------------------------
10 -0--> 010=(10) ===> 01 
10 -1--> 110=(01) ===> 11
-------------------------
11 -0--> 011=(01) ===> 01
11 -1--> 111=(10) ===> 11
-------------------------

From an initial state of 00, the expected symbol can be 00 or 11, depending on whether a '0' or '1' was transmitted.
The received symbol is 11, so it is concluded that the data bit is '1' and the new state is 10.

From the current state of 10, the expected symbol can be 10 or 01, depending on whether a '0' or '1' was transmitted.
The received symbol is 10, so it is concluded that the data bit is '0' and the new state is 01.

From the current state of 01, the expected symbol can be 11 or 00, depending on whether a '0' or '1' was transmitted.
The received symbol is 11, so it is concluded that the data bit is '0' and the new state is 00.

This process continues to recover the message as:

1 0 0 1 1 1 0 1 1


Finding the Best Path

trellis Alternatively, the data can be recovered by identifying the path through the trellis defined by the sequence of symbols. This approach leads to a more robust and systematic approach to finding and correcting bit errors. From the above table, it can be noted that the first symbol '11' could represent the data bit '1' on a path leading from state 00 to 10, or the data bit '0' on a path leading from state 01 to 00. These two possibilities are summarized on the sketch at left, for the symbol '11'. The original data bit associated with a given symbol depends on the current state BA. When all the possibilities for all the received symbols are shown together, as shown below, a distinct path through the trellis can be identified which immediately gives the correct data bits. This path will be continuous if there were no errors in the incoming symbols.

trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis
Each received symbol (XY) could represent either a '1' or a '0' depending on the current state of the circuit (BA). The correct data bits describe a continuous path through the trellis. The final answer is shown below.

trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis
1 0 0 1 1 1 0 1 1 0 0  
Decoded Data Bits (continuous path)


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 symbol stream is received. Note this the same message as above with a single bit error in the third symbol.

11 10 10 11 01 10 01 00 01 01 11

The problem is obvious if the symbols are simply accepted as received:

trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis
1 0 ? 1 1 1 0 1 1 0 0  
Errored Data Bits (no continuous path)

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

The simplest correction, and the one which yields the correct answer, is found by inspection in this case. If the symbol '11' with data bit '0' is used for the third element, the problem is repaired and the data bit '0' is recovered. The restored path is shown below.

trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis
1 0 0 1 1 1 0 1 1 0 0  
Corrected Data Bits (continuous path)

It can be seen that that there is a single bit difference between the (incorrect) path which was received and the repaired path which was computed. The Hamming distance is 1 between these two paths. This reflects the fact that a single bit error caused the problem.


RECEIVED DATA:11 10 10 11 01 10 01 00 01 01 11
REPAIRED PATH:11 10 11 11 01 10 01 00 01 01 11
================================
DIFFERENCE:00 00 01 00 00 00 00 00 00 00 00

Although the above result seems obvious, alternative corrected paths can also be imagined. Other possibilities, and the chance of multiple bit errors must be considered, since it cannot be known in advance where the error occured. Consider the following proposed correct path.

trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis trellis
1 1 0 1 1 1 0 1 1 0 0  
Alternative Continuous Path

So what makes this path any worse than the above answer? The answer lies in the Hamming distance between the proposed path and the actual received symbols. As shown below, this new path lies a distance of 6 from the received data. This suggests that if this path were correct, these exact six bit errors would have had to occur. Statistically, it is expected that a single bit error (the previous result) is much more likely to have occured than six bit errors side by side. For this reason, this approach is sometimes called the "maximum liklihood" method. The second path must be discarded in favor of the previous result which was clearly the most likely occurence.


RECEIVED DATA:11 10 10 11 01 10 01 00 01 01 11
PROPOSED PATH:11 01 01 00 01 10 01 00 01 01 11
================================
DIFFERENCE:00 11 11 11 00 00 00 00 00 00 00

Performing the above operations on very long data streams would not be very efficent. The topic of Viterbi Decoding is examined in the next section.


Mon Mar 4 13:58:45 AST 2024
Last Updated: 16 OCT 2001
Richard Tervo [ tervo@unb.ca ] Back to the course homepage...