I've found that, just as with CRCs, there's an abundance of articles that show the theoretical explanation of RS, but aren't much help for those wanting to actually implement it. Here's a good practical explanation of implementing RS, including the GF operations: <a href="https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders" rel="nofollow">https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_f...</a>
Using Reed-Solomon coding to recover from erasures (at known positions) is relatively straightforward. It can be understood with a basic knowledge of linear algebra and finite field arithmetic.<p>Using RS for error correction (at initially unknown positions) is quite difficult. I wrote a step-by-step guide on it including demo code, and it doesn't even cover the most efficient decoding algorithm (I used PGZ instead of Berlekamp-Massey): <a href="https://www.nayuki.io/page/reed-solomon-error-correcting-code-decoder" rel="nofollow">https://www.nayuki.io/page/reed-solomon-error-correcting-cod...</a>
I implemented the RS encoder that ended up being used on the production satellite bus for the telemetry system in space systems / Loral upgraded bus during my engineering coop in school! All in verilog. It's complicated especially the decoder but understandable with time. The turbo codes and more modern extensions that enable lte / 5g and other low power / small antenna applications are absolute black magic though. Such a cool field!
This is also the essence behind Shamir's Secret Sharing
where the sample at x=0 is a secret shared by k+t parties
any k of which can recover the secret.<p>[1] <a href="https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing" rel="nofollow">https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing</a>
There are many types of Reed-Solomon codes, each with different amount of redundancy, they are a special case of BCH codes, a kind of code that approach the Shannon limit (the maximum rate of error-free data that can be transferred over a noisy channel). The bandwidth of a channel (like radio, or optical fiber) is not really limited by the media, but only by the noise it has. Optical fiber have almost zero noise, that's why they are so fast.<p>There are much better codes nowadays that are closer to the Shannon limit, like LDPC, or convolutional codes. But they are usually much more computationally intensive. They are used in space probes where computation time don't matter, but you often have channels with much more noise than signal.<p>I keep a repo of C implementation of several error-correction codes including Reed-Solomon, that can be used as standard unix filters like gzip: <a href="https://github.com/ortegaalfredo/eccchain" rel="nofollow">https://github.com/ortegaalfredo/eccchain</a>
Shameless plug of my own explanation on how binary fields work:<p><a href="https://vitalik.ca/general/2019/05/12/fft.html" rel="nofollow">https://vitalik.ca/general/2019/05/12/fft.html</a><p>Ctrl+F for "binary fields".
I think my first exposure to this was parchive files from usenet. That feeling when your 3-month download of some "huge" 700MB iso was corrupt, you load up quickpar and suddenly (quite a few minutes later) it's all fixed! No idea how it worked at the time, just magic.
Some additions, as "exercise for the reader":<p>1. The finite field you choose has a minimum size. What is the minimum size field 2^bits for an RS(N,K) coding system? What happens when you try to construct a Reed-Solomon code with a finite field that is too small?<p>2. Consider a Reed-Solomon coding system which uses a lookup table for the finite field multiplication operation that fits in L1 cache. Given that the table already fits in L1 cache, how could you make the encoder/decoder faster, if you had a smaller finite field?
On its two Voyager missions, NASA used (still uses!) a RS encoder/decoder that can correct up to 16 error bits per frame. It became a standard for a number of subsequent missions. This was in an era before ASICs and FPGAs yet the hardware still had to meet strict size, weight, and power requirements. Not to mention maintaining comms over distances greater than 14 billion miles and received signal strengths of 10^-16 watts. Truly humbling.
I think Reed-solomon should be considered in future network protocols designs to combat censorship. Every byte should be demuxed into bits and transferred in independent data streams, so MITM boxes can only intercept incomplete streams, and aggregate streams back to original would be insanely difficult. Let transport layers do only one job and no distinguish whatever the content might be inside.<p>Currently H2 does support M:N stream muxing but popular browsers only support N:1 mode.
I really wish physical and OS network stacks would be able to give you the ability to send uncorrected bit streams. That way you can tune the error rate at the application level that makes sense. For example, with video streaming, you probably don’t need much error correction on the data stream as periodic i-frames would correct any transient glitches (you’d only bother to EC the control headers for the video). Then WiFi networks maybe wouldn’t have to be as careful about time multiplexing all the coex streams and some noise due to conflicts would be fine and not require retransmission (because the application layer could handle it).<p>This does come with tradeoffs (eg it may take your application longer to recover from the noise than a quick retransmit at the physical layer).<p>From a cost perspective it’s also maybe impractical because the computer industry gets efficiency gains by solving a problem for everyone at some quality threshold by giving up optimality for applications that could do something with it. Also you would still need to correct the control layer of the network (IP + MAC) just to make it work at all so it may be a wash (ie the incremental cost of correcting the data vs control + data may be insignificant).<p>Still, at least having the option as a switch that could be flipped for experimentation purposes would be quite neat to allow the curious to find new techniques / layers of abstractions vs what’s orthodoxy today.
Reed-Solomon is the foundation of today's computing. It is used in data storage (hdd, ssd) and in data transfer protocols. It allows for building of a reliable system on top of an unreliable real life fenomens with desired level of certainty. This is so incredible tech that once implemented we can just forget about it in the higher level abstractions.