[Haskell-cafe] ANN: fountain-0.0.0

Tom Hawkins tomahawkins at gmail.com
Tue Oct 19 23:00:10 EDT 2010

This library [1] implements a fountain code [2].  Fountain codes are
forward error correction codes for erasure channels [3].  A fountain
code encodes a message into an infinite stream of packets --
transmitters generate message packets at random, on-the-fly.  To
reconstruct the message, receivers simply need to capture enough
packets for the decoding process.  As a rateless code, fountain codes
automatically adapt to varying channel conditions.

Some of the more interesting applications of fountain codes include
unsynchronized data broadcast and distributed download.  For example,
a multiple number of devices can transmitting content to multiple
receivers without any coordination.  Because packets are generated at
random, receivers increase their bandwidth simply by listening to more
transmitters.  Note that receivers can also start generating packets
and forwarding the message on even before they have decoded the
complete message.

This library provides a packet generator and a decoder for one of the
first known fountain codes: LT codes [4].  It also includes a test
function to experiment with message lengths, and encoding degrees --
it runs a simulation to determine the number of packets needed to
decode a message.


[1] http://hackage.haskell.org/package/fountain
[2] http://en.wikipedia.org/wiki/Fountain_code
[3] http://en.wikipedia.org/wiki/Binary_erasure_channel
[4] http://en.wikipedia.org/wiki/LT_codes

More information about the Haskell-Cafe mailing list