Latest Article
Matroidal Error Correction Networks and Linear Network Error Correction MDS Codes
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
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
[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.