Convolutional coding

Convolutional coding is form of error-correction widely used in mobile communications and is another area of life where discrete mathematics is hard at work for us, even though we are unlikely ever to think about it.

The basic idea in convolutional coding are that a stream of bits of length is converted to a different string of length based on the last input symbols ( is the constraint length of the code and is the code rate.

A widely used form of convolution coding is the Viterbi algorithm.

The simple idea behind the Viterbi algorithm is that given a string of observed bits, it returns the most likely input stream of bits (these bits having been transformed before transmission).

I am going to base my explanation of the Viterbi algorithm on the example used on wikipedia (though the example used there is wrong at time of writing – 14 July 2012 – as it seems to have the order of the states back to front, ie the wording does not agree with the diagram).

In this example a doctor must determine if a patient is ill with fever based on the patient’s report that she either feels normal, cold or dizzy.

From wikipedia:

states = ('Healthy', 'Fever')

observations = ('normal', 'cold', 'dizzy')

start_probability = {'Healthy': 0.6, 'Fever': 0.4}

transition_probability = {
   'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},
   'Fever' : {'Healthy': 0.4, 'Fever': 0.6},
   }

emission_probability = {
   'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
   'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
   }

Ie, 70% of healthy patients remain healthy between observations, and 50% of healthy patients report they feel ‘normal’ and so on…

So, a patient presents on three successive days and reports they feel normal, then cold, then dizzy. What should the doctor regard as the most likely course of underlying (hidden – this is a ‘Hidden Markov Model’) events?

The trellis diagram below shows the transitions and their probabilities…

To find the most likely sequence is to compute the path with the highest probability (generally referred to as the shortest path). In this case this can be seen to be healthy, healthy, fever.

The Veterbi algorithm works on this same principle – data is received and as the convolution algorithm is known then the most likely input pattern can be determined.

Related articles

• Hidden Markov Models, Viterbi and the Higgs Boson (i-programmer.info)
• Risk Matrix – Do Not Multiple Occurance x Impact (herdingcats.typepad.com)

Advertisement