CODEWITHSUNDEEP
algorithmerror-handlingerror-correctionreed-solomongalois-field
Ωmega
Ωmega

Reputation: 43673

Does Reed-Solomon Error algorithm allow correction only if error occur on input data part?

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?

Upvotes: 1

Views: 385

Answers (2)

rcgldr
rcgldr

Reputation: 28826

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

Upvotes: 1

Damien
Damien

Reputation: 4864

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

Upvotes: 2

Related Questions