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.
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.