reed-solomonforwarderrorcorrection

# Error detection capability using Berlekamp-Massey algorithm

I have implemented `RS( n=1023,k=995 )` with 10 bits in each symbol. To find the error polynomial we are using Berlekamp-Massey(B-M) algorithm. The error detection capability of our code should be `n-k = 1023-995 = 28`. The error correction capability is `(n-k)/2 = 14`. The B-M algorithm works perfectly fine for errors less than or equal to 14. How to determine the number of errors if more than 14 errors occur??( As the correction will fail if the errors are greater than 14). I wanted to know if there is any limitation in this algorithm to find the number of errors. According to theory, RS codes should be able to correctly identify that more than 14 errors have occurred.

Solution

• For RS(n=1023,k=995), the distance is n-k+1 = 29: every valid codeword differs in at least 29 symbols from any other valid codeword. The maximum error detection capability is n-k = 28. The maximum error correction capability is (n-k)/2 = 14.

According to theory, RS codes should be able to correctly identify that more than 14 errors have occurred.

This isn't always true. If there are more than 14 errors, there's some chance that miscorrection will result in a valid codeword, but one that differs from the original codeword by 29 or more symbols.

Consider the case where a received codeword has 15 or more symbols in error, then there is some chance that attempting maximum (n-k)/2 correction may create an additional 14 symbols in error, producing what appears to be a valid code word, but one that differs in 29 or more symbols from the original codeword. Miscorrection can only happen if the received codeword differs by 14 or less symbols from a valid codeword. The probability of this occurring is very low for a 15 error case, but increases as the number of errors increases. Which decoder method is used (P-G-Z (matrix), B-M (discrepancy), or Y-S (extended Euclid)), won't make a significant difference.

The probability of miscorrection can be reduced by reducing the maximum number of errors corrected. Say the error correction is limited to 12 symbols instead of 14, then there is no chance of miscorrection unless there are 17 or more symbols in error.

The odds of miscorrection are also reduced if using a shortened codeword, such as RS(n=511, k=483), where there's a 50% chance that a miscalculated location is outside the range (0 to 511) of valid locations.