Distributed Source Coding

SHUANG WANG, University of California, San Diego, USAYONG FANG, Northwest A&F University, China SAMUEL CHENG, University of Oklahoma, USA

• Preface xiiiAcknowledgment xvAbout the Companion Website xvii1 Introduction 11.1 What is Distributed Source Coding? 21.2 Historical Overview and Background 21.3 Potential and Applications 31.4 Outline 4Part I Theory of Distributed Source Coding 72 Lossless Compression of Correlated Sources 92.1 Slepian–Wolf Coding 102.1.1 Proof of the SWTheorem 15Achievability of the SWTheorem 16Converse of the SWTheorem 192.2 Asymmetric and Symmetric SWCoding 212.3 SWCoding of Multiple Sources 223 Wyner–Ziv Coding Theory 253.1 Forward Proof ofWZ Coding 273.2 Converse Proof of WZ Coding 293.3 Examples 303.3.1 Doubly Symmetric Binary Source 30Problem Setup 30A Proposed Scheme 31Verify the Optimality of the Proposed Scheme 323.3.2 Quadratic Gaussian Source 35Problem Setup 35Proposed Scheme 36Verify the Optimality of the Proposed Scheme 373.4 Rate Loss of theWZ Problem 38Binary Source Case 39Rate loss of General Cases 394 Lossy Distributed Source Coding 414.1 Berger–Tung Inner Bound 424.1.1 Berger–Tung Scheme 42Codebook Preparation 42Encoding 42Decoding 434.1.2 Distortion Analysis 434.2 Indirect Multiterminal Source Coding 454.2.1 Quadratic Gaussian CEO Problem with Two Encoders 45Forward Proof of Quadratic Gaussian CEO Problem with Two Terminals 46Converse Proof of Quadratic Gaussian CEO Problem with Two Terminals 484.3 Direct Multiterminal Source Coding 544.3.1 Forward Proof of Gaussian Multiterminal Source Coding Problem with Two Sources 554.3.2 Converse Proof of Gaussian Multiterminal Source Coding Problem with Two Sources 63Bounds for R1 and R2 64Collaborative Lower Bound 66𝜇-sum Bound 67Part II Implementation 755 Slepian–Wolf Code Designs Based on Channel Coding 775.1 Asymmetric SWCoding 775.1.1 Binning Idea 785.1.2 Syndrome-based Approach 79Hamming Binning 80SWEncoding 80SWDecoding 80LDPC-based SWCoding 815.1.3 Parity-based Approach 825.1.4 Syndrome-based Versus Parity-based Approach 845.2 Non-asymmetric SWCoding 855.2.1 Generalized Syndrome-based Approach 865.2.2 Implementation using IRA Codes 885.3 Adaptive Slepian–Wolf Coding 905.3.1 Particle-based Belief Propagation for SWCoding 915.4 Latest Developments and Trends 936 Distributed Arithmetic Coding 976.1 Arithmetic Coding 976.2 Distributed Arithmetic Coding 1016.3 Definition of the DAC Spectrum 1036.3.1 Motivations 1036.3.2 Initial DAC Spectrum 1046.3.3 Depth-i DAC Spectrum 1056.3.4 Some Simple Properties of the DAC Spectrum 1076.4 Formulation of the Initial DAC Spectrum 1076.5 Explicit Form of the Initial DAC Spectrum 1106.6 Evolution of the DAC Spectrum 1136.7 Numerical Calculation of the DAC Spectrum 1166.7.1 Numerical Calculation of the Initial DAC Spectrum 1176.7.2 Numerical Estimation of DAC Spectrum Evolution 1186.8 Analyses on DAC Codes with Spectrum 1206.8.1 Definition of DAC Codes 1216.8.2 Codebook Cardinality 1226.8.3 Codebook Index Distribution 1236.8.4 Rate Loss 1236.8.5 Decoder Complexity 1246.8.6 Decoding Error Probability 1266.9 Improved Binary DAC Codec 1306.9.1 Permutated BDAC Codec 130Principle 130Proof of SWLimit Achievability 1316.9.2 BDAC Decoder withWeighted Branching 1326.10 Implementation of the Improved BDAC Codec 1346.10.1 Encoder 134Principle 134Implementation 1356.10.2 Decoder 135Principle 135Implementation 1366.11 Experimental Results 138Effect of Segment Size on Permutation Technique 139Effect of Surviving-Path Number onWB Technique 139Comparison with LDPC Codes 139Application of PBDAC to Nonuniform Sources 1406.12 Conclusion 1417 Wyner–Ziv Code Design 1437.1 Vector Quantization 1437.2 Lattice Theory 1467.2.1 What is a Lattice? 146Examples 146Dual Lattice 147Integral Lattice 147Lattice Quantization 1487.2.2 What is a Good Lattice? 149Packing Efficiency 149Covering Efficiency 150Normalized Second Moment 150Kissing Number 150Some Good Lattices 1517.3 Nested Lattice Quantization 151Encoding/decoding 152Coset Binning 152Quantization Loss and Binning Loss 153SW Coded NLQ 1547.3.1 Trellis Coded Quantization 1547.3.2 Principle of TCQ 155Generation of Codebooks 156Generation of Trellis from Convolutional Codes 156Mapping of Trellis Branches onto Sub-codebooks 157Quantization 157Example 1587.4 WZ Coding Based on TCQ and LDPC Codes 1597.4.1 Statistics of TCQ Indices 1597.4.2 LLR of Trellis Bits 1627.4.3 LLR of Codeword Bits 1637.4.4 Minimum MSE Estimation 1637.4.5 Rate Allocation of Bit-planes 1647.4.6 Experimental Results 166Part III Applications 1678 Wyner–Ziv Video Coding 1698.1 Basic Principle 1698.2 Benefits of WZ Video Coding 1708.3 Key Components of WZ Video Decoding 1718.3.1 Side-information Preparation 171Bidirectional Motion Compensation 1728.3.2 Correlation Modeling 173Exploiting Spatial Redundancy 1748.3.3 Rate Controller 1758.4 Other Notable Features of Miscellaneous WZ Video Coders 1759 Correlation Estimation in DVC 1779.1 Background to Correlation Parameter Estimation in DVC 1779.1.1 Correlation Model inWZ Video Coding 1779.1.2 Offline Correlation Estimation 178Pixel Domain Offline Correlation Estimation 178Transform Domain Offline Correlation Estimation 1809.1.3 Online Correlation Estimation 181Pixel Domain Online Correlation Estimation 182Transform Domain Online Correlation Estimation 1849.2 Recap of Belief Propagation and Particle Filter Algorithms 1859.2.1 Belief Propagation Algorithm 1859.2.2 Particle Filtering 1869.3 Correlation Estimation in DVC with Particle Filtering 1879.3.1 Factor Graph Construction 1879.3.2 Correlation Estimation in DVC with Particle Filtering 1909.3.3 Experimental Results 1929.3.4 Conclusion 1979.4 Low Complexity Correlation Estimation using Expectation Propagation 1999.4.1 System Architecture 1999.4.2 Factor Graph Construction 199Joint Bit-plane SWCoding (Region II) 200Correlation Parameter Tracking (Region I) 2019.4.3 Message Passing on the Constructed Factor Graph 202Expectation Propagation 2039.4.4 Posterior Approximation of the Correlation Parameter using Expectation Propagation 204Moment Matching 2059.4.5 Experimental Results 2069.4.6 Conclusion 21110 DSC for Solar Image Compression 21310.1 Background 21310.2 RelatedWork 21510.3 Distributed Multi-view Image Coding 21710.4 Adaptive Joint Bit-plane WZ Decoding of Multi-view Images with Disparity Estimation 21710.4.1 Joint Bit-planeWZ Decoding 21710.4.2 Joint Bit-planeWZ Decoding with Disparity Estimation 21910.4.3 Joint Bit-planeWZ Decoding with Correlation Estimation 22010.5 Results and Discussion 22110.6 Summary 22411 Secure Distributed Image Coding 22511.1 Background 22511.2 System Architecture 22711.2.1 Compression of Encrypted Data 22811.2.2 Joint Decompression and Decryption Design 23011.3 Practical Implementation Issues 23311.4 Experimental Results 23311.4.1 Experiment Setup 23411.4.2 Security and Privacy Protection 23511.4.3 Compression Performance 23611.5 Discussion 23912 Secure Biometric Authentication Using DSC 24112.1 Background 24112.2 RelatedWork 24312.3 System Architecture 24512.3.1 Feature Extraction 24612.3.2 Feature Pre-encryption 24812.3.3 SeDSC Encrypter/decrypter 24812.3.4 Privacy-preserving Authentication 24912.4 SeDSC Encrypter Design 24912.4.1 Non-asymmetric SWCodes with Code Partitioning 25012.4.2 Implementation of SeDSC Encrypter using IRA Codes 25112.5 SeDSC Decrypter Design 25212.6 Experiments 25612.6.1 Dataset and Experimental Setup 25612.6.2 Feature Length Selection 25712.6.3 Authentication Accuracy 257Authentication Performances on Small Feature Length (i.e., N = 100) 257Performances on Large Feature Lengths (i.e., N ≥ 300) 25812.6.4 Privacy and Security 25912.6.5 Complexity Analysis 26112.7 Discussion 261A Basic Information Theory 263A.1 Information Measures 263A.1.1 Entropy 263A.1.2 Relative Entropy 267A.1.3 Mutual Information 268A.1.4 Entropy Rate 269A.2 Independence and Mutual Information 270A.3 Venn Diagram Interpretation 273A.4 Convexity and Jensen’s Inequality 274A.5 Differential Entropy 277A.5.1 Gaussian Random Variables 278A.5.2 Entropy Power Inequality 278A.6 Typicality 279A.6.1 Jointly Typical Sequences 282A.7 Packing Lemmas and Covering Lemmas 284A.8 Shannon’s Source CodingTheorem 286A.9 Lossy Source Coding—Rate-distortionTheorem 289A.9.1 Rate-distortion Problem with Side Information 291B Background on Channel Coding 293B.1 Linear Block Codes 294B.1.1 Syndrome Decoding of Block Codes 295B.1.2 Hamming Codes, Packing Bound, and Perfect Codes 295B.2 Convolutional Codes 297B.2.1 Viterbi Decoding Algorithm 298B.3 Shannon’s Channel CodingTheorem 301B.3.1 Achievability Proof of the Channel CodingTheorem 303B.3.2 Converse Proof of Channel CodingTheorem 305B.4 Low-density Parity-check Codes 306B.4.1 A Quick Summary of LDPC Codes 306B.4.2 Belief Propagation Algorithm 307B.4.3 LDPC Decoding using BP 312B.4.4 IRA Codes 314C Approximate Inference 319C.1 Stochastic Approximation 319C.1.1 Importance SamplingMethods 320C.1.2 Markov Chain Monte Carlo 321Markov Chains 321Markov Chain Monte Carlo 321C.2 Deterministic Approximation 322C.2.1 Preliminaries 322Exponential Family 322Kullback–Leibler Divergence 323Assumed-density Filtering 324C.2.2 Expectation Propagation 325Relationship with BP 326C.2.3 Relationship with Other Variational Inference Methods 328D Multivariate Gaussian Distribution 331D.1 Introduction 331D.2 Probability Density Function 331D.3 Marginalization 332D.4 Conditioning 333D.5 Product of Gaussian pdfs 334D.6 Division of Gaussian pdfs 337D.7 Mixture of Gaussians 337D.7.1 Reduce the Number of Components in Gaussian Mixtures 338Which Components to Merge? 340How to Merge Components? 341D.8 Summary 342Appendix: Matrix Equations 343Bibliography 345Index 357