Friday, June 23, 2006

Hamming code: Error Correction Code

Something I spend 2 days re-learning from my MCA days!! Man am i forgetfull.. dont even know if my understanding is correct now..
Generating the Hamming code parity bits
First thing to understand about Hamming code is the following
Step1: Convert data into bits
D0, D1, D2…. Dn-1, Dn where n is divisable by 2
E.g.:
N=8
1 0 0 1 0 1 0 0
Step2: Next thing is called grouping.
Group Bits in sequence of powers of 2 – call them group index
[D0] [D1]…. [Dn] is grouped on power of 0 è[G0_0],[G0_1]…[G0_n]
[D0,D1] [D2, D3].. [Dn-1, Dn] is grouped on Power of 1 è[G1_0],[G1_1]…[G1_n]
[D0,D1, D2, D3].. [Dn-3, Dn-2,Dn-1, Dn] is grouped on Power of 2 è[G2_0],[G2_1]…[G2_n]
Max such groups possible is possible is n/2 è
[D0,.., Dn/2], [Dn/2+1,.., Dn] è[Gn/2_1][Gn/2_2]
E.g:
Groups=
Group index 0: [1], [0], [0], [1], [0], [1], [0], [0]
Group index 1: [1, 0], [0, 1], [0, 1], [0, 0]
Group index 2: [1, 0, 0, 1], [0, 1, 0, 0]

Step 3: Each Group has parity generated for all the data bits of each [Gx_y] using XOR.
[Gx_y] è Dy/x … XOR… D(y/x+1) XOR.. D(y/x+x)
E.g.:
Groups=
Group Parity index 0: [1], [0], [0], [1], [0], [1], [0], [0] è same
Group Parity index 1: [1, 0], [0, 1], [0, 1], [0, 0] è [1], [1], [1], [0]
Group Parity index 2: [1, 0, 0, 1], [0, 1, 0, 0] è[0],[1]

Step 4: Parity Bits Pk and Pk’ are generated based on the following logic:
Where k is 0-n/2 -> same as a group index
Pk is the XOR of all Even parity bits of a group index generated in step 3.
Pk’ is the XOR of all ODD parity bits
So For Group Parity y,
[Gx_0] [Gx_1] [Gx_2] ..[Gx_y],
Pk = [Gx_0] XOR [Gx_2] [Gx_y-1]
Pk = [Gx_1] XOR [Gx_3] [Gx_y]
E.g :
G0 was: [1], [0], [0], [1], [0], [1], [0], [0]
P0: [1], XOR [0], XOR [0], XOR [0] è 1
P0’: [0],XOR, [1], XOR [1], XOR [0] è 0
G1 was : [1, 0], [0, 1], [0, 1], [0, 0] è [1], [1], [1], [0]
P1: [1, 0], XOR [0, 1] è [1], XOR [1]è 0
P1’: [0, 1], XOR [0, 0] è [1], XOR [0] è 1

G2 was: [1, 0, 0, 1], [0, 1, 0, 0] è[1],[1]
P2: [1, 0, 0, 1]è[0]
P2’: [0, 1, 0, 0] è[1]

Fixing a error:
Pold =Say we have old values for which the parity was computed (p0, p0’,p1, p1’ ,p2,p2’)
Pnew =new values generated out of the read values (pn0, pn0’,pn1, pn1’ ,pn2,pn2’)
The Pold XOR Pnew = X
If X==0, there is NO ECC error
If X == num_bits/2, the location of error is pointed by the place the error is. lest 3 bits shows which bit has the problem and rest of the same show where the byte where the problem is.
Else.. Bad data.. dump.. retry.

No comments: