American Institute of Mathematical Sciences

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

Polar codes for distributed hierarchical source coding

Min Ye 1, and  Alexander Barg 2,

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.
Keywords: Successive refinement, multiple descriptions., divisible source.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.
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-5448. 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-726. 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-3073. doi: 10.1109/TIT.2009.2021379.  Google Scholar

[4]

E. Arikan, Source polarization, in Proc. IEEE Int. Symp. Inf. Theory, Austin, 2010, 899-903. 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-275. 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-275. 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-7838. doi: 10.1109/TIT.2013.2282305.  Google Scholar

[10]

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

[11]

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

[12]

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

[13]

V. N. Koshelev, Divisibility of discrete sources with symbol-wise additive error measure, Probl. Inform. Trans., 30 (1994), 31-50.  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-6443. 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-800. 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-2736. 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-969. 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-259. 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-1654. 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-10. 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-1524. 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-5448. 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-726. 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-3073. doi: 10.1109/TIT.2009.2021379.  Google Scholar

[4]

E. Arikan, Source polarization, in Proc. IEEE Int. Symp. Inf. Theory, Austin, 2010, 899-903. 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-275. 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-275. 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-7838. doi: 10.1109/TIT.2013.2282305.  Google Scholar

[10]

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

[11]

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

[12]

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

[13]

V. N. Koshelev, Divisibility of discrete sources with symbol-wise additive error measure, Probl. Inform. Trans., 30 (1994), 31-50.  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-6443. 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-800. 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-2736. 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-969. 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-259. 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-1654. 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-10. 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-1524. doi: 10.1109/ALLERTON.2009.5394494.  Google Scholar

[1]

Xueling Zhou, Meixia Li, Haitao Che. Relaxed successive projection algorithm with strong convergence for the multiple-sets split equality problem. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2557-2572. doi: 10.3934/jimo.2020082
[2]

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
[3]

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

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
[5]

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
[6]

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
[7]

Claudio Arancibia-Ibarra, José Flores, Michael Bode, Graeme Pettet, Peter van Heijster. A modified May–Holling–Tanner predator-prey model with multiple Allee effects on the prey and an alternative food source for the predator. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 943-962. doi: 10.3934/dcdsb.2020148
[8]

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
[9]

Sara Bernardi, Gissell Estrada-Rodriguez, Heiko Gimperlein, Kevin J. Painter. Macroscopic descriptions of follower-leader systems. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021035
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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

Gaurav Nagpal, Udayan Chanda, Nitant Upasani. Inventory replenishment policies for two successive generations price-sensitive technology products. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021036
[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy