A Simple Proof of Threshold Saturation for Coupled Scalar Recursions
Prof. Henry Pfister
Recorded 07 June 2012 in Lausanne, Vaud, Switzerland
Event: SuRI - I&C - Summer Research Institute
It is well-known that belief-propagation (BP) decoding of low-density parity-check (LDPC) codes is suboptimal and that the noise threshold of maximum-a-posteriori (MAP) decoding can be larger than the BP threshold. Recently, Kudekar et al. showed that regular LDPC ensembles can be "spatially coupled" so that their BP noise threshold saturates to the MAP noise threshold of the original ensemble. These new ensembles are actually LDPC convolutional (LDPCC) codes and the new result explains an earlier observation by Lentmaier et al. that terminated LDPCC codes allow reliable communication at rates very close to capacity.
From a statistical physics point of view, LDPC codes can be associated with a collection of electrons whose spins are coupled. Above the MAP threshold, this system behaves like a liquid. Below the BP threshold, this system spontaneously crystallizes into the minimum-energy configuration. If the noise level is between the BP threshold and the MAP threshold, the system behaves like a super-cooled liquid: the system remains a liquid unless there is a seed crystal to start the crystal growth. Spatial coupling alters the ensemble to include a seed crystal and allows the information to crystallize when the noise is below the MAP threshold.
This talk presents a simple proof of threshold saturation that applies to a broad class of coupled scalar recursions. In particular, it applies to the density-evolution (DE) equations of irregular LDPC codes on the erasure channel and the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise. Extensions to coupled vector recursions will also be discussed along with their connection to universality in multiuser scenarios.
Watched 12886 times.Watch