Separating distributed source coding from network coding

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.


Publication typeInproceedings
Published inAllerton Conference on Communication, Control, and Computing
> Publications > Separating distributed source coding from network coding