How to detect errors for Reed-Solomon Code?

2
votes

I am using (7,5) Reed-Solomon Error Correction Code.

I think I can decode "correct 1 error" or "find 2 error position".

However, there is a problem. My code can not find 2 error position.

For example, the message is 1 3 5 2 1 and RS parity is 0 5. So RS code is 0513521.

After then, there are two errors at parity part. So code is changed to 1113521.

I want to find these two errors, but my decoder said the answer is 1113621.

What should I do?

1
decodingreed-solomon
As you corrupt more and more bytes you can get false positives where the decoder not only doesn't detect the corrupted bytes but actually confirms that the incorrect code is correct. This makes sense when you consider that there are many possible valid message/parity combinations for a given number of bytes; you can only change so much of your RS code before you skip over into another valid combination. – 101
I've found it useful to tune the number of error bytes required for robust message encoding by doing a large number of encode/decode runs and checking the false positive rate. There's obviously a trade off between error check bytes required and reliability. Tune it so there is a decent window where you will get no false positives, even if the message can't always be decoded. – 101
We need to see the code to help you. – deviantfan

1 Answers

1
votes

RS(7,5) can correct 1 error or detect up to 2 errors, but not determine the position of the 2 errors. In a two error case, there are multiple combinations of 2 error values and 2 error locations that produce the same 2 syndromes. Using your example, the two error cases 1113521 (errors in locations 0 and 1) and 0463521 (errors in locations 1 and 2) produce the same result: syndrome_1 = 4 and syndrome_2 = 6, and there's no way to determine where the errors are, only that they exist.

As commented, if a 1 error correction is attempted in a 2 error case, it's possible for the decoder to mis-correct and create a third error, in order to create a "valid" codeword, in this case it created 1113621. I got the same result with a test program I have.

The question is missing information, based on the example, it's using GF(8) = GF(2^3), modulo x^3 + x^2 + 1 (hex d), and the generator polynomial = (x-2)(x-4) = x^2 + 6 x + 5. Note for GF(2^m), addition and subtraction are both xor. The data is displayed least significant term first, so 0513521 = 0 + 5x + 1x^2 + 3x^3 + 5x^4 + 2x^5 + 1x^6.