DocumentCode :
3143092
Title :
Polynomial Time Construction Algorithm of BCNC for Network Coding in Cyclic Networks
Author :
Huang, Jiaqing ; Wang, Liang ; Cheng, Wenqing ; Li, Hui
Author_Institution :
Dept. of Electron. & Inf. Eng., Huazhong Univ. of Sci. & Technol., Wuhan, China
fYear :
2009
fDate :
1-3 June 2009
Firstpage :
228
Lastpage :
233
Abstract :
Network coding in cyclic networks meets more problems than in acyclic networks. Recently, S.-Y.R.Li et al.proposed a framework of convolutional network coding (CNC) as well as its four properties for cyclic networks with theoretic fundamentals of discrete valuation ring (DVR). The four properties, convolutional multicast (CM), convolutional broadcast (CB), convolutional dispersion (CD) and basic convolutional network code (BCNC), are notions of increasing strength in this order with regard to linear independence among the global encoding kernels. The existence of a BCNC then implies the existence ofthe rest. That is, BCNC is the best convolutional network code in terms of linear independence. However, the code construction algorithm of BCNC was not presented explicitly. To the best of our knowledge, this is the first paper to propose a polynomial time construction algorithm of BCNC for network coding in cyclic networks, which can deal with different characteristics of cycles in terms of topology, including link cycles but flow acyclic, simple flow cycles and knots. Finally, polynomial time complexity of the algorithm was proved as well as its effectiveness.
Keywords :
computational complexity; convolutional codes; polynomials; acyclic network; basic convolutional network code; convolutional broadcast code; convolutional dispersion code; convolutional multicast code; cyclic network; discrete valuation ring; network coding; polynomial time complexity; polynomial time construction algorithm; Broadcasting; Computer numerical control; Convolutional codes; Dispersion; Encoding; Kernel; Laboratories; Multicast algorithms; Network coding; Polynomials; convolutional network coding; cyclic networks; network coding;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer and Information Science, 2009. ICIS 2009. Eighth IEEE/ACIS International Conference on
Conference_Location :
Shanghai
Print_ISBN :
978-0-7695-3641-5
Type :
conf
DOI :
10.1109/ICIS.2009.52
Filename :
5223067
Link To Document :
بازگشت