Aditya Ramamoorthy, Kamal Jain, Philip A. Chou, and Michelle Effros
This work considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Work by Ho et al. demonstrates that random network coding can solve this problem at the high cost of jointly decod- ing the source and the network code. Motivated by complexity considerations we consider the problem of separating the source coding from the delivery of an ap- propriate 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 partic- ular 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 re- ceivers is always separable, and present counter-examples for other cases. Bounds are 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 prob- lem can be effectively used over a network as well.
|Published in||Allerton Conference on Communication, Control, and Computing|