I am setting up a Reed Solomon library to correct AND detect errors as the come in. For simplicity lets look at a Reed Solomon configuration where
- m(symbol size) : 8 [GF(256)]
- k(user payload) : 2
- 2T(parity symbols): 2
Yielding a transmitted payload of 4 octets.
This can correct any 1 symbol error and, the purpose of this post, it can DETECT 2 symbol errors. There is limited literature on the error detection of RS, however just for a cursary source you can check the introduction in the wikipedia article: https://en.wikipedia.org/wiki/Reed-Solomon_error_correction
By adding t check symbols to the data, a Reed–Solomon code can detect any combination of up to and including t erroneous symbols, or correct up to and including ⌊t/2⌋ symbols.
However this doesnt seem to match my observations.
I have a library, primarily built from https://en.wikiversity.org/wiki/Reed-Solomon_codes_for_coders which from what I can tell works very well. I set up a exhaustive test surrounding our implementation and found a case where there are 2 symbol errors (which from what I understood should be DETECTABLE) however it is not. From what I understand, a simple checok to see if an uncorrectable error occurred which passes the normal checks (i.e. the error locator is valid, find errors has a valid error count, polynomial degree is valid) is to recalculate the syndromes for the corrected message. If the syndromes are non zero then we still have an error. However when I do this the syndromes are all 0, suggesting no error is found and that we have a collision between an error vector with 1 erroneous symbol, and an error vector with 2 erroneous symbols.
This is the test:
# Create Message
msg_in = [0x10,0x2f]
# Append RS FEC codes
msg_enc = rs_encode_msg(msg_in)
# Apply Error
errVec = [0,0x2b,0,0xea]
for i,err in enumerate(errVec):
msg[i] ^= err;
# Decode
# Syndromes
synd = rs_calc_syndromes(msg)
# Error Locator
err_loc = rs_find_error_locator(synd)
# Error Positions
pos = rs_find_errors(err_loc)
# Correct
msg = rs_correct_errata(msg, synd, pos, err_loc)
#Calculate syndromes again
newSynd = rs_calc_syndromes(msg)
Output:
Message
0x10 0x2f
Encoded Message
0x10 0x2f 0x1 0x3e
Encoded Message With Errors
0x10 0x4 0x1 0xd4
Syndromes
0xc1 0x46
Error Locator
0x8 0x1
Error Position
0x00 # The first position
Corrected Message
0xd1 0x4 0x1 0xd4
Recalculated Syndromes
0x0 0x0
If you are still reading, thank you. I know I have no provided the entire library, but I did provide the inputs, and outputs, and key variable values. What I want to know is if my understanding written above is wrong; that we can DETECT 2T symbol errors where 2T is the amount of added symbols. Because from this test case it seems there is a collision, I test this further by just calculating the syndromes across the following error vectors which further supports a collision and that Reed Solomon CANNOT NECESSARILY DETECT ALL errors up to 2T. Let me know if I am wrong.
error vector: 0xc1 0x0 0x0 0x0
yielding syndrome: 0xc1 0x46
and
error vector: 0x0 0x2b 0x0 0xea
yielding syndrome: 0xc1 0x46
Has a collision
I understand now. It’s not: T symbols of error correction AND 2T symbols of error detection. It’s T symbols of error correction OR 2T symbols of error detection. T symbol errors have unique syndromes where 2T are not unique but are non zero. The uniqueness makes it correctable , the non zero makes it detectable. So you cannot both correct T errors and detect 2T because many (in this case about 4000) of the syndromes for T errors is also the syndrome for 2T, and there is no way to differentiate if you should try and correct for a single error, or if you should flag it as an uncorrectable error.
Thanks everyone.