I have a Reed-Solomon encoder/decoder. After manipulating data and evaluating the results, I have experienced the following 3 cases:
Are all 3 cases valid for a proper Reed-Solomon decoder? I am especially unsure about case 2, where the decoder would produce a wrong result (without throwing an error), even if there are much fewer errors than what is allowed by its correction abilities...?
- mis-correction below error correction ability
This would indicate a bug in the code. A RS decoder should never fail if there are less than ⌊(n-k)/2⌋ errors.
- correction detects when there more errors then error correction ability
Even if there are more than ⌊(n-k)/2⌋ errors, there is a good chance that a RS decoder will still detect an uncorrectable error, as most error patterns would not result in a received codeword that is within ⌊(n-k)/2⌋ or fewer error symbols of a valid codeword, since a working RS decoder should only produce a valid codeword or indicate an uncorrectable error. Miscorrection of more than ⌊(n-k)/2⌋ errors involves the decoder creating an additional ⌊(n-k)/2⌋ or fewer error symbols, resulting in a valid codeword, but one that differs from the original by n-k+1 or more symbols.
Detecting an uncorrectable error can be done by regenerating syndromes for the corrected codeword, but it's usually caught sooner when solving the error locator polynomial (normally done by looping through all possible locator values), when it produces fewer locators than it should due to duplicate or missing roots.
I wrote some interactive RS demo programs in C, for both 4 bit and 8 bit fields, that include the 3 most common decoders (PGZ (matrix), BM (discrepancy), SY (extended Euclid)). Note the SY - extended Euclid decoders in my examples emulate a hardware register oriented solution, two registers, always shift left, each register holds two polynomials where the split shifts left along with the register. The right half of each register is reversed (least significant coefficient first). The wiki article example may be easier to follow.