Name
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 ε a family of linear codes of rate R which can be encoded in time proportional to ln(1/ε) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+ε)Rn or more. The recovery algorithm also runs in time proportional to n ln(1/ε). Our algorithms have been implemented and work well in practice; various implementation issues are discussed |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1109/18.910575 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
efficient erasure,high probability,simple criterion,different degree,linear code,simple erasure recovery algorithm,decoding process,corresponding discrete-time random process,block length n,recovery algorithm,rate r,vectors,galois fields,computer science,code rate,bipartite graph,graph theory,erasure channel,probability,algorithm design and analysis,random processes,decoding,random process,indexing terms,discrete time | Graph theory,Discrete mathematics,Combinatorics,Algorithm design,Code rate,Bipartite graph,Stochastic process,Linear code,Decoding methods,Mathematics,Erasure | Journal |
Volume | Issue | ISSN |
47 | 2 | 0018-9448 |
Citations | PageRank | References |
587 | 66.64 | 24 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Luby | 1 | 9010 | 1319.35 |
| Michael Mitzenmacher | 2 | 7386 | 730.89 |
| M. A. Shokrollahi | 3 | 1003 | 128.53 |
| Daniel A. Spielman | 4 | 4257 | 638.57 |