Hamming Code

0
2099

 

(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 chart?cht=tx&chl=n bits and we have chart?cht=tx&chl=k bits of parity , so this will form a code of chart?cht=tx&chl=n%2Bk bit and this code is called hamming code 

STEP (2): Value of chart?cht=tx&chl=k must be chosen in such a way so it will be able to describe number for parity bit in chart?cht=tx&chl=n%2Bk bit code 

 chart?cht=tx&chl=k must satisfy the following condition

 chart?cht=tx&chl=%202%5E%7Bk%7D ≥ chart?cht=tx&chl=n%2Bk%2B1                                                 (1)

let message signal having 4 bits (BCD code) that means chart?cht=tx&chl=n%3D4 

chart?cht=tx&chl=%202%5E%7Bk%7D ≥ chart?cht=tx&chl=%20k%2B5                                                         (2)

So minimum value of chart?cht=tx&chl=%20k 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 chart?cht=tx&chl=%20P %7B%7B1%7D%7D,chart?cht=tx&chl=%20P %7B%7B2%7D%7D and chart?cht=tx&chl=%20P %7B%7B3%7D%7D 

STEP (3): In this step we will decide the position of parity bit chart?cht=tx&chl=%20P %7B%7B1%7D%7D,chart?cht=tx&chl=%20P %7B%7B2%7D%7D and chart?cht=tx&chl=%20P %7B%7B3%7D%7D  in chart?cht=tx&chl=%20n%2Bk bit Hamming code 

parity bit chart?cht=tx&chl=%20P %7B%7B1%7D%7D,chart?cht=tx&chl=%20P %7B%7B2%7D%7D and chart?cht=tx&chl=%20P %7B%7B3%7D%7D … are placed at position 1, 2, 4, … chart?cht=tx&chl=%202%5E%7Bk 1%7D     (chart?cht=tx&chl=k=1, 2, 3, … )

or chart?cht=tx&chl=P %7B%7Bk%7D%7D =chart?cht=tx&chl=(2%5E%7Bk 1%7D)th position  

Position of parity bit  chart?cht=tx&chl=%20P %7B%7B1%7D%7D :

put chart?cht=tx&chl=k =1  in chart?cht=tx&chl=%202%5E%7Bk 1%7D , this will give = 1 , that means parity bit chart?cht=tx&chl=%20P %7B%7B1%7D%7D  will assigned at first position in chart?cht=tx&chl=%20n%2Bk bit Hamming code

Position of parity bit chart?cht=tx&chl=%20P %7B%7B2%7D%7D :

put k=2 in chart?cht=tx&chl=%202%5E%7Bk 1%7D ,this will give = 2 , that means parity bit chart?cht=tx&chl=%20P %7B%7B2%7D%7D  will assigned at second position in chart?cht=tx&chl=%20n%2Bk bit Hamming code 

Position of parity bit chart?cht=tx&chl=P %7B%7B3%7D:

put k=3 in chart?cht=tx&chl=%202%5E%7Bk 1%7D , this will give = 4 , that means parity bit  chart?cht=tx&chl=P %7B%7B3%7D will assigned at fourth position in chart?cht=tx&chl=%20n%2Bk bit 

suppose chart?cht=tx&chl=n %7B%7B1%7D%7D%2Cn %7B%7B2%7D%7D%2Cn %7B%7B3%7D%7D and chart?cht=tx&chl=n %7B%7B4%7D%7D 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 chart?cht=tx&chl=%20P %7B%7B1%7D%7D,chart?cht=tx&chl=%20P %7B%7B2%7D%7D and chart?cht=tx&chl=%20P %7B%7B3%7D%7D  , 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 chart?cht=tx&chl=c %7B%7B3%7D%7D =1

2, 3, 6, 7          then chart?cht=tx&chl=c %7B%7B2%7D%7D =1

4, 5, 6, 7          then chart?cht=tx&chl=c %7B%7B1%7D%7D =1

Therefore 

chart?cht=tx&chl=P %7B%7B1%7D%7D is selected to establish even ( or odd) parity in position 1, 3, 5, 7 ( observe here that chart?cht=tx&chl=P %7B%7B1%7D%7D assigned at first(1) position in chart?cht=tx&chl=n%2Bk bit hamming code )

chart?cht=tx&chl=P %7B%7B2%7D%7D is selected to establish even ( or odd) parity in position 2, 3, 6, 7 ( observe here that chart?cht=tx&chl=P %7B%7B2%7D%7D assigned at second(2) position in  chart?cht=tx&chl=n%2Bk bit hamming code)

chart?cht=tx&chl=P %7B%7B3%7D%7D is selected to establish even ( or odd) parity in position 4, 5, 6, 7 ( observe here that chart?cht=tx&chl=P %7B%7B3%7D%7D  assigned at third(3) position in  chart?cht=tx&chl=n%2Bk 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