Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding

Abstract

There is a fundamental relationship between belief propagation and maximum a posteriori decoding. A decoding algorithm, which we call the Maxwell decoder, is introduced and provides a constructive description of this relationship. Both, the algorithm itself and the analysis of the new decoder are reminiscent of the Maxwell construction in thermodynamics. This paper investigates in detail the case of transmission over the binary erasure channel, while the extension to general binary memoryless channels is discussed in a companion paper.

29 pages, 77 ps files

References in corpus (1)

• Life Above Threshold: From List Decoding to Area Theorem and MSE

Cited by in corpus (30)

• Information-theoretic thresholds from the cavity method
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• Typology of phase transitions in Bayesian inference problems
• Inactivation Decoding of LT and Raptor Codes: Analysis and Code Design
• Performance Analysis and Design of Two Edge Type LDPC Codes for the BEC Wiretap Channel
• Sharp Bounds for Optimal Decoding of Low Density Parity Check Codes
• Threshold Saturation for Nonbinary SC-LDPC Codes on the Binary Erasure Channel
• Tree-structure Expectation Propagation for Decoding LDPC codes over Binary Erasure Channels
• Spectral Shape of Doubly-Generalized LDPC Codes: Efficient and Exact Evaluation
• A Probabilistic Peeling Decoder to Efficiently Analyze Generalized LDPC Codes Over the BEC
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Nonbinary Spatially-Coupled LDPC Codes on the Binary Erasure Channel
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• Spatially-Coupled Codes and Threshold Saturation on Intersymbol-Interference Channels
• Approaching Capacity at High-Rates with Iterative Hard-Decision Decoding
• Spatial Coupling as a Proof Technique
• Design and Analysis of LDGM-Based Codes for MSE Quantization
• On Achievable Rates and Complexity of LDPC Codes for Parallel Channels with Application to Puncturing
• Two Lectures on Iterative Coding and Statistical Mechanics
• Density Evolution, Thresholds and the Stability Condition for Non-binary LDPC Codes
• Tree-Structure Expectation Propagation for LDPC Decoding in Erasure Channels
• A Generalization of Threshold Saturation: Application to Spatially Coupled BICM-ID
• Improving the Finite-Length Performance of Spatially Coupled LDPC Codes by Connecting Multiple Code Chains
• Performance versus Complexity Per Iteration for Low-Density Parity-Check Codes: An Information-Theoretic Approach
• Effects of Single-Cycle Structure on Iterative Decoding for Low-Density Parity-Check Codes
• ML and Near-ML Decoding of LDPC Codes Over the BEC: Bounds and Decoding Algorithms
• Reed-Muller Codes: Theory and Algorithms
• Average Entropy Functions
• Analytical Framework of LDGM-based Iterative Quantization with Decimation
• Analysis of Spatially-Coupled Counter Braids