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

Abstract

We consider communication over memoryless channels using low-density parity-check code ensembles above the iterative (belief propagation) threshold. What is the computational complexity of decoding (i.e., of reconstructing all the typical input codewords for a given channel output) in this regime? We define an algorithm accomplishing this task and analyze its typical performance. The behavior of the new algorithm can be expressed in purely information-theoretical terms. Its analysis provides an alternative proof of the area theorem for the binary erasure channel. Finally, we explain how the area theorem is generalized to arbitrary memoryless channels. We note that the recently discovered relation between mutual information and minimal square error is an instance of the area theorem in the setting of Gaussian channels.

2004 IEEE Information Theory Workshop, San Antonio, October 24-29 (invited paper)

References in corpus (1)

• The Dynamic Phase Transition for Decoding Algorithms

Cited by in corpus (10)

• Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding
• Reed-Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for All Rates Below Capacity
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Optimum estimation via gradients of partition functions and information measures: a statistical-mechanical perspective
• Why We Can Not Surpass Capacity: The Matching Condition
• Low-Complexity LDPC Codes with Near-Optimum Performance over the BEC
• Two Lectures on Iterative Coding and Statistical Mechanics
• Density Evolution, Thresholds and the Stability Condition for Non-binary LDPC Codes
• The Generalized Area Theorem and Some of its Consequences
• Mutual Information and Minimum Mean-square Error in Gaussian Channels