Circular-shift Linear Network Coding

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(2^L–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.