Efficient Erasure Correcting Codes
Authors:
Michael G. Luby,
Michael Mitzenmacher,
M. Amin Shokrollahi, and
Daniel A. Spielman.
Bibliographic Information:
Appeared in
IEEE Transactions on Information Theory,
47(2), pp. 569-584, Feb. 2001.
Preliminary version appeared in the
The Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC)
under the title "Practial Erasure-Resilient Codes" and with Volker Stemann
as a co-author.
Impact
The codes presented in this paper have been dubbed Tornado Codes
and have been examined for use in compensating for packet loss in
internet traffic, especially in multicast video.
Abstract
We present randomized constructions of linear-time encodable and
decodable codes that can transmit over lossy channels at rates
extremely close to capacity.
The encoding and decoding algorithms for these codes have fast and
simple software implementations.
Partial implementations of our algorithms are faster by orders
of magnitude than the best software implementations of any
previous algorithm for this problem.
We expect these codes will be extremely useful for applications
such as real-time audio and video transmission over the Internet,
where lossy channels are common and fast decoding is a requirement.
Despite the simplicity of the algorithms, their design and
analysis are mathematically intricate.
The design requires the careful choice of a random irregular bipartite graph,
where the structure of the irregular graph is extremely important.
We model the progress of the decoding algorithm by a set of differential
equations.
The solution to these equations can then be expressed as
polynomials in one variable with coefficients determined by the
graph structure.
Based on these polynomials, we design a graph structure that
guarantees successful decoding with high probability.
You can download this paper as
Postscript,
compressed Postscript, or
PDF.
Daniel A. Spielman
Last modified: Fri Aug 24 15:47:38 2001