Polar codes for distributed hierarchical source coding

Min Ye; Alexander Barg

doi:10.3934/amc.2015.9.87

Article Contents

2015, Volume 9, Issue 1: 87-103. Doi: 10.3934/amc.2015.9.87

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

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
2.
Dept. of ECE and Institute for Systems Research, University of Maryland, College Park, MD 20742

Received: May 2014

Published: February 2015

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

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, arXiv:1410.3422
[8]	T. C. Gulcu and A. Barg, Interactive function computation via polar coding, preprint, arXiv:1405.0894
[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, arXiv:1401.7006
[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.