Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation

I Introduction

Ever since the publication of Shannon’s seminal paper and the introduction of the first coding schemes by Hamming and Golay , coding theory has been concerned with finding low-delay and low-complexity capacity-achieving schemes. The interested reader can find an excellent historical review in . Let us just briefly mention some of the highlights before focusing on those parts that are the most relevant for our purpose.

In the first 50 years, coding theory focused on the construction of algebraic coding schemes and algorithms that were capable of exploiting the algebraic structure. Two early highlights of this line of research were the introduction of Bose-Chaudhuri-Hocquenghem (BCH) codes as well as Reed-Solomon (RS) codes . Berlekamp devised an efficient decoding algorithm and this algorithm was then interpreted by Massey as an algorithm for finding the shortest feedback-shift register that generates a given sequence . More recently, Sudan introduced a list decoding algorithm for RS codes that decodes beyond the guaranteed error-correcting radius . Guruswami and Sudan improved upon this algorithm and Koetter and Vardy showed how to handle soft information .

Another important branch started with the introduction of convolutional codes by Elias and the introduction of the sequential decoding algorithm by Wozencraft . Viterbi introduced the Viterbi algorithm . It was shown to be optimal by Forney and Omura and to be eminently practical by Heller .

An important development in transmission over the continuous input, band-limited, additive white Gaussian noise channel was the invention of the lattice codes. It was shown in that lattice codes achieve the Shannon capacity. A breakthrough in bandwidth-limited communications came about when Ungerboeck invented a technique to combine coding and modulation. Ungerboeck’s technique ushered in a new era of fast modems. The technique, called trellis-coded modulation (TCM), offered significant coding gains without compromising bandwidth efficiency by mapping binary code symbols, generated by a convolutional encoder, to a larger (non-binary) signal constellation. In Forney showed that lattice codes as well as TCM schemes may be generated by the same basic elements and the generalized technique was termed coset-coding.

Coming back to binary linear codes, in 1993, Berrou, Glavieux and Thitimajshima proposed turbo codes. These codes attain near-Shannon limit performance under low-complexity iterative decoding. Their remarkable performance lead to a flurry of research on the “turbo” principle. Around the same time, Spielman in his thesis , and MacKay and Neal in , independently rediscovered low-density parity-check (LDPC) codes and iterative decoding, both introduced in Gallager’s remarkable thesis . Wiberg showed that both turbo codes and LDPC codes fall under the umbrella of codes based on sparse graphs and that their iterative decoding algorithms are special cases of the sum-product algorithm. This line of research was formalized by Kschischang, Frey, and Loeliger who introduced the notion of factor graphs .

The next breakthrough in the design of codes (based on sparse graphs) came with the idea of using irregular LDPC codes by Luby, Mitzenmacher, Shokrollahi and Spielman , . With this added ingredient it became possible to construct irregular LDPC codes that achieved performance within $0.0045$dB of the Shannon limit when transmitting over the binary-input additive white Gaussian noise channel, see Chung, Forney, Richardson and Urbanke . The development of these codes went hand in hand with the development of a systematic framework for their analysis by Luby, Mitzenmacher, Shokrollahi and Spielman and Richardson and Urbanke .

A central research topic for codes on graphs is the interaction of the graphical structure of a code and its performance. Turbo codes themselves are a prime example how the “right” structure is important to achieve good performance . Further important parameters and structures are, the degree distribution (dd) and in particular the fraction of degree-two variable nodes, multi-edge ensembles , degree-two nodes in a chain , and protographs .

Currently sparse graph codes and their associated iterative decoding algorithms are the best “practical” codes in terms of their trade-off between performance and complexity and they are part of essentially all new communication standards.

Polar codes represent the most recent development in coding theory . They are provably capacity achieving on binary-input memoryless output-symmetric (BMS) channels (and many others) and they have low decoding complexity. They also have no error floor due to a minimum distance which increases like the square root of the blocklength. The simplicity, elegance, and wide applicability of polar codes have made them a popular choice in the recent literature. There are perhaps only two areas in which polar codes could be further improved. First, for polar codes the convergence of their performance to the asymptotic limit is slow. Currently no rigorous statements regarding this convergence for the general case are known. But “calculations” suggest that, for a fixed desired error probability, the required blocklength scales like $1/\delta^{\mu}$, where $\delta$ is the additive gap to capacity and where $\mu$ depends on the channel and has a value around $4$, . Note that random block codes under MAP decoding have a similar scaling behavior but with $\mu=2$. This implies a considerably faster convergence to the asymptotic behavior. The value $2$ is a lower bound for $\mu$ for any system since the variations of the channel itself imply that $\mu\geq 2$. The second aspect is universality: the code design of polar codes depends on the specific channel being used and one and the same design cannot simultaneously achieve capacity over a non-trivial class of channels (under successive cancellation decoding).

Let us now connect the content of this paper to the previous discussion. Our main aim is to explain the role of a further structural element in the realm of sparse graph codes (besides the previously discussed such examples), namely that of “spatial coupling.” We will show that this coupling of graphs leads to a remarkable change in their performance. Ensembles designed in this way combine some of the nice elements of polar codes (namely the fact that they are provably capacity achieving under low complexity decoding) with the practical advantages of sparse graph codes (the codes are competitive already for moderate lengths). Perhaps most importantly, it is possible to construct universal such codes for the whole class of BMS channels. Here, universality refers to the fact that one and the same ensemble is good for a whole class of channels, assuming that at the receiver we have knowledge of the channel.

I-B Prior Work on Spatially Coupled Codes

The potential of spatially coupled codes has long been recognized. Our contribution lies therefore not in the introduction of a new coding scheme, but in clarifying the mechanism that make these codes perform so well.

The term spatially coupled codes was coined in . Convolutional LDPC codes (more precisely, terminated convolutional LDPC codes), which were introduced by Felström and Zigangirov in , and their many variants belong to this class. Why do we introduce a new term? The three perhaps most important reasons are: (i) the term “convolutional” conjures up a fairly specific node interconnection structure whereas experiments have shown that the particular nature of the connection is not important and that the threshold saturation effect occurs as soon as the connection is sufficiently strong; (ii) a well known result for convolutional codes says that the boundary conditions are “forgotten” exponentially fast; but for spatially coupled codes it is exactly the boundary condition which causes the effect and there is no decay of this effect in the spatial dimension of the code; (iii) the same effect has (empirically) been shown to hold in many other graphical models, most of them outside the realm of coding; the term “spatial coupling” is perhaps then somewhat more generally applicable.

There is a considerable literature on convolutional-like LDPC ensembles. Variations on the constructions as well as some analysis can be found in Engdahl and Zigangirov , Engdahl, Lentmaier, and Zigangirov , Lentmaier, Truhachev, and Zigangirov , as well as Tanner, D. Sridhara, A. Sridharan, Fuja, and Costello .

In , Sridharan, Lentmaier, Costello and Zigangirov consider density evolution (DE) analysis for convolutional LDPC ensembles and determine thresholds for the BEC. The equivalent results for general channels were reported by Lentmaier, Sridharan, Zigangirov and Costello in . This DE analysis is in many ways the starting point for our investigation. By comparing the thresholds to the thresholds of the underlying ensembles under MAP decoding (see e.g. ), it quickly becomes apparent that an interesting effect must be at work. Indeed, in a recent paper , Lentmaier and Fettweis followed this route and independently formulated the equality of the belief propagation (BP) threshold of convolutional LDPC ensembles and the MAP threshold of the underlying ensemble as a conjecture.

A representation of convolutional LDPC ensembles in terms of a protograph was introduced by Mitchell, Pusane, Zigangirov and Costello . The corresponding representation for terminated convolutional LDPC ensembles was introduced by Lentmaier, Fettweis, Zigangirov and Costello . A variety of constructions of LDPC convolutional codes from the graph-cover perspective is shown by Pusane, Smarandache, Vontobel, and Costello .

A pseudo-codeword analysis of convolutional LDPC codes was performed by Smarandache, Pusane, Vontobel, and Costello in . Such an analysis is important if we want to understand the error-floor behavior of spatially coupled ensembles.

In , Papaleo, Iyengar, Siegel, Wolf, and Corazza study the performance of windowed decoding of convolutional LDPC codes on the BEC. Such a decoder has a decoding complexity which is independent of the chain length, an important practical advantage. Luckily, it turns out that the performance under windowed decoding, when measured in terms of the threshold, approaches the “regular”” (without windowed decoding) threshold exponentially fast in the window size, see . The threshold saturation phenomenon therefore does not require an infinite window size.

The scaling behavior of spatially coupled ensembles, i.e., the relationship between the chain length, the number of variables per section, and the error probability is discussed by Olmos and Urbanke in .

I-C Prior Results for the Binary Erasure Channel

It was recently shown in that for transmission over the BEC spatially coupled ensembles have a BP threshold which is essentially equal to the MAP threshold of the underlying uncoupled ensemble. Further, this threshold is also essentially equal to the MAP threshold of the coupled ensemble. This phenomena was called threshold saturation in since the BP threshold takes on its largest possible value (the MAP threshold). This significant improvement in the performance is due to the spatial coupling of the underlying code. Those “sections” of the code that have already succeeded in decoding can help their neighboring less fortunate sections in the decoding process. In this manner, the information propagates from the “boundaries”, where the bits are known perfectly towards the “middle”. In a recent paper , Lentmaier and Fettweis independently formulated the same statement as a conjecture and provided numerical evidence for its validity. They attribute the observation of the equality of the two thresholds to G. Liva.

It was shown in that if we couple component codes whose Hamming distance grows linearly in the blocklength then also the resulting coupled ensembles have this property (assuming that the number of “sections” or copies of the underlying code is kept fixed). The equivalent result is true for stopping sets. This implies that for the transmission over the BEC the block BP threshold is equal to the bit BP threshold and that such ensembles do not exhibit error floors under BP decoding.

I-D Prior Results for General Binary-Input Memoryless Output-Symmetric Channels

As pointed out in a preceding section, BP thresholds for transmission over general BMS channels were computed by means of a numerical procedure by Lentmaier, Sridharan, Zigangirov and Costello in . Further, in (conjectured) MAP thresholds for some LDPC ensembles were computed according to the Maxwell construction. Comparing these two values, one can check empirically that also for transmission over general BMS channels the BP threshold of the coupled ensembles is essentially equal to the (conjectured) MAP threshold of the underlying ensemble. Indeed, recently both as well as provided further numerical evidence that the threshold saturation phenomenon also applies to general BMS channels.

For typical sparse graph ensembles the MAP threshold is not equal to the Shannon threshold but the Shannon threshold can only be reached by taking a sequence of such ensembles (e.g., a sequence of increasing degrees). There are some notable exceptions, like MN ensembles or HA ensembles. Kasai and Sakaniwa take this as a starting point to investigate in whether by spatially coupling such ensembles it is possible to create ensembles which are universally capacity achieving under BP decoding.

I-E Spatial Coupling for General Communication Scenarios, Signal Processing, Computer Science, and Statistical Physics

The principle which underlies the good performance of spatially coupled ensembles is broad. It has been shown to apply to a variety of problems in communications, computer science, signal processing, and physics. To mention some concrete examples, the threshold saturation effect (dynamical/algorithmic threshold of the system being equal to the static or condensation threshold) of coupled graphical models has been observed for rate-less codes by Aref and Urbanke , for channels with memory and multiple access channels with erasure by Kudekar and Kasai , for CDMA channels by Takeuchi, Tanaka, and Kawabata , for relay channels with erasure by Uchikawa, Kasai, and Sakaniwa , for the noisy Slepian-Wolf problem by Yedla, Pfister, and Narayanan , and for the BEC wiretap channel by Rathi, Urbanke, Andersson, and Skoglund . Uchikawa, Kurkoski, Kasai, and Sakaniwa recently showed an improvement of the BP threshold has also for transmission over the unconstrained AWGN channel using low-density lattice codes . Further, Yedla, Nguyen, Pfister and Narayanan, demonstrated the universality of spatially-coupled codes in the 2-user binary input Gaussian multiple-access channel and finite state ISI channels like the dicode-erasure channel and the dicode channel with AWGN . In they show in addition that for a fixed rate pair, spatially-coupled ensembles universally saturate the achievable region (i.e., the set of channel gain parameters that are achievable for the fixed rate pair) under BP decoding. Similarly, in they provide numerical evidence that spatially coupled ensembles achieve the symmetric information rate for the dicode erasure channel and the dicode channel with AWGN.

Statistical physics is another very natural area in which the threshold saturation phenomenon is of interest. For the so-called random $K$-SAT problem, random graph coloring, and the Curie-Weiss model, spatially coupled ensembles were investigated by Hassani, Macris, and Urbanke, . In all these cases, the threshold saturation phenomenon was observed. This suggests that it might be possible to study difficult theoretical problems in this area, like the existence of the static threshold, by studying the dynamical threshold of a chain of coupled models, perhaps an easier problem. Further spatially-coupled models were considered by Takeuchi and Tanaka .

I-F Main Results and Consequences

In this paper we show that for transmission over general BMS channels coupled ensembles exhibit the threshold saturation phenomenon. By choosing e.g. regular component ensembles of fixed rate and increasing degree, this implies that coupled ensembles can achieve capacity over this class of channels. More precisely, for each $\delta>0$ there exists a coupled ensemble which achieves at least a fraction $1-\delta$ of capacity universally, under belief propagation decoding, over the whole class of BMS channels. The qualifier ”universal” is important here.

Coupled ensembles inherit to a large degree the error floor behavior of the underlying ensemble. Further, such an ensemble can be chosen so that it has a non-zero error correcting radius, and hence does not exhibit error floors. To achieve this, it suffices to take the variable-node degree to be at least five. This guarantees that a randomly chosen graph from such an ensemble is an expander with expansion exceeding three-quarters with high probability. This expansion guarantees an error correcting radius under the so-called flipping decoder as well as under the BP decoder, assuming that we suitably clip both the received as well as the internal messages .

Although one can empirically observe the threshold saturation phenomenon for a wide array of component codes, we state and prove the main result only for regular LDPC ensembles. This keeps the exposition manageable.

I-G Outline

In Section II we briefly review regular LDPC ensembles and their asymptotic (in the blocklength) analysis. Much of this material is standard and we only include it here to set the notation and to make the paper largely self-contained. The two most important exceptions are our in-depth discussion of the Wasserstein distance and the the so-called area threshold, in particular the (Negativity) Lemma 27.

In Section III we review some basic properties of coupled ensembles. Using simple extremes of information combining techniques, we will see in Section III-G that coupling indeed increases the BP threshold significantly, even though these simple arguments are not sufficient to characterize the BP threshold under coupling exactly.

We state our main result, namely that the BP threshold of coupled ensembles is essentially equal to the area threshold of the underlying component ensemble, in Section IV. We also discuss how one can easily strengthen this result to apply to individual codes rather than ensembles and how this gives rise to codes which are universally close to capacity under BP decoding for the whole class of BMS channels.

We end in Section IV-E with a discussion of what challenges still lie ahead. In particular, spatial coupling has been shown empirically to lead to the threshold saturation phenomenon in a wide class of graphical models. Rather than proving each such scenario in isolation, we want a common framework to analyze all such systems.

Many of the proofs are relegated to the appendices. This makes it possible to read the material on two levels – a casual level, skipping all the proofs and following only the flow of the argument, and a more detailed level, consulting the material in the appendices.

II Uncoupled Systems

II-B Binary-Input Memoryless Output-Symmetric Channels

Throughout we will assume that transmission is taking place over a BMS channel. Let $X$ denote the input and let $Y$ be the output. Further, let $p(Y=y\,|\,X=x)$ denote the transition probability describing the channel. An alternative characterization of the channel is by means of its so-called $L$-distribution, denote it by $\mathsf{c}$. More precisely, $\mathsf{c}$ is the distribution of

Given $\mathsf{c}$, we write $\mathfrak{{c}}$, $|\mathfrak{{c}}|$, and $|\mathfrak{{C}}|$ to denote the corresponding $D$ distribution, the $|D|$ distribution and the cdf in the $|D|$-domain, respectively, see [62, Section 4.1.4].

Typically we do not consider a single channel in isolation but a whole family of channels. We write $\{\text{BMS}(\sigma)\}$ to denote the family parameterized by the scalar $\sigma$. Often it will be more convenient to denote this family by $\{\mathsf{c}_{\sigma}\}$, i.e., to use the family of $L$-densities which characterize the channel family. If it is important to make the range of the parameter $\sigma$ explicit, we will write $\{\mathsf{c}_{\sigma}\}_{\underline{\sigma}}^{\overline{\sigma}}$.

Sometimes it is convenient to use the natural parameter of the family. For example, for the three fundamental channels, the BEC, the binary symmetric channel (BSC) and the binary additive white-Gaussian noise channel (BAWGNC), the corresponding channel families are given by $\{\text{BEC}(\epsilon)\}_{0}^{1}$, $\{\text{BSC}(p)\}_{0}^{\frac{1}{2}}$, and $\{\text{BAWGNC}(\sigma)\}_{0}^{\infty}$. Other times, it is more convenient to use a common parameterization. E.g., we will write $\{\text{BMS}({\tt{h}})\}$ to denote a channel family where $\text{BMS}({\tt{h}})$ denotes the element in the family of entropy ${\tt{h}}$.

Assume that we are given a channel family $\{\text{BMS}(\sigma)\}_{\underline{\sigma}}^{\overline{\sigma}}$. We say that the family is complete if $\text{H}(\text{BMS}(\underline{\sigma}))=0$, $\text{H}(\text{BMS}(\overline{\sigma}))=1$, and for each ${\tt{h}}\in$ there exists a parameter $\sigma$ so that $\text{H}(\text{BMS}(\sigma))={\tt{h}}$. Here $\text{H}(\cdot)$ is the entropy functional defined in Section II-D.

Let $p_{Z\,|\,X}(z\,|\,x)$ denote the transition probability associated to a BMS channel $\mathsf{c}^{\prime}$ and let $p_{Y\,|\,X}(y\,|\,x)$ denote the transition probability of another BMS channel $\mathsf{c}$. We then say that $\mathsf{c}^{\prime}$ is degraded with respect to $\mathsf{c}$ if there exists a channel $p_{Z\,|\,Y}(z\,|\,y)$ so that

We will use the notation $\mathsf{c}\prec\mathsf{c}^{\prime}$ to denote that $\mathsf{c}^{\prime}$ is degraded wrt $\mathsf{c}$ (as a mnemonic think of $\mathsf{c}$ as the erasure probability of a BEC and replace $\prec$ with $<$).

A useful characterization of degradation, see [62, Theorem 4.74], is that $\mathsf{c}\prec\mathsf{c}^{\prime}$ is equivalent to

for all $f(x)$ that are non-increasing and concave on $$. Here,$|\mathfrak{{c}}|(x)$is the so called$|D|$-density associated to the$L$-density$\mathsf{c}$, see [62, p. 179]. In particular, this characterization implies that$F(\mathsf{a})\leq F(\mathsf{b})$for$\mathsf{a}\prec\mathsf{b}$if$F(\cdot)$is either the Battacharyya or the entropy functional. This is true since both are linear functionals of the distributions and their respective kernels in the$|D|$-domain are decreasing and concave. An alternative characterization in terms of the cumulative distribution functions$|\mathfrak{{C}}|(x)$and$|\mathfrak{{C^{\prime}}}|(x)$is that for all$z\in$,

A BMS channel family $\{\text{BMS}(\sigma)\}_{\underline{\sigma}}^{\overline{\sigma}}$ is said to be ordered by degradation if $\sigma_{1}\leq\sigma_{2}$ implies $\mathsf{c}_{\sigma_{1}}\prec\mathsf{c}_{\sigma_{2}}$. (The reverse order, $\sigma_{1}\geq\sigma_{2},$ is also allowed but we generally stick to the stated convention.)

We say that an $L$-density $\mathsf{c}$ is symmetric if $\mathsf{a}(-y)=\mathsf{a}(y)e^{-y}$. We recall that all densities which stem from BMS channels are symmetric, see [62, Sections 4.1.4, 4.1.8 and 4.1.9]. All densities which we consider are symmetric. We will therefore not mention symmetry explicitly in the sequel.

A BMS channel family $\{\mathsf{c}_{\sigma}\}$ is said to be smooth if for all continuously differentiable functions $f(y)$ so that $e^{y/2}f(y)$ is bounded, the integral $\int f(y)\mathsf{c}_{\sigma}(y)\,{\text{d}}y$ exists and is a continuously differentiable function with respect to $\sigma$, see [62, Definition 4.32].

The three fundamental channel families $\{\text{BEC}(\epsilon)\}_{0}^{1}$, $\{\text{BSC}(p)\}_{0}^{\frac{1}{2}}$, and $\{\text{BAWGNC}(\sigma)\}_{0}^{\infty}$ are all complete, ordered, smooth, and symmetric.

II-C MAP Decoder and MAP Threshold

The bit maximum a posteriori (bit-MAP) decoder for bit $i$ finds the value of $x_{i}$ which maximizes $p(x_{i}\,|\,y_{1}^{n})$. It minimizes the bit error probability and is optimal in this sense. The block maximum a posteriori (block-MAP) decoder finds the codeword $x_{1}^{n}$ which maximizes $p(x_{1}^{n}\,|\,y_{1}^{n})$. It minimizes the block error probability and is optimal in this sense.

Consider an ordered and complete channel family $\{\mathsf{c}_{\tt{h}}\}$. The MAP threshold of the $(d_{l},d_{r})$-regular ensemble for this channel family is denoted by ${\tt{h}}^{\text{\tiny MAP}}(d_{l},\!d_{r}\!)$ and defined by

In words, if we are transmitting above the MAP threshold, then the ensemble average bit-error probability is lower bounded by $h_{2}^{-1}(\delta)$, a strictly positive constant. This ensemble is therefore not suitable for reliable transmission above this threshold.

II-D Belief Propagation, Density Evolution, and Some Important Functionals

In principle one can investigate the behavior of coupled ensembles under any message-passing algorithm. We limit our investigation to the analysis of the BP decoder, the most powerful local message-passing algorithm. We are interested in the asymptotic performance of the BP decoder, i.e., the performance when the blocklength $n$ tends to infinity. This asymptotic performance is characterized by the so-called density evolution (DE) equation .

As mentioned, all distributions associated to BMS channels are symmetric and symmetry is preserved under DE, see [62, Chapter 4] for details. There are a number of functionals of densities are of interest to us. The most important functionals are the Battacharyya, the entropy, and the error probability functional. For a density $\mathsf{a}$ these are denoted by $\operatorname{\mathfrak{B}}(\mathsf{a})$, $\text{H}(\mathsf{a})$, and $\operatorname{\mathfrak{E}}(\mathsf{a})$, respectively. Assuming $\mathsf{a}$ is an $L$-density, they are given by

We end this section with the following useful fact. The proof can be found in Appendix A.

For any $L$-density $\mathsf{a}$, $\operatorname{\mathfrak{B}}^{2}(\mathsf{a})\leq\text{H}(\mathsf{a})\leq\operatorname{\mathfrak{B}}(\mathsf{a})$.

II-E Extremes of Information Combining and the Duality Rule

When we are operating on BMS channels, the quantities appearing in the DE equations are distributions. These are hard to track analytically in general, unless we are transmitting over the BEC. Often we only need bounds. In these cases extremes of information combining ideas are handy, see , [62, p. 242].

Let $F(\cdot)$ denote either $\text{H}(\cdot)$ or $\operatorname{\mathfrak{B}}(\cdot)$ and let $\alpha\in$. Let $\mathsf{a}_{\text{\tiny BEC}}$ and $\mathsf{a}_{\text{BSC}}$ denote $L$-densities from the families $\{\text{BEC}(\epsilon)\}$ and $\{\text{BSC}(p)\}$, respectively, so that $F(\mathsf{a}_{\text{\tiny BEC}})=F(\mathsf{a}_{\text{BSC}})=\alpha$. Then for any $\mathsf{b}$,

$\min_{\mathsf{a}:F(\mathsf{a})=\alpha}F(\mathsf{a}\circledast\mathsf{b})=F(\mathsf{a}_{\text{\tiny BEC}}\circledast\mathsf{b})$

$\max_{\mathsf{a}:F(\mathsf{a})=\alpha}F(\mathsf{a}\circledast\mathsf{b})=F(\mathsf{a}_{\text{\tiny BSC}}\circledast\mathsf{b})$

$\min_{\mathsf{a}:F(\mathsf{a})=\alpha}F(\mathsf{a}\boxast\mathsf{b})=F(\mathsf{a}_{\text{\tiny BSC}}\boxast\mathsf{b})$

$\max_{\mathsf{a}:F(\mathsf{a})=\alpha}F(\mathsf{a}\boxast\mathsf{b})=F(\mathsf{a}_{\text{\tiny BEC}}\boxast\mathsf{b})$

Discussion: Although the extremes of information combining bounds are only stated for pairs of distributions, they naturally extend to more than two distributions. E.g., we claim that $\min_{\mathsf{a}:F(\mathsf{a})=\alpha}F(\mathsf{a}^{\circledast d})=F(\mathsf{a}_{\text{\tiny BEC}})^{d}=\alpha^{d}$. To see this, let $\{\mathsf{a}_{i}\}_{i=1}^{d}$ be any set of distributions so that $F(\mathsf{a}_{i})=\alpha$. Then we can use Lemma 5 repeatedly to conclude that

The same remark and the same proof technique applies to the other cases.

For any $\mathsf{a}$ and $\mathsf{b}$ $\text{H}(\mathsf{a}\circledast\mathsf{b})+\text{H}(\mathsf{a}\boxast\mathsf{b})=\text{H}(\mathsf{a})+\text{H}(\mathsf{b})$.

Note: We give a simple proof of this identity at the end of the proof of Lemma 53.

II-F Fixed Points, Convergence, and BP Threshold

We say that the density $\mathsf{x}$ is a fixed point (FP) of DE for the $(d_{l},d_{r})$-regular ensemble and the channel $\mathsf{c}$ if

More succinctly, when the underlying ensemble is understood from the context, we say that $(\mathsf{c},\mathsf{x})$ is a FP.

One way to generate a FP is to initialize $\mathsf{x}_{0}$ with $\Delta_{0}$ and to run DE, as stated in Definition 3. We call such a FP a FP of forward DE. The resulting FPs are the “natural” FPs since they have a natural operational meaning – if we pick sufficiently long ensembles, these are the FPs which we can observe in simulations when we run the BP decoder.

We say that a sequence of distributions $\{\mathsf{a}_{i}\}$ converges weakly to a limit distribution $\mathsf{a}$ if for the corresponding cumulative distributions in the $|D|$-domain, call them $\{\mathfrak{{A}}_{i}\}$, for all bounded and continuous functions $f(x)$ on $$ we have

An equivalent definition is that $|\mathfrak{{A}}|_{i}(x)$ converges to $|\mathfrak{{A}}|(x)$ at points of continuity of $x.$ ∎

A simple proof of the following lemma can be found at the end of Section II-I.

In other words, the BP threshold is characterized by the largest channel parameter so that the forward DE FP is trivial.

We have just seen that the FPs of forward DE are important since they characterize the BP threshold. But there exist FPs that cannot be achieved this way. Let us review a general method of constructing FPs. Assume that, given a channel family $\{\mathsf{c}_{\sigma}\}$, we need a FP $\mathsf{x}$ which has a given error probability $\operatorname{\mathfrak{E}}(\mathsf{x})$, entropy $\text{H}(\mathsf{x})$, or Battacharyya parameter $\operatorname{\mathfrak{B}}(\mathsf{x})$. Such FPs can often be constructed, or at least their existence can be guaranteed, by a procedure introduced in . Let us recall this procedure for the case of fixed entropy.

Consider a smooth, complete, and ordered family $\{\mathsf{c}_{\tt{h}}\}$ and the $(d_{l},d_{r})$-regular ensemble. Let us denote by $T_{{\tt{h}}}$ the ordinary density evolution operator at fixed channel $\mathsf{c}_{\tt{h}}$. Formally,

For any ${\tt{e}}\in$, we define the density evolution operator at fixed entropy ${\tt{e}}$, call it $R_{{\tt{e}}}$, as

where ${\tt{h}}(\mathsf{a},{\tt{e}})$ is the solution of $\text{H}(T_{{\tt{h}}}(\mathsf{a}))={\tt{e}}$. Whenever no such value of ${\tt{h}}$ exists, $R_{{\tt{e}}}(\mathsf{a})$ is left undefined. Since, for a given $\mathsf{a}$, the family $T_{{\tt{h}}}(\mathsf{a})$ is ordered by degradation, $\text{H}(T_{{\tt{h}}}(\mathsf{a}))$ is a non-decreasing function of ${\tt{h}}$. As a consequence the equation $\text{H}(T_{{\tt{h}}}(\mathsf{a}))={\tt{e}}$ cannot have more than a single solution. Furthermore, by the smoothness of the channel family $\mathsf{c}_{\tt{h}}$, $\text{H}(T_{{\tt{h}}}(\mathsf{a}))$ is continuous as a function of ${\tt{h}}$. Notice that $\text{H}(T_{0}(\mathsf{a}))=0$: if the channel is noiseless the output density at a variable nodes is noiseless as well. Therefore, a necessary and sufficient condition for a solution ${\tt{h}}(\mathsf{a},{\tt{e}})$ to exist (when the family $\{\mathsf{c}_{\tt{h}}\}$ is complete) is that $\text{H}(T_{1}(\mathsf{a}))=\text{H}((\mathsf{a}^{\boxast d_{r}-1})^{\circledast d_{l}-1})\geq{\tt{e}}$ (see Theorem 6 in ).

II-G BP Threshold for Large Degrees

What happens to the BP threshold when we fix the design rate $r=1-d_{l}/d_{r}$ and increase the degrees? The proof of the following lemma, which uses basic extremes of information combining arguments, can be found in Appendix B.

Consider transmission over an ordered and complete family $\{\mathsf{c}_{\tt{h}}\}$ of BMS channels using an $(d_{l},d_{r})$-regular dd and BP decoding. Let $r=1-\frac{d_{l}}{d_{r}}$ be the design rate and let ${\tt{h}}^{\text{\tiny BP}}(d_{l},d_{r})$ denote the BP threshold. Then,

In particular, by increasing $d_{r}$ while keeping the rate $r$ fixed, the BP threshold converges to .

II-H The Wasserstein Metric: Definition and Basic Properties

In the sequel we will often need to measure how close various distributions are. Sometimes it is convenient to compare their entropy or their Battacharyya constant. But sometimes a more general measure is required. The Wasserstein metric is our measure of choice.

Let $|\mathfrak{{a}}|$ and $|\mathfrak{{b}}|$ denote two $|D|$-distributions. The Wasserstein metric, denoted by $d(|\mathfrak{{a}}|,|\mathfrak{{b}}|)$, is defined as

where $\text{Lip}(1)$ denotes the class of Lipschitz continuous functions on $$with Lipschitz constant$1$. ∎

Discussion: In the sequel we will say that a function $f(x)$ is $\text{Lip}(c)$ as a shorthand to mean that it is Lipschitz continuous with constant $c$. If we want to emphasize the domain, then we write e.g., $\text{Lip}(c)$. Why have we defined the metric in the $|D|$-domain? As the next lemma shows, convergence in this metric implies weak convergence. Since all the distributions of interest are symmetric, it suffices to look at the $|D|$-domain instead of the $D$-domain. To ease our notation, however, we will formally write expressions like $d(\mathsf{a},\mathsf{b})$, i.e., we will allow the arguments to be e.g. $L$-distributions. It is then implied that the metric is determined using the equivalent $|D|$-domain representations as defined above.

In the following, $\mathsf{a}$, $\mathsf{b}$, $\mathsf{c}$, and $\mathsf{d}$ denote $L$-distributions.

In the $|D|$ domain we have the following expressions for $\operatorname{\mathfrak{B}}(\mathsf{a})$ and $\text{H}(\mathsf{a})$ (compare this to the expressions in the $L$ domain given in Section II-D),

where $h_{2}(x)=-x\log_{2}x-(1-x)\log_{2}(1-x)$ is the binary entropy function. See for more details on metrics for probability measures.

Boundedness: $d(\mathsf{a},\mathsf{b})\leq 1$.

Metrizable and Weak Convergence: The Wasserstein metric induces the weak topology on the space of probability measures on $$. In other words, the space of probability measures under the weak topology is metrizable and convergence in the Wasserstein metric is equivalent to weak convergence (see [104, Theorem 6.9]).

Polish Space: The space of probability distributions on $$metrized by the Wasserstein distance is a complete separable metric space, i.e., a Polish space, and any measure can be approximated by a sequence of probability measures with finite support, i.e., distributions of the form$\sum_{i=1}^{n}c_{i}\delta(x-x_{i})$, where$\sum_{i=1}^{n}c_{i}=1$,$c_{i}\geq 0$, and$x_{i}\in$. Further, the space is compact. (See [104, Theorem 6.18].)

In general, if $\sum_{i}\alpha_{i}=1$, then

Regularity wrt $\circledast$: The Wasserstein metric satisfies the regularity property $d(\mathsf{a}\circledast\mathsf{c},\mathsf{b}\circledast\mathsf{c})\leq 2d(\mathsf{a},\mathsf{b})$, so that

and for $i\geq 2$ and any distribution $\mathsf{c},$ $d(\mathsf{a}^{\circledast i}\circledast\mathsf{c},\mathsf{b}^{\circledast i}\circledast\mathsf{c})\leq 2id(\mathsf{a},\mathsf{b})$.

Regularity wrt $\boxast$: The Wasserstein metric satisfies the regularity property $d(\mathsf{a}\boxast\mathsf{c},\mathsf{b}\boxast\mathsf{c})\leq d(\mathsf{a},\mathsf{b})\sqrt{1-\operatorname{\mathfrak{B}}^{2}(\mathsf{c})}\leq d(\mathsf{a},\mathsf{b})$, so that

Regularity wrt DE: Let $T_{\mathsf{c}}(\cdot)$ denote the DE operator for the dd $(d_{l},d_{r})$ and the channel $\mathsf{c}$. Then $d(T_{\mathsf{c}}(\mathsf{a}),T_{\mathsf{c}}(\mathsf{b}))\leq\alpha d(\mathsf{a},\mathsf{b})$, with

Wasserstein Bounds Battacharyya and Entropy:

Battacharyya Sometimes Bounds Wasserstein:

Discussion: Perhaps the most useful property of the Wasserstein metric is that it interacts nicely with the operations of variable- and check-node convolution. This is the essence of properties (vi), (vii), and (viii). For example, it is easy to see why property (viii) might be useful: Given that two distributions $\mathsf{a}$ and $\mathsf{b}$ are close, it asserts that after one iteration of DE these two distributions are again close. Indeed, as we will see shortly, depending on the Battacharyya parameter of the starting distributions the distance might in fact become smaller, i.e., we might have a contraction.

II-I Wasserstein Metric and Degradation

When densities ordered by degradation, some the Wasserstein metric inherits some additional properties.

In the following $\mathsf{a}$ and $\mathsf{b}$ denote $L$-distributions.

Wasserstein versus Degradation: Let $\mathsf{a}\prec\mathsf{b}$. Let $|\mathfrak{{A}}|$ and $|\mathfrak{{B}}|$ denote the corresponding $|D|$-domain cdfs. Define $D(\mathsf{a},\mathsf{b})=\int_{0}^{1}x(|\mathfrak{{B}}|(x)-|\mathfrak{{A}}|(x)){\text{d}}x$. Note that $D(\mathsf{a},\mathsf{b})$ can be seen as a measure of how much $\mathsf{b}$ is degraded wrt $\mathsf{a}$ since it is the average of the non-negative integrals $\int_{z}^{1}(|\mathfrak{{B}}|(x)-|\mathfrak{{A}}|(x)){\text{d}}x$ (cf. (2)). Then

Furthermore, $D(\mathsf{a},\mathsf{b})\leq 1$ and for any symmetric densities such that $\mathsf{a}\prec\mathsf{b}\prec\mathsf{c}$, $D(\mathsf{a},\mathsf{c})=D(\mathsf{a},\mathsf{b})+D(\mathsf{b},\mathsf{c})$.

Entropy and Battacharyya Bound Wasserstein Distance: Let $\mathsf{a}\prec\mathsf{b}$. Then

and $\operatorname{\mathfrak{B}}(\mathsf{b})-\operatorname{\mathfrak{B}}(\mathsf{a})\leq\sqrt{2(\text{H}(\mathsf{b})-\text{H}(\mathsf{a}))}\,.$

Continuity for Ordered Families: Consider a smooth family of $L$-distributions $\{\mathsf{c}_{\sigma}\}_{\underline{\sigma}}^{\overline{\sigma}}$ ordered by degradation so that $\operatorname{\mathfrak{B}}(\cdot)$ is continuous wrt $\sigma\in[\underline{\sigma},\overline{\sigma}]$. Then the Wasserstein metric is also continuous in $\sigma$.

Discussion: Property (i) is particularly useful. Imagine a sequence of distributions $\{\mathsf{a}_{i}\}_{i=0}^{n}$ ordered by degradation, i.e., $\mathsf{a}_{0}\prec\mathsf{a}_{1}\prec\dots\prec\mathsf{a}_{n}$. Then $\mathsf{a}_{0}\prec\mathsf{a}_{n}$ and we know from that $D(\mathsf{a}_{0},\mathsf{a}_{n})=\int_{0}^{1}z(|\mathfrak{{A}}|_{n}-|\mathfrak{{A}}|_{0}){\text{d}}z$ is non-negative since it is the “average” of the non-negative integrals $\int_{y}^{1}(|\mathfrak{{A}}|_{n}-|\mathfrak{{A}}|_{0}){\text{d}}z$. Now note that $D(\cdot,\cdot)$ is additive and that $D(\mathsf{a}_{0},\mathsf{a}_{n})\leq 1$. From these two facts we can conclude that there must exist an index $i$, $0\leq i\leq n-1$, so that $D(\mathsf{a}_{i},\mathsf{a}_{i+1})\leq\frac{1}{n}$. More generally, we can conclude for any $1\leq k\leq n$ that there must exist an index $i$, $0\leq i\leq n-k$, so that $D(\mathsf{a}_{i},\mathsf{a}_{i+k})\leq\min\{\frac{k}{n-k+1},1\}\leq\frac{2k}{n}$. This follows by upper bounding the average of all these $n-k+1$ such distances. By property (i) this implies “closeness” also in the Wasserstein sense. In words, in a sequence of distributions ordered by degradation we are always able to find a subsequence of distributions which are “close” in the Wasserstein sense.

As an exercise in using the basic properties of the Wasserstein distance, let us give a proof of Lemma 8.

II-J GEXIT Curve

As we have discussed in the preceding section, FPs of DE play a crucial role in the asymptotic analysis. E.g., the BP threshold is characterized by the existence/non-existence of a non-trivial FP of forward DE for a particular channel.

An even more powerful picture arises if instead of looking at a single FP at a time we visualize a whole collection of FPs. In order to visualize many FPs at the same time it is convenient to project them. E.g., given the FP pair $(\mathsf{c},\mathsf{x})$ we might decide to plot the point $(\text{H}(\mathsf{c}),\text{H}(\mathsf{x}))$ in the two-dimensional unit box $\times$.

Note that for the BEC, erasure probability is equal to Battacharyya parameter, and also equal to entropy. Even though all these parameters are equal in this case, our language will reflect that we are plotting entropy.

Rather than plotting $x$ itself it is convenient to plot the EXIT value $(1-(1-x)^{d_{r}-1})^{d_{l}}$. This is the locally best estimate of a bit based on the internal messages only, excluding the direct observation. For this choice the resulting curve is usually called the BP EXIT curve, see and [62, Sections 3.14 and 4.10]. It is the BP EXIT curve since the estimate is a BP estimate. And it is the BP EXIT (where the E stands for “extrinsic”) curve since the estimate excludes the received value associated to this bit.

The FP equation is $x=\epsilon(1-(1-x^{d_{r}-1}))^{d_{l}-1}$, which we can solve for $\epsilon$ to get

Using (7) we can write down the parametric characterization of the BP EXIT curve

This curve is shown in the left-hand side in Figure 1 for the $(3,6)$-regular ensemble and has a typical $C$ shape. In fact, one can show that, in this case, for $\epsilon<\epsilon^{\text{\tiny BP}}(d_{l},d_{r})$ (the BP threshold) there is only one FP at $x=0$ corresponding to perfect decoding; for $\epsilon=\epsilon^{\text{\tiny BP}}(d_{l},d_{r})$ there are 2 FPs, one is at $x=0$ and the other is the FP corresponding to forward DE; and for $\epsilon>\epsilon^{\text{\tiny BP}}(d_{l},d_{r})$ there are exactly 3 FPs of DE, one of the FPs is at $x=0$ and the remaining two FPs are strictly positive, one of which is stable, denoted by $x_{\text{s}}(\epsilon)$, whereas the other is unstable, denoted by $x_{\text{u}}(\epsilon)$. The stable FP is the FP which is reached by forward DE. For details see Lemma 59.

A quantity which will appear throughout this paper is the value of the unstable FP when transmitting over BEC$(\epsilon=1)$. We denote this FP by $x_{\text{u}}(1)$. More precisely, $x_{\text{u}}(1)$ is the smaller non-zero solution of $x=(1-(1-x)^{d_{r}-1})^{d_{l}-1}$. Note that $x_{\text{u}}(1)$ depends on the degrees, but we drop it from the notation for ease of exposition.

Discussion: The above example raises the following two questions. (1) We have a large degree of freedom in selecting the projection operator. Which one is “best”? (2) From the above example we see that the set of FPs forms a smooth curve. Indeed, for the BEC it is not hard to see that the only FPs are the ones on the curve together with all the FPs of the form $(\mathsf{c}_{\epsilon},\Delta_{+\infty})$, where $\mathsf{c}_{\epsilon}$ is any element of the family of BEC channels and $\Delta_{+\infty}$ corresponds to erasure value of 0. Is this picture still valid for general channel families?

In the remainder of this section we address the first question, i.e., we will discuss a particularly effective choice of the projection operator. In the next section we will address the question of the existence and nature of this curve for the general case, presenting some partial results.

A good choice for the projection operator for general channels is the GEXIT functional . For the BEC this coincides with the EXIT functional that we saw in Example 15. For the general case take a FP $(\mathsf{c}_{\sigma},\mathsf{x}_{\sigma})$ and define $\mathsf{y}=\mathsf{x}^{\boxast d_{r}-1}_{\sigma}$. Then

where we think of $\mathsf{y}$ as fixed with respect to $\sigma$. In words, $G(\mathsf{c}_{\sigma},\cdot)$ measures the ratio of the change in entropy of $\mathsf{c}_{\sigma}\circledast\mathsf{y}^{\circledast d_{l}}$ (the entropy of the decision of any variable node under BP decoding) versus the change of entropy of the channel $\mathsf{c}_{\sigma}$ as a function of $\sigma$.

Discussion: Note that if the parameterization in $\sigma$ is Lipschitz, i.e., if for some positive constant $\alpha$, $|\text{H}(\mathsf{c}_{\sigma_{2}})-\text{H}(\mathsf{c}_{\sigma_{1}})|\leq\alpha|\sigma_{2}-\sigma_{1}|$, then the derivative $\frac{{\text{d}}}{{\text{d}}\sigma}\text{H}(\mathsf{c}_{\sigma})$ exists almost everywhere. Further, in this case also $\text{H}(\mathsf{c}_{\sigma}\circledast\mathsf{y}^{\circledast d_{l}})$ is Lipschitz and hence differentiable almost everywhere. This follows since by (the Duality Rule in) Lemma 6, for $\sigma_{2}\geq\sigma_{1}$,

where the last step on the right-hand side assumes that the parameterization is such that $\text{H}(\mathsf{c}_{\sigma})$ increases in $\sigma$. The claim follows since both terms on the left are non-negative (due to degradation), so that in particular the first term is upper bounded by $\alpha|\sigma_{2}-\sigma_{1}|$, i.e., it is Lipschitz. This formulation also shows that the numerator is no larger than the denominator (so that the ratio exists) and that the GEXIT value is upper bounded by $1$ (and is non-negative).

We get the GEXIT curve by plotting $(\text{H}(\mathsf{c}_{\sigma}),G(\mathsf{c}_{\sigma},\mathsf{y}^{\circledast d_{l}}))$ for a family of FPs $\{\mathsf{c}_{\sigma},\mathsf{x}_{\sigma}\}$. This is shown in Figure 2 for the $(3,6)$-regular ensemble assuming that transmission takes place over the BAWGNC. In the last section we have already explained how we can construct in the general case FPs by a numerical procedure. To plot Figure 2 we have used this procedure to get a complete family of FPs for all entropies from to $1$. In each of the two pictures of Figure 2 there is a small black dot. This dot marks a particular FP and the two small inlets show the corresponding distribution of the channel $\mathsf{c}_{\sigma}$ as well as the message distribution emitted at the variable nodes, call it $\mathsf{x}_{\sigma}$. For a detailed discussion we refer the reader to .

Why do we use this particular representation? As we will discuss in detail in Section II-L, assuming this curve indeed exists and is “smooth”, the area which is enclosed by it is equal to $r=1-d_{l}/d_{r}$, the design rate of the ensemble.

This is easy to see for the BEC. To simplify notation, denote the GEXIT value in this case by $G(\epsilon,y^{d_{l}})$, where $\epsilon$ is the erasure probability, $x$ is the FP for this channel parameter, and $y=1-(1-x)^{d_{r}-1}$. We then have $G(\epsilon,y^{d_{l}})=(1-(1-x)^{d_{r}-1})^{d_{l}}$. Let us integrate the area which is enclosed by this curve. We call the corresponding integral the GEXIT integral. For our particular case it is given by

Perhaps surprisingly, the result stays valid for general channels as we will discuss in Section II-L. This property is one of the main ingredients in our proof.

Note that given $\mathsf{c}_{{\tt{h}}}$ and $\mathsf{z}_{{\tt{h}}}$, the GEXIT functional $G(\mathsf{c}_{{\tt{h}}},\mathsf{z}_{{\tt{h}}})$ can be expressed in the form $\int\mathsf{z}_{{\tt{h}}}(w)f({\tt{h}},w){\text{d}}w$, where $f({\tt{h}},w)$ is called as the GEXIT kernel. In the $|D|$-domain this kernel is given by

For a proof of the following see Lemma 4.77, .

For a smooth, ordered, channel family $\{\mathsf{c}_{{\tt{h}}}\}_{{\tt{h}}}$, $f({\tt{h}},w)$, as a function of $w$, exists, is continuous, non-negative, non-increasing and concave on its entire domain. Further $f({\tt{h}},0)=1$ and $f({\tt{h}},1)=0$.

We remark that the above lemma also holds when $\{\mathsf{c}_{{\tt{h}}}\}$ is piece-wise linear.

II-K Existence of GEXIT Curve

As we briefly discussed above, for the BEC it is trivial to see that the BP GEXIT curve indeed exists. But for general BMS channels this is not immediate. The aim of this section is to show the existence of the BP GEXIT curve for at least a subset of parameters.

Let us first recall the following lemma which was stated and proved in a slightly weaker form in . For the convenience of the reader we reproduce the proof in Appendix E.

Assume that communication takes place over an ordered and complete family $\{\mathsf{c}_{{\tt{h}}}\}_{{\tt{h}}}$, where ${\tt{h}}=\text{H}(\mathsf{c}_{\tt{h}})$, using the dd pair $(d_{l},d_{r})$.

Then, for any ${\tt{h}}\in$, there exists at most one density $\mathsf{x}_{{\tt{h}}}$ so that $(\mathsf{c}_{{\tt{h}}},\mathsf{x}_{{\tt{h}}})$ forms a FP which fulfills

Furthermore, if such a density $\mathsf{x}_{{\tt{h}}}$ exists, then it coincides with the forward DE FP. Finally, $\operatorname{\mathfrak{B}}(\mathsf{x}_{{\tt{h}}})$ is Lipschitz continuous with respect to $\operatorname{\mathfrak{B}}(\mathsf{c}_{{\tt{h}}})$. More precisely, if two FPs $(\mathsf{c}_{{\tt{h}}_{1}},\mathsf{x}_{{\tt{h}}_{1}})$ and $(\mathsf{c}_{{\tt{h}}_{2}},\mathsf{x}_{{\tt{h}}_{2}})$ satisfy the condition $\operatorname{\mathfrak{B}}(\mathsf{c}_{{\tt{h}}_{i}})(d_{l}-1)(d_{r}-1)(1-\operatorname{\mathfrak{B}}(\mathsf{x}_{{\tt{h}}_{i}})^{2})^{d_{r}-2}\leq 1-\delta$ for some $\delta>0$, then

The following lemma states that, at least for sufficiently large entropies, the BP GEXIT curve indeed exists and is well behaved.

Assume that communication takes place over an ordered and complete family $\{\mathsf{c}_{{\tt{h}}}\}_{{\tt{h}}}$, where ${\tt{h}}=\text{H}(\mathsf{c}_{\tt{h}})$, using the dd pair $(d_{l},d_{r})$. Consider the set of FP pairs $\{(\mathsf{c}_{{\tt{h}}},\mathsf{x}_{{\tt{h}}})\}$ obtained by applying forward DE to each channel $\mathsf{c}_{{\tt{h}}}$. Let

Although it is easy and stable to compute the above lower bound on the entropy numerically, it will be convenient to have a universal and analytic such lower bound. This is accomplished in the following lemma, whose proof can be found in Appendix E.

Assume that communication takes place over an ordered and complete family $\{\mathsf{c}_{{\tt{h}}}\}_{{\tt{h}}}$, where ${\tt{h}}=\text{H}(\mathsf{c}_{\tt{h}})$, using the dd pair $(d_{l},d_{r})$ with $d_{r}\geq 4$ and $d_{l}\geq 3$. Let $a(x)$ be defined as in Lemma 18. Consider the set of FP pairs $\{(\mathsf{c}_{{\tt{h}}},\mathsf{x}_{{\tt{h}}})\}$ which is derived by applying forward DE to each channel $\mathsf{c}_{{\tt{h}}}$. Then the GEXIT curve associated to $\{(\mathsf{c}_{{\tt{h}}},\mathsf{x}_{{\tt{h}}})\}_{{\tt{h}}>\overline{{\tt{h}}}}$, where

Table I lists these universal upper bounds $\overline{{\tt{h}}}$ for all the dds.

The following corollary follows immediately from Lemma 17, property (ii) of Lemma 14, and property (ix) of Lemma 13.

The proof of the following lemma can be found in Appendix F.

Bound for Partially Degraded Case: Let $\mathsf{a^{\prime}}$ be degraded with respect to the channel density $\mathsf{a}$ and let $\mathsf{b^{\prime}}$ be such that $d(\mathsf{b}^{\prime},\mathsf{b})\leq\delta$. Then

Bound for Fully Degraded Case: Let $\mathsf{a^{\prime}}$ be degraded with respect to the channel density $\mathsf{a}$ and let $\mathsf{b^{\prime}}$ be degraded with respect to the channel density $\mathsf{b}.$ Then

We will find it more convenient to parameterize the densities using $b=b({\tt{h}})=\operatorname{\mathfrak{B}}(\mathsf{c}_{\tt{h}}).$ Let us define

We claim that $D(b^{\prime},b)$ is continuous in both its arguments. Note that $G_{\tt{h}}=D(b({\tt{h}}),b({\tt{h}}))\frac{{\text{d}}b({\tt{h}})}{{\text{d}}{\tt{h}}}$ and, correspondingly, we define $G_{b}=D(b,b).$ To show continuity of $D$ in the first component note that $(D(b^{\prime\prime},b)-D(b^{\prime},b))\rightarrow 0$ by the smooth channel family assumption. To show continuity of $D$ in the second component consider $\text{H}((\mathsf{c}_{b^{\prime\prime\prime}}-\mathsf{c}_{b^{\prime\prime}})\circledast(\mathsf{z}_{b^{\prime}}-\mathsf{z}_{b})).$ By (the Entropy Product Inequality) Lemma 21, property (iii), we have

showing that $D$ is actually Lipschitz in its second argument. It follows, in particular, that $G_{b}$ is continuous in $b$. Since the Battacharyya parameter is a bounded functional and the channel family is smooth, we have $\frac{{\text{d}}b({\tt{h}})}{{\text{d}}{\tt{h}}}$ is continuous in ${\tt{h}}$. Consequently, $G_{\tt{h}}$ is continuous in ${\tt{h}}$. ∎

II-L Area Theorem

In Section II-J we introduced the GEXIT curve associated to a regular ensemble, see e.g. Figure 2. In Section II-K we then derived conditions which guarantee that this curve indeed exists and is continuous in a given region. We will now discuss the GEXIT integral, the area under the GEXIT curve. In order to derive some properties of this integral, we will first introduce GEXIT integrals in a slightly more general form before we apply them to ensembles.

Given two families $\{\mathsf{c}_{\sigma}\}_{\underline{\sigma}}^{\overline{\sigma}}$ and $\{\mathsf{z}_{\sigma}\}_{\underline{\sigma}}^{\overline{\sigma}}$, the GEXIT integral $\{\mathsf{c}_{\sigma},\mathsf{z}_{\sigma}\}_{\underline{\sigma}}^{\overline{\sigma}}$ is defined as

Discussion: In the above definition, and some definitions below, we need regularity conditions to ensure that the integrals exist. Rather than stating some general conditions here, we will discuss and verify them in the specific cases. E.g., one case we will discuss is if the channel family $\mathsf{c}_{\sigma}$ is smooth and $\mathsf{z}_{\sigma}$ is a polynomial in $\sigma$ with “coefficients” which are fixed densities.

Consider a binary linear code of length $n$ whose graphical representation is a tree. Assume that we are given an ordered family of channels $\{\mathsf{c}_{\sigma}\}_{\underline{\sigma}}^{\overline{\sigma}}$. Assume that when all variable nodes “see” the channel $\mathsf{c}_{\sigma}$ the distribution of the resulting extrinsic BP message density at the $i$-th variable node is $\mathsf{z}_{\sigma,i}$. Then the GEXIT integral associated of the $i$-th variable node is $G(\{\mathsf{c}_{\sigma},\mathsf{z}_{\sigma,i}\}_{\underline{\sigma}}^{\overline{\sigma}})$. ∎

Discussion: Note that the distribution $\mathsf{z}_{\sigma,i}$ is the best guess we can make about bit $i$ given the code constraints and all observations except the direct observation on bit $i$. This is why we have called the distribution the extrinsic message density. Note further that we have assumed that the graphical structure of the code is a tree. Therefore, BP equals MAP, the optimal such estimator.

The GEXIT integral applied to an ensemble is just the integral under the GEXIT curve of this ensemble.

Consider the $(d_{l},d_{r})$-regular ensemble and assume that $\{\mathsf{c}_{\sigma},\mathsf{x}_{\sigma}\}_{\underline{\sigma}}^{\overline{\sigma}}$ is a family of FPs of DE. Define $\mathsf{y}_{\sigma}=\mathsf{x}_{\sigma}^{\boxast d_{r}-1}$. Then

In the sequel it will be handy to explicitly evaluate the integral. The proof of the following lemma is contained in Appendix G.

Discussion: Note that this GEXIT integral has a simple graphical interpretation; it is the area under the GEXIT curve as e.g. shown in the right-hand picture of Figure 1. The condition ${\tt{h}}^{*}\geq{\tt{h}}(d_{l},d_{r},\{\mathsf{c}_{\tt{h}}\})$ ensures that this curve is well defined and integrable.

We have seen in the last section that the value of a GEXIT integral of an ensemble is determined by the expression $A$. We will soon see that it is crucial to describe the region where $A$ is negative. The following lemma, whose proof can be found in Appendix H, gives a characterization of this property.

Let $(\mathsf{c},\mathsf{x})$ be an approximate FP of the $(d_{l},d_{r})$-regular ensemble of design rate $r=1-d_{l}/d_{r}$. Assume that $d_{r}\geq 1+5(\frac{1}{1-r})^{\frac{4}{3}}$ and for some fixed $0\leq\delta\leq(\frac{\ln(2)d_{l}}{16\sqrt{2}d_{r}})^{2}$, $d(\mathsf{x},\mathsf{c}\circledast(\mathsf{x}^{\boxast d_{r}-1})^{\circledast d_{l}-1})\leq\delta$. Let

For $0\leq\kappa\leq\frac{1}{4e}\frac{d_{l}}{d_{r}}$, if $\text{H}(\mathsf{x})\in[(\frac{3}{4})^{\frac{d_{l}-1}{2}}+\frac{1}{(d_{r}-1)^{3}},\frac{d_{l}}{d_{r}}-d_{l}e^{-4(d_{r}-1)(\frac{2d_{l}}{11ed_{r}})^{\frac{4}{3}}}-\kappa]$, then $A\leq-\kappa$.

Discussion: In words, for sufficiently high degrees, $A(\mathsf{x})$ is strictly negative for all $\mathsf{x}$ with entropies in the range $(0,d_{l}/d_{r})$. Note that $d_{l}/d_{r}$ corresponds to the Shannon threshold for a code of rate $1-d_{l}/d_{r}$. In the preceding lemma we introduced the notion of an approximate FP of DE: we say that $(\mathsf{c},\mathsf{x})$ is a $\delta$-approximate FP if for some $\delta>0$ we have $d(\mathsf{x},\mathsf{c}\circledast(\mathsf{x}^{\boxast d_{r}-1})^{\circledast d_{l}-1})\leq\delta$.

II-M Area Threshold

The most important goal of this paper is to show that suitable coupled ensembles achieve the capacity. The preceding (Negativity) Lemma 27 is an important tool for this purpose. But we will in fact prove a refined statement, namely we will determine the threshold for fixed dds. This threshold is the so-called area threshold and it was first introduced in in the context of the Maxwell construction.

Consider the $(d_{l},d_{r})$-regular ensemble and transmission over a complete and ordered channel family $\{\mathsf{c}_{\tt{h}}\}_{{\tt{h}}=0}^{1}$. For each ${\tt{h}}\in$, let $\mathsf{x}_{\tt{h}}$ be the forward DE FP associated to channel $\mathsf{c}_{\tt{h}}$. The area threshold, denote it by ${\tt{h}}^{A}(d_{l},d_{r},\{\mathsf{c}_{\tt{h}}\})$, is defined as

where $A(\mathsf{x}_{{\tt{h}}},d_{l},d_{r})$ is equal to $A$, which is given in Lemma 26, evaluated at the FP $\mathsf{x}_{{\tt{h}}}$, when transmitting with the $(d_{l},d_{r})$-regular ensemble. ∎

Table II gives some values for ${\tt{h}}^{A}(d_{l},d_{r},\{\mathsf{c}_{\tt{h}}\})$ for various dds and channels.

Recall that the GEXIT integral has a simple graphical interpretation – it is the area under the GEXIT curve, assuming of course that both the curve and the integral exist. The area threshold is therefore that channel parameter ${\tt{h}}^{A}(d_{l},d_{r},\{\mathsf{c}_{\tt{h}}\})$ such that the GEXIT integral from ${\tt{h}}^{A}(d_{l},d_{r},\{\mathsf{c}_{\tt{h}}\})$ to $1$ is equal to $1-\frac{d_{l}}{d_{r}}$, the design rate.

Consider e.g. the case of the $(10,20)$-regular dd depicted in Figure 3.

From Lemma 19 we know that the GEXIT curve is Lipschitz continuous at least in the range ${\tt{h}}\in[0.341,1]$. An explicit check shows that $A(\mathsf{x}_{{\tt{h}}=0.341})<0$, so that ${\tt{h}}^{A}\geq 0.341$. We know that for ${\tt{h}}\in[0.341.1]$ the expression $1-\frac{d_{l}}{d_{l}}-A(\mathsf{x}_{\tt{h}})$ corresponds to the area under this GEXIT curve between ${\tt{h}}$ and $1$. This expression is therefore a decreasing function in ${\tt{h}}$, or equivalently, $A(\mathsf{x}_{\tt{h}})$ is an increasing function in ${\tt{h}}$. Using bisection, we can therefore efficiently find the area threshold and we get ${\tt{h}}^{A}\approx 0.49985$. Note that for this case the area threshold has the interpretation as that unique channel parameter ${\tt{h}}^{A}$ so that the enclosed area under the GEXIT curve between ${\tt{h}}^{A}$ and $1$ is equal to $1-\frac{d_{l}}{d_{r}}$. This is obviously the reason for calling ${\tt{h}}^{A}$ the area threshold.

The same interpretation applies to any dd ($d_{l},d_{r})$ and any BMS channel where the area threshold ${\tt{h}}^{A}(d_{l},d_{r},\{\mathsf{c}_{\tt{h}}\})$ is such that the GEXIT curve from ${\tt{h}}^{A}(d_{l},d_{r},\{\mathsf{c}_{\tt{h}}\})$ up till $1$ exists and is integrable. Empirically this is true for all regular dds and all BMS channels. Consider e.g. the case of the $(3,6)$ ensemble and transmission over the BAWGNC, see Figure 4. From Table I we are assured that this curve exists and is smooth at least in the range ${\tt{h}}\in[0.5931,1]$. This region is unfortunately too small. But it is easy to compute the curve numerically over the whole range. Since the resulting curve is smooth everywhere, it is easy to compute the area threshold numerically in this way. We get ${\tt{h}}^{A}\approx 0.4792$.

Fortunately, if we fix the rate then for all dd of sufficiently high degree this interpretation applies.

Consider a sequence of $(d_{l},d_{r})$-regular ensembles of fixed design rate $r=1-d_{l}/d_{r}$ and with $d_{l},d_{r}$ tending to infinity.

Furthermore, $A(\mathsf{x}_{{\tt{h}}^{A}},d_{l},d_{r})=0$ and, for fixed rate and increasing degrees, the sequence of the area thresholds ${\tt{h}}^{\text{A}}(d_{l},d_{r},\{\mathsf{c}_{\tt{h}}\})$ converges to the Shannon threshold ${\tt{h}}^{\text{Shannon}}(d_{l},d_{r})=\frac{d_{l}}{d_{r}}=1-r$ universally over the whole class of BMS channel families.

Let us prove the last claim of the lemma. We want to show that at the area threshold $A(\mathsf{x}_{{\tt{h}}^{A}},d_{l},d_{r})=0$. Recall that the area threshold was defined as the supremum over all ${\tt{h}}$ so that $A(\mathsf{x}_{{\tt{h}}},d_{l},d_{r})$ is less than or equal to zero. Therefore, all we need to show is that $A(\mathsf{x}_{{\tt{h}}},d_{l},d_{r})$ is continuous as a function of ${\tt{h}}$ around ${\tt{h}}^{A}$.

III Coupled Systems

Our goal is to show that coupled ensembles can achieve capacity on general BMS channels. Let us recall the definition of an ensemble which is particularly suited for the purpose of analysis. We call it the $(d_{l},d_{r},L,w)$ ensemble. This is the ensemble we use throughout the paper. For a quick historical review on some of the many variants see Section I-B.

For the whole paper we will always be interested in the limit when $M$ tends to infinity while $L$ as well as $d_{l}$ and $d_{r}$ stay fixed. In this limit we can analyze the system via density evolution, simplifying our task.

Not surprisingly, spatially coupled ensembles inherit many of their properties from the underlying ensemble. Perhaps most importantly, the local connectivity is the same. Further, the design rate of the coupled ensemble is close to that of the original one. A proof of the following lemma can be found in .

The design rate of the ensemble $(d_{l},d_{r},L,w)$, with $w\leq L$, is given by

There is an entirely equivalent way of describing a spatially coupled ensemble in terms of a circular construction. This construction has the advantage that it is completely symmetric. This simplifies some of the ensuing proofs.

Given an $(d_{l},d_{r},L,w)$ ensemble we can associate to it a circular ensemble. This circular ensemble has $w-1$ extra sections, all of whose variable nodes are set to zero. To be concrete, we assume that the sections are numbered from $[-L,L+w-1]$, where the sections in $[-L,L]$ are the sections of the original ensemble and the sections in $[L+1,L+w-1]$ are the extra sections. In this new circular ensemble all index calculations (for the connections) are done modulo $2L+w$ and indices are mapped to the range $[-L,L+w-1]$. For all positions in the range $i\in[L+1,L+w-1]$ the channel is $\mathsf{c}_{i}=\Delta_{+\infty}$, and consequently, $\mathsf{x}_{i}=\Delta_{+\infty}$. For all “regular” positions $i\in[-L,L]$ the associated channel is the standard channel $\mathsf{c}$. This circular ensemble has design rate equal to $1-d_{l}/d_{r}$. ∎

As we will see, it is the global structure which helps all the individual codes to perform so well – individually they can only achieve their BP threshold, but together they reach their MAP performance.

III-B Density Evolution for Coupled Ensemble

Let us describe the DE equations for the $(d_{l},d_{r},L,w)$ ensemble. In the sequel, densities are $L$-densities. Let $\mathsf{c}$ denote the channel and let $\mathsf{x}_{i}$ denote the density which is emitted by variable nodes at position $i$. Throughout the paper, $\Delta_{+\infty}$ denotes an $L$-density with all its mass at $+\infty$ and represents the perfect decoding density. Also, $\Delta_{0}$ denotes an $L$-density with all its mass at and represents a density with no information.

Note that $g(\mathsf{x},\dots,\mathsf{x})=(\mathsf{x}^{\boxast d_{r}-1})^{\circledast d_{l}-1}$, where the right-hand side represents DE (without the effect of the channel) for the underlying $(d_{l},d_{r})$-regular ensemble. Also define

As before we see that $\hat{g}(\mathsf{x},\!\dots\!,\mathsf{x})$ denotes the EXIT value of DE for the underlying $(d_{l},d_{r})$-regular ensemble. It is not hard to see that both $g(\mathsf{x}_{i-w+1},\dots,\mathsf{x}_{i+w-1})$ as well as $\hat{g}(\mathsf{x}_{i-w+1},\dots,\mathsf{x}_{i+w-1})$ are monotone wrt degradation in all their arguments $\mathsf{x}_{j}$, $j=i-w+1,\dots,i+w-1$. More precisely, if we degrade any of the densities $\mathsf{x}_{j}$, $j=i-w+1,\dots,i+1-1$, then $g(\cdot)$ (respectively $\hat{g}(\cdot)$) is degraded. We say that $g(\cdot)$ (respectively $\hat{g}(\cdot)$) is monotone in its arguments. ∎

Fix the parameters $(d_{l},d_{r})$ and $w$ and assume that $d(\mathsf{a}_{i},\mathsf{b}_{i})\leq\kappa$, $i=-w+1,\dots,w-1$. Then

Using once again property (v) of Lemma 13

III-C Fixed Points and Admissible Schedules

Consider DE for the $(d_{l},d_{r},L,w)$ ensemble. Let $\mathsf{\underline{x}}=(\mathsf{x}_{-L},\dots,\mathsf{x}_{L})$. We call $\mathsf{\underline{x}}$ the constellation (of $L$-densities). We say that $\mathsf{\underline{x}}$ forms a FP of DE with channel $\mathsf{c}$ if $\mathsf{\underline{x}}$ fulfills (12) for $i\in[-L,L]$. As a short hand we say that $(\mathsf{c},\mathsf{\underline{x}})$ is a FP. We say that $(\mathsf{c},\mathsf{\underline{x}})$ is a non-trivial FP if $\mathsf{x}_{i}\neq\Delta_{+\infty}$ for at least one $i\in[-L,L]$. Again, for $i\notin[-L,L]$, $\mathsf{x}_{i}=\Delta_{+\infty}$. ∎

III-D Entropy, Error and Battacharyya Functionals for Coupled Ensemble

Let $\mathsf{\underline{x}}$ be a constellation. Let $F(\cdot)$ denote either the $\text{H}(\cdot)$ (entropy), $\operatorname{\mathfrak{E}}(\cdot)$ (error probability), or $\operatorname{\mathfrak{B}}(\cdot)$ (Battacharyya) functional defined in Section II-D.

We define the (normalized) entropy , error and Battacharyya functionals of the constellation $\mathsf{\underline{x}}$ to be

III-E BP GEXIT Curve for Coupled Ensemble

We now come to a key object, the BP GEXIT curve for the coupled ensemble. We have discussed how to compute BP GEXIT curves for uncoupled ensembles in Section III-E. For coupled ensembles the procedure is similar.

In Section III-C we have seen that for coupled systems FPs of forward DE are well defined and that they can be computed by applying a parallel schedule. This procedure allows us to compute some FPs.

But we can also use DE at fixed entropy, as discussed in Section II, to compute further FPs (in particular unstable ones). More, precisely, fix the desired average entropy of the constellation, call it ${\tt{h}}$. Start with the initialization $\mathsf{\underline{x}}^{(0)}=\underline{\Delta}_{0}$, the vector of all $\Delta_{0}$. In each iteration proceed as follows. Perform one round of DE without incorporating the channel, i.e., set

Now find a channel $\mathsf{c}_{\sigma}\in\{\mathsf{c}_{\sigma}\}$, assuming it exists, so that after the convolution with this channel the average entropy of the constellation is equal to ${\tt{h}}$. Continue this procedure until the constellation has converged (under some suitable metric).

Assume that we have computed (via the above procedure) a complete family $\{\mathsf{c}_{\sigma},\mathsf{\underline{x}}_{\sigma}\}$ of FPs of DE, i.e., a family so that for each ${\tt{h}}\in$, there exists a parameter $\sigma$ so that ${\tt{h}}=\frac{1}{2L+1}\sum_{i=-L}^{L}\text{H}(\mathsf{x}_{\sigma,i})$. Then we can derive from it a BP GEXIT curve by projecting it onto

where $\hat{g}(\cdot)$ was introduced in Section III-B, and $\frac{1}{2L+1}\sum_{i=-L}^{L}G(\mathsf{c}_{\sigma},\hat{g}(\mathsf{x}_{\sigma,i\!-\!w\!+\!1},\!\dots\!,\mathsf{x}_{\sigma,i\!+\!w\!-\!1}))$ is the (normalized) GEXIT function of the constellation $\mathsf{\underline{x}}_{\sigma}$.