3 ms·
Just to interrogate this description: So, there is a trick to picking the points such that any can be lost, and only the remaining number matters? I think this
by Chris2048 10y ago
Just to interrogate this description:
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?
- infogulch 10y agoFrom the Go implementation linked upthread: > 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.
- algo646464 10y agoThis is true only for erasure RS-codes, but not for general RS-codes. In erasure RS-codes you must specify which points are corrupted and the decoder discards them. 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.
- deleted 10y ago[deleted]