Spatially Coupled Generalized LDPC Codes: Asymptotic Analysis and Finite Length Scaling

Generalized low-density parity-check (GLDPC) codes are a class of LDPC codes in which the standard single parity check (SPC) constraints are replaced by constraints defined by a linear block code. These stronger constraints typically result in improved error floor performance, due to better minimum distance and trapping set properties, at a cost of some increased decoding complexity. In this paper, we introduce spatially coupled generalized low-density parity-check (SC-GLDPC) codes and present a comprehensive analysis of these codes, including: (1) an iterative decoding threshold analysis of SC-GLDPC code ensembles demonstrating capacity approaching thresholds via the threshold saturation effect; (2) an asymptotic analysis of the minimum distance and free distance properties of SC-GLDPC code ensembles, demonstrating that the ensembles are asymptotically good; and (3) an analysis of the finite-length scaling behavior of both GLDPC block codes and SC-GLDPC codes based on a peeling decoder (PD) operating on a binary erasure channel (BEC). Results are compared to GLDPC block codes, and the advantages and disadvantages of SC-GLDPC codes are discussed.


I. INTRODUCTION
Low-density parity-check (LDPC) block codes, with iterative message passing decoding, were introduced by Gallager in 1963 [1] as a class of codes whose decoder implementation complexity grows only linearly with block length, in contrast to maximum likelihood (ML) and maximum a posteriori (MAP) decoding methods whose complexity typically has exponential growth. As a result of the low-density constraint on the parity-check matrix H, the minimum distance of LDPC block codes is sub-optimal. However, Gallager showed that regular constructions, where the variable and check node degrees of the Tanner graph representation of H are fixed, maintain linear minimum distance growth with block length, i.e., they are asymptotically good, although their iterative decoding thresholds are bounded away from capacity. Irregular constructions, introduced by Luby et al. in 2001 [2], where the node degrees are not fixed and can be numerically optimized, have capacity-approaching thresholds, but typically involve a large fraction of degree two variable nodes that can preclude linear distance growth. As a result, irregular codes perform best in the waterfall, or low signal-to-noise ratio (SNR), portion of the bit-error-rate (BER) performance curve, while regular codes perform better at high SNRs, i.e., in the error floor region of the BER curve.
Generalized LDPC (GLDPC) block codes, first proposed by Tanner in 1981 [3], are constructed by replacing some/all of the single parity-check (SPC) constraint nodes in the Tanner graph of a conventional LDPC code by more powerful generalized constraint (GC) nodes corresponding to an (n, k) linear block code. The n variable nodes connected to a GC node in the Tanner graph of a GLDPC code are then considered as the code bits of the corresponding (n, k) code, and the sub-code associated with each GC node is referred to as a constraint code. In message passing decoding of GLDPC codes, the constraint codes are decoded using standard block code decoders which, in the case of simple constraint codes such as Hamming codes [4] or Hadamard codes [5], can be ML or MAP decoders. GLDPC codes have many potential advantages compared to conventional SPC/LDPC codes, such as large minimum distance [4], [6], low error floors [7], and fast iterative decoding convergence [8].
Spatially coupled LDPC (SC-LDPC) codes, also known as LDPC convolutional codes, were introduced by Jimenez-Felstrom and Zigangirov in 1999 [9]. SC-LDPC codes can be viewed as a sequence of LDPC block codes whose graph representations are coupled together over time, resulting in a convolutional structure with block-to-block memory. A remarkable property of SC-LDPC codes, established numerically in [10] and analytically in [11], [12], is that their iterative message passing decoding threshold is equal to the MAP decoding threshold of the underlying LDPC block code ensemble, a phenomenon known as threshold saturation. In other words, the (exponential complexity) MAP decoding performance of the underlying block code can be achieved by its coupled version with (linear complexity) message passing decoding.
Thus motivated to combine the threshold improvement of spatial coupling with the improved distance properties of generalized constraints, this paper proposes spatially coupled versions of GLDPC codes, denoted SC-GLDPC codes, and presents both asymptotic (threshold and distance) and finite-length analyses of SC-GLDPC code ensembles. A principle contribution of this paper is to extend the results of [13], [14], [15], [16] and present a unified treatment and analysis of SC-GLDPC codes. We first extend the threshold analysis of protograph-based SC-LDPC code ensembles in [10] to GLDPC code ensembles and use this to perform an iterative decoding threshold analysis of SC-GLDPC codes ensembles. This method is used to show numerically that threshold saturation is achieved for SC-GLDPC code ensembles, i.e., their thresholds coincide with the maximum a-posteriori (MAP) decoding threshold of the underlying GLDPC block code ensemble. 1 This is followed by a minimum distance analysis of terminated and tail-biting SC-GLDPC code ensembles and a free distance analysis of unterminated ensembles, both of which demonstrate that the ensembles are asymptotically good and have large distance growth rates. In order to study the finite-length scaling properties of SC-GLDPC code ensembles, a method to analyze the finite-length scaling behavior of GLDPC block codes over the binary erasure channel (BEC) with peeling decoding (PD) is first introduced. We then extend this approach to study SC-GLDPC code ensembles and demonstrate robust finite-length scaling performance.

II. PROTOGRAPH-BASED SC-GLDPC CODES
A protograph [19] is a small bipartite graph that connects a set of n v variable nodes V = {v 1 , v 2 , . . . , v nv } to a set of n c constraint nodes C = {c 1 , c 2 , . . . , c nc } by a set of edges E. The edges connected to a variable node v j of degree ∂(v j ) or a constraint node c i of degree ∂(c i ) are labeled by e v j,a or e c i,b , respectively, where a = 1, . . . , ∂(v j ) and b = 1, . . . , ∂(c i ). If the a-th edge associated with v j is the b-th edge associated with c i , then e v j,a = e c i,b . 2 In a protograph-based GLDPC code ensemble, each constraint node c i can represent an arbitrary block constraint code C i with parity-check matrix H c i , length n c i , and m c i linearly independent parity-check equations.
The design rate of the GLDPC code ensemble is then given by A protograph can be represented by means of an n c × n v bi-adjacency matrix B, which is called the base matrix of the protograph. The nonnegative integer entry B ij in row i and column j of B is equal to the number of edges that connect nodes c i and v j in the protograph. In order to construct ensembles of protograph-based GLDPC codes, a protograph can be interpreted as a template for the Tanner graph of a derived code, which is then obtained by a copy-and-permute or graph lifting operation [19]. In matrix form, the protograph is lifted by replacing each nonzero  ( If we suppose both the constraint nodes are (7,4) Hamming codes with parity-check matrix where the constraint code length is n c = 7 and the row rank of H c is m c = 3, then the resulting ensemble has design rate R = 1/7. Note that even though both constraints are defined by the same (7, 4) Hamming code, a different ordering of columns can be used. In Fig. 1, the column of H c that the variable node is connected to is shown on the edge.

A. Unterminated SC-GLDPC codes
An unterminated SC-GLDPC code can be described by a convolutional protograph [20] with base matrix where w denotes the syndrome former memory or coupling width of the code and the b c × b v component base matrices B i , i = 0, 1, . . . , w, represent the edge connections from the b v variable nodes at time t to the b c (generalized) constraint nodes at time t + i. An ensemble of (in general) time-varying SC-GLDPC codes can then be formed from B [0,∞] using the protograph construction method described above with lifting factor M . The decoding constraint length of the resulting ensemble is given by ν s = (w + 1)M b v , the design rate is given by and at each time instant t the encoder creates a block v t of M b v symbols resulting in the Starting from a b c ×b v base matrix B of a block code ensemble, one can construct SC-GLDPC code ensembles with the same variable and check node degrees as B. This is achieved by an edge spreading procedure [20] that divides the edges connected to each variable node in the base matrix B among w + 1 component base matrices B i , i = 0, 1, . . . , w, such that the condition We now give some examples of constructing SC-GLDPC code ensembles.
Example 2: For w = 1, we can apply the edge spreading technique to the (b c , b v ) = (2, 7)regular block code base matrix in (2) to obtain the following component base matrices The convolutional protograph associated with the resulting base matrix B [0,∞] defined in (4) (3) and that the constraint nodes c 1 and c 2 represent shortened codes.) After lifting, the constraint length of the resulting SC-GLDPC code ensemble is ν s = 14M and the design rate is R = 1/7.
We will refer to this SC-GLDPC code ensemble as Ensemble A 7 . An extension to the Ensemble ... To illustrate the flexibility of SC-GLDPC code designs, multiple edges can also be introduced in the block protograph. The protograph-based braided block code (BBC) ensembles considered in [21] are another example of SC-GLDPC code ensembles. These can be derived by using the Tanner graph of a tightly BBC [22] as a protograph. The component base matrices of such an SC-GLDPC code can be identified as where i = 1, . . . , w, e i = (0, . . . , 0, 1, 0, . . . , 0) is the length w vector with a one at the i th position and zeros elsewhere, 0 is the all-zero vector, and i the all-one vector, of length w. We   will use the term Ensemble C n c when referring to such SC-GLDPC code ensembles based on constraint codes of length n c = 2w + 1.
Example 4: For the (b c , b v ) = (2, 7)-regular GLDPC base matrix with (7, 4) Hamming constraint codes and design rate R = 1/7 from Example 1, the convolutional protograph resulting from the tightly BBC construction of (9) with w = 3, n c = 7, and m c = 3, corresponding to Ensemble C 7 , is illustrated in Fig. 4, where the upper constraint nodes correspond to the "horizontal constraints" and the lower constraint nodes correspond to the "vertical constraints" of the braided construction. Its girth is equal to eight, which follows from the structure of the array and is true for any SC-GLDPC code resulting from a tightly BBC protograph.
Observe that the sum of the component base matrices in (9) is equal to the base matrix B in (2) of the corresponding GLDPC code, i.e., the all-one matrix of dimension b c × b v = 2 × 7.
This reflects the fact that the graph in Fig. 4 can be obtained by repeating the GLDPC graph in where L is called the coupling length. The matrix B [0,L−1] is then the base matrix of a terminated SC-GLDPC code. The corresponding terminated convolutional protograph is slightly irregular, with lower constraint node degrees at both ends. This is illustrated for the A 7 ensemble of where m c denotes the (constant) number of independent parity checks associated with each constraint code and ∆ ≥ 0 accounts for a possible rate increase due to the shortened constraint ...
...  The generalized convolutional base matrix B [0,∞] can also be terminated using tail-biting [23], [24], resulting in the base matrix of a tail-biting generalized LDPC (TB-GLDPC) code ensemble. Here, for any λ ≥ w, the last b c w rows of the terminated parity-check matrix B [0,λ −1] are removed and added to the first b c w rows to form the λb c × λb v tail-biting parity-check matrix 4 We assume here the simplified case where each generalized constraint code is described by a parity-check matrix Hc with m c independent parity checks. Under this assumption, the rate formula in (1) for GLDPC block codes becomes R = 1 − bcm c /bv.
Note that, if w = 1 and λ = 1, the tail-biting base matrix is simply the original block code base matrix, i.e., B (1) in such a way preserves the design rate of the ensemble, i.e., tb has exactly the same degree distribution as the original block code base matrix B.

III. THRESHOLD ANALYSIS OF SC-GLDPC CODES
We assume belief propagation (BP) decoding, with log-likelihood ratios (LLRs) acting as messages. At every iteration , first all constraint nodes and then all variable nodes are updated.
The outgoing messages computed at a constraint node c i at iteration are then equal to is the LLR received at constraint node c i from the variable node connected to e c i,b at iteration , and we have partitioned C i into the sets C b,0 corresponds to the b-th extrinsic output generated by an optimal a posteriori probability (APP) decoder for component code C i , which is computed from the incoming messages L to constraint node c i . The incoming messages of the first iteration are initialized by the channel LLRs L ch (v j ) of the neighboring variable nodes, i.e., where v j is the variable node connected to e c i,b . The outgoing messages computed at a variable node v j at iteration are equal to where a, a ∈ {1, . . . , ∂(v j )}.

A. Density evolution for GLDPC code ensembles
For transmission over a binary erasure channel (BEC), the messages that are passed between the nodes represent either an erasure or the correct symbol values 0 or 1. In this case the BP decoder is particularly simple and exact density evolution can be described explicitly. Let . . , ∂(c i )}, denote the probabilities that the incoming messages to c i computed in the previous iteration are erasures. For a GLDPC code ensemble, where c i corresponds to an arbitrary block code, (15) can be replaced by the general expression where f C i b is a multi-dimensional input/output transfer function that characterizes the APP decoder that computes the messages L ( ) c (e c i,b ) corresponding to (13). Note that, for generalized codes, which implies that the ordering of edges can affect the performance of the ensemble. A method for computing explicit expressions for the APP decoder output distributions that can be used in (16) was presented in [25]. This method is based on a Markov chain analysis of the decoder metrics using a trellis representation of the block code C i .
The variable to check node message sent along edge e v j,a is an erasure if all incoming messages from the channel and from the other neighboring check nodes are erasures. Thus we have where a, a ∈ {1, . . . , ∂(v j )} and is the erasure probability of the BEC. The largest channel value for which (16) and (17) converge, denoted BP , is the threshold of the BP decoder for the GLDPC code ensemble.
B. Bounding MAP thresholds from above with BP extrinsic information transfer functions The extrinsic probability p BP,extr (v j , ) that a symbol associated with variable node v j remains erased after iterations of BP decoding can be expressed as Note that here the product is over all incoming messages to v j and the channel erasure probability does not appear in the expression but implicitly involved in the calculation of q ( ) (e v j,a ). The BP extrinsic information transfer (EXIT) function h BP ( ) [26] is given by the average of p BP,extr (v j , ) over all transmitted variable nodes v j . 6 Example 5: Consider the (2, 7)-regular protograph-based GLDPC block code ensemble with Hamming component codes of length n c = 7 from Example 1. The BP EXIT function h BP ( ) of this ensemble is shown in Fig. 6. The vertical line indicates the channel value at which the grey area below the curve is equal to the rate of the ensemble, which forms an upper bound MAP = 0.856 on the threshold of an optimal MAP decoder. This follows from the area theorem [27] and the fact that h BP ( ) can never be below the EXIT function of the MAP decoder. In this case, the calculated BP threshold is given by BP = 0.756, and we see that there exists a large gap between the BP and the MAP thresholds, which indicates the suboptimality associated with BP decoding. 7 2

C. Threshold saturation of terminated SC-GLDPC code ensembles
Assume now that we start encoding at time t = 0 and terminate after L time instants. As a result we obtain the terminated base matrix B [0,L−1] from (10). These terminated SC-GLDPC codes can be interpreted as GLDPC block codes that inherit the structure of convolutional codes.
The length of these codes depends not only on the lifting factor M but also on the coupling length L. For a fixed L, the BEC density evolution thresholds BP corresponding to codes with 6 Punctured nodes which are not transmitted are excluded. 7 A detailed analysis of unstructured irregular ensembles, including results on the tightness of this bound, can be found in [26]. For structured protograph ensembles, this technique has been applied in [28].  Fig. 8. Analogously to SC-LDPC codes (see [20]) with SPC constraints, it can be observed that, as L → ∞, the BP thresholds numerically coincide with the upper bounds on the MAP decoding thresholds of the underlying block code ensembles, thus exhibiting the threshold saturation phenomenon (see [10], [11]).
The BP EXIT functions of the terminated codes from ensemble A 7 are shown in Fig. 9, where it can be seen that, with increasing L, the BP and the MAP thresholds of the terminated SC-GLDPC code ensembles are converging. Moreover, the MAP thresholds (and hence the BP thresholds) of the terminated SC-GLDPC code ensemble can also be observed to converge to the MAP threshold MAP = 0.856 of the underlying GLDPC block code ensemble with increasing L.
We note that, while the numerical convergence of the BP thresholds of the terminated SC-GLDPC code ensemble to the MAP threshold of the underlying GLDPC block code ensemble implies threshold saturation in the conventional sense [11], the converging BP and MAP thresholds of the terminated SC-GLDPC codes is a stronger result. This implies that, asymptotically, BP decoding of SC-GLDPC codes provides optimal (MAP) decoding performance.
Further, we note that large values of L are realistic in conjunction with sliding window decoders, like those suggested in [29], where decoding delay and storage requirements depend on the window size W , which is independent of the coupling length L (typically W L) of the transmitted code sequences. For shorter values of L, which induce rate loss, BP decoding of terminated SC-GLDPC codes is suboptimal but still provides a flexible adjustment between code rate and threshold (see Fig. 8).

IV. DISTANCE ANALYSIS OF SC-GLDPC CODES
A. Minimum distance analysis of terminated SC-GLDPC codes In [30], Abu-Surra, Divsalar, and Ryan presented a technique to calculate the average weight enumerator and asymptotic spectral shape function for protograph-based GLDPC block code ensembles. The spectral shape function can be used to test if an ensemble is asymptotically good, i.e., if the minimum distance typical of most members of the ensemble is at least as large as δ min n, where δ min is the minimum distance growth rate of the ensemble and n is the block length.
Example 6: Consider the (2, 7)-regular GLDPC block code protograph with base matrix B from (2) and the generalized constraint nodes shown in Fig. 1. If we suppose the constraint codes to be (7, 4) Hamming codes with parity-check matrix H c from (3), then the resulting ensemble has design rate R = 1/7, is asymptotically good, and has growth rate δ min = 0.186 [30]. 2 We now consider the associated (2, 7)-regular terminated SC-GLDPC code ensembles A 7 discussed above in Sections II and III, whose protograph is shown in Fig. 2, with constraints corresponding to the (7, 4) Hamming code with parity-check matrix H c . After termination, the design rate of the ensemble is given by where ∆ = 2 in this case because the two leftmost (shortened) constraint nodes in Fig. 2 correspond to shortened codes with rate 1/3, i.e., the number of parity checks in these two constraint nodes is 2, while all the other constraint nodes have m c = 3 parity-checks. These ensembles were shown to have thresholds numerically indistinguishable from the MAP threshold of the underlying GLDPC block code ensemble as L → ∞ in Section III.
The evaluation of the asymptotic weight enumerators for SC-GLDPC codes is complex, since the conjecture regarding simplification of the numerical evaluation proposed in [30] cannot be applied to SC ensembles. This conjecture relies on grouping together nodes of the same type and optimizing them together. However, in the SC-GLDPC case, nodes from different time instants must be optimized separately, even if they are of the same type.  with coupling lengths L = 7, 8, 10, 12, 14, 16, 18, and 20. Also shown are the asymptotic spectral shape functions for "random" codes with the corresponding rates R L calculated using (see [1]) where H(δ) = −(1 − δ) ln(1 − δ) − δ ln(δ) is the binary entropy function. We observe that the SC-GLDPC code ensembles A 7 are asymptotically good and have relatively large minimum distance growth rates, ranging from about 25% to 65% of the (optimal) random coding growth rates. This indicates that long codes chosen from these ensembles have, with probability near one, a large minimum distance. As L increases, the design rate R L approaches R = 1/7 and the minimum distance growth rate decreases, as was also observed in the case of SC-LDPC codes with SPC constraints (see [20]).

B. Free distance analysis of SC-GLDPC code ensembles
In Fig. 10 we saw that the minimum distance growth rates of terminated SC-GLDPC codes decrease as the coupling length L increases. However, since SC-GLDPC codes can be decoded as unterminated (no preset coupling length) convolutional codes by employing a sliding window decoder, a more appropriate distance measure for assessing their ML decoding performance is DRAFT the free distance growth rate of the SC-GLDPC ensemble. In this section, we first calculate the minimum distance growth rates of TB-GLDPC code ensembles and show that, for sufficiently large coupling lengths, the growth rates coincide with those calculated for the terminated SC-GLDPC code ensembles in Section IV-A. We then show that the growth rates of the TB-GLDPC code ensembles and the terminated SC-GLDPC code ensembles can be used to obtain lower and upper bounds on the free distance growth rate of the unterminated SC-GLDPC code ensemble, respectively.

1) Minimum distance analysis of TB-GLDPC code ensembles:
We now consider terminating the protograph in Fig. 2 as a TB-GLDPC code with coupling length λ. Unlike the previous termination technique, this results in a (2, 7)-regular protograph with design rate R λ = 1/7 for all λ. The minimum distance growth rates of the TB-GLDPC code ensembles are presented in Fig. 11 alongside those corresponding to the terminated SC-GLDPC code ensembles. We observe that the TB-GLDPC growth rates remain constant at δ min = 0.186 (the growth rate of the original GLDPC block code ensemble) for λ = 1, 2, . . . , 8, and then begin to decay to zero as λ → ∞. Also, as a result of the convolutional structure, we observe that the TB-GLDPC and SC-GLDPC growth rates coincide for L, λ ≥ 10. This is the same behavior observed for TB-LDPC and SC-LDPC codes with SPC constraints [31].
2) Free distance bounds for SC-GLDPC code ensembles: Now consider an ensemble of periodically time-varying unterminated SC-GLDPC codes with rate R = 1 − b c m c /b v and period T constructed from a convolutional protograph with base matrix B [0,∞] (see (4)) as described in Section II-A. Using a modification of the proof techniques in [31], [32], we can show that the average free distance of this ensemble is bounded below by the average minimum distance of an ensemble of TB-GLDPC codes derived from the base matrix B Proof. There is a one-to-one relationship between members of the periodically time-varying unterminated SC-GLDPC code ensemble and members of the corresponding terminated SC-GLDPC code ensemble with coupling length L = T . For any such pair of codes, every codeword in the terminated SC-GLDPC code can also be viewed as a in the unterminated code. It follows that the free distance d  Since there is no danger of ambiguity, we will henceforth drop the overline notation when discussing ensemble average distance measures.
3) Free distance growth rates of SC-GLDPC code ensembles: For unterminated SC-GLDPC codes, it is natural to define the free distance growth rate with respect to the decoding constraint length ν s , i.e., as the ratio of the free distance d free to ν s . By bounding d free we observe that, for T ≥ 10, the upper and lower bounds coincide, indicating that, for these values of the period T , δ (T ) free = 0.805, significantly larger than the minimum distance growth rate δ min = 0.186 of the underlying GLDPC block code ensemble. 9 In addition, we note that, at the point where the upper and lower bounds on δ (T ) free coincide, the minimum distance growth rates for both termination methods also coincide. Recall that the TB-GLDPC code ensembles all have rate 1/7, wheras the rate of the SC-GLDPC code ensembles is a function of the coupling length L given by (19). This general technique can be used to bound the free distance growth rate above and below for any regular or irregular periodically time-varying protograph-based unterminated SC-GLDPC code ensemble.
While large free distance growth rates are indicative of good ML decoding performance, when predicting the iterative decoding performance of a code ensemble in the high SNR region other graphical objects such as trapping sets, pseudocodewords, absorbing sets, etc., come into effect. Based on results from the SPC case [31], we would expect SC-GLDPC codes with large minimum/free distance growth rates to also have large trapping set growth rates, indicating good iterative decoding performance in the high SNR region.

V. FINITE-LENGTH ANALYSIS OF GLDPC BLOCK AND SC-GLDPC CODES
To analyze the finite-length performance of LDPC codes over the BEC, a decoding method called peeling decoding (PD) can be employed [33]. PD is a simple algorithm that is initialized by removing all of the correctly received variable nodes, as well as their attached edges, from the Tanner graph of H after BEC transmission. The algorithm then iteratively removes degreeone check nodes from the graph, along with their attached variable nodes and edges. We now describe an extension of PD to GLDPC block and terminated SC-GLDPC codes, referred to as generalized peeling decoding (GPD). 9 Note that the free distance growth rate may also be calculated with respect to the encoding constraint length νe, which corresponds to the maximum number of transmitted symbols that can be affected by a single nonzero block of information digits. As a result of normalizing by the decoding constraint length, it is possible to have free distance growth rates larger than 0.5. For further details, see [31]. DRAFT

A. Type vectors and initialization of GPD
Recall that represents the set of edges in a given protograph. In the Tanner graph of a resulting lifted constraint matrix H (resp. H [0,L−1] ), we say that a particular edge is of type e v j,a if it connects a variable node and a constraint node that are copies of the two nodes that edge e v j,a connects in the protograph. For a variable node v in the Tanner graph of H (resp. H [0,L−1] ), we also define the variable node type by a binary |E|-dimensional vector t v , where each entry is a "1" iff a particular edge type is connected to variable node v. Similarly, for a constraint node c, we define its type by a binary |E|-dimensional vector t c . We denote the set of variable and constraint node types in the Tanner graph of H (resp. H [0,L−1] ) by F tv and F tc , respectively. Note that the sets F tv and F tc are determined from the connectivity of the protograph, as will be illustrated in Example 7 below. Finally, we let L tv and R tc represent the number of variable and constraint nodes of type t v and t c in H (resp. H [0,L−1] ), respectively.
The details of the GPD algorithm are presented in Section V-B. We first discuss GPD initialization, which is identical to PD initialization: the correctly received variable nodes of H (resp. H [0,L−1] ) and their attached edges are removed from the graph. After initialization, the residual graph contains constraint nodes with types that are not included in F tc , the set of constraint node types in the original graph, but the set of variable node types F tv remains the same. We now define D(t c ) as the set of constraint node types that can appear in the graph of H (resp. H [0,L−1] ) after GPD initalization when a constraint node of type t c ∈ F tc loses one or more edges. The extended set of all possible constraint node types which are present in the residual graph after GPD initialization is then given by F tc = tc∈F tc D(t c ). then the type vector for c 1 is t c 1 = (1, 1, . . . , 1, 0, 0, . . . , 0) ∈ F tc and the type vector for c 2 is t c 2 = (0, 0, . . . , 0, 1, 1, . . . , 1) ∈ F tc . 10 Both vectors are of length |E| = 14, the number of edges in the protograph, and have weight n c = 7, the length of the constraint code. In any lifted graph with lifting factor M , there are precisely M copies of each edge, variable node, or constraint node of a given type, where the types are defined from the protograph as described above.
Corresponding to each of the constraint node types in this example, 2 7 = 128 residual types can appear in the graph when edges are removed. Thus, in total, F tc contains 256 constraint node types. 2 According to the above definitions, the expected degree distribution (DD) of the residual graph after initialization can be expressed as follows: for t v ∈ F tv and t c ∈ F tc , where L tv (0) (resp. R t c (0)) represents the number of variable (resp. constraint) nodes of type t v (resp. t c ) after GPD initialization and |t c | (resp. |t c |) is the weight of the vector t c (resp. t c ).

B. Decodable constraint nodes and the GPD
In general, each constraint node type in the protograph B (resp. B [0,L−1] ) of a GLDPC code can be associated with a different constraint code. Let C tc be the constraint code associated with the constraint nodes in the base matrix B (resp. B [0,L−1] ) of type t c ∈ F tc . By extension, each constraint node in the graph of H (resp. H [0,L−1] ) is associated with a constraint code according to its type. After GPD initialization, the type of a given constraint node can be modified from t c to t c , where |t c | < |t c |, and we say that t c is the input erasure pattern seen by the constraint code C tc . The question now is if, by decoding the constraint code C tc associated with a constraint node of type t c in the residual graph using a given decoding algorithm, for instance ML decoding or some suboptimal algorithm, we are able to recover the |t c | variables still connected to the constraint node. In general, for each constraint code C tc , only a subset of input erasure patterns can be decoded. This subset is denoted by A(t c ) ⊂ D(t c ). If a constraint node in the residual graph is of type t c ∈ A(t c ), then we say it is a decodable constraint node and t c a decodable constraint node type. For example, if all the constraint codes are SPCs, then only constraint node types with input erasure patterns containing exactly one erasure are decodable. However, if the constraint code is a (7,4) Hamming code with ML decoding, then all input erasure patterns with one and two erasures and some input erasure patterns of weight three are decodable.
The set of all decodable constraint node types is defined as A .
= ∪ tc∈F tc A(t c ) ⊂ F tc . Given the discussion above, the GPD algorithm can now be seen as a straightforward extension of PD for LDPC codes to GLDPC codes. After the graph is initialized, GPD chooses one constraint node at random from the graph that is decodable. This constraint node, all connected variable nodes, and all attached edges are then removed from the graph. GPD continues in this way until there are no further constraint nodes that can be removed from the graph, which corresponds to a decoding failure, or until there are no variable nodes left in the graph, which corresponds to successful decoding.

C. Expected graph evolution
We now define the normalized DD at time τ as where is the GPD iteration index, R tc (τ ) (resp. L tv (τ )) is the number of constraint (resp. variable) nodes in the graph of type t c (resp. t v ) at time τ , and n = M b v (resp. M b v L) is the block (resp. termination) length. Following the methodology developed in [33] to analyze the BEC finite-length performance of LDPC block codes, we can investigate the BEC finite-length performance of GLDPC codes by analyzing the statistical evolution of the normalized DD in (26) during the decoding process. As shown in [33], the expected value of r tc (τ ) and l tv (τ ), denoted byr tc (τ ) andl tv (τ ), respectively, can be computed as the solution to the following system of differential equations: i.e., the derivative ofr tc (τ ) w.r.t. τ in (28) can be evaluated by computing the variation in the number of constraint nodes of type t c with GPD iteration given that the normalized DD at time τ is at its mean {l tv (τ ),r tc (τ )} tv∈F tv ,tc∈F tc . A similar interpretation holds for (27). Further, the solution to (27) and (28) is unique and, with probability 1 − O(e − √ n ), any particular realization of the normalized DD in (26) deviates from its mean by a factor of less than n −1/6 for the initial conditionsr which can be computed from (24) and (25) [33]. The actual computation of the expectations in (27) and (28) is described in [15]. The GPD threshold is defined as the maximum value of for which the expected fraction of decodable constraint nodeŝ is positive for any τ ∈ [0, ), whereâ(τ ) is the mean of the random process Finally, we can compute the expected fraction of variable nodes in the graph at any time τ , denoted byv(τ ), asv In addition to characterizing the asymptotic behavior, i.e., to computing the GPD threshold ensemble, the solution to the system of equations given by (27) and (28) can be used to determine the quantities needed to assess the finite-length performance of GLDPC block and terminated SC-GLDPC codes. We refer to critical points as the points in time for whichâ(τ ) has a local minima.
As shown in [33], the average (over the ensemble of codes) error probability is dominated by the probability that the process a(τ ) survives, i.e., does not go to zero around the critical points.
Therefore, characterizing the critical points and the expected fraction of decodable constraint nodes in the graph at those points in time are the parameters needed to determine the GLDPC block or terminated SC-GLDPC code finite-length performance, and they can be computed from (27) and (28).

D. Numerical results: GLDPC block codes
With the tools described above, we can now investigate the asymptotic and finite-length performance of GLDPC code ensembles. We start by considering the uncoupled (2, 7)-regular GLDPC block code ensemble from Example 1. Example 8: Consider the (2, 7)-regular GLDPC block code ensemble of Example 1. Assume that a (7, 4) Hamming code is associated with each of the two constraint nodes and that the constraint codes are decoded using ML decoding. The design rate of this ensemble is R = 1/7.
All constraint node types with one or two erasures can be decoded, as well as some constraint node types with three erasures. Fig. 12 shows the evolution of the expected fraction of decodable constraint nodesâ(τ ) versus the expected fraction of variable nodesv(τ ) in the graph for different values. 11 We also include a set of 10 simulated trajectories of a(τ ) for = 0.69 to demonstrate that they concentrate around the predicted mean. Note first thatâ(τ ) has a single critical point atv(τ * ) ≈ 0.43. Indeed, we can compute the threshold * as the maximum value of for which the minimum is exactly zero, and in this case we obtain * ≈ 0.7025.
The finite-length error probability is dominated by the statistics of a(τ ) around τ * . Following 11 Note that the time variable τ runs backwards in this figure (right to left), in the sense that small values of τ correspond tov(τ ) on the right, where the graph still contains a relatively large fraction of variable nodes, whereas large values of τ correspond to small values ofv(τ ) on the left. [33], for each n and pair, we can estimate the finite-length error probability as whereâ(τ * ) is the expected value of a(τ ) at τ * and Var[a(τ * )] represents its variance.â(τ * ) was computed using numerical integration of the system of differential equations in (27)-(28), and Var(a[τ * ]) was estimated using Monte Carlo simulation. 12 Also in [33], the authors showed that the ratio of the expected number of degree-one constraint nodes to the standard deviation at the critical point approximately scales as α √ n( * − ), where α is a scaling parameter that only depends on the DD. In the GLDPC case, simulated trajectories for a(τ ) suggest that the same scaling holds and that the performance for any pair (n, ) can be estimated as After computingâ(τ * )/ Var(a(τ * )) for a given (n, ) pair, we estimate α by equating the arguments in (34) and (35), so that .
For the (2, 7)-regular GLDPC block code ensemble with (7, 4) Hamming constraint codes and an ML decoder, we thus obtain α = 1.8024. In Fig. 13, we plot the simulated performance versus (35), where we observe that the estimate is very accurate for a sufficiently large lifting factor. 2

E. Numerical results: SC-GLDPC codes
We now investigate the asymptotic and finite-length performance of a terminated version of the coupled A 7 SC-GLDPC code ensemble from Example 2.
Example 9: Following a similar procedure as in Example 8, we now analyze the finite-length behavior of terminated SC-GLDPC codes. In Figure 14, we show the evolution of the expected fractionâ(τ ) of decodable check nodes during iterations of the GPD for a terminated version of the A 7 SC-GLDPC code ensemble of Example 2 (corresponding to the GLDPC block code ensemble of Example 1) with coupling lengths L = 50, 100, and 150, lifting factor M = 1000, and a channel parameter = 0.75. Also included is a set of simulated decoding trajectories 12 Var(a[τ * ]) can be obtained from the solution of the covariance evolution system of differential equations, first presented in [33] for LDPC code ensembles  of a(τ ), computed for L = 150. Unlike the GLDPC block code, the expected evolutionâ(τ ) displays a constant critical phase that corresponds to a decoding wave traveling towards the central positions of the graph. Further, the critical valueâ(τ * ) during such a phase does not depend on L, and the length of the critical phase is roughly proportional to L. The threshold * is given by the maximum value of for which the critical value is exactly zero, and in this case we obtain * = 0.8. 13 Similar effects were first described in [34] for (non-generalized) terminated SC-LDPC codes.
As also suggested in [34], using simulated decoding trajectories we should observe that Var[a(τ )] is fairly flat during the critical phase and that the covariance CoVar[a(τ ), a(ξ)] decays exponentially fast with |τ − ξ|, with a rate of decay that we denote by θ. Fig. 15 demonstrates that this is indeed the case. In Fig. 15(a), we show the empirical variance of the process a(τ ) computed from 500 simulated trajectories with L = 100 and M = 2000. In Fig. 15(b), we show the empirical covariance CoVar[a(τ ), a(ξ)] of the process obtained from the same set of simulations, where the covariance is normalized by Var[a(ξ)] so that the maximum value is equal to one. Observe that an exponentially decaying function provides an accurate estimate of the normalized covariance, in which the parameter θ = 0.87 was obtained by a least squares fit.
Based on this evidence, the survival probability of the a(τ ) process during the critical phase follows a scaling law of the same form as the one proposed in [34], and thus the block error probability P Block can be estimated as where Φ(z) is the c.d.f. of the standard Gaussian distribution, N (0, 1), L is the length of the critical phase, and, as in the uncoupled case, α √ M ( * − ) corresponds to the ratio of the expected number of decodable constraint nodes during the critical phase to the standard deviation of a(τ ).
Both θ and α are parameters that depend on the underlying GLDPC block code and the edge spreading. Given the results in Fig. 14 and Fig. 15, we estimate that α ≈ 5.66. 13 The threshold * = 0.8 computed here for GPD differs from the value * ≈ 0.85 obtained earlier for the terminated A7 ensemble with L = 150 (see Fig. 8) due to a difference in the method of decoding the constraint codes (ML decoding in this example vs. BCJR decoding in Fig. 8). If we change the component decoder from ML to BCJR, the scaling law in (37) that predicts the finite-length performance of the SC-GLDPC code will be the same, but with different scaling parameters. Var[a(ξ)] so that the maximum value is equal to one. Fig. 16 shows a comparison between the simulated performance (solid lines) and estimated error probability using (37) (dashed lines) for the terminated A 7 SC-GLDPC code ensemble with L = 50 and (7, 4) Hamming constraint codes decoded with ML decoding. We again note that, as the lifting factor M increases, the performance estimate becomes very accurate. 14 We also show the corresponding results for the uncoupled (2, 7)-regular GLDPC block code ensemble of Fig. 1 with ML-decoded (7, 4) Hamming constraint codes and comparable lifting factors.
Besides the advantage enjoyed by the SC-GLDPC codes in decoding threshold, we see that they also exhibit better finite-length scaling behavior than GLDPC block codes, in the sense that their performance converges more quickly to the threshold.

VI. CONCLUDING REMARKS
Generalized LDPC (GLDPC) codes can offer significant performance improvements when compared to LDPC codes with SPC constraints at the expense of a modest increase in decoding complexity (depending on the particular constraint codes and decoders chosen), albeit with the advantage of a typically smaller number of message passing iterations. In this paper, we presented a comprehensive study of spatially coupled generalized LDPC (SC-GLDPC) codes, including both asymptotic and finite-length analyses. Specifically, terminated SC-GLDPC code ensembles were shown to achieve threshold saturation with near-capacity iterative decoding thresholds, thus assuring SC-GLDPC codes of having better waterfall performance than their underlying GLDPC block codes. They were also shown to be asymptotically good and to possess large minimum distance growth rates, thus assuring them of also having excellent error floor performance. Finally, terminated SC-GLDPC codes were shown to outperform their GLDPC block code counterparts in the finite length regime. Based on these results, we believe SC-GLDPC codes are an attractive choice for applications requiring excellent performance throughout the entire range of decoded error rates with a limited number of decoding iterations. DRAFT November 1, 2019