Polar Codes are Optimal for Lossy Source Coding
arXiv:0903.0307
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 (8)
- Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
- Iterative Quantization Using Codes On Graphs
- Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
- Thouless-Anderson-Palmer Approach for Lossy Compression
- Binary quantization using Belief Propagation with decimation over factor graphs of LDGM codes
- Lossy data compression with random gates
- On the Rate of Channel Polarization
- Low-density graph codes that are optimal for source/channel coding and binning
Cited by in corpus (6)
- Lossy compression of discrete sources via Viterbi algorithm
- Channel Polarization on q-ary Discrete Memoryless Channels by Arbitrary Kernels
- Nested Polar Codes Achieve the Shannon Rate-Distortion Function and the Shannon Capacity
- An Algebraic Framework for Concatenated Linear Block Codes in Side Information Based Problems
- Analytical Framework of LDGM-based Iterative Quantization with Decimation
- Refined rate of channel polarization