Forums

What is the stop condition for Decoding Reed Solomon Codes with s erasures and v errors when s+2v>d using Euclid's Algorithm?

Started by Unknown March 5, 2006
Hi,

   I am trying to simulate a RS decoder using Euclid's Algorithm. I
have one question about the stop condition.
   If there are s erasures and v errors satisfying s+2v>d, what is the
stop condition for Euclid's Algorithm.

Thanks in advance.
Have a nice day.

Dayu Huang

dayuhuang@gmail.com wondered:

> I am trying to simulate a RS decoder using Euclid's Algorithm. I > have one question about the stop condition. > If there are s erasures and v errors satisfying s+2v>d, what is the > stop condition for Euclid's Algorithm.
If the decoder *knows* that s erasures and v errors occurred where s+2v>d-1, then it is necessary to run the Euclidean algorithm at all! More commonly, the decoder *does* know the value of s, but not the value of v, and so does not know whether s+2v > d-1 or not (except, of course, when s > d-1). The stopping condition is no different than for the case when s + 2v < d. Note also when s + 2v > d-1, it is entirely possible that the Euclidean algorithm will stop *before* the stopping condition is met (last nonzero remainder has degree greater than the value used in the stopping condition), or will terminate "normally" but the polynomials that it provides will result in decoding failure or decoding error.
Thank you.

Should I run this algorithm in the following way:

Check if s>d-1. If not, run Euclidean algorithm using the normal stop
condition.

If the Euclidean algorithm stops before the stop condition if met, a
decoder failure occurs.

The Eculidean algorithm stops normally, check the roots to see whether
they are distinct and within the frame. If not, a decoder failure
occurs.

"gary" <dayuhuang@gmail.com> wrote in message 
news:1141611571.294157.79480@v46g2000cwv.googlegroups.com...
> Should I run this algorithm in the following way: > > Check if s>d-1. If not, run Euclidean algorithm using the normal stop > condition. > > If the Euclidean algorithm stops before the stop condition if met, a > decoder failure occurs. > > The Eculidean algorithm stops normally, check the roots to see whether > they are distinct and within the frame. If not, a decoder failure > occurs.
Yes, that's the way to run the algorithm, except that when the Euclidean algorithm terminates normally, not only should the roots be distinct and within the frame, but the total number of roots should also be equal to the degree of the error-locator polynomial. Else, you have a decoder failure.
Thank you!

After running Euclid algorithm, I use Forney alogrithm to evaluate the
magnitude.
I met the following problem.
one of the Roots of Yi(x) (Errata Locator), denoted by X' will result
in:
YI'(X')=0,i.e. the derivatives of Errata Locator equals 0 when X take
the value of X'.
Is it a decoder failure? 

Gary