Linear-time encodable and decodable error-correcting codes

被引：181

作者：

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; superconcentrators;

D O I：

10.1109/18.556668

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present a new class of asymptotically good, linear error-correcting codes. These codes can be both encoded and decoded in linear time. They can also be encoded by logarithmic-depth circuits of linear size and decoded by logarithmic depth circuits of size O(n log n). We present both randomized and explicit constructions of these codes.

引用

页码：1723 / 1731

页数：9

共 25 条

[1]

Aho A. V., 1974, ADDISON WESLEY SERIE

[2] EIGENVALUES AND EXPANDERS [J].

ALON, N .

COMBINATORICA, 1986, 6 (02) :83-96

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

ALON, N ;

CHUNG, FRK .

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

[4]

Bassalygo L. A., 1977, Problems of Information Transmission, V13, P166

[5]

BIEN F, 1989, NOT AM MATH SOC, V36, P5

[6] EXPLICIT CONSTRUCTIONS OF LINEAR-SIZED SUPERCONCENTRATORS [J].

GABBER, O ;

GALIL, Z .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1981, 22 (03) :407-420

[7]

Gelfand S. I., 1973, 2 INT S INF THEORY, P177

[8] COMPLEXITY OF DECODING REED-SOLOMON CODES [J].

JUSTESEN, J .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (02) :237-238

[9]

Kahale N., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P296, DOI 10.1109/SFCS.1992.267762

[10]

Kolmogorov A.N., 1958, Usp. Mat. Nauk., V13, P3

← 1 2 3 →