
Matroidal Error Correction Networks and Linear Network Error Correction MDS Codes 
Time:2014107 
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: 119122. [2] Yeung R W, Cai N. Network error correction, part Ⅰ: Basic concepts and upper bounds [J]. Communications in Infoma tion and Systems, 2006, 6: 1936.
[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): 209218.
[5] Matsumoto R. Construction algorithm for network error correcting codes attaining the singleton bound [J]. IEICE Trans Fund, E90A, 2007, 9: 17291735.
[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): 14091424.
[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): 10301047.
[8] Guang X, Fu F W. Linear network error correction multi cast/broadcast/dispersion codes [EB/OL]. [20130218]. http: //arXiv: 1302.4146.
[9] Dougherty R, Freiling C, Zeger K. Networks, matroids, and nonshannon information inequalities [J]. IEEE Trans Inf Theory, 2007, 53(6): 19491969.
[10] Dougherty R, Freiling C, Zeger K. Insufficiency of linear coding in networks
[11] Kim A, Medard M. Scalarlinear solvability of matroidal networks Associated with representable matroids [C]//International Symposium on Turbo Codes and Iterative Information Processing. Brest: IEEE Press, 2010: 452456.
[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. 
