Introduction to Reed-Solomon and Berlekamp-Welch
innovation.vivint.com
innovation.vivint.com
Also, Reed Solomon is not a particularly great forward error correcting code. They are optimal as "erasure codes" (i.e, you can lose some data, but the remaining data cannot have changed), but as error correcting codes, LDPC codes / Turbo codes outperform them a lot: e.g. satellite communication (DVB-S2), hard drive error correction all switched to LDPC's.
Visualize a lattice of possible input words: https://people.xiph.org/~greg/temp/lattice.png lets say that we are using a code where the valid codewords (dark dots) are at least 4 moves apart. If you use this code for error correction, you'll take a received word and move to the nearest codeword, but this is only unambiguous if you correct errors at up to half the distance between any two words.
RS codes are optimal in that they achieve the best possible distance for their size (they are MDS codes).
They may not be what you want to use in some applications because of the computational complexity of decoding with errors, or because the application can make use of list decoding which can be more efficiently achieved with other codes, or because they need different sizes in particular, the symbol size constraint with RS is burdensome for many applications.
The symbol size issue is a particular driver for other choices. Say your HDD codes data with 4-bit symbols but to get good performance you want a code that is a whole sector wide. If you use a 10 bit RS code to code in blocks of 10240 bits, then a single 4-bit symbol error potentially corrupts 20 bits of input.
Codes with large input symbols also don't lend themselves well to soft-input. (because instead of propagating around a single 1 or 0 probability you need to propagate around a probability distribution function equal in size to the field). So they're generally much less attractive for noisy channel coding since modems can easily give soft-outputs.
I'll plug mine, too, written in C. https://github.com/quiet/libcorrect
Learning enough about finite fields to implement one is really mind bending. Definitely recommend people try it, or at least make the encoder side
It used lots of table lookups to make things run at a reasonable speed, but the tables couldn't be too big since there was only an 8K EEPROM. The Z80 code only did d=3 codes (so could correct 1 error or detect two).
Working out how to solve a quadratic equation over GF(256) in Z80 assembler was my personal highlight!
The trick here is that because p(1) is the sum of the coefficients, it must also be bigger than any of coefficients, so p(p(1)) is always "safe" to use.
To avoid base conversions, I think you can always use next power of ten for the second value, i.e. p(10^n) where n = floor(log10(p(1)))+1. For example if p(1) = 182, then you could ask p(1000) = 12000140030 or 12 000 140 030, which gives us the coefficients (12x³ + 140x + 30). Arguably easier than trying figure out what 72368326 is in base 182.
EDIT: i cannot read. please ignore :)
Nice
high-performance [...] Reed-Solomon
RS codes, where they exist, achieve greater distance than BCH codes... but they have a far more restricted set of parameters than BCH codes.
Many applications are moving to things other than BCH codes because even though they are a much better class than RS codes they are still limited and the existing BCH codes at many sizes are not as good as other kinds of codes.