skip to main content
article

Separating distributed source coding from network coding

Published: 01 June 2006 Publication History

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]
{8} R. Koetter and M. Médard, "An algebraic approach to network coding," IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 782-795, 2003.
[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]
{20} K. Jain, M. Mahdian, and M. R. Salavatipour, "Packing Steiner trees," in SODA, 2003.
[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.

Cited By

View all
  • (2009)Practical source-network decodingProceedings of the 6th international conference on Symposium on Wireless Communication Systems10.5555/1719380.1719447(283-287)Online publication date: 7-Sep-2009
  • (2009)Joint distributed source and network coding for multiple wireless unicast sessionsProceedings of the 2009 IEEE conference on Wireless Communications & Networking Conference10.5555/1688345.1688400(302-306)Online publication date: 5-Apr-2009
  • (2009)Joint source-channel coding for transmitting correlated sources over broadcast networksIEEE Transactions on Information Theory10.1109/TIT.2009.202372255:8(3864-3868)Online publication date: 1-Aug-2009
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 14, Issue SI
Special issue on networking and information theory
June 2006
475 pages

Publisher

IEEE Press

Publication History

Published: 01 June 2006
Published in TON Volume 14, Issue SI

Author Tags

  1. distributed source coding
  2. multicast
  3. network coding
  4. separation

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 10 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2009)Practical source-network decodingProceedings of the 6th international conference on Symposium on Wireless Communication Systems10.5555/1719380.1719447(283-287)Online publication date: 7-Sep-2009
  • (2009)Joint distributed source and network coding for multiple wireless unicast sessionsProceedings of the 2009 IEEE conference on Wireless Communications & Networking Conference10.5555/1688345.1688400(302-306)Online publication date: 5-Apr-2009
  • (2009)Joint source-channel coding for transmitting correlated sources over broadcast networksIEEE Transactions on Information Theory10.1109/TIT.2009.202372255:8(3864-3868)Online publication date: 1-Aug-2009
  • (2009)On practical design for joint distributed source and network codingIEEE Transactions on Information Theory10.1109/TIT.2009.201301655:4(1709-1720)Online publication date: 1-Apr-2009
  • (2009)Universal source coding over generalized complementary delivery networksIEEE Transactions on Information Theory10.1109/TIT.2008.201143855:3(1360-1373)Online publication date: 1-Mar-2009
  • (2007)Information fusion for wireless sensor networksACM Computing Surveys10.1145/1267070.126707339:3(9-es)Online publication date: 3-Sep-2007
  • (2006)On optimal communication cost for gathering correlated data through wireless sensor networksProceedings of the 12th annual international conference on Mobile computing and networking10.1145/1161089.1161124(310-321)Online publication date: 29-Sep-2006

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media