Efficient erasure correcting codes
Michael G. Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi et al. · IEEE Transactions on Information Theory · 2001
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.
Cited by 1,180 works. doi:10.1109/18.910575
Authors
References
- Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
- The Theory of Error-Correcting Codes
- Low-density parity-check codes
- Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1
- Low-Density Parity-Check Codes
- Randomized Algorithms
- Good error-correcting codes based on very sparse matrices
- Theory and practice of error control codes
- Design of capacity-approaching irregular low-density parity-check codes
- The capacity of low-density parity-check codes under message-passing decoding