On expander codes

被引：95

作者：

Zémor, G ^{[1
]}

机构：

[1] Ecole Natl Super Telecommun Bretagne, F-75634 Paris 13, France

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2001年 / 47卷 / 02期

关键词：

decoding; expander code; Ramanujan graph;

D O I：

10.1109/18.910593

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Sipser and Spielman have introduced a constructive family of asymptotically good linear error-correcting codes-expander codes-together with a simple parallel algorithm that will always remove a constant fraction of errors. We introduce a variation on their decoding algorithm that, with no extra cost in complexity, provably corrects up to 12 times more errors.

引用

页码：835 / 837

页数：3

共 6 条

[1] EXPLICIT CONSTRUCTION OF LINEAR SIZED TOLERANT NETWORKS [J].

ALON, N ;

CHUNG, FRK .

DISCRETE MATHEMATICS, 1988, 72 (1-3) :15-19

[2] RAMANUJAN GRAPHS [J].

LUBOTZKY, A ;

PHILLIPS, R ;

SARNAK, P .

COMBINATORICA, 1988, 8 (03) :261-277

[3]

Mac Williams F., 1977, THEORY ERROR CORRECT

[4]

Margulis G. A., 1988, Problems of Information Transmission, V24, P39

[5] Expander codes [J].

Sipser, M ;

Spielman, DA .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1996, 42 (06) :1710-1722

[6] A RECURSIVE APPROACH TO LOW COMPLEXITY CODES [J].

TANNER, RM .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1981, 27 (05) :533-547

← 1 →