Hamming Code And Hamming Distance Tutorial With Example

Greetings!
We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners. Also, if you are interested in content writing, you can mail us at tutorialwing@gmail.com.

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:

Tutorialwing Computer Networks Hamming code tutorial with example finding parity bits

Finding Parity Bits

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

Tutorialwing Computer Networks Finding parity bits tutorial with example

Final Data

Finding the parity bits on Receiver’s Side:

Now, assume the received code word is

Tutorialwing Computer Networks Hamming Code Error Correction Technique

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.

Tutorialwing computer networks finding parity bits hamming code error correction method

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.

Tutorialwing hamming code finding parity bits error correction technique

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.

Tutorialwing Computer networks Error correction using hamming code

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.

Support Us

If you like Tutorialwing and would like to contribute, you can email an article on any educational topic at tutorialwing@gmail.com. We would love to publish your article. See your article on Tutorialwing and help others with your knowledge. Follow Facebook, LinkedIn, Google+, Twitter, Youtube for latest updates.
Greetings!
We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners