{'fraction_non_alphanumeric': 0.057541567695962, 'fraction_numerical': 0.013776722090261283, 'mean_word_length': 4.063439567047505, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Simple Proof of Threshold Saturation for Coupled Scalar Recursions

Low-density parity-check (LDPC) convolutional codes (or spatially-coupled codes) have been shown to approach capacity on the binary erasure channel (BEC) and binary-input memoryless symmetric channels. The mechanism behind this spectacular performance is the threshold saturation phenomenon, which is characterized by the belief-propagation threshold of the spatially-coupled ensemble increasing to an intrinsic noise threshold defined by the uncoupled system. In this paper, we present a simple proof of threshold saturation that applies to a broad class of coupled scalar recursions. The conditions of the theorem are verified for the density-evolution (DE) equations of irregular LDPC codes on the BEC, a class of generalized LDPC codes, and the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise. Our approach is based on potential functions and was motivated mainly by the ideas of Takeuchi et al. The resulting proof is surprisingly simple when compared to previous methods.

The fundamental mechanism behind this is explained well in [12], where it is proven analytically for the BEC that the BP threshold of a particular SC ensemble converges to the maximum-a-posteriori (MAP) threshold of the underlying ensemble. This phenomenon is now called threshold saturation. A similar result was also observed independently in [13] and stated as a conjecture. The same result for general binary memoryless symmetric (BMS) channels was first empirically observed [4], [5] and recently proven analytically [11].
The underlying principle behind threshold saturation appears to be very general and it has now been applied, with much success, to a variety of more general scenarios in information theory and coding. In [14], the benefits of spatial coupling are described for K-satisfiability, graph coloring, and the Curie-Weiss model in statistical physics. SC codes are shown to achieve the entire rate-equivocation region for the BEC wiretap channel in [6]. The authors observe in [7] This material is based upon work supported by the National Science Foundation (NSF) under Grants No. 0747470 and No. 0802124. Any opinions, findings, conclusions, and recommendations expressed in this material are those of the authors and do not necessarily reflect the views of these sponsors. that the phenomenon of threshold saturation extends to multiterminal problems (e.g., a noisy Slepian-Wolf problem) and can provide universality over unknown channel parameters. Threshold saturation has also been observed for the binaryadder channel [15], for intersymbol-interference channels [8], [9], [10], for message-passing decoding of code-division multiple access (CDMA) [16], [17], and for iterative hard-decision decoding of SC generalized LDPC codes [18]. For compressive sensing, SC measurement matrices were investigated first with verification-based reconstruction in [19], and then proved to achieve the information-theoretic limit in [20].
In many of these papers it is conjectured, either implicitly or explicitly, that threshold saturation occurs for the studied problem. A general proof of threshold saturation (especially one where only a few details must be verified for each system) would allow one to settle all of these conjectures simultaneously. In this paper, we provide such a proof for systems with scalar density-evolution (DE) equations.
Our method is based on potential functions and was motivated mainly by the approach taken in [21]. It turns out that their approach is missing a few important elements and does not, as far as we know, lead to a general proof of threshold saturation. Still, it introduces the idea of a potential function defined by an integral of the DE recursion and this is an important element in our approach. More recently, a continuum approach to DE is used, in [20], to prove threshold saturation for compressed sensing and was reported informally to give a general proof [22].

II. A SIMPLE PROOF OF THRESHOLD SATURATION
In this section, we provide a simple proof of threshold saturation via spatial-coupling for a broad class of scalar recursions. The main tool is a potential theory for scalar recursions that extends naturally to coupled systems of recursions.

A. Single-System Potential
First, we define potential functions for a class of scalar recursions and discuss threshold parameters associated with the potential.
Lemma 1: The potential function of a scalar admissible system has the following properties: 1) U (x; ε) is strictly decreasing in ε, for ε ∈ (0, 1]. 2) An x ∈ [0, 1] is a f.p. iff it is a s.p. of the potential.
Proof: These properties hold because the potential function is the integral of (z − f (g(z); ε)) g ′ (z) w.r.t. z, which is strictly decreasing in ε, for ε ∈ (0, 1], and zero iff z is a fixed point of the recursion.
Definition 4: The single-system threshold is defined to be and is the ε-threshold for convergence of the single-system recursion to 0. It is well defined because U ′ (x; ε) is strictly decreasing in ε. This implies that, for ε < ε * s , (1) has no fixed points in (0, 1]. For DE recursions associated with BP decoding, the threshold ε * s is called the BP threshold. Example 1: For the standard irregular ensemble of LDPC codes (e.g., see [23]), the DE recursion, is an scalar admissible system with f (x; ε) = ελ(x) and g(x) = 1 − ρ(1 − x). In this case, the single-system potential is given by (6) and is shown in Fig. 1 for the (3, 6)-regular LDPC code ensemble defined by (λ, ρ) = (x 2 , x 5 ). Figure 2. A portion of a generic SC system. The f -node at position i is coupled with the g-nodes at positions i, . . . , i + w − 1 and, by reciprocity, g-node at position i is coupled with the f -nodes at positions i − w + 1, . . . , i. Here, π i and π ′ i are random permutations.
Definition 5: For ε > ε * s , we define the minimum unstable fixed point to be Definition 6: Let the potential threshold of the system be For DE recursions associated with BP decoding, the potential threshold is analogous to the threshold predicted by the Maxwell conjecture [24, Conj. 1].

B. Coupled System Potential
Now, we extend our definition of potential functions to coupled systems of scalar recursions. In particular, we consider a "spatial-coupling" of the single-system recursion, (1), that gives rise to the vector recursion (4). For the vector recursion of the coupled system, we define a potential function and show that, for ε < ε * , the only fixed point of the coupled system is the zero vector.
Definition 7 (cf. [12]): The basic spatially-coupled system is defined by placing 2L + 1 single systems at positions in the set L 0 ≜ {−L, −L + 1, . . . , L} and coupling them with w systems as shown in Fig. 2. Let x (ℓ) i be the input to the g-function in the i-th position after ℓ iterations and define x (ℓ) . . , L + w − 1} and all ℓ. For the coupled system, we have the recursion where ε i = ε for i ∈ L 0 and ε i = 0 for i ∉ L 0 . Definition 8: The recursion defined by (4) can be rewritten as a vector recursion. Let f (x; ε) and g(x) be defined for vector arguments by respectively. Then, (4) is equivalent to Remark 2: In contrast to [12], the SC recursion defines x (ℓ) to be the SC-average of the f -function (e.g., bit node in the LDPC example) output values rather than the output values. Since there are 2L+1 active f -function outputs, the vector x (ℓ) contains the 2L + w active averaged values after convolution with the length-w averaging sequence. This also shifts the maximum value of the vector from position 0, in [12], to position i 0 ≜ ⌊ w−1 2 ⌋ in this work. One might also expect that A 2 is square and that all rows and columns should sum to 1, but the termination leads to a rectangular matrix with reduced column sums near the boundaries. In particular, A 2 g(x) is a length 2L + 1 vector representing the inputs to the 2L + 1 active f -functions.

Remark 3:
The right hand side of (5) accurately represents a single iteration of the one-sided SC system update for i ∈ L ′ , but cannot be used recursively unless the boundary condition x i0 for i ≥ i 0 is enforced after each step. Lemma 2 (cf. [12,Lem. 14]): For both the basic and onesided SC systems, the recursions are component-wise decreasing with iteration and converge to well-defined fixed points. The one-sided recursion is also a component-wise upper bound on the basic SC recursion for i ∈ L and it converges to a nondecreasing fixed-point vector.
Proof: The proof follows easily from the arguments in [12, Sec. V] and is, hence, omitted.
Definition 11: The coupled-system potential can be computed for general vector recursions written in the form of (5).
Integrating a scaled version of the vector update step along a curve C, from 0 to x, gives the potential function

Remark 4:
A key observation in this paper is that a potential function for coupled systems can be written in the simple form in Def. 11. Remarkably, this holds for general coupling coefficients because of the A, A ⊺ reciprocity that appears naturally in SC.
Lemma 3: Let x ∈ [0, 1] n be a non-decreasing vector generated by averaging z ∈ [0, 1] n over a sliding window of size w. Let the shift operator S ∶ R n → R n be defined by Since x is non-decreasing, the 1-norm sum telescopes and we get Sx − Lemma 4: For the vector one-sided SC system, a shift changes the potential by U Sketch of Proof: Rewriting the coupled potential gives . One can verify that the contribution, from the first two terms in the square brackets, to U (Sx; ε)−U (x; ε) is a telescoping sum that leaves only the difference between the first and last values. For the third term in the square brackets, more care is required. Since the first w values of x are 0 and the last 2w+1 values of Lemma 5: For the SC potential, the norm of the Hessian U ′′ (x; ε) is independent of L and w and satisfies Proof: One can verify that the Hessian is given by . Taking the norm gives We now state the main result of the paper. Roughly speaking, it says that, if ε < ε * and w is sufficiently large, then one can always lower the coupled potential of a non-zero vector by shifting. Since this implies the next step of the recursion must reduce some value, the only fixed point is the zero vector.
Theorem 1: Consider a scalar admissible system (f, g). If ε < ε * and w > K f,g ∆E(ε), then the only fixed point of the spatially-coupled system, defined by (4), is x = 0.
Proof: Using Lem. 2, let x be the unique fixed point of the one-sided recursion defined in Def. 9. This fixed point upper bounds the fixed point of the basic SC system defined in Def. 7. If x ≠ 0, then x i0 ≥ u(ε) because the system has no fixed points with x i < u(ε) for all i. From Lem. 4, we have ∆U ≜ U (Sx; ε)−U (x; ε) = −U (x i0 ; ε). Expanding U (Sx; ε) in a Taylor series (with remainder) around U (x; ε) gives Now, we observe that Sx − x ⪯ 0 (i.e., the fixed point is non-decreasing) and So, one more iteration must reduce the value of the i-th component for some i ∈ L ′ . This gives a contradiction and shows that the only fixed point of the onesided SC system is x = 0. The result follows since the fixed point of the basic SC system is upper bounded by this f.p.

III. APPLICATIONS
In this section, we consider some applications of Theorem 1 for coding problems that are characterized by a scalar recursion. We liberally use notation and definitions from [23].

A. Irregular LDPC Codes
Consider the ensemble LDPC(λ, ρ) and transmission over an erasure channel with parameter ε. Let x (ℓ) be the fraction of erasure messages sent from variable to check nodes during iteration ℓ. The DE equation can be written in the form of (1), where f (x; ε) = ελ(x) and g(x) = 1 − ρ(1 − x). It is easy to verify that f and g describe a scalar admissible system if λ(0) = 0. The single system potential is given by where P (x) is the trial entropy defined in [23,Def. 3.119], ε(x) = x λ(1 − ρ(1 − x)) and L(x) = ∫ x 0 λ(y)dy ∫ 1 0 λ(y)dy.
In this case, the potential U (x; ε) is the same as the pseudodual of the Bethe variational entropy in [25,Part 2,.
Lemma 6: Consider the potential threshold ε * given by (3). Let ε Max be the Maxwell threshold [24,Conj. 1], defined by Then, ε * = ε Max for the ensemble LDPC(λ, ρ). Sketch of Proof: Let x Max be the x-value that achieves the minimum. Then, (6) and (7) Remark 5: For regular ensembles, ε Max equals the MAP threshold ε MAP and this is conjectured to hold in general.
Consider an SC ensemble of irregular LDPC(Λ, P ) codes defined as follows. The f -nodes at each position are replaced by M copies of the node degree profile Λ(x) = ∑ i Λ i x i , where Λ i is the number of bit nodes of degree i. The g-nodes at each position are replaced by M copies of the node degree profile P (x) = ∑ i P i x i , where P i is the number of check nodes of degree i. For sufficiently large M , these nodes can be coupled uniformly using an averaging window of length w (see Fig. 2) in a manner similar to the (l, r, L, w) ensemble defined in [12].
Corollary 1: Applying Theorem 1 shows that, if ε < ε Max and w > K f,g ∆E(ε), then the SC DE recursion converges to the zero vector.

B. Generalized LDPC Codes on the BEC and BSC
Consider a generalized LDPC (GLDPC) code with degree-2 bits and generalized check constraints based on a BCH code of block-length n. For iterative decoding using bounded-distance decoding of the BCH code, the DE recursions can be derived for both the BEC and binary symmetric channel (BSC) [18]. On the BEC, the code is chosen to correct all patterns of at most t erasures and, on the BSC, the code is chosen to correct all error patterns of weight at most t.
For both cases, the iterative decoding performance of this ensemble is characterized by a DE recursion of the form (1), where ε denotes the channel parameter. In this case, the scalar system is defined by f (x; ε) ≜ εx and g(x) ≜ ∑ n−1 e=t n−1 e x e (1−x) n−1−e . Here, x denotes the erasure (resp. error) probability of bit-to-check messages for the BEC (resp. BSC) case.
It can be verified that f and g define a scalar admissible system whose single-system potential is given by dz is the analogous to the trial entropy defined in [23].
Remark 6: Since this decoder uses suboptimal component decoders, the threshold defined by the unique zero of P (x) does not give an upper bound on the MAP threshold.
We now describe the SC ensemble for the ensemble of GLDPC codes. The f -nodes in Fig. 2 are replaced by M n degree-2 variable nodes and the g-nodes are replaced by 2M BCH codes of block-length n. These nodes are coupled using an averaging window of length w in a manner similar to the (l, r, L, w) ensemble defined in [12] (e.g., see [18]).
Corollary 2: Applying Theorem 1 to this SC GLDPC ensemble shows that the SC DE recursion converges to the zero vector whenever ε <ε and w > K f,g ∆E(ε).

C. Intersymbol-Interference Channels with Erasure Noise
In [26], a family of intersymbol-interference (ISI) channels with erasure noise is investigated as an analytically tractable model of joint iterative decoding of LDPC codes and channels with memory. Let ψ(t; ε) be the function that maps the a priori erasure rate t from the code and the channel erasure rate ε to the erasure rate of extrinsic messages from the channel detector to the bit nodes. Then, the resulting DE update equation for the erasure rate, x (ℓ) , of bit-to-check messages can be written in the form of (1), where f (x; ε) = ψ(L(x); ε)λ(x) and g(x) = 1−ρ(1−x) [26]. Under mild conditions on ψ(x; ε), this defines a scalar admissible system with potential U (x; ε) = 1 L ′ (1) Ψ(L(g(x)); ε(x)) − Ψ(L(g(x)); ε) − P (x), where ε(x) and P (x) are defined in [9] for generalized erasure channels and Ψ(x; ε) = ∫ x 0 ψ(y; ε)dy. Lemma 8: Consider the potential threshold ε * defined by (3) and let ε Max be defined by (7). Then, ε * = ε Max . If, in addition, P (x) has a unique rootx ∈ (0, 1], thenε MAP = ε(x) is an upper bound on the MAP threshold and ε * =ε MAP .
Proof: Omitted due to similarity with Lem. 6. Corollary 3: Consider the SC ensemble defined in Section III-A. If ε < ε * and w > K f,g ∆E(ε), then Theorem 1 shows that the SC DE recursion converges to the zero vector.

IV. CONCLUSIONS
A new theorem is presented that provides a simple proof of threshold saturation for many scalar DE recursions. The conditions of the theorem are verified for the density-evolution (DE) equations of irregular LDPC codes on the BEC, a class of generalized LDPC codes, and the joint iterative decoding of some intersymbol-interference channels with erasure noise. Therefore, threshold saturation is now proved for these cases. Moreover, we believe this approach opens the door to threshold-saturation proofs for many more general spatiallycoupled systems.