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…).

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.

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.

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.

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.

P8 row shows even parity so P8 = 0

Step3: Final data (data + parity bits)

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

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

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!!