Rank deficient decoding of linear network coding

Since all packets in linear network coding are subject to linear combinations, in all existing network coding schemes, a full rank of received packets is required to start decoding. This requirement unfortunately results in long delays and low throughputs. In this work we propose two classes of rank deficient decoders that work for rank deficient received packets. Within either class, different decoding strategies have been proposed for tradeoffs between delay/throughput and data accuracy. The decoders of the first class take advantage of the sparsity inherent in data and produce the data vectors with the smallest Hamming weight. Since these decoders have high complexities, we propose a class of decoders with polynomial complexities based on linear programming. Both classes of decoders can recover data from fewer received packets and hence achieve higher throughputs and shorter delays than the full rank decoder.