Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform So Well over the BEC

By Shrinivas Kudekar, T. Richardson, Rüdiger L. Urbanke. IEEE Transactions on Information Theory, 2010

688 citations recorded by the source corpus.

Convolutional low-density parity-check (LDPC) ensembles, introduced by Felström and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing functions of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism that explains why “convolutional-like” or “spatially coupled” codes perform so well. In essence, the spatial coupling of individual codes increases the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum a posteriori (MAP) threshold of the underlying ensemble. For this reason, we call this phenomenon “threshold saturation.” This gives an entirely new way of approaching capacity. One significant advantage of this construction is that one can create capacity-approaching ensembles with an error correcting radius that is increasing in the blocklength. Although we prove the “threshold saturation” only for a specific ensemble and for the binary erasure channel (BEC), empirically the phenomenon occurs for a wide class of ensembles and channels. More generally, we conjecture that for a large range of graphical systems a similar saturation of the “dynamical” threshold occurs once individual components are coupled sufficiently strongly. This might give rise to improved algorithms and new techniques for analysis.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/0726f99e4d3a669f19b9245a68b10a0a546b4027

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Statistical physics-based reconstruction in compressed sensing (2011, methodology): “Its performance will be studied here with a joint use of numerical and analytic studies using methods from statistical physics [6].”
Statistical physics of inference: thresholds and algorithms (2015, background): “[145] Shrinivas Kudekar, Thomas J Richardson, and Rüdiger L Urbanke.”
Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices (2012, methodology): “This idea, together with the previous work on spatially coupled LDPC codes [40], also motivated the design of the seeding matrix in [1].”
Spatially coupled ensembles universally achieve capacity under belief propagation (2012, background): “The term spatially coupled codes was coined in [10].”
Rate Adaptation and Reach Increase by Probabilistically Shaped 64-QAM: An Experimental Demonstration (2016, background): “In fact, most spatially coupled codes have the outstanding property that their estimated decoding performance is close to the performance of the underlying code ensemble under maximum likelihood decoding as the block length grows, even when a very simple, practically feasible message passing decoder”
Coded Slotted ALOHA: A Graph-Based Method for Uncoordinated Multiple Access (2014, methodology): “Considering again the collision channel, the extra-ordinary performances obtained in the LDPC codin g context by exploiting spatial coupling [37] prompt the adoption of this paradigm toward th e design of “convolutional” CSA schemes.”