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.
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.
Comments