Hamming Code. Algorithm Operation Example

Introduction.

First of all, it is worth saying what the Hamming Code is and why it is needed. The following definition is given on Wikipedia :

Hamming codes are the best-known and probably the first of self-checking and self-correcting codes. They are built with reference to the binary number system.

In other words, this is an algorithm that allows you to encode an informational message in a certain way and after transmission (for example, over the network) to determine whether there was any error in this message (for example due to interference) and, if possible, restore this message . Today, I will describe the simplest Hamming algorithm, which can correct only one error.

It is also worth noting that there are more advanced modifications of this algorithm that allow to detect (and if possible correct) a larger number of errors.

It’s worth saying right away that the Hamming code consists of two parts. The first part encodes the original message by inserting control bits (calculated in a special way) into it in certain places. The second part receives the incoming message and recalculates the control bits (using the same algorithm as the first part). If all the newly computed control bits match those received, then the message is received without error. Otherwise, an error message is displayed and, if possible, the error is corrected.

How it works.

In order to understand the operation of this algorithm, consider an example.

Training

Suppose we have a habr message that needs to be transmitted without error. To do this, you first need to encode our message using the Hamming Code. We need to present it in binary form.



At this stage, it is worth deciding on the so-called information word length, that is, the length of the string of zeros and ones that we will encode. Suppose we have a word length of 16. Thus, we need to divide our original message (“habr”) into blocks of 16 bits, which we will then encode separately from each other. Since one character occupies 8 bits in memory, exactly two ASCII characters are placed in one encoded word. So, we got two binary strings of 16 bits:

and

After this, the encoding process is parallelized, and the two parts of the message (“ha” and “br”) are encoded independently of each other. Let's consider how this is done using the example of the first part.
First of all, you need to insert the control bits. They are inserted in strictly defined places - these are positions with numbers equal to powers of two. In our case (with an information word length of 16 bits) these will be positions 1, 2, 4, 8, 16. Accordingly, we got 5 control bits (highlighted in red):

It was:


It became:


So, the length of the whole message increased by 5 bits. Before calculating the control bits themselves, we assigned them a value of "0".

Calculation of control bits.

Now you need to calculate the value of each control bit. The value of each control bit depends on the values ​​of the information bits (as unexpectedly), but not on all, but only on those that this control bit controls. In order to understand which bits each control bit is responsible for, it is necessary to understand a very simple pattern: the control bit with number N controls all subsequent N bits every N bits, starting from position N. It’s not very clear, but I think it’ll become from the picture clearer:

Here, the “X” denotes those bits that the control bit controls, whose number is on the right. That is, for example, bit number 12 is controlled by bits with numbers 4 and 8. It is clear that in order to find out which bits the bit with number N is controlled, you just need to decompose N in powers of two.

But how to calculate the value of each control bit? This is done very simply: we take each control bit and see how many units there are among the bits controlled by it, we get some integer and, if it is even, then we set zero, otherwise we set one. That's all! It is possible, of course, and vice versa, if the number is even, then set to unity, otherwise, set to 0. The main thing is that the algorithm should be the same in the “coding” and “decoding” parts. (We will apply the first option).
After calculating the control bits for our information word, we get the following:

and for the second part:


That's all! The first part of the algorithm is complete.

Decoding and error correction.

Now, let's say we got a message encoded by the first part of the algorithm, but it came to us with an error. For example, we got this (the 11th bit was transmitted incorrectly):

The whole second part of the algorithm is that you need to recalculate all the control bits (as well as in the first part) and compare them with the control bits that we received. So, counting the control bits with the wrong 11th bit, we get the following picture:

As we see, the control bits under the numbers: 1, 2, 8 do not match the same control bits that we received. Now just adding up the position numbers of the incorrect control bits (1 + 2 + 8 = 11) we get the position of the erroneous bit. Now just by inverting it and discarding the control bits, we get the original message in its original form! We do exactly the same with the second part of the message.

Conclusion

In this example, I took the length of the informational message exactly 16 bits, since it seems to me that it is the most optimal for considering the example (not too long and not too short), but of course you can take any length. Just keep in mind that in this simple version of the algorithm, only one error can be corrected per information word.

Note.

I was inspired by the writing of this topic because in the search I did not find articles on this topic on Habré (which I was extremely surprised). Therefore, I decided to partially correct this situation and show in as much detail as possible how this algorithm works. I intentionally did not give a single formula in order to try to convey in my own words the process of the algorithm using an example.

Sources.

1. Wikipedia
2. Calculating the Hamming Code