2001 | Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, and Daniel A. Spielman
The paper introduces a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyzes the algorithm using a discrete-time random process. The analysis yields a criterion involving the fractions of nodes of different degrees on both sides of the graph, which is necessary and sufficient for successful decoding with high probability. By carefully designing these graphs, the authors construct linear codes of rate \( R \) that can be encoded in time proportional to \( \ln(1/\epsilon) \) times their block length \( n \). Additionally, a codeword can be recovered with high probability from a portion of its entries of length \( (1+\epsilon)n \). The recovery algorithm also runs in time proportional to \( n \ln(1/\epsilon) \). The algorithms have been implemented and perform well in practice, with various implementation issues discussed. The paper includes a detailed construction of the codes, the analysis of the decoding process, and practical considerations for implementation.The paper introduces a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyzes the algorithm using a discrete-time random process. The analysis yields a criterion involving the fractions of nodes of different degrees on both sides of the graph, which is necessary and sufficient for successful decoding with high probability. By carefully designing these graphs, the authors construct linear codes of rate \( R \) that can be encoded in time proportional to \( \ln(1/\epsilon) \) times their block length \( n \). Additionally, a codeword can be recovered with high probability from a portion of its entries of length \( (1+\epsilon)n \). The recovery algorithm also runs in time proportional to \( n \ln(1/\epsilon) \). The algorithms have been implemented and perform well in practice, with various implementation issues discussed. The paper includes a detailed construction of the codes, the analysis of the decoding process, and practical considerations for implementation.