Polar Codes are Optimal for Lossy Source Coding

Abstract

We consider lossy source compression of a binary symmetric source using polar codes and the low-complexity successive encoding algorithm. It was recently shown by Arikan that polar codes achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a successive decoding strategy. We show the equivalent result for lossy source compression, i.e., we show that this combination achieves the rate-distortion bound for a binary symmetric source. We further show the optimality of polar codes for various problems including the binary Wyner-Ziv and the binary Gelfand-Pinsker problem

15 pages, submitted to Transactions on Information Theory

References in corpus (3)

• Binary quantization using Belief Propagation with decimation over factor graphs of LDGM codes
• On the Rate of Channel Polarization
• Low-density graph codes that are optimal for source/channel coding and binning