Convolutional Codes
David Jiménez
Georgia Institute of Technology 
This project was realized during the MSRI Mathematical
Graphics Summer School 2005 at Reed College. Many many
thanks for the computer help, suggestions, patience and
good conversation to David Austin, Jim Fix and Bill
Casselman, as well as most of the participants on the
Summer School, at leat for the patience to listen to
me when I needed to explain myself something.
In any case, if there is somebody to blame for the quality of the presentation, it should be me and nobody else (Sorry!). 
General Coding Paradigm

When transmiting a digital signal trough a noisy channel, usually noise is added to the signal and it is necesary to recover the original signal to process. In an ideal world, the situation is the following, A code, for most of our pourpuses, is a function T from the set of finite strings of zeros and ones to itself such that T is injective (there is a more general setting on which this definition can be setted). The code is intended to add redundancy to the message to cancel (with a high probability) the efect of the noise in the channel. 
Block Codes and Convolutional Codes.

In order to do an efficient and simple model of a code that can be used in practice, the idea is to reduce the space of messages to the space of strings of length exactly k, and the space of codewords of to the space of strings of length exactly n, k greater than n, and T most likely will be linear. The original message will be cutted into pieces of length k, after potentially a pad completition, and each of the blocks is usually coded independently. In this case the code is said to be a memoryless block code. Now, the content itself of a file may give extra redundancy to the code, and therefore robustness. The basic idea of a convolutional code is that the encoding of each block of information is not independent from all the others. The encoding is going to depend on the block to be encoded and on the state of the encoder in the moment the encoding is performed. The special feature is that this state is updated each time than the encoder encodes a block of information. This, of course introduces an extra degree of complexity to the process. The basic idea of the encoding process is the following: The open node pointing to the left is the input (one bit input), the open nodes pointing to the right are the output (two bits output), the little dots are splitters, the squares are memory cells and the adders perform the addition of the arguments (binary addition). The lines can be traversed on only one direction. The function of the memory cells is basically to storage a Memory Value that is originally zero, and each time it received a signal, it send the signal storaged as Memory Value and storage the received signal as the memory value. 
State diagram

A way to analyze the situation of a convolutional code, a useful technique is to treat it as a directed graph where each possible state of the code (possible configuration of the memory cells) and the directed edges go from one node to another if it is possible to go after a run from one of the state to the other. The figure below shows the State diagram of the same coder than above. 
Trellis's Diagram and Vitterbi Algorithm Decoding.

Given this encoding method, the question should be: Is there a way to decode a received word in an efficient way? Andrew Viterbi answered this question in an heuristic, very efficient way. Viterbi's Algorithm basically intents to maximize p(rc), this means, assuming that the probability to make a mistake is less than 1/2, Viterbi's idea is to track all the possible paths in the Trellis's Diagram, This algorithm is a lot more economical and gives with a very high probability a unique path corresponding to the most likely code word for the received word. The probability of error decreases as the size of the stack of paths and the size of the codeword increases. 
Disclaimer 
If any, all the opinions expressed here are my own, or else satirical, or honest errors. They are not necessarily those of MSRI or Reed College. 
More Formal Disclaimer 
Any opinions expressed in these web pages are my own, and have not been reviewed nor approved by anyone else. In particular, they are not to be construed as policies of the Mathematical Science Research Institute nor of the Reed College. 