Toward One Symbol Network Coding Vectors

Abstract—In this paper, we propose a novel design for network coding vectors that limits the overhead information. Network coding vectors contain information regarding the operations the packets have undergone in the network nodes. They are used at the decoder side to invert coding operations and recover the data. We propose to reduce the size of this side information with the use of Vandermonde-like generator matrices at the sources. These matrices permit to describe the coding operations performed on packets with only one symbol. We analytically investigate the limitations arising from such design constraints. Interestingly, we find that the feasible generation size is upper bounded by log2 q in Galois field Fq of size q as this is the maximum packet diversity allowed by the employed generator matrices. In addition, we show that network coding nodes should only perform addition operations in order to maintain the properties of the coding vectors. We finally discuss the benefits and limitations of the proposed coding vectors in practical systems. Index Terms—Network coding, coding vectors, header com-pression. I