Syndrome-decoding: Why do we correct the error locations, rather than interpolating with the non-error locations?

Question

so for setup, let's say we have an $[n,k]$- Reed-Solomon-Code over $\mathbb{F}_q$ for some prime power $q = p^m$. It could be $q \neq 2$. We turned a message $M$ of length $k$ into a codeword $W$ of length $n$, and the receiver got the erroneous word $R$ with at most $t \leq \frac{n-k}{2}$ errors. And we are already at the point where we found the error locator polynomial $\Lambda$ and its roots. So, we know where the errors are.
Now, my first idea would be to avoid the error locations and to use $k$ of the correct locations for a polynomial interpolation. Instead, I often read that we use the Forney-algorithm to correct the errors. But then, what? Do we use a list where we map the correct codeword back to its original word, or what? Would that be faster than the polnomial interpolation? Because the list has $q^k$ entrances, so that could take a while. Although there may be faster ways to search through that list.

Am I on the right track, or am I completely off?

Answer 1

A Reed-Solomon decoder finds the coefficients of the error-locator polynomial, and then (usually) uses a process called the Chien Search to find the inverse roots of the error-locator polynomial (the inverse roots are the error locations). The Chien search is a $n$-step process that examines the $n$ symbols one at a time to determine whether that symbol is in error. Thus, the decoder cannot compile the complete list of error locations till the Chien search is over. Then, the decoder can (if it so wishes), interpolate from known error-free locations to find the correct values of the symbols known to be in error. However, as @Jyrki's comment cogently says, Forney's algorithm is better suited for this purpose since it computes each error value immediately after each error location has been determined, and this error value can be subtracted off from the received symbol immediately (no need to store the error value). In short, with a slightly more complicated (and time-consuming) $n$-step process, the errors can be determined and removed from the received word. Indeed, in the interest of time complexity and storage requirements, most Reed-Solomon decoders combine the error correction process and the output process (sending the corrected codeword out into the world for delivery to its intended recipient) into one so that each received symbol is corrected (if necessary) just as it is leaving the decoder on its way to its final destination.

---

So why (as the OP asks in a comment on this answer) should the decoder even bother to correct errors in the parity-check symbols?Shouldn't just correcting the errors (if any) in the $k$ information symbols suffice? Why waste extra time and effort? This is indeed a very valid question but the answer gets into matters of practical implementation of decoders, topics that are far interests of math.SE.

Let $\mathbf C$ denote the transmitted codeword and $\mathbf R$ the received word, Than, all bounded-distance decoders have the following characteristic that some people do not fully absorb:

If there is a codeword $\hat{\mathbf C}$ that differs from the received word $\mathbf R$ in $t$ or fewer locations, then the decoder finds $\hat{\mathbf C}$.

Note the complete absence of any mention of $\hat{\mathbf C}$ being the correct (i.e. transmitted) codeword $\mathbf C$. Now, if $\mathbf R$ does happen to differ from $\mathbf C$ in $t$ or fewer locations, then the decoder does indeed find $\mathbf C$. Note that since the minimum distance is $2t+1$, there is no competing codeword $\mathbf C^\prime$ that is also within distance $t$ of $\mathbf R$ to lead the decoder astray: there is at most one codeword within distance $t$ from any given $\mathbf R$ and when such a codeword exists, the decoder finds it. But just because the decoder finds a codeword, there is no guarantee that it is the correct codeword $\mathbf C$; it might be some $\hat{\mathbf C} \neq \mathbf C$ that happens to be at distance $\leq t$ from $\mathbf R$. (The decoder is following the sailor's philosophy of "When I'm not near the girl I love, I love the girl I'm near" with the addendum that on the high seas, no girls are near). What it is correct to say is that (with the usual assumption that fewer errors are more likely to have occurred than many errors) with high probability the $\hat{\mathbf C}$ that the decoder finds is indeed the transmitted codeword $\mathbf C$.

What happens when there are $e > t$ errors (the decoder is, of course, unaware of this)? Well, if $e = t+1$, there is a very very very small chance that the Reed-Solomon decoder will find the correct error-locator polynomial and be able to decode successfully. In almost all cases, the decoder will end up with an error-locator polynomial of degree $t$ or less,but it will have fewer roots that its degree or the Forney algorithm will compute an error value of $0$ and the occurrence of either event tells the decider that something is awry. The Reed-Solomon decoder then sends an emergency follow-up signal to the recipient of the purported corrected codeword that something has gone wrong and the codeword just sent out should be discarded, or at least treated with great deal of suspicion. That is why the Reed-Solomon decoder should not correct just the errors in the information symbols only, but should do error-correction on all the symbols. Good decoders need to check that they are not putting out garbage: if the error-locator polynomial has degree $e \leq t$, it better have $e$ roots and the Forney algorithm better compute nonzero error values for all $e$ error locations.

With a well-designed Reed-Solomon decoder, whenever $e > t$, in almost all cases, the decoder will declare a decoder failure: the special emergency signal that the purported codeword just sent out is garbage (the sailor is on the high seas!), and in a very few instances, the decoder will not declare a decoder failure because the number of errors is such that the wrong codeword $\mathbf C^\prime \neq \mathbf C$ has been sent out. Neither the decoder nor the recipient has any way to determine that a decoding error has occurred, whereas with a decoder failure, there is the option for asking for a re-transmission of the mangled codeword. In a well-designed Reed-Solomon decoder, $$P_{\text{correct decoding}} \gg P_{\text{decoder failure}} \gg P_{\text{decoder error}}$$ while poorly-designed run-of-the-mill Reed-Solomon decoders choose not to distinguish between decoder failure and decoder error and just lump both occurrences into decoder error.

Talk of the tail wagging the dog!

Answer 2

There are two variations of Reed Solomon encoding, the original method and the BCH method. Most Reed Solomon implementations use the BCH method, in which case polynomial interpolation cannot be used, since encoding produces codeword that is an exact multiple of a predefined generator polynomial as opposed to a polynomial based on the message to be encoded. The Wikipedia article explains both methods including the encoding and decoding algorithms.

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction