####
Efficient erasure correcting codes

We introduce a simple erasure recovery algorithm for codes derived
from cascades of sparse bipartite graphs and analyze the algorithm by
analyzing a corresponding discrete-time random process. As a result,
we obtain a simple criterion involving the fractions of nodes of
different degrees on both sides of the graph which is necessary and
sufficient for the decoding process to finish successfully with high
probability. By carefully designing these graphs we can construct for
any given rate R and any given real number epsilon a family of linear
codes of rate R which can be encoded in time proportional to
ln(1/epsilon) times their block length n. Furthermore, a codeword can
be recovered with high probability from a portion of its entries of
length (1+epsilon)Rn or more. The recovery algorithm also runs in time
proportional to n ln(1/epsilon). Our algorithms have been implemented
and work well in practice; various implementation issues are discussed.