Efficient erasure correcting codes
Top Cited Papers
- 1 February 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 47 (2) , 569-584
- https://doi.org/10.1109/18.910575
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.Keywords
This publication has 17 references indexed in Scilit:
- Expander graph arguments for message-passing algorithmsIEEE Transactions on Information Theory, 2001
- Design of capacity-approaching irregular low-density parity-check codesIEEE Transactions on Information Theory, 2001
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001
- Efficient erasure correcting codesIEEE Transactions on Information Theory, 2001
- Good error-correcting codes based on very sparse matricesIEEE Transactions on Information Theory, 1999
- Iterative decoding of compound codes by probability propagation in graphical modelsIEEE Journal on Selected Areas in Communications, 1998
- Expander codesIEEE Transactions on Information Theory, 1996
- Linear-time encodable and decodable error-correcting codesIEEE Transactions on Information Theory, 1996
- Near Shannon limit performance of low density paritycheck codesElectronics Letters, 1996
- Codes and iterative decoding on general graphsEuropean Transactions on Telecommunications, 1995