error-correctionreed-solomonforwarderrorcorrection# Reed solomon error correction and false positives

I have a Reed-Solomon encoder/decoder. After manipulating data and evaluating the results, I have experienced the following 3 cases:

- The decoder decodes the message correctly and does not throw an error
- The decoder decodes the message to a wrong result, without complaining - effectively producing a false positive. The chance should be very low, but can happen, even if the number of manipulated data is far below the error correction ability (even after changing a single bit...)
- The decoder fails (throws an error), if more data is manipulated, than what is allowed by its error correction ability.

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...?

Solution

- 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.

- Implementing an extended Hamming code encoder
- Error correcting code
- How to determine LDPC generator matrix from parity check matrix (802.16e)
- Java: ECC (error correcting code) library?
- The Go Programming Language book example server2 is wrong?
- Error correcting codes
- Cyclic Redundancy check : Single and double bit error
- Bonferroni correction of p-values from hypergeometric analysis
- How to find the incorrect movement in pose estimation
- Error correction on small message (8-Bit) with high resilience, what is the best method?
- Compile liberasurecode (missing libshss.so)
- How do i return more than one result from this if the input have similar value
- how to correct single bit error with CRC?
- Is it possible to do rudimentary error correction with CRC?
- Difference between BCH code in MATLAB and python
- Reed solomon how many missing bytes can be corrected?
- Parity check matrix of LDPC encoder and decoder in Matlab
- Calculate correction factor in Python
- Why error-only decoding has high miscorrection rate for small parity?
- My code to find all pairs of numbers such that x^y > y^x producing the wrong output
- 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
- How to make v-for drop-down text with a function?
- Is it possible to read a QR code's error correction value from iOS?
- Cannot convert string to char in c++?
- No matter if the condition is true if always executes in c++
- Search a copied value MACRO
- Correcting consecutive errors in time series
- 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