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 2×5 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:
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 comparison 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.