__Hamming Code__

__Hamming Code__

Hamming code is an improvement over the other parity systems, this approach enable us to detect one bit error that might get introduced during transmission in every byte of information, However, this is done at the cost of increased data size due to introduction of multiple parity bits.

**Calculating the Hamming Code**

The Hamming method make use of multiple parity bits at bit positions 1,2,4,8,………. Whereas VRC/HRC method was able to detect a single bit error in a block of data, the help of Hamming code enable us to detect and correct single bit error in every byte that is being sent or received.

The following step helps in creating the Hamming code word:

- 1st of all mark all bit positions (1, 2, 4, 8, 16, 32, 64, etc.) that are powers of two as parity bits.

n…….. | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

D6 | D5 | D4 | D3 | D2 | D1 | D0 |

- All other bit positions (3, 5, 6, 7, 9, 10, 11, 12 ……etc) are for the data to be encoded, the data bits are marked and shown in the above table..
- Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.

Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,…)

Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,,…)

Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,…)

Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,…)

etc. - Now decide whether even or odd parity is to be generated. The parity is marked as 0 or 1 by following the algorithm given in step-1. That is, set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.

**Example of Hamming coding:**

Consider a data byte to be transmitted: 10111011, generate the Hamming code with even parity, transmit this encoded information, now if an error get picked in this stream, how the receiver will the the bit in error and correct the erroneous bit.

**Hamming Code Generation:**

Step-1: Mark parity bit position.

Step-2: Fil the data bits

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | ? | 1 | 0 | 1 | ? | 1 | ? | ? |

Step-3: Calculate the parity bits for positions P8, P4, P2 and P1 as:

P1= Check no. Of 1’s at positions 1,3,5,7,9,11,13…, set bit position-1 to 1 if odd no. Of 1’s, else reset to zero. In the above format we need to reset bit P1 as 1’s are even, this is shown below:

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | ? | 1 | 0 | 1 | ? | 1 | ? | 0 |

P2: Check bit position 2,3,46,7,10,11 for no. Of 1’s. In this case 1’s are ofdd so set parity bit P2 to 1. This is shown below:

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | ? | 1 | 0 | 1 | ? | 1 | 1 | 0 |

P4: Count number of 1’s at bit positions 4,5,6,7,12, we find that the 1’s are odd, so set parity bit P4 to 1. This is shown below:

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | ? | 1 | 0 | 1 | 1 | 1 | 1 | 0 |

P8: finally count the 1’s at position 8,9,10,11,12 …. , we find the 1’s are odd on these positions, so we set the parity bit P8. This is shown below:

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |

So the Hamming code word becomes: 101111011110

**b. Error Detection and Correction:**

For detecting the erroneous bit, the receiver, checks the encoded recieved data for integrity by rechecking the stream for the even parity information at parity bit positions P8, P4, P2, P1**.**

**Example:**

Assume that the above encoded data 101111011110 is transmitted and is received at the receiver as 101111001110, detect the erroneous bit and correct it.

**Detecting the bit in error:**

** **

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |

Using the same algorithm as used for Hamming code generation:

Check P1: checking for even parity at bit position 1,3,5,7,9,11. The parity is odd, so parity bit P1 is found to be in error, mark it as False shown below:

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |

False |

Check P2: checking for even parity at bit position 2,3,6,7,9,10,11. The parity is Even, so parity bit P2 is found to be correct, mark it as True shown below:

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |

True | False |

Check P4: checking for even parity at bit position 4,5,6,7,12. The parity is odd, so parity bit P4 is found to be in error, mark it as False shown below:

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |

False | True | False |

Check P8: checking for even parity at bit position 8,9,10,11,12. The parity is Even, so parity bit P8 is found to be correct, mark it as True shown below:

12 | 11 | 10 | 9 | P8 | 7 | 6 | 5 | P4 | 3 | P2 | P1 |

1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |

True | False | True | False |

#### We have verified each check bit and written down the True or False correct and incorrect parity bits respectively. Doing so, we discover that parity bits 1 and 4 are incorrect. Adding the incorrect parity bits 1+4 =5, and that bit position 5 is the location of the bad bit.

**Correcting the Error:**

Once the erroneous bit has been detected, the correction is very easy, simply complement the erreneous bit, and the correction is done.** **

**Exercise:**

1. Assuming that the data is encoded with even parity using Hamming Coding method and is in the following format:

P1 | P2 | 3 | P4 | 5 | 6 | 7 | P8 | 9 | 10 | 11 | 12 |

Check the following code word, if the receiver has received them as correct or not. If one is incorrect, correct the error, and indicate what the original data was.

If the format is

- 010101100011
- 111110001100
- 000010001011

Sol:

(i)

P1 | P2 | 3 | P4 | 5 | 6 | 7 | P8 | 9 | 10 | 11 | 12 |

0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |

On checking we find the Parity bits P1(True), P2(True), P4(True), P8(True), so parity is found to be intact, so is code, and hence no error in code (i).

The Original data was: 00110011

(ii)

P1 | P2 | 3 | P4 | 5 | 6 | 7 | P8 | 9 | 10 | 11 | 12 |

1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |

On checking we find the Parity bits P1(True), P2(False), P4(True), P8(True), so parity is found to be incorrect at position P2, so the parity bit is in error, but, the data is intact with no error in data bits of code (ii).

The original data was: 11001100

(iii)

P1 | P2 | 3 | P4 | 5 | 6 | 7 | P8 | 9 | 10 | 11 | 12 |

0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |

On checking we find the Parity bits P1(False), P2(False), P4(True), P8(False), so parity information is found to be incorrect at position P21, P2,and P8. So the bit is in error is 1+2+8=11, and hence the correct code should be as :

000010001001

2. If the data 100 was sent as 111000 and at the receiver it is received as : 111001, find error if any using Hamming System.

Ans:

P1 | P2 | 3 | P4 | 5 | 6 |

1 | 1 | 1 | 0 | 0 | 1 |

Checking for error if any:

Check Parity bit 1 – checks bits 1, 3,5 – 11 0 – OK

Check Parity bit 2 – checks bits 2,3,6 – 1 1 1 – WRONG

Check Parity bit 4 – checks bits 4,5,6 – 0 0 1 – WRONG

The bad bit is bit (2 + 4) = bit 6. Data was corrupted.

Correction is complement bit 6, complementing it, Correct data should be 100.