Concepedia

Efficient erasure correcting codes

Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman

IEEE Transactions on Information Theory · 2001 · 1.2K citations · 28 references

Open access

TL;DR

The authors introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs. They analyze the algorithm via a discrete‑time random‑process model. They establish a necessary and sufficient degree‑fraction criterion for successful decoding with high probability, construct linear codes of any rate R that can be encoded in O(n ln(1/ε)) time, recover codewords from a (1+ε)R n fraction of entries, and demonstrate that the algorithm runs in O(n ln(1/ε)) time and performs well in practice.

Abstract

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 /spl epsiv/ a family of linear codes of rate R which can be encoded in time proportional to ln(1//spl epsiv/) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+/spl epsiv/)Rn or more. The recovery algorithm also runs in time proportional to n ln(1//spl epsiv/). Our algorithms have been implemented and work well in practice; various implementation issues are discussed.