Maxwell Construction: The Hidden Bridge Between Iterative and Maximuma PosterioriDecoding

DOI10.1109/TIT.2008.2006466zbMATH Open1319.94027arXivcs/0506083OpenAlexW4292232932MaRDI QIDQ3604902FDOQ3604902

Ruediger Urbanke, Cyril Measson, Andrea Montanari

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0506083

Recommendations

• Bounds on the performance of belief propagation decoding
• A joint decoding algorithm of LDPC codes
• Cross-entropy and iterative decoding
• Iterative decoding of binary block and convolutional codes
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs

zbMATH Keywords

entropythresholdmaximum likelihoodphase transitionarea theoremMaxwell constructionmaximum a posteriori (MAP)belief propagation (BP)EXIT curve

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Linear codes (general theory) (94B05)

Cited In (3)

• Information-theoretic thresholds from the cavity method
• Reed-Muller Codes
• The all-or-nothing phenomenon in sparse linear regression

This page was built for publication: Maxwell Construction: The Hidden Bridge Between Iterative and Maximuma PosterioriDecoding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604902)