February  2015, 9(1): 87-103. doi: 10.3934/amc.2015.9.87

Polar codes for distributed hierarchical source coding

1. 

Department of ECE and Institute for Systems Research, University of Maryland, College Park, MD 20742, United States

2. 

Dept. of ECE and Institute for Systems Research, University of Maryland, College Park, MD 20742

Received  May 2014 Published  February 2015

We show that polar codes can be used to achieve the rate-distortion functions in the problem of hierarchical source coding also known as the successive refinement problem. We also analyze the distributed version of this problem, constructing a polar coding scheme that achieves the rate distortion functions for successive refinement with side information.
Citation: Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87
References:
[1]

E. Abbe and E. Telatar, Polar codes for the $m$-user multiple access channel,, IEEE Trans. Inform. Theory, 58 (2012), 5437.  doi: 10.1109/TIT.2012.2201374.  Google Scholar

[2]

R. Ahlswede, The rate-distortion region for multiple descriptions without excess rates,, IEEE Trans. Inform. Theory, 31 (1985), 721.  doi: 10.1109/TIT.1985.1057102.  Google Scholar

[3]

E. Arikan, Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,, IEEE Trans. Inform. Theory, 55 (2009), 3051.  doi: 10.1109/TIT.2009.2021379.  Google Scholar

[4]

E. Arikan, Source polarization,, in Proc. IEEE Int. Symp. Inf. Theory, (2010), 899.  doi: 10.1109/ISIT.2010.5513567.  Google Scholar

[5]

A. El Gamal and T. Cover, Achievable rates for multiple descriptions,, IEEE Trans. Inform. Theory, 28 (1991), 269.  doi: 10.1109/TIT.1982.1056588.  Google Scholar

[6]

W. Equitz and T. Cover, Successive refinement of information,, IEEE Trans. Inform. Theory, 37 (1991), 269.  doi: 10.1109/18.75242.  Google Scholar

[7]

T. C. Gulcu and A. Barg, Achieving secrecy capacity of the wiretap channel and broadcast channel with a confidential component,, preprint, ().   Google Scholar

[8]

T. C. Gulcu and A. Barg, Interactive function computation via polar coding,, preprint, ().   Google Scholar

[9]

J. Honda and H. Yamamoto, Polar coding without alphabet extension for asymmetric models,, IEEE Trans. Inform. Theory, 59 (2013), 7829.  doi: 10.1109/TIT.2013.2282305.  Google Scholar

[10]

S. B. Korada, Polar Codes for Channel and Source Coding,, Ph.D thesis, (2009).  doi: 10.5075/epfl-thesis-4461.  Google Scholar

[11]

V. N. Koshelev, Hierarchical coding of discrete sources,, Probl. Inform. Trans., 16 (1980), 11.   Google Scholar

[12]

V. N. Koshelev, Estimation of mean error for a discrete successive-approximation scheme,, Probl. Inform. Trans., 17 (1981), 20.   Google Scholar

[13]

V. N. Koshelev, Divisibility of discrete sources with symbol-wise additive error measure,, Probl. Inform. Trans., 30 (1994), 31.   Google Scholar

[14]

H. Mahdavifar and A. Vardy, Achieving the secrecy capacity of wiretap channels using polar codes,, IEEE Trans. Inform. Theory, 57 (2011), 6428.  doi: 10.1109/TIT.2011.2162275.  Google Scholar

[15]

M. Mondelli, H. Hassani, I. Sason and R. L. Urbanke, Achieving Marton's region for broadcast channels using polar codes,, IEEE Trans. Inform. Theory, 61 (2015), 783.  doi: 10.1109/TIT.2014.2368555.  Google Scholar

[16]

R. Mori and T. Tanaka, Source and channel polarization over finite fields and Reed-Solomon matrices,, IEEE Trans. Inform. Theory, 60 (2014), 2720.  doi: 10.1109/TIT.2014.2312181.  Google Scholar

[17]

W. Park and A. Barg, Polar codes for $q$-ary channels, $q=2^r$,, IEEE Trans. Inform. Theory, 59 (2013), 955.  doi: 10.1109/TIT.2012.2219035.  Google Scholar

[18]

B. Rimoldi, Successive refinement of information: Characterization of achievable rates,, IEEE Trans. Inform. Theory, 40 (1994), 253.  doi: 10.1109/18.272493.  Google Scholar

[19]

A. Sahebi and S. S. Pradhan, Polar codes for some multi-terminal communications problems,, preprint, ().   Google Scholar

[20]

Y. Steinberg and N. Merhav, On successive refinement for the Wyner-Ziv problem,, IEEE Trans. Inform. Theory, 50 (2004), 1636.  doi: 10.1109/TIT.2004.831781.  Google Scholar

[21]

A. Wyner and J. Ziv, The rate-distortion function for source coding with side information at the decoder,, IEEE Trans. Inform. Theory, 22 (1976), 1.  doi: 10.1109/TIT.1976.1055508.  Google Scholar

[22]

Y. Zhang, S. Dumitrescu, J. Chen and Z. Sun, LDGM-based codes for successive refinement,, in 47th Ann. Allerton Conf. Commun. Control Comput., (2009), 1518.  doi: 10.1109/ALLERTON.2009.5394494.  Google Scholar

show all references

References:
[1]

E. Abbe and E. Telatar, Polar codes for the $m$-user multiple access channel,, IEEE Trans. Inform. Theory, 58 (2012), 5437.  doi: 10.1109/TIT.2012.2201374.  Google Scholar

[2]

R. Ahlswede, The rate-distortion region for multiple descriptions without excess rates,, IEEE Trans. Inform. Theory, 31 (1985), 721.  doi: 10.1109/TIT.1985.1057102.  Google Scholar

[3]

E. Arikan, Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,, IEEE Trans. Inform. Theory, 55 (2009), 3051.  doi: 10.1109/TIT.2009.2021379.  Google Scholar

[4]

E. Arikan, Source polarization,, in Proc. IEEE Int. Symp. Inf. Theory, (2010), 899.  doi: 10.1109/ISIT.2010.5513567.  Google Scholar

[5]

A. El Gamal and T. Cover, Achievable rates for multiple descriptions,, IEEE Trans. Inform. Theory, 28 (1991), 269.  doi: 10.1109/TIT.1982.1056588.  Google Scholar

[6]

W. Equitz and T. Cover, Successive refinement of information,, IEEE Trans. Inform. Theory, 37 (1991), 269.  doi: 10.1109/18.75242.  Google Scholar

[7]

T. C. Gulcu and A. Barg, Achieving secrecy capacity of the wiretap channel and broadcast channel with a confidential component,, preprint, ().   Google Scholar

[8]

T. C. Gulcu and A. Barg, Interactive function computation via polar coding,, preprint, ().   Google Scholar

[9]

J. Honda and H. Yamamoto, Polar coding without alphabet extension for asymmetric models,, IEEE Trans. Inform. Theory, 59 (2013), 7829.  doi: 10.1109/TIT.2013.2282305.  Google Scholar

[10]

S. B. Korada, Polar Codes for Channel and Source Coding,, Ph.D thesis, (2009).  doi: 10.5075/epfl-thesis-4461.  Google Scholar

[11]

V. N. Koshelev, Hierarchical coding of discrete sources,, Probl. Inform. Trans., 16 (1980), 11.   Google Scholar

[12]

V. N. Koshelev, Estimation of mean error for a discrete successive-approximation scheme,, Probl. Inform. Trans., 17 (1981), 20.   Google Scholar

[13]

V. N. Koshelev, Divisibility of discrete sources with symbol-wise additive error measure,, Probl. Inform. Trans., 30 (1994), 31.   Google Scholar

[14]

H. Mahdavifar and A. Vardy, Achieving the secrecy capacity of wiretap channels using polar codes,, IEEE Trans. Inform. Theory, 57 (2011), 6428.  doi: 10.1109/TIT.2011.2162275.  Google Scholar

[15]

M. Mondelli, H. Hassani, I. Sason and R. L. Urbanke, Achieving Marton's region for broadcast channels using polar codes,, IEEE Trans. Inform. Theory, 61 (2015), 783.  doi: 10.1109/TIT.2014.2368555.  Google Scholar

[16]

R. Mori and T. Tanaka, Source and channel polarization over finite fields and Reed-Solomon matrices,, IEEE Trans. Inform. Theory, 60 (2014), 2720.  doi: 10.1109/TIT.2014.2312181.  Google Scholar

[17]

W. Park and A. Barg, Polar codes for $q$-ary channels, $q=2^r$,, IEEE Trans. Inform. Theory, 59 (2013), 955.  doi: 10.1109/TIT.2012.2219035.  Google Scholar

[18]

B. Rimoldi, Successive refinement of information: Characterization of achievable rates,, IEEE Trans. Inform. Theory, 40 (1994), 253.  doi: 10.1109/18.272493.  Google Scholar

[19]

A. Sahebi and S. S. Pradhan, Polar codes for some multi-terminal communications problems,, preprint, ().   Google Scholar

[20]

Y. Steinberg and N. Merhav, On successive refinement for the Wyner-Ziv problem,, IEEE Trans. Inform. Theory, 50 (2004), 1636.  doi: 10.1109/TIT.2004.831781.  Google Scholar

[21]

A. Wyner and J. Ziv, The rate-distortion function for source coding with side information at the decoder,, IEEE Trans. Inform. Theory, 22 (1976), 1.  doi: 10.1109/TIT.1976.1055508.  Google Scholar

[22]

Y. Zhang, S. Dumitrescu, J. Chen and Z. Sun, LDGM-based codes for successive refinement,, in 47th Ann. Allerton Conf. Commun. Control Comput., (2009), 1518.  doi: 10.1109/ALLERTON.2009.5394494.  Google Scholar

[1]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[2]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[3]

Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257

[4]

Stefan Ruschel, Serhiy Yanchuk. The spectrum of delay differential equations with multiple hierarchical large delays. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 151-175. doi: 10.3934/dcdss.2020321

[5]

Fanni M. Sélley. A self-consistent dynamical system with multiple absolutely continuous invariant measures. Journal of Computational Dynamics, 2021, 8 (1) : 9-32. doi: 10.3934/jcd.2021002

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (87)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]