(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 bits and we have
bits of parity , so this will form a code of
bit and this code is called hamming code
STEP (2): Value of must be chosen in such a way so it will be able to describe number for parity bit in
bit code
must satisfy the following condition
≥
(1)
let message signal having 4 bits (BCD code) that means
≥
(2)
So minimum value of 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
,
and
STEP (3): In this step we will decide the position of parity bit ,
and
in
bit Hamming code
parity bit ,
and
… are placed at position 1, 2, 4, …
(
=1, 2, 3, … )
or =
position
Position of parity bit :
put =1 in
, this will give = 1 , that means parity bit
will assigned at first position in
bit Hamming code
Position of parity bit :
put k=2 in ,this will give = 2 , that means parity bit
will assigned at second position in
bit Hamming code
Position of parity bit :
put k=3 in , this will give = 4 , that means parity bit
will assigned at fourth position in
bit
suppose and
represents first ,second , third, fourth bit of message signal then 7 bit hamming code will be
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 ,
and
, there are seven (7) error position , listed in table below
we can observe from above table if error occurs in position
1, 3, 5, 7 then =1
2, 3, 6, 7 then =1
4, 5, 6, 7 then =1
Therefore
is selected to establish even ( or odd) parity in position 1, 3, 5, 7 ( observe here that
assigned at first(1) position in
bit hamming code )
is selected to establish even ( or odd) parity in position 2, 3, 6, 7 ( observe here that
assigned at second(2) position in
bit hamming code)
is selected to establish even ( or odd) parity in position 4, 5, 6, 7 ( observe here that
assigned at third(3) position in
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
