miércoles, 8 de mayo de 2013

Homework 5: Error correction

For this week's class information theory and coding methods, we were given the task of implementing a block code for a binary transmission channel that is able to find and correct errors in the transmission. The algorithm we chose is to calculate the Hamming code and this publication will serve as a report for this task.

The Hamming Code


[image obtained from:"http://thebestschools.org/wp-content/uploads/2011/08/hamming_cat.jpg"]
Hamming code is an algorithm created by Dr. Richard Hamming a remarkable American mathematician who worked in many applications in computer science and telecommunications. This method adds code to a data or group of data to detect bit errors when the data is stored or transmitted from one computer to another.

Parity bits
The algorithm use to detect errors parity bits. The parity bits are bits that are added to data to indicate whether the number of bits that appear in positions indicated are odd or even, in the case of the algorithm Hamming if the number of bits is odd, the parity bit is set to 1 in case of pair has value 0.

Example:
Given this word as input:
01010
And by adding a parity bit at the beginning of the chain to check all bits in the same word would be:
[0]01010
The parity bit in square brackets, is zero because the number of ones in the data is two on two is an even number.

Cheking errors
Since the parity bit is the amount of numbers on the chain, if a bit of the original word does change then the number of bits it will be odd and this is not consistent with the parity bit.

example:
Our word with parity bit is:
001010
If a bit change in the fourth position:
001110
To check if the word change, we just have to recalculate the parity bit for the chain, which in this case is 1, which does not match the parity bit of the string is zero.

Building the Hamming code
Given a word we have to create a new word, ensuring that they have parity bits in positions that are powers of two: 1, 2, 4, 8, 16, etc. The bits of the original word are put in the spaces that are between parity bits.

Example:
for the word:
01010
Parity bits are added in power of two positions with this output:
__1_101_0
 
Now depending of their position to each parity bit position each parity bit have assigned different bits, if the parity bit is in position 1 (counting positions from 1 and not from 0) it has assign itself a bit and skipped a bit, if it is in position 2 are checked two and skip two positions.
Calculating each bit of parity with their respective positions, we have the following string:

010010100

Find bit with error
After taking the Hamming code we can check if one of the bits of the word changed by recalculate all parity bits in the word to recalculate the Hamming code, if the parity bits are different then a bit has been altered and the sum of the positions of parity bits that differ is the value of the error position. Example:

Taking the Hamming code $010010100$ y modifying a bit $011010100$ we can know which bit has change by calculating again the parity bits of this word:
__1_101_0

101010100

Know to know if there is a change in the words we apply an exor:
011010100
101010100
---------
110000000


 We realize that there is a change in the parity bits in positions 1 and 2, adding these positions $1 +2 =  3$ we know that the modified bit is to position 3 and we can change it in the first modified Hamming code for the Hamming code generated in the above example.
011010100$ --> $010010100$ = $010010100 


Applications
Error correction is very important in many areas of computing to name some of the applications:

  • Internet for sending packages commonly adds a checksum value to verify the contents and minimize processing costs.
  • Travel deep into space, due to the difficulty that send messages over long distances with out noise in space.
  • Data saved, because eventually it would have data errors.
  • Satellite broadcasting, cause it helps increase the data delivery ratio.

My implementation
My implementation of this algorithm was build in Python programming language and i used gnuplot for graphs. The implementation was done on a transmission code to simulate a binary channel for the task one done in this class.
 
Code


Result
To show the implementation in the first part as input it gives as input the same string used in the previous example, and in the second part it also generate random words and simulates the sending of a channel with little chance of error in the words, then shows the number of errors found and these few were arranged.

max@max-laptop:~/Dropbox/teoria_informacion/homework5$ python hamming.py 
Example with one error
Original Word: 01010
Recived word:  011010100
Checked word:  010010100

generating 250 words...
Words without errors: 221
Fixed words: 2
Not fixed words: 27

Experiment
As an experiment i wanted to know how efficient the algorithm correcting errors, for which we used the simulator to transmit words and then count how many words are corrected, increasing the ratio of errors for the first experiment. The second experiment was the same as above but this time you increase the amount of bits per Hamming code.

Resut:

Increasing the ratio of errors

Increasing the number of bit per word

Conclusions
Since my implementation is capable of correcting single bit, can be inefficient when the number of errors in a channel is very high. My theory was that the algorithm been affect by chain length too, but as can be seen in the graph it is not determinant for the algorithm.
I would use this implementation just in channels with few errors in which the number of bits per Hamming code is not very big.

Referencias:
http://users.cs.fiu.edu/~downeyt/cop3402/hamming.html
http://whatis.techtarget.com/definition/Hamming-code
http://es.wikipedia.org

1 comentario:

  1. Los verbos irregulares no son lo tuyo (sent, found). 5+5.

    ResponderEliminar