Reed-Solomon detection capability

0
votes

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

2
pythonerror-detectionreed-solomon
This isn't really my area of expertise, but my understanding is that the error detection and correction abilities of Reed-Solomon are mutually exclusive. You can detect errors up to a certain size, but you cannot tell just how big the error was - if it was over half of the detectable size, it wouldn't be correctable, but the attempt to do so might appear to be successful. Or in other words, correction only works if you assume that no error is over the correctable size limit. - jasonharper
I updated my answer for the question's specific case. With only 10 symbols in a codeword, it would be relatively rare for a 2 error case to appear to be a valid one error case at a third location, since all three locations would have to be in the range 0 to 9. - rcgldr

2 Answers

0
votes

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.

0
votes

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