Circular-shift Linear Network Coding

Prof. Qifu (Tyler) Sun
University of Science and Technology Beijing
Thursday, 15 June, 2017
4:00 – 5:00pm
Room 833, Ho Sin Hang Engineering Building, CUHK

We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations at intermediate nodes consist of only circular-shift and bit-wise addition (XOR). Departing from existing literature, we systematically formulate circular-shift LNC as a special type of vector LNC, where the local encoding kernels of an L-dimensional circular-shift linear code of degree d are summation of at most d cyclic-permutation matrices of size L. Under this framework, an intrinsic connection between scalar LNC and circular-shift LNC is established. In particular, on a general network, for some block lengths L, every scalar linear solution over GF(2L–1) can induce an (L–1, L)-fractional circular-shift linear solution of degree (L–1)/2.   

Specific to multicast networks, an (L–1, L)-fractional circular-shift linear solution of arbitrary degree d can be efficiently constructed. While the constructed solution has one-bit redundancy per edge transmission, we show that this is inevitable, and that circular-shift LNC is insufficient to achieve the exact capacity of multicast networks. In addition, we prove that randomly constructed circular-shift LNC schemes can asymptotically approach the multicast capacity with increasing block length L. Both theoretical and numerical analysis imply that with increasing L, the probability of randomly constructing a circular-shift linear solution of degree 1, in which there are L+1 possible local encoding kernels, is comparable to the one of randomly constructing a permutation-based linear solution, in which the local encoding kernels are selected from L! possible permutation matrices of size L.




Qifu (Tyler) Sun received the B.Eng. (first class honors) and Ph.D. degrees from the Department of Information Engineering, The Chinese University of Hong Kong in 2005 and 2009, respectively. He has been a postdoctoral fellow at the Institute of Network Coding, The Chinese University of Hong Kong and a visiting fellow at the University of New South Wales. He is currently an associate professor at the School of Computer and Communication Engineering, University of Science and Technology Beijing. His research interests include fundamental study of network coding, channel coding and modulation. He has been the principal investigator of two grants of National Natural Science Foundation of China.