How can i construct RS code which can detect and correct errors.
E.g, I would like to construct RS(76,64,8), where
I could easily construct 6 symbol correcting code, using pyfinite python library (https://pypi.org/project/pyfinite/).
I am also interested in constructing - a different variant - which can provide 8 symbol detection OR 4 symbol correction using the 12 check symbols.
Is there a reason you can't use the python pyfinite code to handle the cases you want?
If interested, I have an old interactive RS ecc demo written in C. The user selects 1 of 30 possible GF(2^8) fields, some parameters about the RS generator polynomial, number of parity bytes (a define limits this to 20, but it can be changed), number of data bytes. Then the use can enter data, encode data, change data, change data and mark as erasure, fix data, ... . The code includes the 3 common decoders, PGZ matrix inversion, Berleykamp Massey discrepancy, Sugiyama's extended Euclid algorithm. The Euclid decoder is similar to a hardware implementation (emulating a pair of shift registers), since it was used to assist a hardware team implementing RS code back in the 1980's. I used Visual Studio to compile it, but there shouldn't be much issue with other compilers. It's too large to post directly in this answer, so here is a link to a zip file, that includes the source code and a readme.txt file:
http://rcgldr.net/misc/eccdemo8.zip
With 12 parities, RS code can correct up to 4 errors while still detecting 8 errors. Assume the worst case non-failing scenario of 8 errors. The code calculates the wrong 4 locations for errors, resulting in a total of 12 errors, the 4 mis-corrected errors plus the existing 8 errors. This can never fail because the Hamming distance between any two valid codewords is 13 bytes. For an example failure case, there could be 9 errors, the code calculates the wrong 4 errors, resulting in a total of 13 error for a possible mis-correction (which will create a valid codeword, but the wrong codeword).
To check for up to 8 errors after calculating up to 4 errors locations, the generated error locator polynomial should be verified using all 12 syndromes. This is done at line 871 in GenPErrorsE(), the Sugiyama extended Euclid decoder. That check could also be included in the other 2 decoders, but since the demo program calls all 3 decoders, it's not needed. Note that if the decoders calculate 6 errors, then it will always produce a valid codeword, but possibly the wrong codeword if there are actually 7 or more errors. The simplest fix to handle this in eccdemo8.c is to limit the number of errors to <= 4, which only requires inserting 4 lines of code at line 204:
GenForneyErr(); /* generate forney err values */
/* insert this code to limit to 4 errors */
if(vOffsets.size > 4){ /* limit to 4 errors */
printf("uncorrectable, > 4 errors\n");
return;
}
printf("vLocators: ");
There's also another type of Reed Solomon code referred to as "original view" (versus the more common "BCH" view). For a RS(n,k) code, decoding operates on n symbols, while "BCH view" decoders operates on n-k symbols (syndromes), making "BCH view" significantly faster than "original view". Some erasure only codes, are based on "original view", but the most common case is Raid 6, which generates "BCH view" syndromes (yet another approach, the syndromes are not part of a "codeword"). The Wiki article explains this:
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction