Iterative Quantization Using Codes On Graphs

Abstract

We study codes on graphs combined with an iterative message passing algorithm for quantization. Specifically, we consider the binary erasure quantization (BEQ) problem which is the dual of the binary erasure channel (BEC) coding problem. We show that duals of capacity achieving codes for the BEC yield codes which approach the minimum possible rate for the BEQ. In contrast, low density parity check codes cannot achieve the minimum rate unless their density grows at least logarithmically with block length. Furthermore, we show that duals of efficient iterative decoding algorithms for the BEC yield efficient encoding algorithms for the BEQ. Hence our results suggest that graphical models may yield near optimal codes in source coding as well as in channel coding and that duality plays a key role in such constructions.

10 pages

References in corpus (1)

• Constraint Satisfaction by Survey Propagation

Cited by in corpus (21)

• Binary quantization using Belief Propagation with decimation over factor graphs of LDGM codes
• Analysis of LDGM and compound codes for lossy compression and binning
• Encoding for the Blackwell Channel with Reinforced Belief Propagation
• Low density codes achieve the rate-distortion bound
• Low-density graph codes that are optimal for source/channel coding and binning
• Polar Codes are Optimal for Lossy Source Coding
• A Practical Approach to Lossy Joint Source-Channel Coding
• Design and Analysis of LDGM-Based Codes for MSE Quantization
• Lower Bounds on the Rate-Distortion Function of Individual LDGM Codes
• On Superposition Coding for the Wyner-Ziv Problem
• Approaching the Rate-Distortion Limit with Spatial Coupling, Belief propagation and Decimation
• Rewriting Flash Memories by Message Passing
• A Semiclassical Proof of Duality Between the Classical BSC and the Quantum PSC
• Performance of Polar Codes for Channel and Source Coding
• Low-density constructions can achieve the Wyner-Ziv and Gelfand-Pinsker bounds
• Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes
• Lossy Source Compression of Non-Uniform Binary Sources Using GQ-LDGM Codes
• Duality between erasures and defects
• Analytical Framework of LDGM-based Iterative Quantization with Decimation
• Blahut-Arimoto Algorithm and Code Design for Action-Dependent Source Coding Problems
• Lower Bounds on the Rate-Distortion Function of LDGM Codes