Comment by hcs | Hacker News Reader

Comment by hcs | Hacker News Reader

Parent Full thread

The Wikipedia article has a section "Reed & Solomon's original view: The codeword as a sequence of values" which I think is fairly easy to follow.

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)

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?

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.

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.

Reply on news.ycombinator.com