Circular-shift Network Coding

The essence of network coding(NC)theory is to allow the intermediate nodes in a network encode received messages,so as to enhance the network throughput,reliability,security and reduce the transmission delay.At present,the computational overhead of NC has become one of the bottlenecks that hinder its practical deployment.As circular-shift operations can be very efficiently implemented by software and hardware,they have been utilized in the design of channel coding technologies such as quasi-cyclic LDPC codes and array codes.In order to decrease the coding complexity in network coding,in this thesis,we study a novel linear NC technique based on circular-shift operations.Particularly,we establish a theoretical framework of circular-shift NC based on the concept of vector NC.This framework facilitates us to obtain the following three fundamental results as:(?)unveiling an intrinsic connection between scalar NC and circular-shift NC(?)designing an algorithm of constructing a circular-shift NC solution in a multicast network(?)characterizing the multicast capacity of the circular-shift NC.First,by modeling the circular-shift operation of a binary vector of length L to the right as postmultiplication of a circular-shift matrix,we formulate circular-shift NC as a special type of vector NC.Since we show that the capacity of some classical multicast networks cannot be exactly achieved by circular-shift NC,we introduce the concept of fractional circular-shift linear solutions.For an arbitrary odd L,we unveil an intrinsic connection between scalar NC and circular-shift NC such that every scalar linear solution over GF(2mL)can induce a circular-shift linear code,which can be further turned into a linear solution at a certain rate by appropriately designing a precoding matrix at the source at a certain rate.Herein mL refers to the multiplicative order of 2 modulo L.As an extension of the induced circular-shift linear solution at a certain rate,we further prove that there exists a circular-shift linear solution at rate ?(L)/L in every multicast network,where ?(L)refers to the Euler's totient function of L.In addition to proving the existence of a circular-shift linear solution at rate?(L)/L,we further investigate how to construct such a solution in the second part of this thesis.Based on the classical flow path algorithm,we design a polynomial-time iterative algorithm to construct the local encoding kernels at intermediate nodes.Different from an exact vector linear solution,a fractional linear solution requires an extra source precoding matrix.We further introduce a general method to construct a precoding matrix at the source and the corresponding decoding matrix at receivers.Based on the above general method,some special instances of precoding matrices with low implementation complexity are also listed in this part.In the third part of this thesis,we further characterize the multicast capacity of circular-shift network coding.First,we prove that there exists an exact circular-shift linear solution over GF(2)if and only if there exists a scalar linear solution over GF(2)in a multicast network,which justifies that the consideration of circular-shift linear solution at a rate less than 1 is necessary in the above two parts.Moreover,by deterministically constructing a circular-shift linear solution at rate(L-1)/L with a prime L,we prove that circular-shift NC can asymptotically approach the multicast capacity.On the other hand,we also prove the same asymptotical behavior of circular-shift NC from the perspective of random codes.To keep this thesis self-contained,we focus on multicast networks as the network model and the finite fields of characteristic 2 as the alphabets.However,some theoretical results are not limited to the above settings and can be extended to general networks or finite fields of general characteristics.Such extensions,wherever possible,are remarked in the thesis.