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

[[email protected]]

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

[[email protected]]

[email protected] 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.

[gary]

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.

[Dilip V. Sarwate]

"gary" <[email protected]> wrote in message
news:[email protected] ups.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.

[gary]

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