What is a Convolutional Encoder / Convolutional Encoding?

What Is A Convolutional Encoder / Convolutional Encoding...
Written By: Kia Javadi

The purpose of a convolutional encoder is to take a single or multi-bit input and generate a matrix of encoded outputs. One reason why this is important is that in digital modulation communications systems (such as wireless communication systems, etc.) noise and other external factors can alter bit sequences. By adding additional bits we make bit error checking more successful and allow for more accurate transfers. By transmitting a greater number of bits than the original signal we introduce a certain redundancy that can be used to determine the original signal in the presence of an error. For our illustration we will assume a 5-bit input and rate-1/2 code (two output bits for every input bit). This will yield a 2x5 output matrix, with the extra bits allowing for the correction.

From the nature of the input being 5-bits in length, there would be 32 possible input sequences that could be used. This page is designed to illustrate convolutional encoding with an emphasis on the Viterbi algorithm by way of an example.

The Viterbi Algorithm...

The Viterbi Algorithm (named after Andrew Viterbi) is a dynamic algorithm that uses certain path metrics to compute the 'most likely' path of a transmitted sequence. From this 'most likely' path, certain bit errors can be corrected to decipher the original bit sequence after it has been sent down a communicative line. An important feature of the Viterbi algorithm is that ties are arbitrarily solved (can be picked randomly) and still yield an original sequence. What the Viterbi algorithm can do is correctly replicate your input string at the output even in the presence of one or more errors. Obviously, with more errors introduced the likelihood of a successful decryption does go down. But the algorithm has proved to be effective.

Example Of Convolutional Encoding / Viterbi Algorithm...

From the following Encoder diagram and state table:

We can build the following input / output table:

Convolutional Encoder - Input/Output Table
Input	Output	Input	Output	Input	Output	Input	Output
00000	00000	01000	01110	10000	11100	11000	10010
	00000		01010		10100		11110

00001	00001	01001	01111	10001	11101	11001	10011
	00001		01011		10101		11111

00010	00011	01010	01101	10010	11111	11010	10001
	00010		01000		10110		11100

00011	00010	01011	01100	10011	11110	11011	10000
	00011		01001		10111		11101

00100	00111	01100	01001	10100	11011	11100	10101
	00101		01111		10001		11011

00101	00110	01101	01000	10101	11010	11101	10100
	00100		01110		10000		11010

00110	00100	01110	01010	10110	11000	11110	10110
	00111		01101		10011		11001

00111	00101	01111	01011	10111	11001	11111	10111
	00110		01100		10010		11000

And a sample Trellis Diagram with 4 states:

To implement a basic Viterbi Algorithm decoder, it is necessary to develop a scheme for dynamic calculation of Hamming Distances and Next State/Previous State outputs. To do this, one can assign two variables to each state in the Trellis Diagram (as illustrated above) – one to calculate the minimum path metric (total Hamming Distances) to that point so far and the other to record the previous state input/output transition pair. The first of the two variables can be used to ultimately calculate the minimum path metric to the final state (most probabilistic path) and the second variable could be used in the Path Determination walkup (to regenerate the inputs from our output pairs). Once the minimum path is determined, a series of comparisons can be done to work backwards from the ending point to the origination point via the most probabilistic path. This would yield our original sequence. A good program to use to illustrate this would be Matlab or a similar programming suite.

With the algorithm implemented we could then check it by introducing errors at different parts along the trellis, increasing the probabilistic likelihood of an error to test the accuracy of the algorithm. For a single instance (1-bit) error starting from an input of (00000) we can generate 10 possible sequences. A function can be written to run each of these 10 error-containing sequences through our decoder and to measure the resultant effect on the output. From this data it would be seen that every sequences would be correctly decoded, as the Viterbi algorithm would work absolutely under that configuration.