Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, and with local encoding kernels chosen from cyclic permutation matrices. When L is a prime with primitive root 2, it was recently shown that a scalar linear solution over GF(2L-1) induces an L-dimensional circular-shift linear solution at rate (L-1)/L. In this paper, we prove that for arbitrary odd L, every scalar linear solution over GF(2mL), where mL refers to the multiplicative order of 2 modulo L, can induce an L-dimensional circular-shift linear solution at a certain rate. Based on the generalized connection, we further prove that for such L with mL beyond a threshold, every multicast network has an L-dimensional circular-shift linear solution at rate φ(L)/L, where φ(L) is the Euler's totient function of L. An efficient algorithm for constructing such a solution is designed. Finally, we prove that every multicast network is asymptotically circular-shift linearly solvable.

We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations consist of only circular-shifts and bit-wise additions. Formulated as a special vector linear code over GF(2), an L-dimensional circular-shift linear code of degree δ restricts its local encoding kernels to be the summation of at most δ cyclic permutation matrices of size L. We show that on a general network, for a certain block length L, every scalar linear solution over GF(2L-1) can induce an L-dimensional circular-shift linear solution with 1-bit redundancy per-edge transmission. Consequently, specific to a multicast network, such a circular-shift linear solution of an arbitrary degree δ can be efficiently constructed, which has an interesting complexity tradeoff between encoding and decoding with different choices of δ. By further proving that circular-shift LNC is insufficient to achieve the exact capacity of certain multicast networks, we show the optimality of the efficiently constructed circular-shift linear solution in the sense that its 1-bit redundancy is inevitable. Finally, both theoretical and numerical analysis imply that with increasing L, a randomly constructed circular-shift linear code has linear solvability behavior comparable to a randomly constructed permutation-based linear code, but has shorter overheads.

Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, with local encoding kernels chosen from cyclic permutation matrices. When L is a prime with primitive root 2, it was recently shown that a scalar linear solution over GF(2L-1) induces an Ldimensional circular-shift linear solution at rate (L-1)/L. In this work, we prove that for an arbitrary odd L, every scalar linear solution over GF(2(m)L), where mLrefers to the multiplicative order of 2 modulo L, can induce an L-dimensional circularshift linear solution at a certain rate. Based on the generalized connection, we further prove that every multicast network has an L-dimensional circular-shift linear solution at rate φ(L)/L, where φ(L) is the Euler's totient function of L and (m)Lis beyond a threshold. Stemming from this, we last prove that every multicast network is asymptotically circular-shift linearly solvable.

We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations at intermediate nodes consist of only circular-shifts and bitwise 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 δ are summation of at most δ cyclic-permutation matrices of size L. Under this framework, an intrinsic connection between scalar LNC and circular-shift LNC is established. In consequence, for some block lengths L, an (L - 1, L)-fractional circular-shift linear solution of arbitrary degree δ can be efficiently constructed on a multicast network. With different δ, the constructed solution has an interesting encoding-decoding complexity tradeoff, and when δ = (L - 1)/2, it requires fewer binary operations for both encoding and decoding processes compared with scalar LNC. While the constructed (L - 1, L)-fractional 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.