Reed-Solomon Implementation - Decoding¶

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.

c(x)=c0+c1(x)+c2(x2)+.. ck-1(xk-1)
r(x)=r0+r1(x)+ r2(x2)+.. rk-1(xk-1)

error polynomial
e(x)=c(x)-r(x)= e0+e1(x)+ e2(x2)+.. ek-1(xk-1)

In decoding, we need to determine error location and values.
The example below shows how to proceed

Let’s consider e(x) has 3 errors at the locations x1, x2, x3
The error location numbers are z= α1 z2=α2 z3 =α3
And the error values are e1, e2, e3
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
And then the received polynomial is r(x) = c(x) + e(x) + e*(x) = c(x) + u(x)
With e(x) and e*(x) represent the error and the erasure polynomial.

Syndrome Computation
Received data
r(x)=r0+r1(x)+ r2(x2)+.. rn-1(xn-1)
Generator polynomial
g(x) = (x+α)+ (x+α2)+ (x+α3)+..+ (x+α2t), so α, α2,..α2t are the roots
c(αi)= m(αi) g(αi) where i= 1,2…2t
and r(αi) = c(αi)+ e(αi)
The syndrome Si = r(αi)
The syndrome can be obtained by this way
r(x) = a(x)(x +αi) + bi
bi =GF, and then Si= r(αi)= bi
And the circuit is shown below

References

http://cwww.ee.nctu.edu.tw/course/channel_coding/chap6.pdf