The fundamental idea is a polynomial of degree n is uniquely described by n+1 points (2 points give a unique line, 3 points a unique parabola, etc). If the polynomial is the data you want to protect, you can pick enough points to describe it redundantly. Then, if a point is lost, as long as there are enough to still uniquely determine the original polynomial, you can recover the original data. And if the points do not all come from the same polynomial (as when the data has been corrupted) you can at least detect this, and you may be able to throw out some of the points to recover.
(Edited to correct that the polynomial is the original message, not some set of points)
So, there is a trick to picking the points such that any can be lost, and only the remaining number matters? I think this was the case with par2, that used RS - you could lose any of the files, and as long as you had enough left, you could infer the lost files. I guess this method is the bit I get stuck on.
How are 'corrupt' points detected? By determining that no polynomial is described by a set of points, and then computing the least number of points needed to remove for a polynomial-describing set of points?
> The encoder does not know which parts are invalid, so if data corruption is a likely scenario, you need to implement a hash check for each shard.
The coder just does some simple matrix math to reconstruct what you tell it to reconstruct. You have to build the checking and detection yourself.
For general RS-codes you don't need to detect which points are corrupted. An intuitive explanation of the decoding process here is that, if a small number of evaluation points are corrupted, then the original degree n polynomial is still the closest polynomial to the (slightly corrupted) set of evaluation points. The decoding algorithm uses this fact.
This however comes at cost. General RS-codes can correct only half as many errors as Erasure RS-codes.
[...] by the end of this post, we will have written a complete working implementation of a simple variant of Reed–Solomon coding, not entirely unlike what is used in [OpenStack] Swift itself. No prior knowledge will be assumed except a working knowledge of high-school algebra and the Python programming language.
https://www.swiftstack.com/blog/2015/04/20/the-foundations-o...
(For example: 10GB Ethernet went with a low-density parity-check (LDPC))
i don't think so. RS erasure coding performs the same operation over all words in the block, that is perfectly vectorizable and parallelizable
SSDs goes from RS to LDPC probably because it's faster (and their controllers are already pretty hot!), in paricular LDPC allows faster soft decoders (i.e. ones that understand that 7 is more probably decoded as 8 rather than 2). Overall, classic RS encoder speed is O(1/N) where N is amount of parity blocks. Probably, modern media employs larger amount of parity blocks that slows down classic RS algorithms
OTOH, LDPC codecs afaik usually have fixed speed so with larger N they became faster than RS - sooner or later. So, as time goes and N increases, interest shifts from RS to LDPC algos. The same applies to other fast codes (fountain, raptor...) - they are also faster than classic RS for large enough N
Free videos/slides for Stanford's introductory networking class (linked the Reed-Solomon video)
i (FastECC author) learned everything from this great text. It contains anything required to understand RS coding from standard programmer knowledge base (i.e no Galois Fields or matrix arithmetic). it's longer than most other texts referenced here but it contains enough info to even make your own implementation if you want
note that it doesn't include info regarding my fast O(N*logN) implementation. If you need to learn that - read docs in my repository, although i'm not as good teacher as professor Plank
also note that there are several different approaches to RS implementation. While they all are called RS codes, they are pretty different. Plank describes the scheme that is easier to understand (and implement) than any other one