Reed-Solomon detection capability

Question

I am interested on the analysis of the Reed-Solomon capabilities for detection (detection only, when correction is not possible), in particular for RS(10,8), with symbol 8 bits, 10 symbols total in a codeword, out of which 8 are for data and 2 for ECC. In this case the Reed-Solomon code should be able to correct 1 symbol with multiple errors, but in the literature I don't find much information on the error detection capability (with no correction), for example with 2 errors in 2 different symbols the RS should be able to detect but not correct.

I would like to do some Montecarlo analysis in Python, I have found this package for Reed-Solomon: https://pypi.org/project/unireedsolomon/

the python package allows me to create the RS code, inject error and decode with correction, but it does not seem to provide detection capability, I tried to inject 2 errors in two different symbol and I get a miss-correction, I believe that in this case the Reed-Solomon should be able to report an error that cannot be corrected. The unireedsolomon package does not seem to have implemented such detection capability, or maybe I am wrong. Do you know if such capability exist in the unireedsolomon package?

Or do you have suggestions on how I can run such detection only analysis maybe with a different python package? Or any comment about the detection in the Reed-Solomon code would be useful too. Thank you

Answer 1

The Reed-Solomon code RS(10,8) has d_min = n-k+1 = 3 minimum distance. A code with minimum distance d_min can correct t = floor((d_min-1) / 2) symbol errors or detect d_min-1 symbol errors. So the code you described can detect 2 symbol errors.

The algebraic structure of the code ensures that all valid codewords with d_min-1 or fewer errors will result in a syndrome not equal to zero (which is the indicator there are errors).

I created a Python package galois that extends NumPy arrays over Galois fields. Since algebraic FEC codes are closely related, I included them as well. Reed-Solomon codes are implemented, as well as a detect() method.

Here is an example of the RS(10,8) code using galois. In my library, shortened codes RS(n-s,k-s) are used by first creating the full code RS(n,k) and then passing k-s message symbols into encode() or n-s symbols into decode() or detect().

In [1]: import galois                                                                                   

# Create the full code over GF(2^8) with d_min=3
In [2]: rs = galois.ReedSolomon(255, 253); rs                                                           
Out[2]: <Reed-Solomon Code: [255, 253, 3] over GF(2^8)>

# The Galois field the symbols are in
In [3]: GF = rs.field                                                                                   

In [4]: print(GF.properties)                                                                            
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: x^8 + x^4 + x^3 + x^2 + 1
  is_primitive_poly: True
  primitive_element: x

# Create a shortened message with 8 symbols
In [6]: message = GF.Zeros(8); message                                                                  
Out[6]: GF([0, 0, 0, 0, 0, 0, 0, 0], order=2^8)

# Encode the message into a codeword with 10 symbols
In [7]: codeword = rs.encode(message); codeword                                                         
Out[7]: GF([0, 0, 0, 0, 0, 0, 0, 0, 0, 0], order=2^8)

# Corrupt the first 2 symbols
In [8]: codeword[0:2] = [123, 234]; codeword                                                            
Out[8]: GF([123, 234,   0,   0,   0,   0,   0,   0,   0,   0], order=2^8)

# Decode the corrupted codeword, the corrected errors are -1 (meaning could not correctly decode)
In [9]: rs.decode(codeword, errors=True)                                                                
Out[9]: (GF([123, 234,   0,   0,   0,   0,   0,   0], order=2^8), -1)

# However, the RS code can correctly detect there are <= 2 errors
In [10]: rs.detect(codeword)                                                                            
Out[10]: True

Answer 2

RS(10,8) is guaranteed to detect any 2 errors or correct any single error, but not both. With 2 errors and only 10 symbols in codeword, most of the time it should detect a 2 error case is uncorrectable, but there is a small chance that depending on the 2 error values and locations, that it will appear as if there is a single error at a third location, and the correction process will mis-correct, producing a valid codeword (both syndromes == 0), but one that differs from the original codeword at 3 locations. The probability of 2 errors in 10 symbols resulting in this type of mis-correction is low, about .00001538.

If the unireedsolomon package has a higher mis-correction rate, I suspect that it's not eliminating locations outside the range of the 0 to 9 valid locations for a 10 symbol codeword, and is producing an invalid codeword due to a bad mis-correction.