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(x^2) +.. ck-1(x^k-1)
r(x) = r0 + r1(x) + r2(x^2) +.. rk-1(x^k-1)

error polynomial
e(x)=c(x)-r(x)= e0 + e1(x) + e2(x^2)+.. ek-1(x^k-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(x^2)+.. rn-1(x^n-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