Polar codes for distributed hierarchical source coding

Previous Article
Derived and residual subspace designs
AMC Home
This Issue
Next Article
Multiple coverings of the farthest-off points with small density from projective geometry

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

Abstract
Related Papers

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.
[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.
[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.
[4]	E. Arikan, Source polarization, in Proc. IEEE Int. Symp. Inf. Theory, Austin, 2010, 899-903. doi: 10.1109/ISIT.2010.5513567.
[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.
[6]	W. Equitz and T. Cover, Successive refinement of information, IEEE Trans. Inform. Theory, 37 (1991), 269-275. doi: 10.1109/18.75242.
[7]	T. C. Gulcu and A. Barg, Achieving secrecy capacity of the wiretap channel and broadcast channel with a confidential component,, preprint, ().
[8]	T. C. Gulcu and A. Barg, Interactive function computation via polar coding,, preprint, ().
[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.
[10]	S. B. Korada, Polar Codes for Channel and Source Coding, Ph.D thesis, EPFL, 2009. doi: 10.5075/epfl-thesis-4461.
[11]	V. N. Koshelev, Hierarchical coding of discrete sources, Probl. Inform. Trans., 16 (1980), 11-19.
[12]	V. N. Koshelev, Estimation of mean error for a discrete successive-approximation scheme, Probl. Inform. Trans., 17 (1981), 20-33.
[13]	V. N. Koshelev, Divisibility of discrete sources with symbol-wise additive error measure, Probl. Inform. Trans., 30 (1994), 31-50.
[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.
[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.
[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.
[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.
[18]	B. Rimoldi, Successive refinement of information: Characterization of achievable rates, IEEE Trans. Inform. Theory, 40 (1994), 253-259. doi: 10.1109/18.272493.
[19]	A. Sahebi and S. S. Pradhan, Polar codes for some multi-terminal communications problems,, preprint, ().
[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.
[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.
[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.

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.
[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.
[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.
[4]	E. Arikan, Source polarization, in Proc. IEEE Int. Symp. Inf. Theory, Austin, 2010, 899-903. doi: 10.1109/ISIT.2010.5513567.
[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.
[6]	W. Equitz and T. Cover, Successive refinement of information, IEEE Trans. Inform. Theory, 37 (1991), 269-275. doi: 10.1109/18.75242.
[7]	T. C. Gulcu and A. Barg, Achieving secrecy capacity of the wiretap channel and broadcast channel with a confidential component,, preprint, ().
[8]	T. C. Gulcu and A. Barg, Interactive function computation via polar coding,, preprint, ().
[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.
[10]	S. B. Korada, Polar Codes for Channel and Source Coding, Ph.D thesis, EPFL, 2009. doi: 10.5075/epfl-thesis-4461.
[11]	V. N. Koshelev, Hierarchical coding of discrete sources, Probl. Inform. Trans., 16 (1980), 11-19.
[12]	V. N. Koshelev, Estimation of mean error for a discrete successive-approximation scheme, Probl. Inform. Trans., 17 (1981), 20-33.
[13]	V. N. Koshelev, Divisibility of discrete sources with symbol-wise additive error measure, Probl. Inform. Trans., 30 (1994), 31-50.
[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.
[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.
[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.
[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.
[18]	B. Rimoldi, Successive refinement of information: Characterization of achievable rates, IEEE Trans. Inform. Theory, 40 (1994), 253-259. doi: 10.1109/18.272493.
[19]	A. Sahebi and S. S. Pradhan, Polar codes for some multi-terminal communications problems,, preprint, ().
[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.
[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.
[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.

[1]	Xueling Zhou, Meixia Li, Haitao Che. Relaxed successive projection algorithm with strong convergence for the multiple-sets split equality problem. Journal of Industrial and 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 and Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
[3]	Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems and Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044
[4]	Noam Presman, Simon Litsyn. Recursive descriptions of polar codes. Advances in Mathematics of Communications, 2017, 11 (1) : 1-65. doi: 10.3934/amc.2017001
[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 and 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 and 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 and 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 and Related Models, 2021, 14 (6) : 981-1002. doi: 10.3934/krm.2021035
[10]	Nahid Banihashemi, C. Yalçın Kaya. Inexact restoration and adaptive mesh refinement for optimal control. Journal of Industrial and 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 and 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 and Continuous Dynamical Systems - S, 2014, 7 (3) : 543-556. doi: 10.3934/dcdss.2014.7.543
[13]	Michael Herty, Torsten Trimborn, Giuseppe Visconti. Mean-field and kinetic descriptions of neural differential equations. Foundations of Data Science, 2022, 4 (2) : 271-298. doi: 10.3934/fods.2022007
[14]	Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial and Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651
[15]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[16]	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
[17]	Barbara Kaltenbacher, Jonas Offtermatt. A refinement and coarsening indicator algorithm for finding sparse solutions of inverse problems. Inverse Problems and Imaging, 2011, 5 (2) : 391-406. doi: 10.3934/ipi.2011.5.391
[18]	Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete and Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453
[19]	Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553
[20]	Gaurav Nagpal, Udayan Chanda, Nitant Upasani. Inventory replenishment policies for two successive generations price-sensitive technology products. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1629-1650. doi: 10.3934/jimo.2021036

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Min Ye Alexander Barg
on Google Scholar
Min Ye Alexander Barg

[Back to Top]