Hamming Code

HAMMING CODE

Hamming code:

(1) Hamming code  were invented by Richard Hamming in 1950

(2) Hamming code is known as error correcting code that means by use of this code in digital electronics we can detect the error in  digital message signal received at receiver as well as we can also correct the error   

(3) The simple parity code (even or odd parity ) cannot correct errors, and can detect only error. but hamming code can also detect and correct the error 

(4) Hamming code can detect two bit error and can correct one bit error in the stream of bit of digital message signal received at receiver 

Steps to generate a Hamming code:

STEP (1): Let we have a message signal having n bits and we have k bits of parity , so this will form a code of n+k bit and this code is called hamming code 

STEP (2): Value of k must be chosen in such a way so it will be able to describe number for parity bit in n+k bit code 

 k must satisfy the following condition

  2^{k} ≥ n+k+1                                                 (1)

let message signal having 4 bits (BCD code) that means n=4 

 2^{k} ≥  k+5                                                         (2)

So minimum value of  k that satisfy inequality (2) is 3 , this will give idea of number of parity bit to add with message signal bit to form hamming code ,so here we required 3 parity bit  P_{{1}}, P_{{2}} and  P_{{3}} 

STEP (3): In this step we will decide the position of parity bit  P_{{1}}, P_{{2}} and  P_{{3}}  in  n+k bit Hamming code 

parity bit  P_{{1}}, P_{{2}} and  P_{{3}} … are placed at position 1, 2, 4, …  2^{k-1}     (k=1, 2, 3, … )

or P_{{k}} =(2^{k-1})th position  

Position of parity bit   P_{{1}} :

put k =1  in  2^{k-1} , this will give = 1 , that means parity bit  P_{{1}}  will assigned at first position in  n+k bit Hamming code

Position of parity bit  P_{{2}} :

put k=2 in  2^{k-1} ,this will give = 2 , that means parity bit  P_{{2}}  will assigned at second position in  n+k bit Hamming code 

Position of parity bit P_{{3}:

put k=3 in  2^{k-1} , this will give = 4 , that means parity bit  P_{{3} will assigned at fourth position in  n+k bit 

suppose n_{{1}},n_{{2}},n_{{3}} and n_{{4}} represents first ,second , third, fourth bit of message signal then 7 bit hamming code will be 

hammingcode

 

 

 

Value (0 or 1 ) are assigned to the parity bits so as to make the Hamming code by considering either even parity or odd parity system 

STEP(4):

In above case (in case of BCD code) with three parity bits  P_{{1}}, P_{{2}} and  P_{{3}}  , there are seven (7) error position , listed in table below 

position error

we can observe from above table if error occurs in position 

 1, 3, 5, 7         then c_{{3}} =1

2, 3, 6, 7          then c_{{2}} =1

4, 5, 6, 7          then c_{{1}} =1

Therefore 

P_{{1}} is selected to establish even ( or odd) parity in position 1, 3, 5, 7 ( observe here that P_{{1}} assigned at first(1) position in n+k bit hamming code )

P_{{2}} is selected to establish even ( or odd) parity in position 2, 3, 6, 7 ( observe here that P_{{2}} assigned at second(2) position in  n+k bit hamming code)

P_{{3}} is selected to establish even ( or odd) parity in position 4, 5, 6, 7 ( observe here that P_{{3}}  assigned at third(3) position in  n+k bit hamming code)

Example: Construct Hamming code for BCD 0110 . use even parity ?

Solution:                         1       2       3     4      5     6     7

                                              P1     P2     n1    P3   n2    n3   n4

Original BCD                                        0              1       1      0

Even parity in 

position 1, 3, 5, 7

required P1=1                    1                 0             1         1       0

Even parity in 

position 2, 3, 6, 7

required P2= 1                  1      1         0            1          1       0

Even parity in 

position 4, 5, 6, 7

required P3=0                 1       1        0      0     1         1      0 

Therefore resultant Hamming code for BCD digit 0110 with even parity is 1100110

Method to Correct Error:

If above Hamming code sequence 1100110 is transmitted by transmitter and due to error in channel we received as 1110110 by receiver therefore we have to find the position of error bit and correction in error 

in above hamming code construction we use even parity therefore we have to check parity in received signal 1110110

parity check on 4, 5, 6, 7 (0110) position gives C1 = 0( even parity )

parity check on 2, 3, 6, 7(1110) position gives C2= 1( odd parity) 

parity check on 1, 3, 5, 7(1110) position gives C3= 1 ( odd parity) 

therefore position number formed is C1 ,C2, C3 = 011 

decimal value of 011 will be 3 so error will be at position 3 , therefore make complement of bit at position 3 to correct the error in received signal  

 

Leave a Comment

Your email address will not be published.