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
  • Multiple bit errors
  • Burst errors

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
  • Cyclic Redundancy Check (CRC)
  • Longitudinal Redundancy Check (LRC)

Parity Checking:

  • It is also known as a parity check.
  • It has a cost-effective mechanism for error detection.
  • In this technique, the redundant bit is known as a parity bit. It is appended for every data unit. The total number of 1s in the unit should become even, which is known as a parity bit.

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

  • Hamming code is a technique build by R.W.Hamming to detect errors.
  • Hamming code should be applied to data units of any length and uses the relationship between data and redundancy bits.
  • He worked on the problem of the error-correction method and developed an increasingly powerful array of algorithms called Hamming code.
  • In 1950, he published the Hamming Code, which widely used today in applications like ECC memory.

Application of Hamming code

Here are some common applications of using Hemming code:

  • Satellites
  • Computer Memory
  • Modems
  • PlasmaCAM
  • Open connectors
  • Shielding wire
  • Embedded Processor

Advantages of Hamming code

  • Hamming code method is effective on networks where the data streams are given for the single-bit errors.
  • Hamming code not only provides the detection of a bit error but also helps you to indent bit containing error so that it can be corrected.
  • The ease of use of hamming codes makes it best them suitable for use in computer memory and single-error correction.

Disadvantages of Hamming code

  • Single-bit error detection and correction code. However, if multiple bits are founded error, then the outcome may result in another bit which should be correct to be changed. This can cause the data to be further errored.
  • Hamming code algorithm can solve only single bits issues.

Process of Encoding a message using Hamming Code

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

  • Calculation of total numbers of redundant bits.
  • Checking the position of the redundant bits.
  • Lastly, calculating the values of these redundant bits.

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:

  • n- number of data bits
  • p - number of redundant bits which are added to it so that np can indicate at least (n + p + 1) different states.

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 −

  • Total numbers of bits in the message is made even is called even parity.
  • The total number of bits in the message is made odd is called odd parity.

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:

  • Counting the number of redundant bits.
  • Correctly positioning of all the redundant bits.
  • Parity check

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

  • Transmitted data can be corrupted during communication
  • Three types of Bit error are 1) Single Bit Errors 2) Multiple Bit Error 3) Burst Bit errors
  • The change made in one bit in the entire data sequence is known as "Single bit error."
  • 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."
  • The change of the set of bits in data sequence is known as "Burst error".
  • 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
  • Three types of error detection codes are 1) Parity Checking 2) Cyclic Redundancy Check (CRC) 3) Longitudinal Redundancy Check (LRC)
  • 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.
  • Hamming code is a technique build by R.W.Hamming to detect errors.
  • Common applications of using Hemming code are Satellites Computer Memory, Modems, Embedded Processor, etc.
  • The biggest benefit of the hamming code method is effective on networks where the data streams are given for the single-bit errors.
  • The biggest drawback of the hamming code method is that it can solve only single bits issues.
  • We can perform the process of encrypting and decoding the message with the help of hamming code.

 

YOU MIGHT LIKE: