Thank you very much

Jaco



Dilip V. Sarwate <sarwate@uiuc.edu> wrote in message news:<sLVTa.3798$o7.48855@vixen.cso.uiuc.edu>...
> jaco_versfeld@hotmail.com (Jaco Versfeld) writes:
> 
> >Two traditional ways to decode Reed-Solomon codes include the
> >Massey-Berlekamp and Euclidean decoding algorithms.
>  
> >Can someone please explain the underlying theory on which the
> >Euclidean algorithm is based, or perhaps give some pointers in
> >literature where it is covered?
>  
> >Does it have anything to do with the Euclidean algorithm used in
> >abstract algebra to compute the GCD?
> 
> 
> 
> 
> Yes, it is the same algorithm or more precisely, the extended
> Euclidean algorithm for finding the GCD of two polynomials
> a(x) and b(x).  The extended version of the Euclidean algorithm
> also finds two polynomials c(x) and d(x) such that
> 
> 		c(x).a(x) + d(x).b(x) = g(x)
> 
> where g(x) is the GCD of a(x) and b(x).  The process is iterative
> in that 3 sequences of polynomials are constructed step by step.
> One sequence is the set of **remainder** polynomials that begins
> a0(x) = a(x), a1(x) = b(x), a2(x), a3(x), ... , and ends in
> an(x) = g(x).  The degrees of these polynomials decrease at
> each step.  The other two sequences are
> c0(x) = 1, c1(x) = 0, c2(x), ... , cn(x) and
> d0(x) = 0, d1(x) = 1, d2(x), .... , dn(x).  These polynomials
> increase in degree.  Then, the following result holds for
> i = 0, 1, 2, ... , n:
> 
> 		ci(x).a(x) + di(x).b(x) = ai(x).
> 
> 
> 
> In Reed-Solomon decoding, we wish to solve the congruence
> 
> 		L(x).S(x) = W(x) mod x^{2t}
> 
> where the syndrome polynomial S(x) is of degree < 2t, while L(x)
> has degree at most t, and deg(W(x)) < deg(L(x)).  Note that S(x)
> is known while L(x) and W(x) are to be found.  The congruence to
> be solved is equivalent to the equation
> 
> 		M(x).x^{2t} + L(x).S(x) = W(x)
> 
> and is solved by applying the extended Euclidean algorithm to
> a(x) = x^{2t} and b(x) = S(x).  Let ai(x) be the first remainder
> on the remainder sequence whose degree is strictly less than t.
> This ai(x) is essentially the W(x) we seek, and the corresponding
> di(x) is esentially the L(x) we seek:  they both happen to have
> have an extraneous scalar multiplicative factor.  This factor is
> equal to di(0), the coefficient of x^0 in the polynomial di(x)
> found by the above process.  In other words, W(x) = ai(x)/di(0)
> and L(x) = di(x)/di(0) is the solution.  I also mention that it
> is unnecessary to carry out this "normalization" in almost all
> decoder implementations.  What the decoder needs are the roots
> of L(x) and the values taken on by W(x)/L'(x) at the roots, and
> these quantities are unaffected if both W(x) and L(x) are 
> multiplied by the same scalar factor.
> 
> 
> Hope this helps.

jaco_versfeld@hotmail.com (Jaco Versfeld) writes:

>Two traditional ways to decode Reed-Solomon codes include the
>Massey-Berlekamp and Euclidean decoding algorithms.

>Can someone please explain the underlying theory on which the
>Euclidean algorithm is based, or perhaps give some pointers in
>literature where it is covered?

>Does it have anything to do with the Euclidean algorithm used in
>abstract algebra to compute the GCD?

Yes, it is the same algorithm or more precisely, the extended
Euclidean algorithm for finding the GCD of two polynomials
a(x) and b(x).  The extended version of the Euclidean algorithm
also finds two polynomials c(x) and d(x) such that

		c(x).a(x) + d(x).b(x) = g(x)

where g(x) is the GCD of a(x) and b(x).  The process is iterative
in that 3 sequences of polynomials are constructed step by step.
One sequence is the set of **remainder** polynomials that begins
a0(x) = a(x), a1(x) = b(x), a2(x), a3(x), ... , and ends in
an(x) = g(x).  The degrees of these polynomials decrease at
each step.  The other two sequences are
c0(x) = 1, c1(x) = 0, c2(x), ... , cn(x) and
d0(x) = 0, d1(x) = 1, d2(x), .... , dn(x).  These polynomials
increase in degree.  Then, the following result holds for
i = 0, 1, 2, ... , n:

		ci(x).a(x) + di(x).b(x) = ai(x).

In Reed-Solomon decoding, we wish to solve the congruence

		L(x).S(x) = W(x) mod x^{2t}

where the syndrome polynomial S(x) is of degree < 2t, while L(x)
has degree at most t, and deg(W(x)) < deg(L(x)).  Note that S(x)
is known while L(x) and W(x) are to be found.  The congruence to
be solved is equivalent to the equation

		M(x).x^{2t} + L(x).S(x) = W(x)

and is solved by applying the extended Euclidean algorithm to
a(x) = x^{2t} and b(x) = S(x).  Let ai(x) be the first remainder
on the remainder sequence whose degree is strictly less than t.
This ai(x) is essentially the W(x) we seek, and the corresponding
di(x) is esentially the L(x) we seek:  they both happen to have
have an extraneous scalar multiplicative factor.  This factor is
equal to di(0), the coefficient of x^0 in the polynomial di(x)
found by the above process.  In other words, W(x) = ai(x)/di(0)
and L(x) = di(x)/di(0) is the solution.  I also mention that it
is unnecessary to carry out this "normalization" in almost all
decoder implementations.  What the decoder needs are the roots
of L(x) and the values taken on by W(x)/L'(x) at the roots, and
these quantities are unaffected if both W(x) and L(x) are 
multiplied by the same scalar factor.

Hope this helps.

--
 .-.     .-.     .-.     .-.     .-.     .-.     .-.
/ D \ I / L \ I / P \   / S \ A / R \ W / A \ T / E \
     `-'     `-'     `-'     `-'     `-'     `-'