Hamming Code: Error Correction Examples

Details

What is an Error?

Transmitted data can be corrupted during communication. It is likely to be affected by external noise or other physical failures. In such a situation, the input data can't be the same as the output data. This mismatch is known as "Error."

The data errors may result in the loss of important or secure data. Most of the data transfer in digital systems will be in the form of 'Bit transfer.' Even a small bit of change can affect the performance of the entire system. In a data sequence, if 1 is changed to 0 or 0 is changed to 1, it is called "Bit error."

In this Hamming code tutorial, you will learn:

Types Of Errors

There are mainly three types of a bit error that occur in data transmission from the sender to the receiver.

Single Bit Errors

The change made in one bit in the entire data sequence is known as "Single bit error". However, the occurrence of single-bit error is not that common. Moreover, this error only occurs in a parallel communication system because data is transferred bitwise in a single line. Therefore, there is more chances that a single line can be noisy.

Multiple Bit Errors

In data sequence, if there is a change in two or more bits of a data sequence of a transmitter to receiver, it is known as "Multiple bit errors."

This type of error mostly occurs in both serial and parallel type data communication networks.

Burst Errors

The change of the set of bits in data sequence is known as "Burst error". This type of data error is calculated in from the first-bit change to last bit change.

What is Error Detection and Correction?

In digital communication system error will be transferred from one communication system into another. If these errors are not detected and corrected, then the data will be lost. For effective communication, system data should transfer with high accuracy. This will be done by first identifying the errors and them correcting them.

Error detection is a method of detecting the errors which are present in the data transmitted from a transmitter to receiver in a data communication system.

Here, you can use redundancy codes to find these errors, by adding to the data when it is transmitted from the source. These codes is called "Error detecting codes".

Three types of error detection codes are:

Parity Checking:

Longitudinal Redundancy Check

In this error detection technique, a block of bits is organized in the tabular format. LRC method helps you to calculate the parity bit for every column. The set of this parity is also sent along with the original data. The block of parity helps you to check the redundancy.

Cyclic Redundancy Check

Cyclic Redundancy Check is a sequence of redundant that must be appended to the end of the unit. That's why the resulting data unit should become divisible by a second, predetermined binary number.

At the destination, the incoming data needs to be divided by the same number. In case if there is no remainder, then the data unit is assumed to be correct and is accepted. Otherwise, it indicates that the data unit is damaged in transmission, and hence it must be rejected.

What is a Hamming code?

Hamming code is a liner code that is useful for error detection up to two immediate bit errors. It is capable of single-bit errors.

In Hamming code, the source encodes the message by adding redundant bits in the message. These redundant bits are mostly inserted and generated at certain positions in the message to accomplish error detection and correction process.

History of Hamming code

Application of Hamming code

Here are some common applications of using Hemming code:

Advantages of Hamming code

Disadvantages of Hamming code

Process of Encoding a message using Hamming Code

The process used by the sender to encode the message includes the following three steps:

When the above redundant bits are embedded within the message, it is sent to the user.

Step 1) Calculation of the total number of redundant bits.

Let assume that the message contains:

Here, (n + p) depicts the location of an error in each of (n + p) bit positions and one extra state indicates no error. As p bits can indicate 2p states, 2p has to at least equal to (n + p + 1).

Step 2) Placing the redundant bits in their correct position.

The p redundant bits should be placed at bit positions of powers of 2. For example, 1, 2, 4, 8, 16, etc. They are referred to as p1 (at position 1), p2 (at position 2), p3 (at position 4), etc.

Step 3) Calculation of the values of the redundant bit.

The redundant bits should be parity bits makes the number of 1s either even or odd.

The two types of parity are −

Here, all the redundant bit, p1, is must calculated as the parity. It should cover all the bit positions whose binary representation should include a 1 in the 1st position excluding the position of p1.

P1 is the parity bit for every data bits in positions whose binary representation includes a 1 in the less important position not including 1 Like (3, 5, 7, 9, …. )

P2 is the parity bit for every data bits in positions whose binary representation include 1 in the position 2 from right, not including 2 Like (3, 6, 7, 10, 11,…)

P3 is the parity bit for every bit in positions whose binary representation includes a 1 in the position 3 from right not include 4 Like (5-7, 12-15,… )

Process of Decrypting a Message in Hamming code

Receiver gets incoming messages which require to performs recalculations to find and correct errors.

The recalculation process done in the following steps:

Step 1) Counting the number of redundant bits

You can use the same formula for encoding, the number of redundant bits

2p ≥ n + p + 1

Here, the number of data bits and p is the number of redundant bits.

Step 2) Correctly positing all the redundant bits

Here, p is a redundant bit which is located at bit positions of powers of 2, For example, 1, 2, 4, 8, etc.

Step 3) Parity check

Parity bits need to calculated based on data bits and the redundant bits.

p1 = parity(1, 3, 5, 7, 9, 11…)

p2 = parity(2, 3, 6, 7, 10, 11… )

p3 = parity(4-7, 12-15, 20-23… )

Summary

 

YOU MIGHT LIKE: