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

And the circuit is shown below

!SyndromeRS.png!

!Syndrome2RS.png!