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]

Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577

[2]

Noam Presman, Simon Litsyn. Recursive descriptions of polar codes. Advances in Mathematics of Communications, 2017, 11 (1) : 1-65. doi: 10.3934/amc.2017001

[3]

Sharif E. Guseynov, Eugene A. Kopytov, Edvin Puzinkevich. On continuous models of current stock of divisible productions. Conference Publications, 2011, 2011 (Special) : 601-613. doi: 10.3934/proc.2011.2011.601

[4]

Walter Briec, Bernardin Solonandrasana. Some remarks on a successive projection sequence. Journal of Industrial & Management Optimization, 2006, 2 (4) : 451-466. doi: 10.3934/jimo.2006.2.451

[5]

Seung-Yeal Ha, Eitan Tadmor. From particle to kinetic and hydrodynamic descriptions of flocking. Kinetic & Related Models, 2008, 1 (3) : 415-435. doi: 10.3934/krm.2008.1.415

[6]

Nahid Banihashemi, C. Yalçın Kaya. Inexact restoration and adaptive mesh refinement for optimal control. Journal of Industrial & Management Optimization, 2014, 10 (2) : 521-542. doi: 10.3934/jimo.2014.10.521

[7]

Ludovic Rifford. Refinement of the Benoist theorem on the size of Dini subdifferentials. Communications on Pure & Applied Analysis, 2008, 7 (1) : 119-124. doi: 10.3934/cpaa.2008.7.119

[8]

Francesca Marcellini. Free-congested and micro-macro descriptions of traffic flow. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 543-556. doi: 10.3934/dcdss.2014.7.543

[9]

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651

[10]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[11]

Giuseppe D'Onofrio, Enrica Pirozzi. Successive spike times predicted by a stochastic neuronal model with a variable input signal. Mathematical Biosciences & Engineering, 2016, 13 (3) : 495-507. doi: 10.3934/mbe.2016003

[12]

Barbara Kaltenbacher, Jonas Offtermatt. A refinement and coarsening indicator algorithm for finding sparse solutions of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 391-406. doi: 10.3934/ipi.2011.5.391

[13]

Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453

[14]

Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553

[15]

Guanghui Hu, Peijun Li, Xiaodong Liu, Yue Zhao. Inverse source problems in electrodynamics. Inverse Problems & Imaging, 2018, 12 (6) : 1411-1428. doi: 10.3934/ipi.2018059

[16]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485

[17]

Luís Tiago Paiva, Fernando A. C. C. Fontes. Sampled–data model predictive control: Adaptive time–mesh refinement algorithms and guarantees of stability. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2335-2364. doi: 10.3934/dcdsb.2019098

[18]

Ernan Haruvy, Ashutosh Prasad, Suresh Sethi, Rong Zhang. Competition with open source as a public good. Journal of Industrial & Management Optimization, 2008, 4 (1) : 199-211. doi: 10.3934/jimo.2008.4.199

[19]

Hui-Ling Li, Heng-Ling Wang, Xiao-Liu Wang. A quasilinear parabolic problem with a source term and a nonlocal absorption. Communications on Pure & Applied Analysis, 2018, 17 (5) : 1945-1956. doi: 10.3934/cpaa.2018092

[20]

Rinaldo M. Colombo, Graziano Guerra. Hyperbolic balance laws with a dissipative non local source. Communications on Pure & Applied Analysis, 2008, 7 (5) : 1077-1090. doi: 10.3934/cpaa.2008.7.1077

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (23)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]