Latest Article
Matroidal Error Correction Networks and Linear Network Error Correction MDS Codes
Time:2014-1-07  
ZHOU Hang1,2, LIU Guangjun3
1. The State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710071, Shaanxi, China; 2. College of Science, Engineering University of the Chinese People’s Armed Police Force, Xi’an 710086, Shaanxi, China; 3. School of Mathematics and Computer Engineering, Xi’an University of Arts and Science, Xi’an 710065, Shaanxi, China
Abstract:
In this paper, we further study the connections between linear network error correction codes and representable matroids. We extend the concept of matroidal network introduced by Dougherty et al. to a generalized case when errors occur in multi- ple channels. Importantly, we show the necessary and sufficient conditions on the existence of linear network error correction mul- ticast/broadcast/dispersion maximum distance separable (MDS) code on a matroidal error correction network.  
Key words: network error correction code; error pattern; imagi- nary error channels; extended network; matroid
CLC number: TN 915.01; TN 919.3+1
References:
[1] Cai N, Yeung R W. Network coding and error correction [C] //Proc IEEE Information Theory Workshop. Bangalore: IEEE Press, 2002: 119-122. [2] Yeung R W, Cai N. Network error correction, part Ⅰ: Basic concepts and upper bounds [J]. Communications in Infoma- tion and Systems, 2006, 6: 19-36.  
[3] Cai N, Yeung R W. Network error correction, part Ⅱ: Lower bounds [J]. Communications in Infomation and Sys-
tems, 2006, 6: 37- 54. 
[4] Zhang Z. Linear network error correction codes in packet networks [J]. IEEE TransInf  Theory, 2008, 54(1): 209-218. 
[5] Matsumoto R. Construction algorithm for network error -correcting codes attaining the singleton bound [J]. IEICE Trans Fund, E90-A, 2007, 9: 1729-1735. 
[6] Yang S, Yeung R W, Ngai C K. Refined coding bounds and code constructions for coherent network error correction [J]. IEEE Trans Inf  Theory, 2011, 57(3): 1409-1424. 
[7] Guang X, Fu F W, Zhang Z. Construction of network error correction codes in packet networks [J]. IEEE Trans Inf Theory, 2013, 59(2): 1030-1047. 
[8] Guang X, Fu F W. Linear network error correction multi- cast/broadcast/dispersion codes [EB/OL]. [2013-02-18]. http: //arXiv: 1302.4146. 
[9] Dougherty R, Freiling C, Zeger K. Networks, matroids, and non-shannon information inequalities [J]. IEEE Trans Inf Theory, 2007, 53(6): 1949-1969. 
[10] Dougherty R, Freiling C, Zeger K. Insufficiency of linear coding in networks
[11] Kim A, Medard M. Scalar-linear solvability of matroidal networks Associated with representable matroids [C]//International Symposium on Turbo Codes and Iterative Information Processing. Brest: IEEE Press, 2010: 452-456. 
[12] Oxley J G. Matroid Theory [M]. New York: Oxford Univer- sity Press, 1992. 
[13] Koetter R, Medard M. An algebraic approach to network cod- ing [J]. IEEE/ACM Transon Networking, 2003, 11: 782- 795.