Forums

Euclidean algorithm used to decode Reed-Solomon codes?

Started by Jaco Versfeld July 17, 2003
Hi,

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?

Your time, effort and suggestions will be greatly appreciated
Jaco
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 \ `-' `-' `-' `-' `-' `-'
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.