Efficient erasure correcting codes

We introduce a simple erasure recovery algorithm for codes derived from cas cades of sparse bipartite graphs and analyze the algorithm by analyzing a c orresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sid es 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 epsi lon a family of linear codes of rate R which can be encoded in time proport ional 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 len gth (1 + epsilon) Rn or more. The recovery algorithm also runs in time prop ortional to n ln(1/epsilon). Our algorithms have been implemented and work well in practice; various implementation issues are discussed.