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.

- Error correcting code
- Reed Solomon Decoding - Error Correction - Syndromes Calculation
- Estimate BER of QPSK in AWGN with Reed-Solomon (240,224) Coding
- How to efficiently create generator Matrix using Reed-Solomon encoding
- Can the Euclid algorithm be used to do Reed Solomon decoding for the more general case where b > 1 in WHP 031?
- Differences Between Systematic Reed Solomon Encoding Methods
- 'UTF-8' decoding error while using unireedsolomon package
- Welch-Berlekamp Algorithm for Reed Solomon code as nonbinary BCH code
- How to apply Reed-Solomon algorithm using zxing in C#
- Error correction on small message (8-Bit) with high resilience, what is the best method?
- Reed-Solomon detection capability
- Reed-Solomon Code for large code length and errors
- CDROM, F2 Reed-Solomon P Q codes in CIRC encoder
- Reed solomon how many missing bytes can be corrected?
- Why error-only decoding has high miscorrection rate for small parity?
- Berlekamp-Massey Algorithm not working for Syndrome's Least significant Symbol being 0
- Construction of Reed Solomon - detection and correction
- Can you please explain Reed Solomon encoding part's Identity matrix?
- Does Reed-Solomon Error algorithm allow correction only if error occur on input data part?
- Use of Reed-Solomon error correction algorithm with 4-state barcodes
- What is the value of the ideal value of the generator polynomial index in the Schifra library for Reed-Solomon error correcting code?
- QR code generation algorithm implementation case analysis
- Reed Solomon Error DETECTION capability is not 2T
- Encoding image, using reed-solomon coder
- Reed Solomon error correction for QR-Code
- CCSDS Reed Solomon Encoding
- Addition and multiplication in a Galois Field
- Errata (erasures+errors) Berlekamp-Massey for Reed-Solomon decoding
- Reed solomon error correction and false positives
- Error detection capability using Berlekamp-Massey algorithm