[IT] Homework 5: Error detection (Hamming Block Code)

For this week we had to implement an error detection technique using a block code method. We had to simulate the transmission of data through a noisy channel and use our error detection technique to fix the errors during the transmission.
I use the Hamming Code as my block code method.

NOTE: If you want to understand how works the Hamming Block Code, check the references at the footer.


Experiment

For my experiment, I prepared a Python script that generate several random words of length 4 (4 bits) and then, send them through a noisy channel, the parameters of the experiment are:

• wordLength: Word length (4 bits)
• frecZeros: Frequency of zeros in the word
• probError: Probability that a word is transmitted wrong by the channel
• errorBits: Maximum number of errors in the transmitted word
• rep: Amount of experiment repetitions

For the experiment, the wordLength and the errorBits are fixed at 4 and 1, respectively, the parameters freqZeros and probError only affects the final behavior of the channel.

As we can see, with 1 as the number of error bits in the word, the Hamming Block code can fix all the errors without problems.

If we increase the amount of erros in each word, for instance, 2 errors per word, we begin to experience some failures in the method

There are not much difference if we increase the amount of errors to 3

The Hamming Code methos works fine while the amount of errors in a word still's one, but, when the amount of errors increases two a number bigger than one, the Hamming Code will start to experiment some failures.

Also,we can see that the amount of good transmissions and errors follows a linear relation.

The implemented Hamming Code uses a 7x4 "H" matrix, with which is able to correct a single bit error.

When you multiply the original 4-bits word and the encode "G" matrix, the result is a 7-bit codeword "xG":

When you decode the codeword using the "H" matrix, the multiplication result is a 3-bit word. That word is a binary representation of a single digit. The digit represents the bit that is wrong in the transmitted codeword through the noisy channel.

We only need to translate the binary representation to an integer, which we will be able to correct the bit error.

Code



References:

• Michael Dipperstein, Hamming (7,4) Code Discussion and Implementation, extraído de: http://michael.dipperstein.com/hamming/
• Encoding and Decoding with the Hamming Code, extraído de: http://www.uwyo.edu/moorhouse/courses/4600/encoding.pdf