Category: Binary Code

Eg.  Now form a hamming code for 5-bit information bits 10110 with odd parity

m=5 and we have to follow         2^p >= m + p + 1

The value of p as 4 to satisfy 2⁴ (16) >= 5 + 4 + 1 but p=3 doesn’t satisfy as 2³ (8) >= 5 + 3 + 1

So p=4 and hence a total of 9 bits

Parity bit positions are 1, 2, 4, 8

And hence hamming code composition is as follow

0001       0010      0011      0100       0101       0110       0111       1000       1001 

1              2              3              4              5              6              7              8              9

P₁                P₂             M₁             P₃              M₂            M₃               M₄               P₄             M₅

Now if we see P₁ has 1 at LSB so message bits with this parity bit are M₁ M₂ M₄ M₅

Similarly we see P₂ checks M₁ M₃ M₄

Similarly we see P₃ checks M₂ M₃ M₄

Similarly we see P₄ checks M₅

Or we can also put it as

P₁ checks code bits 1, 3, 5, 7, 9

P₂ checks code bits 2, 3, 6, 7

P₃ checks code bits 4, 5, 6, 7

P₄ checks code bits 8, 9

For message 10110 we hamming code

Bit positions  

1              2              3              4              5              6              7              8              9 

P₁               P₂               1 P₃             0 1 1 P₄              0

We see P₁=1 to make no. of 1’s to 3 i.e. odd

We see P₂=0 to make no. of 1’s to 3 i.e. odd

We see P₃=1 to make no. of 1’s to 3 i.e. odd

We see P₄=1 to make no. of 1’s to 1 i.e. odd

So we get the hamming code as 101101110

Eg. So let’s form hamming code using 4-bit message bits 1101 with parity bits as even parity bit and check how it is able to detect and correct error.

As we have already decided parity bit positions and their corresponding message bits for a 4-bit message

For the moment we have hamming code as P₁    P₂    1 P₃ 1 0 1

As we have already seen              P₁ Checks bit number 1,3,5,7

So P_{1 =} 1 to make number of 1’s to 4 i.e. even in positions 1,3,5,7

 P₂ Checks bit number 2,3,6,7

So P_{2 =} 0 to make number of 1’s to 2 i.e. even in positions 2,3,6,7

P₃ Checks bit number 4,5,6,7

So P_{3 =} 0 to make number of 1’s to 2 i.e. even in positions 4,5,6,7

Hence we have the hamming code as 1010101

As we have already mentioned that hamming code can only detect and correct only single error. So we have error at 5^th position which means bit changes from 1 to 0 so we have data changed from 1010101 to 1010001

Now let’s start checking all 3 parity bits starting from P₁

P₁ Checks bit number 1,3,5,7 and we see we have number 1’s in these bits is 3 i.e. odd which is wrong as it should have been even so put a 1

P₂ Checks bit number 2,3,6,7 and we see we have number 1’s in these bits is 2 i.e. even which is right so put a 0

P₃ Checks bit number 4,5,6,7 and we see we have number 1’s in these bits is 1 i.e. odd which is wrong as it should have been even so put a 1

Now we collect all the bits recorded with bit from P₁ as LSB

So we get 101 hence we get bit 5 with

So as P₁  and P₃ give wrong results so now we find which code bit position is common but not found in code bit position of parity bit P₂ and we see that we 5 and 7 common for P₁  and P₃ but 7 is also present in P₂ so we are left with code position 5.

RULE TO FIND POSITION OF ERROR: We start from P₁ and start checking whether bit is correct or wrong and if it is wrong then we put a 1 and put a zero if it is correct. And while we reach end we collect all those bits taking bit from P₁ as LSB. The decimal equivalent we get from the bits collected is the bit position of error

Hence we have the bit change in position 5 so re-change it to get the correct value.  Hence we change 5^th bit of received message which is 1010001, we get 1010101 which is correct one.

So we see hamming code is able to detect and correct single error.

E.g.  Consider the parity bit P₁ and we have to find the position of message bits which we’ll cover with this parity bit.

Firstly write the binary equivalents of positions of message bit

Bit1        bit2       bit3        bit4        bit5        bit6        bit7

Parity    parity                    parity

P₁                  P₂             M₁                P₃           M₂               M₃          M₄

 001          010         011          100         101         110         111

Now let’s see in the binary equivalent of position of parity bit P₁ that at which position we have 1and we see 1 is at LSB so we select the message bits which have positions with 1 at LSB which are M_1, M₂ and M₄ So P₁ bit would check the parity for M_1, M₂ and M₄

E.g.  Consider the parity bit P₂ and we have to find the position of message bits which we’ll cover with this parity bit

We have 1 at second position from left so we choose message bits which have 1 at 2^nd position n their position’s binary equivalent. Hence we get message bits M₁ M₃ and M₄. So P₂ checks parity for message bits of M₁ M₃ and M₄

Similarly we have 1 at 3^rd position of P₃ message bits with 1 at 3^rd position are  M₂M₃ M₄

So we now have

P₁ Checks bit number 1,3,5,7

P₂ Checks bit number 2,3,6,7

P₃ Checks bit number 4,5,6,7

These parity bits can be either even or odd parity bits but all  parity bits must be same i.e. all odd or all even