BitTorrent - It's not just about copyright any more • Hacker News Board

Re: BitTorrent - It's not just about copyright any more

#11

Post by jevinskie » Tue, Jun 21, 2011, 5:00 PM UTC

anamax wrote: post #9

I'm surprised that the bittorrent patent issued because the patent looks like it claims what the digital fountain patents (now owned by qualcomm) claimed several years previously. google "digital fountain".

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.

Re: BitTorrent - It's not just about copyright any more

#12

Post by kragen » Tue, Jun 21, 2011, 6:02 PM UTC

jevinskie wrote: post #11

anamax wrote: post #9

I'm surprised that the bittorrent patent issued because the patent looks like it claims what the digital fountain patents (now owned by qualcomm) claimed several years previously. google "digital fountain".

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 distrib…

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

#13

Post by hadronzoo » Tue, Jun 21, 2011, 6:22 PM UTC

kragen wrote: post #12

jevinskie wrote: post #11

Earlier quoted context omitted.

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 distrib…

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 degre…

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

#14

Post by kragen » Tue, Jun 21, 2011, 8:33 PM UTC

hadronzoo wrote: post #13

kragen wrote: post #12

Earlier quoted context omitted.

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 degre…

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!