Internet Security

FEBRUARY 16, 2020
by **Shashwat45**

The hamming code technique, which is an **error-detection and error-correction technique**, was proposed by **R.W. Hamming**. Whenever a data packet is transmitted over a network, there are possibilities that the data bits may get lost or damaged during transmission.

Let's understand the Hamming code concept with an example:

Let's say you have received a **7-bit Hamming code **which is `1011011`

.

First, let us talk about the redundant bits.

The **redundant bits** are some extra binary bits that are not part of the original data, but they are generated & added to the original data bit. All this is done to ensure that the data bits don't get damaged and if they do, we can recover them.

Now the question arises, how do we determine the number of redundant bits to be added?

We use the formula, `2r >= m+r+1;`

where **r = redundant bit** & **m = data bit**.

From the formula we can make out that there are **4 data bits** and **3 redundancy bits**, referring to the received **7-bit hamming code**.

To proceed further we need to know about **parity bit**, which is a bit appended to the data bits which ensures that the total number of 1's are even (even parity) or odd (odd parity).

While checking the parity, if the total number of 1's are odd then write the value of parity bit **P1**(or **P2** etc.) as **1** (which means the error is there ) and if it is even then the value of parity bit is **0** (which means no error).

As we go through the example, the first step is to identify the bit position of the data & all the bit positions which are powers of 2 are marked as parity bits (e.g. 1, 2, 4, 8, etc.). The following image will help in visualizing the received hamming code of 7 bits.

First, we need to detect whether there are any errors in this received hamming code.

__ Step 1:__ For checking parity bit

As we can observe the total number of bits are odd so we will write the value of parity bit as **P1 = 1**. This means **error is there**.

__ Step 2:__ Check for P2 but while checking for P2, we will use

As we can observe that the number of 1's are even, then we will write the value of **P2 = 0**. This means **there is no error**.

__ Step 3:__ Check for P4 but while checking for P4, we will use

As we can observe that the number of 1's are odd, then we will write the value of **P4 = 1**. This means the error is there.

So, from the above parity analysis, P1 & P4 are not equal to 0, so we can clearly say that the received hamming code has errors.

Since we found that received code has an error, so now we must correct them. To correct the errors, use the following steps:

Now the error word E will be:

Now we have to determine the decimal value of this error word **101** which is **5 (22 *1 + 21 * 0 + 20 *1 = 5)**.

We get **E = 5**, which states that the error is in the fifth data bit. To correct it, just invert the fifth data bit.

So the correct data will be:

So in this article, we have seen how the hamming code technique works for error detection and correction in a data packet transmitted over a network.