
doi: 10.1109/18.910575
Summary: 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 \(\varepsilon\) a family of linear codes of rate \(R\) which can be encoded in time proportional to \(\ln(1/\varepsilon)\) times their block length \(n\). Furthermore, a codeword can be recovered with high probability from a portion of its entries of length \((1+\varepsilon)Rn\) or more. The recovery algorithm also runs in time proportional to \(n\ln(1/\varepsilon)\). Our algorithms have been implemented and work well in practice; various implementation issues are discussed.
erasure channel, Other types of codes, Decoding, large deviation analysis, Applications of graph theory, sparse bipartite graphs, Channel models (including quantum) in information and communication theory, low-density parity-check codes
erasure channel, Other types of codes, Decoding, large deviation analysis, Applications of graph theory, sparse bipartite graphs, Channel models (including quantum) in information and communication theory, low-density parity-check codes
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 903 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 0.01% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 1% |
