Error-Correcting codes

For this homework we need to implement a block code for a binary channel, then we need to explain how many errors it is able to detect or correct and why, we need to do a test program and try it out.

So, I do the hamming code because I think is easy to implement and explain, hamming code is a block code that can detect and correct errors in a binary channel, but this code can only detect just one bit for a all the sequence of bits, so for that, you need to implement a variant of this block code, for this homework I just experiment a normal hamming code.

For do the hamming code we need to do some procedures into the program, for example we need to do some subroutine that can do a parity and also check and jump into vector, I'm going to explain how I do it in Python.

So, first of all, we have a sequence of bits, then, I made a subroutine that creates a vector that have a bits only in a position when the number is the power of two, that is in the position 1, 2, 3, 8, 16, 32, 64, etc. and in the others position we didn't want save any data.

Then, we need to compute a bit of parity, so for that, I do a procedure that do a general rule that we have in the hamming code, jump n-1 bits, then check n bits, then jump n bit, etc, at the moment to do that, we have another vector that we need to compute a logic xor for each value in the vector, just for have the parity bits.

Then we need to join the bits of parity into the vector that we have, and we already have a hamming code, but now the important thing is to know when we have an error, so for that we need to do a test of parity, and if we have in each row, 0 in the xor, we are right, it is just the same of the hamming code but in the inverse.

If we can detect an error, we have a sequence of bits that we can translate to a decimal and we have that number to know the position of the error, then just change that bit and we already have a good sequence.

This only works when we have only one bit with an error, but if we have many, we need to implement another error-correcting code, so, in conclusion, this is simple to implement, to understand how works a block code with a correcting solution, but it fail at the moment that we have many errors.

This is an example, suppose that we have the following bits

1010101

Then we do a vector just in the positions that are power of two.

['', '', '1', '', '0', '1', '0', '', '1', '0', '1']

Then we do for each vector, xor of all the items, following the rule " jump n-1 bits, then check n bits..."


['', '', '1', '', '0', '', '0', '', '1', '', '1'] :  1
['', '', '1', '', '', '1', '0', '', '', '0', '1'] :  1
['', '', '', '', '0', '1', '0', '', '', '', '']     :  1
['', '', '', '', '', '', '', '', '1', '0', '1']     :  0


So we add this bit into the coding

['1', '1', '1', '1', '0', '1', '0', '0', '1', '0', '1']

Suppose that we have an error, and we have the next sequence.

['1', '0', '1', '1', '0', '1', '0', '0', '1', '0', '1']

So we do with that sequence, just obtain the bits and compare if we have the same using parity, for that we need to do for each vector an xor.

COMP:1
ERRO:1

COMP:1
ERRO:0

COMP:1
ERRO:1

COMP:0
ERRO:0

We have the next sequence:
['0', '0', '1', '0']
     Pos = 2

Then if we know, in 10 are 2 in decimal, so in the position 2, we have the error.


['1', '0', '1', '1', '0', '1', '0', '0', '1', '0', '1']
['1', '1', '1', '1', '0', '1', '0', '0', '1', '0', '1']

And we correct this sequence.

I hope my english is good and you can understand.

This is my code.