Re:Reed-Solomon coder computing one million ECC blocks at 1 ...
by infogulch on Monday May 08, 2017 @01:49PM
(#14293875)
From 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.
Re:Reed-Solomon coder computing one million ECC blocks at 1 ...
by algo646464 on Monday May 08, 2017 @02:17PM
(#14294142)
This 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.
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?