3
$\begingroup$

I know that Reed-Solomon codes of the form $(N,N-2t)$ can correct up to $t$ errors, and detect up to $2t$ errors, but I've only seen the correction procedure: Berlekamp-Massey or Euclidean to get the error-locating polynomial $\Lambda(x)$, then the Chien search to find its roots, then the Forney algorithm to find the error coefficients.

If I am told that there are at most $2t$ errors, is there a way to unambiguously tell how many errors $e$ there are? Or at least distinguish between the case of $e \le t$ (correctable errors) and $t < e \le 2t$? Is it just a matter of determining the degree of $\Lambda(x)$? Somehow that doesn't seem right, because then finding the roots of $\Lambda(x)$ would tell me where they were, and then I could correct them.

I'm confused, because both the Berlekamp-Massey and Euclidean algorithms appear to find polynomials of degree $2t$ or less -- for Berlekamp-Massey it's mentioned in Blahut's book, and for the Euclidean algorithm it's $\Lambda(x)S(x) + Q(x)x^{2t} = \Omega(x)$ for known syndrome polynomial $S(x)$.

$\endgroup$
  • 1
    $\begingroup$ I believe it is impossible to tell how many errors there are. Consider the simple Hamming (7,4) code. If there are 4 errors, the received codeword is indistinguishable from one with only 1 error. I think the same limitation applies to RS codes. $\endgroup$ – MBaz Jun 2 '18 at 22:19
  • $\begingroup$ Hamming codes are perfect, RS codes are not $\endgroup$ – Jason S Jun 3 '18 at 13:15
  • 1
    $\begingroup$ I don't think that invalidates the intuition provided by Hamming codes, but I'd be happy to be corrected. $\endgroup$ – MBaz Jun 3 '18 at 17:01
3
$\begingroup$

The Berlekamp-Massey algorithm and the extended Euclidean algorithm (both further extended with the Chien search and the Forney calculation of error values) for decoding BCH and RS codes (hereinafter referred to as the decoder) have the following characteristic that is not well understood by many people:

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 more errors) with high probability the $\hat{\mathbf C}$ that the decoder finds is indeed the transmitted codeword $\mathbf C$.

But the question is what happens when there have been more than $t$ errors. Can such an occurrence be unambiguously detected? The answer is NO for the reasons described above: the decoder may well find a $\hat{\mathbf C}$ that is different from the transmitted codeword $\mathbf C$ exactly as the decoder is designed to do because $\hat{\mathbf C}$ is at distance $\leq t$ from $\mathbf R$ and the poor schmuck of a system designer will have no idea that s/he has just bought a pig in a poke. Once again, probability comes to the rescue. In the (fairly unlikely) event that more than $t$ errors have occurred, it is very much more often the case that the decoder fails to decode in several possible ways (which may or may not be detected by the system designer depending on how many safeguards have been built into the system) than that the decoder produces an incorrect codeword.

The Berlekamp-Massey algorithm or the extended Euclidean algorithm find an error-locator polynomial $\Lambda(z)$ of degree $e$ and an error-evaluator polynomial $\Omega(z)$ where the inverse roots of $\Lambda(z)$ (as found by the Chien search) are the $e$ error locations and the Forney error-evaluation formula gives the error values at these $e$ error locations. When more than $t$ errors have occurred, it is usually the case that $\Lambda(z)$ has fewer than $e$ roots and/or that the Forney error-evaluation formula returns a zero error value at a purported error location that the Chien search has found. Both of these conditions indicate that something is awry but testing for these conditions is expensive in hardware implementations and time-consuming in software implementations. The simplest test for detecting a decoder failure is to let the Chien search and Forney formula do their jobs, and the recompute the syndrome of whatever the decoder spits out. If the recomputed syndrome is zero, then the decoder output is a valid codeword - whether it is $\mathbf C$ or an impostor $\hat{\mathbf C}$ is unknown - but if the recomputed syndrome is nonzero, then the system designer knows that the decoder output is not a valid codeword and that the decoder has actually failed to decode. But again, such a test is expensive to implement and very often skipped by system designers who know about it, and, of course, not even thought about by those who don't know of the possibility of decoder failure that can be detected.

For a well-designed RS decoder system, it is the case that $$P_{\text{decoder output correct}} \gg P_{\text{decoder failure}} \gg P_{\text{decoder output incorrect}}.$$ The decoding spheres (the set of vectors or possible received words $\mathbf R$ that are at distance at most $t$ from some codeword and thus lead to a successful decoding, whether correct or incorrect) have very small total volume and so it is far more likely than not that when more than $t$ errors have occurred, $\mathbf R$ is not in any of the decoding spheres, and the decoder will fail to decode and spit out garbage. Whether it is worthwhile detecting such failures is up to the system designer. It is sometimes the case that $1-P_{\text{decoder output correct}}$ is a perfectly acceptable word error rate and so ignoring decoder failure is an option, but in high-performance systems where very low error rates are required, detecting decoder failure and asking for a re-transmission of a codeword that was badly munged up in transmission allows the achievement of the desired low error rates at the expense of increased delay.

$\endgroup$
  • $\begingroup$ insightful + made me laugh -- thanks! So it all boils down to Hamming distance arguments. Is there any simple way to calculate probability of false positives for exactly $t+1$ errors if all error patterns are equally likely? (Would a Monte Carlo simulation based on the all-zero codeword give me any useful information? that is, create $t+1$ errors, put into RS decoder, see whether it gives me the all-zero codeword, gives me an error, or corrects to a different codeword?) $\endgroup$ – Jason S Jun 4 '18 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.