Hamming Code

Hamming Code

In data transmission, error detection is required as there are high chances of having bit changes in the data. Hamming code is a linear error-detecting and correcting code invented by R. W. Hamming. It can detect up to 2 bit errors (simultaneous) and can correct single bit error. The key concept in Hamming code calculation is the use of extra parity bits.

Hamming distance 3 means it uses 3 parity bits and it can encode n bits of data into n+3 bits by adding 3 parity bits. This can detect and correct single bit errors or detect all single-bit and two-bit errors. That means double bit errors can be detected only if correction is not enabled. By adding one extra parity bit (hamming distance = 4) both single and double error detection and single error correction are possible.

Hamming Code Calculation

For example, your data is "01100011" [8 bits] and to calculate the hamming code, follow the below steps.

Step1: Identify Positions of Parity Bits

Parity bits will be inserted into bit positions that are powers of 2 (i.e. 1, 2, 4, 8, ...). These are marked as P1, P2, P4 and P8. The data is inserted in the remaining positions (i.e. 3, 5, 6, 7, 9...).

hc1

Step2: Calculate Position Bits

Position bit 1 This will check 1 bit and skip the next as shown below. So positions 1,3,5,7,9 etc. will be in use.

hc2 P1 row shows even parity so P1 = 0

Position bit 2 This will check 2 bits and skip the next 2 bits as shown below. So positions 2,3,6,7 etc. will be in use. Start position is 2.

hc3 P2 row shows even parity so P2 = 0

Position bit 4 This will check 4 bits and skip the next 4 bits as shown below. So positions 4,5,6,7 etc. will be in use.

hc4 P4 row shows odd parity so P4 = 1

Position bit 8 This will check 4 bits and skip the next 4 bits as shown below. So positions 4,5,6,7 etc. will be in use.

hc5 P8 row shows even parity so P8 = 0

Step3: Final data (data + parity bits)

hc6 Data = 01100011 Data + Parity = 000111000011

Error Detection:

In the above example we have taken data as “01100011” and final transmitted data by adding parity bits is “000111000011”. For example, if data bit position 10 got corrupted and final received data is 000111000111

hc7

Same calculation we have done on Step2 has to be done on this receive data to find out whether any error occurred or not. hc8

Check whether P1, P2, P4 and P8 are having even parity or not. P1 = 001001: Yes, P2 = 001011: No, P4 = 11101: Yes, P8 = 00111: No

Now, to find out which position of the bit is wrong, add the positions where the parity do not match. Here it is P2 and P8. That means 2+8=10. Bit position 10 is wrong!!