The essence of Reed-Solomon coding(mazzo.li) |
The essence of Reed-Solomon coding(mazzo.li) |
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): https://www.nayuki.io/page/reed-solomon-error-correcting-cod...
I would strongly recommend anyone interested in the topic to check out any of these videos:
How to send a self-correcting message (Hamming codes): https://www.youtube.com/watch?v=X8jsijhllIA
Hamming codes part 2, the elegance of it all: https://www.youtube.com/watch?v=b3NxrZOu_CE
And any of Ben Eater's five videos on error correction: https://eater.net/crc
As an aside, Ben Eater does all of his videos and demonstrations using an 8-bit computer he has built step by step in videos on a breadboard. Very impressive and inspiring.
https://en.wikipedia.org/wiki/Cross-interleaved_Reed%E2%80%9...
https://en.wikipedia.org/wiki/Optical_disc#Surface_error_sca...
Pseudo-random scrambling is used in places like https://en.wikipedia.org/wiki/64b/66b_encoding to reduce the chances of many consecutive 0s or 1s which could cause clock desynchronization between the sender and receiver.
Then you use something like LDPC codes for in-packet ECC. RS for multi-packet ECC.
In my experience, LDPC is usually better for soft-decision decoding, where you have information about how reliable each bit is. RS is usually better for hard-decision where you don't know anything about the error locations. Also LDPC is usually bit-oriented, and RS is always a symbol-oriented code, so RS works well for burst errors.
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
https://vitalik.ca/general/2019/05/12/fft.html
Ctrl+F for "binary fields".
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 already fits in L1 cache, how could you make the encoder/decoder faster, if you had a smaller finite field?
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 lookup table in a 64-bit general-purpose register and use bit shifting, or in a 128/256/512-bit SIMD register and use extraction instructions (shuffle bytes, etc.).
Currently H2 does support M:N stream muxing but popular browsers only support N:1 mode.
Which is good, because it means higher cost of middle boxes
> But if you’re able to get packets out of one, what’s stopping you from getting the whole stream out that network?
It's practically impossible, unless the MITM box were setup very close to both ends on the edge. In real world packets were routed slightly different, the server might have several IPs or CDNs, so if your middlebox were placed in backbone it will be useless as packets were transfered out-of-order and not in the same stream.
> just encrypting the information which also blinds the network operator
Yes, but the network operator was sure every information is inside one exact stream, just with a thick layer of protection, state-of-the-art classifiers are able to match metadata patterns to the individual websites, so protocol designers would then take huge amount of time to fight it. You either have a very fast TTFB protocol, or you'd have to add some padding redundancy (noise) to disguise the metadata. By metadata I mean packet length and frequency pattern.
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).
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).
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.
Folk do that sort of thing when transmitting low latency first-person-video from drones, using commodity wifi hardware.
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 video the symptoms are an accumulation of visual corruption until the next key frame.
FPS games also do this (or at least used to), servers would send a stream of UDP packets of entity states (as opposed to sending deltas of state changes), so things like player1 is at x,y,z coordinate with velocity a and heading vector of b.
If clients missed a packet they would just wait for the next one since it’s useless to know later where someone else was, all you actually care about is where they are, or what’s happening, now.
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.
As for where the +1 comes from, the clue is in the "noting that you shouldn't use the value 0 in the encoding matrix" remark. The TLDR is that the +1 isn't required, and arises from an (incorrect) attempt to fix an incorrect construction. The non-TLDR is rather long. First, we need to move from polynomials (per the article) to matrices (per the quoted remark). For this movement, let F denote the polynomial from the article, then it so happens that F(k+1) can be expressed as a linear combination of F(1), F(2), ..., F(k). Similarly, F(k+2) can be expressed as a linear combination of F(1), F(2), ..., F(k). This continues to be true up to F(k+t) (and beyond). These various linear combinations can be written as a k-by-t matrix, which is what the quoted remark means by "encoding matrix". Second, once thinking with matrices rather than with polynomials, people want to construct the encoding matrix directly, rather than deriving it from a polynomial. In this direct construction, the requirement is that every square submatrix (of any size) of the k-by-t matrix is invertible. Accordingly, no element of the k-by-t matrix can be zero, as the 1-by-1 submatrix containing just that zero element isn't invertible. Third, one common (but incorrect) direct construction is to create a k-by-t Vandermonde matrix. Such a matrix is usually constructed from some number of distinct elements, but if zero is used as such an element, then the resultant matrix will contain zeroes, which is problematic. Excluding zero causes the Vandermonde construction to _sometimes_ work, but it still doesn't _always_ work. Per https://www.corsix.org/content/reed-solomon-for-software-rai..., there's a slightly different Vandermonde construction that _does_ always work, and also a Cauchy construction that always works, both of which work for zero. Both of these correct constructions have a strong parallel to the polynomial construction: they involve choosing N+K distinct field elements, which is akin to choosing the N+K distinct x co-ordinates for the polynomial.
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.
I stand corrected!
Heh