My first real exposure to RS ECC was when I had to reverse-engineer a hardware ECC. There's plenty of material out there, and I spent a significant amount of time reading through various articles, but IMHO the maths/theory really got in the way of understanding what actually happens, i.e. all of them talk about finite fields and polynomials and such, but almost none answered the main question I had: "what does this mean for the bits and bytes I'm looking at?" Furthermore, there is also a scarcity of material discussing RE of RS (i.e. finding the parameters used.)
Eventually I came across https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_f... which was really enlightening, and I wrote some code to essentially bruteforce combinations of generator polynomials and bit/byte ordering --- and luckily discovered the details of the implementation on the first try. (The first polynomial in my list was 0x211, and it was the right one.)
The final implementation turned out to be relatively straightforward, less than 250 lines of C for a correcting decoder including the unusual (but probably trivial/circuit-simplifying) bit permutation/expansion scheme the original hardware used. The core algorithm itself is mostly composed of XORs and table lookups. I believe I used BkM and Forney for the correction part. If anyone is curious, I'll see if I can find and release some of the code I used.
Do you still have that bruteforce code? I've been trying on and off to reverse engineer the RS ECC in Chirp, a (now discontinued) app for sharing tokens over speaker/microphone.
A few references I've found suggest that is RS(9,5) and might not actually be using GF(32); although you have 18 "symbols" of 90 bits total, with 50 bits of data and 40 parity, I doubt those are the actual RS symbols.
In fact, those parameters line up with 9 * 10-bit symbols in each block, 5 10-bit data and 4 10-bit ECC. I would try a shortened RS(1023,1019) in GF(1023), taking pairs of the 5-bit "symbols".
Here is the code I originally used. I was bruteforcing a non-shortened RS(511,503) in GF(511) which had a somewhat complex transformation between bytes and symbols, fortunately partly documented at the time:
A good example of this being implemented is in parchives. Parchives were originally made as a way to recover from errors on unreliable usenet servers, but now I think they are mostly used for bitrot recovery. https://en.wikipedia.org/wiki/Parchive
@nayuki In your Python code, the module 'fieldmath' imports 'numbers'. However it only uses a single reference - 'numbers.Integral'. Did you mean to remove this when you modified the code from your _Gauss-Jordan elimination over any field_ page?
This is why you can scratch a cd-rom and it still works fine. If I recall correctly the version used in cd-roms is an eleventh order (x^11 + x^10...) polynomial.
As someone who can go through algebra and linear math this was wayyyy too heavy me. It was very hard to follow and map it to how to code such an algorithm.
You really need to give a number of examples. Remember human brains are fast example based learners. We see patterns and make abstract concepts out of it. Here the abstract concepts is the crazy math.
Another thing - the linear algebra presented in the article is all at high school or early-university level: systems of linear equations, matrices, row reduction, unique solutions, solution space. It might be heavy in terms of quantity, but I would not consider it to be terribly advanced math.
I think the only part that most students have not seen is the finite field arithmetic, because that knowledge is pretty specialized for people who actually design math for computers to execute.
Sorry about not meeting your expectations. I was planning to make an interactive JavaScript demo in the future to show all the steps of the computation with actual numbers as examples.
For the time being, try running the Python code and adding print statements to the places of interest.
Another example of Reed-Solomon codes in the wild:
RS codes are used in QR codes because they're particularly resistant to localized errors, e.g. a physically-contiguous section of the code becoming damaged or unreadable.
I was motivated to learn Reed-Solomon decoding precisely because it was the only technical aspect of QR Code decoding that I couldn't implement from scratch!
Eventually I came across https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_f... which was really enlightening, and I wrote some code to essentially bruteforce combinations of generator polynomials and bit/byte ordering --- and luckily discovered the details of the implementation on the first try. (The first polynomial in my list was 0x211, and it was the right one.)
The final implementation turned out to be relatively straightforward, less than 250 lines of C for a correcting decoder including the unusual (but probably trivial/circuit-simplifying) bit permutation/expansion scheme the original hardware used. The core algorithm itself is mostly composed of XORs and table lookups. I believe I used BkM and Forney for the correction part. If anyone is curious, I'll see if I can find and release some of the code I used.