Wave-Like Solutions of General One-Dimensional Spatially Coupled Systems

We establish the existence of wave-like solutions to spatially coupled graphical models which, in the large size limit, can be characterized by a one-dimensional real-valued state. This is extended to a proof of the threshold saturation phenomenon for all such models, which includes spatially coupled irregular LDPC codes over the BEC, but also addresses hard-decision decoding for transmission over general channels, the CDMA multiple-access problem, compressed sensing, and some statistical physics models. For traditional uncoupled iterative coding systems with two components and transmission over the BEC, the asymptotic convergence behavior is completely characterized by the EXIT curves of the components. More precisely, the system converges to the desired fixed point, which is the one corresponding to perfect decoding, if and only if the two EXIT functions describing the components do not cross. For spatially coupled systems whose state is one-dimensional a closely related graphical criterion applies. Now the curves are allowed to cross, but not by too much. More precisely, we show that the threshold saturation phenomenon is related to the positivity of the (signed) area enclosed by two EXIT-like functions associated to the component systems, a very intuitive and easy-to-use graphical characterization. In the spirit of EXIT functions and Gaussian approximations, we also show how to apply the technique to higher dimensional and even infinite-dimensional cases. In these scenarios the method is no longer rigorous, but it typically gives accurate predictions. To demonstrate this application, we discuss transmission over general channels using both the belief-propagation as well as the min-sum decoder.

Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation

We investigate spatially coupled code ensembles. For transmission over the binary erasure channel, it was recently shown that spatial coupling increases the belief propagation threshold of the ensemble to essentially the maximum a-priori threshold of the underlying component ensemble. This explains why convolutional LDPC ensembles, originally introduced by Felstrom and Zigangirov, perform so well over this channel. We show that the equivalent result holds true for transmission over general binary-input memoryless output-symmetric channels. More precisely, given a desired error probability and a gap to capacity, we can construct a spatially coupled ensemble which fulfills these constraints universally on this class of channels under belief propagation decoding. In fact, most codes in that ensemble have that property. The quantifier universal refers to the single ensemble/code which is good for all channels but we assume that the channel is known at the receiver. The key technical result is a proof that under belief propagation decoding spatially coupled ensembles achieve essentially the area threshold of the underlying uncoupled ensemble. We conclude by discussing some interesting open problems.

Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC

Convolutional LDPC ensembles, introduced by Felstrom and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing as a function 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 which explains why convolutional-like or spatially coupled codes perform so well. In essence, the spatial coupling of the individual code structure has the effect of increasing 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 such a construction is that one can create capacity-approaching ensembles with an error correcting radius which is increasing in the blocklength. Our proof makes use of the area theorem of the BP-EXIT curve and the connection between the MAP and BP threshold recently pointed out by Measson, Montanari, Richardson, and Urbanke. Although we prove the connection between the MAP and the BP threshold only for a very specific ensemble and only for the binary erasure channel, empirically a threshold saturation 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 as well as to new techniques for analysis.

Coding for Network Coding

We consider communication over a noisy network under randomized linear network coding. Possible error mechanism include node- or link- failures, Byzantine behavior of nodes, or an over-estimate of the network min-cut. Building on the work of Koetter and Kschischang, we introduce a probabilistic model for errors. We compute the capacity of this channel and we define an error-correction scheme based on random sparse graphs and a low-complexity decoding algorithm. By optimizing over the code degree profile, we show that this construction achieves the channel capacity in complexity which is jointly quadratic in the number of coded information bits and sublogarithmic in the error probability.