Circular-shift Linear Network Codes with Arbitrary Odd Block Lengths
share
Circular-shift linear network coding (LNC) is a special type 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(2^L-1) can induce an L-dimensional 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 m_L 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 every multicast network, as long as m_L is larger than a threshold, there exists an L-dimensional circular-shift linear solution at rate ϕ(L)/L, where ϕ(L) means the Euler's totient function of L. An efficient algorithm for constructing such a solution is also designed. Finally, we prove that every multicast network is asymptotically circular-shift linearly solvable.
READ FULL TEXT