News for hackers. Stuff that matters.
Re:BitTorrent - It's not just about copyright any more by kragen on Tuesday June 21, 2011 @02:02PM (#2679736)
There is a little more to them than that. What you describe can be achieved simply by broadcasting the whole file over and over again with sequence numbers. The thing about fountain codes, if I remember them correctly, is that you can recover from having received corrupted packets by receiving only a few more packets, instead of the whole newspaper again.

But that, too, is achievable in a simple way: just fit a degree-N polynomial over a finite field to N+1 symbols made out of your data and emit an infinite stream of values of the polynomial. Any N+1 correctly received symbols are sufficient to reconstruct the original polynomial. A computable algorithm for error correction in this case is to try all the N+1-sized subsets of the data you've received, largest first: omit received symbol #1, then #2, then #3, etc. If you have found a subset with no errors, then the polynomial fit to its N+1 first values will successfully predict the rest.

Unfortunately, this error correction algorithm is absurdly inefficient. But I seem to recall that fountain codes have an efficient error correction algorithm as well.

Re:BitTorrent - It's not just about copyright any more by hadronzoo on Tuesday June 21, 2011 @02:22PM (#2679814)
RaptorQ codes, an efficient fountain code implementation, have a relative reception overhead of K+2 symbols with probability of 99.9999%. See: http://tools.ietf.org/html/draft-ietf-rmt-bb-fec-raptorq-06

Unfortunately, they're patent encumbered.

Re:BitTorrent - It's not just about copyright any more by kragen on Tuesday June 21, 2011 @04:33PM (#2680283)
Not here!