Comment by jevinskie | Hacker News Reader

Comment by jevinskie | Hacker News Reader

Parent Full thread

I'm going to explain "digital fountains" a bit more because I think they are really cool. The "fountain" in "digital fountain" refers to fountain code. A fountain code can take a file and generate an infinite stream of codes. As long as the receiver obtains a portion of the codes that is just slightly larger than the file size, they can recover the original file. These codes are immensely useful for broadcast distribution. You can broadcast the morning newspaper using a fountain code and everyone's mobile device will obtain the file after downloading the paper's size + a bit more of the fountain codes. When using wireless radios, broadcast distribution is very desirable because unicast distribution (think HTTP) doesn't scale while broadcast scales perfectly.

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.

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.

Not here!

Reply on news.ycombinator.com