This is, for example, how Amazon S3 works.
It's also how GCS (and the underlying Colossus system) works.
The essence of Reed-Solomon coding
21–30 of 44 posts
Re: The essence of Reed-Solomon coding
#22I 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…
This is already done by many audio/video chat compression algorithms which use UDP. The idea being that with something like voice or video, if a packet doesn’t arrive, instead of stalling everything while you wait for a retransmit, you instead just carry on regardless. The occasional missing packet in voice is almost imperceptible, however the more packets that get lost the more the voice seems to “break up”. With vi…
Most engines I've seen will delta all the entity states against the client's last acknowledged state. Costs some memory and computation on both sides to keep the deltas valid, but keeps the state update to under an MTU, generally.
Re: The essence of Reed-Solomon coding
#23I 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…
This is already done by many audio/video chat compression algorithms which use UDP. The idea being that with something like voice or video, if a packet doesn’t arrive, instead of stalling everything while you wait for a retransmit, you instead just carry on regardless. The occasional missing packet in voice is almost imperceptible, however the more packets that get lost the more the voice seems to “break up”. With vi…
I think the ask is for something like let a bit flip inside the UDP packet or let a byte fall out of the UDP packet. The integrity of UDP packets is still checked for (at different layers).
For most networks the error rate is so low that I don't think it's that valuable. Also you'd still want your metadata checked otherwise it'll get potentially delivered to the wrong place.
Re: The essence of Reed-Solomon coding
#24Using 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. 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…
Is there a resource which lists out different codes and the decoding algorithms that work with them?
Re: The essence of Reed-Solomon coding
#25Using 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. 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…
Usually, you would see RS used in a setting where any error is going to be erasure (non erasure error -> failed checksum -> erasure error).
Then you use something like LDPC codes for in-packet ECC. RS for multi-packet ECC.
Re: The essence of Reed-Solomon coding
#26There 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.
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.
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: https://github.com/ortegaalfredo/eccchain
Re: The essence of Reed-Solomon coding
#27Earlier quoted context omitted.
This is already done by many audio/video chat compression algorithms which use UDP. The idea being that with something like voice or video, if a packet doesn’t arrive, instead of stalling everything while you wait for a retransmit, you instead just carry on regardless. The occasional missing packet in voice is almost imperceptible, however the more packets that get lost the more the voice seems to “break up”. With vi…
I think the ask is for something like let a bit flip inside the UDP packet or let a byte fall out of the UDP packet. The integrity of UDP packets is still checked for (at different layers). For most networks the error rate is so low that I don't think it's that valuable. Also you'd still want your metadata checked otherwise it'll get potentially delivered to the wrong place.
That's what I assumed they meant but there's so many layers of correction/protection going on and most of it is non-optional if you want a working system. For example, if you disabled the FEC that's used over high-speed serdes links within a core router you'll be left with a broken system, the error rate is much too high. In the designs I've worked on you can't disable the internal CRC/ECC on the databuses without risking corrupting the control data, which won't end well. Nobody provides separate data and control ECC protection, that's pointless overhead.
I guess they probably meant disable checking the ethernet FCS, that might still work but I think it's a very bad plan. I doubt this option is even exposed to network operators.
Re: The essence of Reed-Solomon coding
#28I 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.
Re: The essence of Reed-Solomon coding
#29Some additions, as "exercise for the reader": 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? 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…
> What is the minimum size field 2^bits for an RS(N,K) coding system? Your field size must be at least N+1, noting that you shouldn't use the value 0 in the encoding matrix. > What happens when you try to construct a Reed-Solomon code with a finite field that is too small? Your system of linear equations doesn't have enough linearly independent equations. > how could you make the encoder/decoder faster Maybe put the…
Hmm, do you mean N+K+1 (to have enough points for both the data and parity shards)? Why isn't N+K sufficient, fitting a polynomial to N points and emitting K more?
Re: The essence of Reed-Solomon coding
#30Shameless plug of my own explanation on how binary fields work:
https://vitalik.ca/general/2019/05/12/fft.html
Ctrl+F for "binary fields".