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

# 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 ●March 5, 2006

Reply by ●March 5, 20062006-03-05

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.

Reply by ●March 5, 20062006-03-05

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.

Reply by ●March 6, 20062006-03-06

"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.

Reply by ●March 10, 20062006-03-10

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