Separating Distributed Source Coding from Network Coding

This work considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Work by Ho et. al [1] demonstrates that random network coding can solve this problem at the high cost of jointly decoding the source and the network code. Motivated by complexity considerations we consider the problem of separating the source coding from the delivery of an appropriate number of coded bits to each receiver. A multiplicative factor called the \price of separation” is defined that measures the gap to separability for a particular network and source distribution. Both networks with capacities and networks with costs on links are studied. We show that the problem with 2 sources and 2 receivers is always separable, and present counter-examples for other cases. Bounds re presented on the \price of separation”. While examples can be constructed where separation does not hold, our experimental results show that in most cases separation holds implying that existing solutions to the classical Slepian-Wolf problem can be effectively used over a network as well.