In the next few set of tutorials, we will study about Error Control methods used in computer networking. We will look at the types of errors and the ways the errors can be corrected or detected. In this tutorial, we will study about hamming code and hamming distance in greater detail.

What is an Error?

While sending data from a sender to a receiver, there is a possibility that the data bits may change or get corrupted. This change or corruption of data bits is called an error.

Types of Errors

Errors can be of two types:

• Burst errors: More than one bit is corrupted
• Single bit errors: Only one bit is corrupted

How to Handle the Errors?

While sending the data, the data packets may get lost due to congestion. Thus, we need methods to handle errors. Error can be handled in two ways –

• Error Correction
• Error Detection

Now, let us look at the two techniques in greater detail.

Error Correction Technique

In the error correction technique, the error can be detected and the location of error is also known. Thus, it is possible to correct the detected error. One of the methods of error correction is the hamming code.

A parity bit, or check bit, is a bit added to a string of binary code to ensure that the total number of 1-bits in the string is even or odd.

In this tutorial, we will assume even number of 1-bits.

1. Hamming code

Let us understand hamming code error correction through an example. Assume,
Data = 10011010
No of parity bits to be added to data: $2^r$ >= m + r + 1 ……. (i)
where,
   r = number of parity bits,
   m = number of message bits

Using hit and trial method, we will find the value of ‘r’.
Let’s assume we first take r = 4.

Now, using equation (i)
$2^4$ >= 8 + 4 + 1 (Therefore, the inequality holds)

Now, once we get the value of ‘r’, we know the no. of parity bits to add in the data. The parity bits are added at power of 2’s position. For example, position will be 1st ($2^0$), 2nd ($2^1$), 4th ($2^2$), 8th ($2^3$) …and so on.

Now, total bits that will be sent to the receiver will be the message bits + parity bits. So, final bits will be $P_1$ $P_2$ 1 $P_4$ 0 0 1 $P_8$ 1 0 1 0 .

To find the parity bits, we start from $P_i$ position. we take ‘i’ bits and leave the next ‘i’ bits. Then, again consider the next ‘i’ bits and continue the process till the last bit.

Finding parity bits at the Sender’s Side:

Finding Parity Bits

Thus, the data to be sent to the receiver after padding the parity bits is:

Final Data

Finding the parity bits on Receiver’s Side:

Now, assume the received code word is

Data Received by Receiver

The receiver will also find the parities using the same method.
Now, total bits that will be sent to the receiver will be the message bits + parity bits.

Finding parity bits

Now, to find the parity bits, we start from $P_i$ position. We take ‘i’ bits and leave the next ‘i’ bits. Again, consider the next ‘i’ bits and continue the process till the last bit.

Finding parity bits steps

The receiver received the parity set to be 0, 1, 1, 0 . But, the calculated parity set here is 0, 0, 1, 1. Thus, there is an error at 2 + 8 = 10th position. So, the bit at 10th position is complemented. Hence, the error is corrected.

Error correction

Drawback of Hamming Code:

• Correct only single bit errors

Finding the hamming distance: (BITWISE XOR)

Hamming distance between two numbers is equal to number of positions at which the corresponding symbols are different.

We can find the hamming distance by using XOR operation. For example,

Hamming distance between two numbers (10101010 and 10101101) is –

1 0 1 0 1 0 1 0
1 0 1 0 1 1 0 1
———————–
0 0 0 0 0 1 1 1
———————–

The no of 1’s gives the hamming distance.

Note:
– To correct ‘d’ bits, hamming distance should be equal to 2d + 1.
– To detect ‘d’ bits, hamming distance should be equal to d + 1.

That’s end of tutorial on hamming code tutorial. We also discussed about hamming distance in greater detail. Now, we will see the error detection techniques in the next tutorials.

[latexpage]