Reed-Solomon Implementation - Decoding » History » Version 3

ABDALLAH, Hussein, 03/16/2016 10:55 PM

1 1 ABDALLAH, Hussein
h1. Reed-Solomon Implementation - Decoding
2 1 ABDALLAH, Hussein
3 1 ABDALLAH, Hussein
Decoding of a RS codes is similar to the decoding of a BCH codes as there are considered as a special class of non binary BCH codes.
4 1 ABDALLAH, Hussein
5 1 ABDALLAH, Hussein
c(x)=c0+c1(x)+c2(x2)+.. ck-1(xk-1)
6 1 ABDALLAH, Hussein
r(x)=r0+r1(x)+ r2(x2)+.. rk-1(xk-1)
7 1 ABDALLAH, Hussein
8 1 ABDALLAH, Hussein
error polynomial 
9 1 ABDALLAH, Hussein
e(x)=c(x)-r(x)= e0+e1(x)+ e2(x2)+.. ek-1(xk-1)
10 1 ABDALLAH, Hussein
11 1 ABDALLAH, Hussein
In decoding, we need to determine error location and values.
12 1 ABDALLAH, Hussein
The example below shows how to proceed
13 1 ABDALLAH, Hussein
14 1 ABDALLAH, Hussein
Let’s consider e(x) has 3 errors at the locations x1, x2, x3
15 1 ABDALLAH, Hussein
The error location numbers are z= α1 z2=α2 z3 =α3
16 1 ABDALLAH, Hussein
And the error values are e1, e2, e3
17 1 ABDALLAH, Hussein
Another important point is about erasures. So if there are p erasure symbols and q errors in the received data r(x), then RS decoder is able to decode and correct if 2q+p<= d-1=n-k
18 1 ABDALLAH, Hussein
And then the received polynomial is r(x) = c(x) + e(x) + e*(x) = c(x) + u(x)
19 1 ABDALLAH, Hussein
With e(x) and e*(x) represent the error and the erasure polynomial.
20 1 ABDALLAH, Hussein
21 1 ABDALLAH, Hussein
*Syndrome Computation*
22 1 ABDALLAH, Hussein
Received data
23 1 ABDALLAH, Hussein
r(x)=r0+r1(x)+ r2(x2)+.. rn-1(xn-1)
24 1 ABDALLAH, Hussein
Generator polynomial
25 1 ABDALLAH, Hussein
g(x) = (x+α)+ (x+α2)+ (x+α3)+..+ (x+α2t), so α, α2,..α2t are the roots
26 1 ABDALLAH, Hussein
c(αi)= m(αi) g(αi) where i= 1,2…2t
27 1 ABDALLAH, Hussein
and r(αi) = c(αi)+ e(αi)
28 1 ABDALLAH, Hussein
The syndrome Si = r(αi)
29 1 ABDALLAH, Hussein
The syndrome can be obtained by this way
30 1 ABDALLAH, Hussein
r(x) = a(x)(x +αi) + bi
31 1 ABDALLAH, Hussein
bi =GF(2m), and then Si= r(αi)= bi
32 1 ABDALLAH, Hussein
And the circuit is shown below
33 2 ABDALLAH, Hussein
34 2 ABDALLAH, Hussein
!SyndromeRS.png!
35 3 ABDALLAH, Hussein
36 3 ABDALLAH, Hussein
!Syndrome2RS.png!