SOURCEFORGE » RALF » 2015 Simplified communications schemes of Voyager I probe

h1. 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(2m), and then Si= r(α^i)= bi

And the circuit is shown below

!SyndromeRS.png!

!Syndrome2RS.png!

*References*

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