0
$\begingroup$

According to the Reed-Solomon Wikipage, the RS code can correct up to $\lfloor\frac{t}{2}\rfloor$.

While I was playing around with Reed-Solomon FEC (github repo), I noticed that sometimes the RS(544, 514, t=30, m=10) can correct more than 15 symbol errors. Based on the wiki page above, this RS coding scheme should be able to correct only up to 15 symbol errors. However, I observed that this RS code could sometimes correct 16~18 symbol errors (but not always!).

Now I am curious why this is happening in RS code and what would be the most intuitive way to understand this phenomenon. I would greatly appreciate it if anyone could share your knowledge about this issue.

$\endgroup$

1 Answer 1

2
$\begingroup$

Beware: what you're seeing could be the result of a bug in your code.

Having said that: in general, algebraic codes such as BCH and RS are very hard to decode using algebraic algorithms. Practical decoding algorithms are called "minimum distance decoders": they guarantee they can correct a certain number of errors (15 in your case), but they do not guarantee that they cannot correct a greater number. This constraint makes the decoding problem tractable.

Note that almost all codes have the potential to correct more errors than the minimum-distance alone would indicate. Only "perfect codes", of which there's only a handful, have the property of not being able to correct more than $\lfloor t/2 \rfloor$ errors.

In other words, practical decoders for algebraic codes leave a lot of performance on the table, and that is part of the reason these codes have been out of fashion for a while. I highly recommend reading McKay's book on information theory (available online for free) and also this website for an astonishing recently-developed decoder: https://www.granddecoder.mit.edu/

$\endgroup$
3
  • $\begingroup$ Thanks a lot for the book recommendations and this nice-looking GRAND decoder. I will check this out. I still do have some questions about the mystery about correcting more than t/2 errors: I understand that the practical decoding algorithm is minimum distance decoder in the codeword space. However, if I have more than t/2 errors, this means that the received (and corrupted) codewords will be more close to the other codewords than what it was sent originally. This is why I was not sure how can a RS decoder can correct greater than t/2 sometimes... $\endgroup$
    – Emm386
    Commented Jan 6, 2023 at 18:34
  • 1
    $\begingroup$ The minimum distance is the "worst case", but the weight distribution is not necessarily uniform in all codes. Consider a code with three elements: "000000", "000001", and "111111". The minimum distance is 1, but the error pattern "110000" can be corrected: the word closest to "001111" is "111111", the word closest to "110000" is "000000", and the word closest to "110001" is "000001". Not all error patterns with more errors than floor(t/2) can be fixed, but some of them can. This particular example is extreme, but the same thing happens in all non-perfect codes. $\endgroup$
    – MBaz
    Commented Jan 6, 2023 at 20:00
  • 1
    $\begingroup$ thanks a lot for detailed explanation ! $\endgroup$
    – Emm386
    Commented Jan 7, 2023 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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