Hamming Code In Computer Network

Share

Hamming Code

  1. It is a technique developed by R.W. Hamming for error correction.
  2. It is the set of error-correction codes that can be used to detect and correct errors that occur when the data is moved or stored from the sender to the receiver.
  3. 7-bit Hamming code is used commonly.

Structure of Hamming code

Fig: 7 bits hamming code

We have to follow two rules to make a 7-bit Hamming code,

  1. Data bits
    • It is a given data to transfer.
    • It is sent along with a parity bit.
  2. Parity bits or redundant bits:
    1. Even parity bit
      • Here, for a given set of bits, the number of 1’s are counted.
      • If that count is odd, the parity bit value is set to 1 (or we can say add 1), making the total count of occurrences of 1’s an even number.
      • If the total number is 0 (or we can say there is no need to add 1 because it is already even).
    2. Odd parity bit
      • Here also, for a given set of bits, the number of 1’s are counted.
      • If that count is an even, the parity bit value is set to 1 (or we can say add 1), making the total count of occurrences of 1’s an odd number.
      • If the total number is 0 (or we can say no need to add 1 because it is already odd).

A simple formula to know the parity is,

Formula: 2^n where, n=0, 1, …, n

For example:

2^0=1 2^2=4

2^1=2 2^3=8 …. so on

and which aren’t the power of 2 can be known as data bits.

Here, we denote parity by P and data by D.

Determine the value of parity bits

The value of the parity bit is determined by the sequence of bits that are alternatively checked and skipped.

For P1: 1, 3, 5, 7, 9, 10, ………            (checks 1 and skips 1)

For P2: 2, 3, 6, 7, 10, 11, …             (starting from 2, checks 2 numbers, and skips 2 numbers)

For P4: 4, 5, 6, 7, 12, 13, 14, 15, …             (Starting from 4, checks 4 numbers, and skips 4 numbers)

Example: Transfer data 1101 from sender to receiver, and determined the parity bits.

The above example shows how we are sending the hamming code.

Detecting Error

  1. When a message is sent to a receiver error detecting checks if there is an error in the message or not and whether the message sent is the same or not.
  2. if all the parity bits are 0 then there is no error.
  3. if anyone’s parity bit has another number than 0, then there occurs an error.

Correcting Error

  • An error is located by forming a 3-bit number of 3 parity checks.

finding P1:

  1. Check parity of (P1 D3 D5 and D7)
  2. If it is an odd error exit P1=1
  3. If it is an even no error P1=0

similarly for P2 and P4,

  • After we have found the error word, we find its decimal value.
  • Then we replace or invert the incorrect bit to obtain the correct word.

Example:

If the 7-bit Hamming code word received by a receiver is 1011011. Assuming the even parity state, whether the received code word is correct or wrong. If wrong, locate the bit having an error.

Solution:

Given hamming code:

Detecting error:

Analyzing bits 1,3,5 &7

we have, P1: D3 D5 D7 => 1 0 1 1 [odd parity means error exits]

now put P1=1

Analyzing bits 2,3,6&7

we have, P2: D3 D6 D7 => 1001 [even parity means no error]

now put P2=0

Analyzing bits 4,5,6&7

we have, P4: D D6 D7 => 1101 [odd parity means error exits]

now, put P4=1

Correcting error:

error word (E)=

Decimal value = 5 means the 5th bit is an error, so correct it by simply inverting the 5th bit.

Therefore, the correct word is 1001011.

Computer network articles : Computer Networks

Share
%d bloggers like this: