Efficient erasure correcting codes

被引:615
作者
Luby, MG
Mitzenmacher, M
Shokrollahi, MA
Spielman, DA
机构
[1] Int Comp Sci Inst, Berkeley, CA 94704 USA
[2] Digital Equipment Corp, Syst Res Ctr, Palo Alto, CA 94301 USA
[3] MIT, Dept Math, Cambridge, MA 02139 USA
基金
美国国家科学基金会;
关键词
erasure channel; large deviation analysis; low-density parity-check codes;
D O I
10.1109/18.910575
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 epsilon a family of linear codes of rate R which can be encoded in time proportional to ln(1/epsilon) times their block length n, Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1 + epsilon) Rn or more. The recovery algorithm also runs in time proportional to n ln(1/epsilon). Our algorithms have been implemented and work well in practice; various implementation issues are discussed.
引用
收藏
页码:569 / 584
页数:16
相关论文
共 26 条
[1]   A linear time erasure-resilient code with nearly optimal recovery [J].
Alon, N ;
Luby, M .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1996, 42 (06) :1732-1736
[2]  
[Anonymous], P 22 IEEE ANN S FDN
[3]  
BERROU C, 1993, IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS 93 : TECHNICAL PROGRAM, CONFERENCE RECORD, VOLS 1-3, P1064, DOI 10.1109/ICC.1993.397441
[4]  
Blahut R. E., 1983, THEORY PRACTICE ERRO
[5]  
Elias P., 1955, INF THEOR 3 LOND S, P61
[6]   Analysis of two simple heuristics on a random instance of k-SAT [J].
Frieze, A ;
Suen, S .
JOURNAL OF ALGORITHMS, 1996, 20 (02) :312-355
[7]  
GALLAGHER RG, 1963, LOW DENSITY PARITY C
[8]  
KURTSZ TG, 1981, CBMS NSF REG C SER A
[9]  
Luby M., 1998, P 9 ANN ACM SIAM S D, P364
[10]  
LUBY M, 2000, IEEE T INFORM THEORY, V47, P671