Reed-Solomon algorithm is adding an additional data to the input, so potential errors (of particular size/quantity) on such damaged input can be corrected back to the original state. Correct? Does this algorithm protects also such added data not being part of the input, but used by the algorithm? If not, what happened if the error occurs in such non-input data part?
Asked
Active
Viewed 235 times
2 Answers
2
An important aspect is that Reed-Solomon (RS) codes are cyclic: the set of codewords is stable by cyclic shift.
A consequence is that no particular part of a code word is more protected or less protected.
A RS code has a error correction capability equal to t = (n-k)/2, where n is the code length (generally expressed in bytes) and k is the information part length.
If the total number of errors (in both parts) is less than t, the RS decoder will be able to correct the errors (more precisely, the t erroneous bytes in the general case). If it is higher, the errors cannot be corrected (but could be detected, another story).
The emplacement of the errors, either in the information part or the added part, has no influence on the error correction capability.
EDIT: the rule t = (n-k)/2 that I mentioned is valid for Reed-Solomon codes. This rule is not generally correct for BCH codes: t <= (n-k)/2. However, with respect to your question, this does not change the answer: these families of code have a given capacity correction, corresponding to the minimum distance between codewords, the decoders can then correct t errors, whatever the position of the errors in the codeword
Damien
- 4,809
- 4
- 15
- 20
-
Original view Reed Solomon codes may not be cyclic. They aren't used much though. Take a look at [Wiki article](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction) . Also shouldn't that be correction of errors is possible if total number of errors is less than or equal to `t = (n-k)/2` (note that this does not depend on a RS code being cyclic). – rcgldr May 06 '20 at 20:48
-
@rcgldr All RS codes I have met in my too long carreer of researcher in telecommunications were cyclic. But in practice, it is not so important to answer OP question – Damien May 07 '20 at 16:28
-
The original view RS (where the the encoding can be based on a Vandermonde matrix) code is not as popular as BCH view RS (which is cyclic), and you may have never seen an example of it. Original view RS was recently brought up in [this question and answer](https://stackoverflow.com/questions/59929677), where the set of evaluation points = {0,1,2,3,4,5}. If the set of evaluation points were successive powers of the field primitive, {1, , ^2, ^3...}, then it will be cyclic, but that choice of evaluation points excludes zero, and reduces the maximum length codeword by 1. – rcgldr May 07 '20 at 19:49
-
My point here is that "no particular part of a code word is more protected or less protected" can also be true for non cyclic codes. This doesn't conflict with the statement that if a code is cyclic, then "no particular part of a code word is more protected or less protected". – rcgldr May 07 '20 at 20:46
1
As long as only half or less of the added data is in error, then errors that are only in the added data can be corrected.
With the appended data, the data + appended data form what is called a codeword, one that meets the rules for a codeword. Note there are two basic types of Reed Solomon code, the "original view" and the "BCH view". What constitutes a valid codeword depends which type of Reed Solomon code is being used. Link to Wiki article that explains this:
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
For an erasure only code, the location of all errors is determined by other means, and this case, even if all of the appended data is known to be bad, it can be corrected (or regenerated).
rcgldr
- 27,407
- 3
- 36
- 61
-
There is no difference between syndromes and reminders. Only terminology – Damien May 07 '20 at 05:27
-
@Damien - I removed the reference to syndromes in my answer, since Raid 6 doesn't generate true codewords. Parties and syndromes are not the same, and original view RS code doesn't involve syndromes at all. For BCH view RS, for p parities, the parties are the remainder of division of a message by the generator polynomial, while each syndrome is the remainder of a message by each factor of the generator polynomial. It's is possible to use matrices to map between parities and syndromes. – rcgldr Jun 02 '20 at 19:55