Re: [dtn-interest] Question

[Daniel Ellard <[e-mail]>]

On 1/28/13 8:44 PM, [e-mail] wrote:
> I did, and my understanding is it is an erasure code  with a larger margin
> of error allowed for the signal can be recovered from a subset of the
> encoded signals...so it still cant handle losses?

It is correct that a "digital fountain" is an instance of a forward
error-correcting code.

As such, it has the property that it encodes a string of data D of
length N as a set of much smaller strings e0, e1, ..., eX such that
the original string D can be reconstructed from any subset of e0,
e1, ... eX if the sum of the lengths of each e in the subset is
greater or equal to N.  (an "efficient" FEC is one such that any
subset of length N will suffice; my recollection is that fountain
codes are not guaranteed to be efficient, but are generally within a
small margin of it.)  It is possible to choose an encoding method to
make each e computable independently of the rest, and the set of all
possible e's for a given D practically unlimited.

The sender can continuously compute and transmit e's, and as soon as
the receiver receives enough e's, the receiver is successful.  It
doesn't matter how many e's are lost en route (or which are lost) as
long as enough arrive eventually.

Fountain codes are one example of a FEC with this property, but the
last time I checked (which was a while ago, admittedly) they had two
drawbacks: first, the efficient implementations were protected by
patents, and second, they weren't well-described or available as
open-source.  Perhaps that has changed.

In any case, if you want to understand the basic theory of efficient
FECs, Rabin's "Information Dispersal Algorithm", based on polynomial
interpolation, is a good place to start.  For implementations of
related codes that can be implemented efficiently, James Plank's
work on erasure codes for storage is the most practical work of
which I am aware.

-Dan

-- 
Daniel Ellard, Ph.D.
Senior Scientist, Network Research
Raytheon BBN Technologies
[e-mail]