Separating distributed source coding from network coding

ABSTRACT

This correspondence considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Each receiver seeks to reconstruct all of the original sources. The work by Ho et al. 2004 demonstrates that random network coding can solve this problem at the potentially high cost of jointly decoding the source and the network code. Motivated by complexity considerations we consider the performance of separate source and network codes. Previous work by Effros et al. 2003 demonstrates the failure of separation between source and network codes for nonmulticast networks.We demonstrate that failure for multicast networks. We study networks with capacity constraints on edges. It is shown that the problem with two sources and two receivers is always separable. Counterexamples are presented for other cases.

REFERENCES

• 1: [1] D. Slepian and J. Wolf, "Noiseless coding of correlated information sources," IEEE Trans. Inf. Theory, vol. IT-19, no. 4, pp. 471-480, Jul. 1973.
• 2: [2] I. Csiszár, "Linear codes for sources and source networks: Error exponents, universal coding," IEEE Trans. Inf. Theory, vol. IT-28, no. 4, pp. 585-592, Jul. 1982.
• 3: [3] S. S. Pradhan, J. Kusuma, and K. Ramchandran, "Distributed compression in a dense sensor network," IEEE Signal Process. Mag., Mar. 2003.
• 4: [4] J. Garcia-Frias and Y. Zhao, "Compression of correlated binary sources using turbo codes," IEEE Commun. Lett., vol. 5, pp. 417-419, Oct. 2001.
• 5: [5] Z. Xiong, A. D. Liveris, and S. Cheng, "Distributed source coding for sensor networks," IEEE Signal Process. Mag., Sep. 2004.
• 6: [6] R. Ahlswede, N. Cai, S.-Y. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, Jul. 2000.
• 7: [7] S.-Y. Li, R.W.Yeung, and N. Cai, "Linear network coding," IEEE Trans. Info. Theory, vol. 49, no. 2, pp. 371-381, 2003.
• 8: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 9: [9] T. Ho, M. Médard, J. Shi, M. Effros, and D. R. Karger, "On randomized network coding," in Proc. 41st Allerton Conf. Communication, Control and Computing, Monticello, IL, Sep. 2003.
• 10: [10] P. A. Chou, Y.Wu, and K. Jain, "Practical network coding," in Proc. 41st Allerton Conf. Communication, Control and Computing, Monticello, IL, Sep. 2003.
• 11: [11] A. Ramamoorthy, J. Shi, and R. D. Wesel, "On the capacity of network coding for random networks," IEEE Trans. Inf. Theory, vol. 51, no. 8, pp. 2878-2885, Aug. 2005.
• 12: [12] R. Cristescu, B. Beferull-Lozano, and M. Vetterli, "Networked Slepian-Wolf: Theory, algorithms and scaling laws," IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4057-4073, Dec. 2005.
• 13: [13] T. Ho, M. Médard, M. Effros, and R. Koetter, "Network coding for correlated sources," in Proc. Conf. Information Science and Systems, 2004.
• 14: [14] M. Effros, M. Médard, T. Ho, S. Ray, D. Karger, and R. Koetter, "Linear network codes: A unified framework for source, channel and network coding," in Proc. DIMACS Workshop Networking Information Theory, Piscataway, NJ, 2003.
• 15: [15] A.Wyner, "Recent results in Shannon theory," IEEE Trans. Inf. Theory, vol. IT-20, no. 1, pp. 2-10, Jan. 1974.
• 16: [16] S. S. Pradhan and K. Ramchandran, "Distributed source coding using syndromes (DISCUS): Design and construction," IEEE Trans. Inf. Theory, vol. 49, no. 3, pp. 626-643, Mar. 2003.
• 17: [17] J. Barros and S. D. Servetto, "Network information flow with correlated sources," IEEE Trans. Inf. Theory, vol. 52, no. 1, pp. 155-170, Jan. 2006.
• 18: [18] T. S. Han, "Slepian-Wolf-Cover theorem for a network of channels," Inf. Contr., vol. 47, no. 1, pp. 67-83, 1980.
• 19: [19] Y. Wu, V. Stanković, Z. Xiong, and S. Y. Kung, "On practical design for joint distributed source coding and network coding," in Proc. 1st Workshop Netw. Coding, Theory Applicat., Riva del Garda, Italy, 2005.
• 20: Kamal Jain , Mohammad Mahdian , Mohammad R. Salavatipour, Packing Steiner trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 21: [21] C. Fragouli and E. Soljanin, "Subtree decomposition for network coding," in Proc. IEEE Int. Symp. Information Theory, Chicago, IL, Jun./Jul. 2004, p. 145.
• 22: [22] A. Ramamoorthy, K. Jain, P. A. Chou, and M. Effros, ""Separating distributed source coding from network coding," Tech. Rep.," MSR, to be published.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Design studies

General Terms:
Design, Performance

Keywords:
distributed source coding, multicast, network coding, separation