Statistical mechanics of error exponents for error-correcting codes

Abstract

Error exponents characterize the exponential decay, when increasing message length, of the probability of error of many error-correcting codes. To tackle the long standing problem of computing them exactly, we introduce a general, thermodynamic, formalism that we illustrate with maximum-likelihood decoding of low-density parity-check (LDPC) codes on the binary erasure channel (BEC) and the binary symmetric channel (BSC). In this formalism, we apply the cavity method for large deviations to derive expressions for both the average and typical error exponents, which differ by the procedure used to select the codes from specified ensembles. When decreasing the noise intensity, we find that two phase transitions take place, at two different levels: a glass to ferromagnetic transition in the space of codewords, and a paramagnetic to glass transition in the space of codes.

32 pages, 13 figures

References in corpus (13)

• The Bethe lattice spin glass revisited
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Simplest random K-satisfiability problem
• The glassy phase of Gallager codes
• On the dynamics of the glass transition on Bethe lattices
• The Dynamic Phase Transition for Decoding Algorithms
• Landscape of solutions in constraint satisfaction problems
• From Large Scale Rearrangements to Mode Coupling Phenomenology
• Average and reliability error exponents in low-density parity-check codes
• The cavity method for large deviations
• Exactly solvable models of adaptive networks
• The polynomial error probability for LDPC codes

Cited by in corpus (8)

• Gallager error correcting codes for binary asymmetric channels
• Optimum estimation via gradients of partition functions and information measures: a statistical-mechanical perspective
• The random energy model in a magnetic field and joint source-channel coding
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Statistical mechanics of LDPC codes on channels with memory
• Statistical mechanical analysis of a hierarchical random code ensemble in signal processing
• An identity of Chernoff bounds with an interpretation in statistical physics and applications in information theory
• Relations between random coding exponents and the statistical physics of random codes