Construction algorithm for network error-correcting codes attaining the singleton bound

被引：29

作者：

Matsumoto, Ryutaroh ^{[1
]}

机构：

[1] Tokyo Inst Technol, Dept Commun & Integrated Syst, Tokyo 1528550, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2007年 / E90A卷 / 09期

关键词：

error correction; MDS code; network coding; random network coding; Singleton bound;

D O I：

10.1093/ietfec/e90-a.9.1729

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We give a centralized deterministic algorithm for constructing linear network error-correcting codes that attain the Singleton bound of network error-correcting codes. The proposed algorithm is based on the algorithm by Jaggi et al. We give estimates on the time complexity and the required symbol size of the proposed algorithm. We also estimate the probability of a random choice of local encoding vectors by all intermediate nodes giving a network error-correcting codes attaining the Singleton bound. We also clarify the relationship between the robust network coding and the network error-correcting codes with known locations of errors.

引用

页码：1729 / 1735

页数：7

共 14 条

[1] Network information flow [J].

Ahlswede, R ;

Cai, N ;

Li, SYR ;

Yeung, RW .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1204-1216

[2] Performance and microbial diversity of a trickle-bed air biofilter under interchanging contaminants [J].

Cai, Z ;

Kim, D ;

Sorial, GA ;

Saikaly, R ;

Zein, MM ;

Oerther, DB .

ENGINEERING IN LIFE SCIENCES, 2006, 6 (01) :37-42

[3]

HARADA K, 2005, SITA 2005, V2, P741

[4] Resilient network coding in the presence of Byzantine adversaries [J].

Jaggi, S. ;

Langberg, M. ;

Katti, S. ;

Ho, I. ;

Katabi, D. ;

Medard, M. .

INFOCOM 2007, VOLS 1-5, 2007, :616-624

[5]

Jaggi S, 2005, 2005 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), VOLS 1 AND 2, P1455

[6] Polynomial time algorithms for multicast network code construction [J].

Jaggi, S ;

Sanders, P ;

Chou, PA ;

Effros, M ;

Egner, S ;

Jain, K ;

Tolhuizen, LMGA .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (06) :1973-1982

[7] An algebraic approach to network coding [J].

Koetter, R ;

Médard, M .

IEEE-ACM TRANSACTIONS ON NETWORKING, 2003, 11 (05) :782-795

[8]

KURIHARA M, 2006, IT200641 IEICE

[9]

Lang Serge, 1987, Undergraduate Texts in Mathematics, Vthird

[10] Linear network coding [J].

Li, SYR ;

Yeung, RW ;

Cai, N .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2003, 49 (02) :371-381

← 1 2 →