Expander codes

被引：492

作者：

Sipser, M

Spielman, DA

机构：

[1] Department of Mathematics, Massachusetts Institute of Technology, Cambridge

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 1996年 / 42卷 / 06期

基金：

美国国家科学基金会;

关键词：

asymptotically good error-correcting code; linear-time; expander graph;

D O I：

10.1109/18.556667

中图分类号：

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

学科分类号：

0812 ;

摘要：

Using expander graphs, we construct a new family of asymptotically good, linear error-correcting codes, These codes have linear time sequential decoding algorithms and logarithmic time parallel decoding algorithms that use a linear number of processors. We present both randomized and explicit constructions of these codes, Experimental results demonstrate the good performance of the randomly chosen codes.

引用

页码：1710 / 1722

页数：13

共 35 条

[1]

Aho A. V., 1974, ADDISON WESLEY SERIE

[2]

AJTAI M, 1987, 19TH P ACM S THEOR C, P132

[3] CONSTRUCTION OF ASYMPTOTICALLY GOOD LOW-RATE ERROR-CORRECTING CODES THROUGH PSEUDORANDOM GRAPHS [J].