Finite-Length Analysis of Spatially-Coupled Regular LDPC Ensembles on Burst-Erasure Channels

Regular spatially-Coupled LDPC (SC-LDPC) ensembles have gained significant interest since they were shown to universally achieve the capacity of binary memoryless channels under low-complexity belief-propagation decoding. In this work, we focus primarily on the performance of these ensembles over binary channels affected by bursts of erasures. We first develop an analysis of the finite length performance for a single burst per codeword and no errors otherwise. We first assume that the burst erases a complete spatial position, modeling for instance node failures in distributed storage. We provide new tight lower bounds for the block erasure probability ($P_{\mathrm{B}}$) at finite block length and bounds on the coupling parameter for being asymptotically able to recover the burst. We further show that expurgating the ensemble can improve the block erasure probability by several orders of magnitude. Later we extend our methodology to more general channel models. In a first extension, we consider bursts that can start at a random position in the codeword and span across multiple spatial positions. Besides the finite length analysis, we determine by means of density evolution the maximnum correctable burst length. In a second extension, we consider the case where in addition to a single burst, random bit erasures may occur. Finally, we consider a block erasure channel model which erases each spatial position independently with some probability $p$, potentially introducing multiple bursts simultaneously. All results are verified using Monte-Carlo simulations.


I. INTRODUCTION AND MOTIVATION
Low-density parity-check (LDPC) codes, first introduced by Gallager in 1962 [3], are graph-based codes that have found widespread use due to their excellent performance under iterative belief-propagation (BP) decoding.
However, BP decoding is suboptimal and does not reach the performance of optimal maximum-a-posteriori (MAP) decoding [4]. Yet, it is commonly employed in practice due to its significant computational advantage over MAP decoding. The BP decoding threshold of LDPC codes can be improved towards values close to the capacity of the channel by the use of irregular LDPC codes [5]. However, capacity-approaching irregular LDPC codes usually require a large fraction of degree-2 variable nodes, which leads to undesirable finite-length properties like small minimum distance and a large amount of stopping or trapping sets that impair the BP decoding performance.
An attractive possibility to overcome this deficiency is the use of terminated spatially-coupled (SC) LDPC codes-originally introduced as convolutional LDPC ensembles by Felström and Zigangirov in [6]-which show significantly better BP thresholds than LDPC codes without requiring large fractions of degree-2 variable nodes.
It was numerically observed and conjectured [7] that the BP threshold of terminated SC-LDPC codes saturates to the MAP threshold of the underlying LDPC code ensemble. This phenomenonm, termed as threshold saturation, was subsequently rigorously proven in [8] and it was shown that this method allows us to asymptotically achieve capacity on the binary erasure channel (BEC) under low-complexity BP decoding with regular SC-LDPC ensembles.
Threshold saturation was later shown to be universally true for any binary memoryless symmetric (BMS) channel [9], and the result has triggered a lot of research interest for SC-LDPC codes and their practical applications. While the asymptotic behavior of SC-LDPC codes is now well understood for a few years, recently the finite length performance of various constructions of SC-LDPC codes has been studied [10]- [12] and scaling laws to predict the finite length behavior have been proposed.
In this paper, we investigate the asymptotic as well as the finite-length behavior of regular SC-LDPC codes when a single burst or a sporadic random bursts of erasures occur on the channel. Burst erasures can model some common practical communication scenarios such as, e.g., deep fades in wireless communications, the failure of nodes in distributed storage systems and content delivery networks (CDNs), collisions in code slotted ALOHA [13], or the loss of packets in packet-based communication systems, to name just a few. One particularly interesting case is the erasure of a complete spatial position (SP), which can happen for instance when a node fails in distributed noisy storage, where every node is mapped to an SP. In such scenarios, many of the common practically relevant protograph-based constructions of SC-LDPC codes fail by construction. For example, if a complete SP is erased in the protograph construction of [8, Fig. 3], all check nodes that have connections to this SP have at least two erased connections and hence, the erased variable nodes of that SP are not recoverable. This situation has been studied in [14], where the authors additionally provide protograph constructions that avoid this situation and also maximize the correctable burst length given some structural constraints of the code. To correct bursts encompassing an SP, the authors in [15] apply interleaving (therein denoted band splitting) to a protograph-based SC-LDPC code. Interleaving however increases system latency and if windowed decoding is used, this approach results in an increased required window length and thus complexity.
The paper is organized as follows: In Section II, we review the essential technical background, motivate our problem and define the channel models. In Section III, we introduce the novel finite-length analysis of the random ensemble for the case when a complete SP is erased. Then, in Section IV, we detail the effects of expurgating the ensemble on this channel. In section V, we extend the finite-length analysis to some other channel models including: a single burst of erasures of arbitrary length and starting position inside the codeword, the transmission of the bits over a binary erasure channel (BEC) before a burst erasure occurs, and finally the block erasure channel which erases each spatial position independently with some probability. Finally, in Section VI we conclude the paper highlighting directions for future research.

A. Notation
We use N to denote the set of positive integers and [n] to denote the set [n] = {1, 2, . . . , n}. In a graph, we denote the neighborhood of a vertex v i by N (v i ), i.e., N (v i ) is the set of all nodes such that there exists an edge between v i and the node. We say that, for n ∈ N, a function f (n) is O(g(n)) if there exists an n 0 ∈ N and a positive constant γ such that |f (n)| ≤ γ|g(n)| for all integers n > n 0 . For two real values a and b, we say a b if a ≤ b and b a ≈ 1, i.e. b is a good approximation of a. Similarly, we define the sign . The symmetric binary erasure channel with parameter is denoted by BEC( ) and its transition probabilities are defined, for x ∈ {0, 1} and y ∈ {0, 1, ?}, where ? denotes an erasure, by .

B. The Random Regular SC-LDPC Ensemble
We now briefly review how to sample a code from the random regular SC-LDPC ensemble [8], denoted as C R (d v , d c , w, L, M ). We first lay out a set of positions indexed from z = 1 to L on a spatial dimension. At each spatial position (SP) z, there are M variable nodes (VNs) and M dv dc check nodes (CNs), where M dv dc ∈ N and, d v and d c denote the variable and check node degrees, respectively. Let w > 1 denote the coupling (smoothing) parameter. Then, we additionally consider w − 1 sets of M dv dc CNs in SPs L + 1, . . . , L + w − 1. Every CN is equipped with d c sockets and imposes an even parity constraint on its d c neighboring VNs. Each VN in SP z is connected to d v CNs from SPs z, . . . , z + w − 1 as follows: each of the d v edges of this VN is allowed to randomly and uniformly connect to any of the wM d v free sockets arising from the CNs in SPs z, . . . , z + w − 1, such that parallel edges are avoided in the resultant bipartite graph. When a VN has multiple edges connected between itself and a particular CN, those edges are called parallel edges. We avoid parallel edges as it is well known that for finite M , the presence of parallel edges can have detrimental effects on the decoding performance [4]. This graph represents the code so that we have N = LM code bits, distributed over L SPs. Note that the CNs at the boundaries, i.e., at SPs 1, . . . , w − 1 and L + 1, . . . , L + w − 1, can have degree less than d c , due to termination of the code.
CNs of degree zero are removed from the code. Because of the additional CNs in SPs z > L, the code rate is . Throughout this work, we assume the two mild conditions of d v ≥ 3 and wM ≥ 2(d v + 1)d c (see Appendix A).
A subset A of VNs in a code is a stopping set if all the neighboring CNs of (the VNs in) A connect to A at least twice [4,Def. 3.137]. In such a case, if all VNs in A have been erased by the channel, then the BP decoder will fail since all the neighboring CNs are connected to at least two erased VNs. Therefore, such a set will stop the decoding process and hence is called a stopping set. The cardinality of the set A is also its size. A minimal stopping set is one which does not contain a smaller size non-empty stopping set within itself.
The Poisson SC-LDPC Ensemble (C P ) For the sake of comparison, we also consider another ensemble. We still assume a regular variable node degree d v , but there is no limit placed on the check degree. For each VN at spatial position z, we assume that its edges can connect to any check node at spatial positions z, . . . , z + w − 1 such that parallel edges are avoided (and without constraining the check node degree). Check nodes are selected uniformly at random for each edge. This construction yields the so-called Poisson ensemble C P (d v , d c , w, L, M ), where d c specifies the average check node degree of this ensemble. By the described construction procedure, we do not have a regular check node degree but instead an irregular distribution that follows a binomial distribution (which converges to a Poisson distribution for M → ∞). By fixing the number of CNs per SP to M dv dc , we indeed get an average check node degree of d c .

C. Motivation
Consider the random regular SC-LDPC ensemble C R (d v , d c , w, L, M ) affected by a single burst of b bits. Let S ∈ [M ] denote the random starting VN of the burst at some SP z 0 . Note that z 0 is arbitrary 1 . We define the normalized quantities s S M and β b M , so that 0 ≤ s ≤ 1 and 0 ≤ β ≤ L. Using density evolution in the limit of M , we showed numerically in [2] that for any fixed s, there is a maximum normalized β(s) recoverable with an arbitrarily small probability of decoding failure. Then, a burst of length βM and random starting position is recoverable in the limit of M if β < β max = min 0≤s<1 β(s). Interestingly, we observed that when β max > 1, s = 0 (the full erasure of the position z 0 ) is the worst case scenario as β(0) is a minimum of β(s). We will also see later in Example 16 that the error floor is also larger when s = 0.
The observations of Fig. 1 motivates our first focus on a very simple channel model, where the starting position of a burst is S = 1 and the burst length is exactly b = M . Later, we will extend our results to arbitrary values of S and b and then, to the case of occurring more than a single-burst. We refer the interested reader to [2] for the details of density evolution and focus in this paper on the error floor due to the occurrence of a random burst of length b < β max M when M is finite. The fourth and final channel model is the Block Erasure Channel, denoted by BLEC(p), which completely erases each SP independently with probability p. This channel model includes the case of multiple independent bursts, which can occur in some practical scenarios like distributed storage. We show how the basic single-burst models can be used as building structures to closely estimate the decoding failure probability in the BLEC(p). A similar approach may be applicable for other more complex channel models.
The simple single-burst channel model has for instance been used in [14] to study the recoverability of single bursts in protograph-based SC-LDPC codes. While multiple other models exist for a correlated erasure channel, like the Gilbert-Elliott model [14], the above models can also describe some realistic scenarios: for instance, the BLEC can model simultaneous multiple node failures in a distributed storage scenario with nodes associated to SPs. Or, the SPBC can be used to model a slotted-ALOHA multiple access scheme where each user transmits an SC-LDPC codeword over L time slots, but one SP might be erased in the case of a single collision event. Moreover, long burst erasures might occur in block fading scenarios, in optical communications which are subject to polarization dependent loss.

III. ERROR ANALYSIS ON THE SPBC
As highlighted above, we empirically observed in [2] that the worst burst scenario is when the starting position of the burst is the first bit of a spatial position in the codeword. Hence, we first analyze the performance of SC-LDPC code ensembles on the SPBC in this section and later generalize to the RBC. We give lower bounds on the block erasure rate after decoding and also provide a comparison with the Poisson ensemble.
First, we start by giving a necessary condition for being able to correct a burst. x ( ) where i denotes the erasure probability at SP i. For the SPBC, we have z = 1 and ∼z = 0, where the subscript ∼ z denotes all SPs i ∈ [L]\{z}. We can immediately see that x ( ) ∼z = 0 and then we can simplify the DE equation as After a change of variablex is the BP threshold of the underlying regular uncoupled ensemble [4]. Rearranging this condition completes the proof. Proof. By using the fact that BP (d v , d c ) ≤ 1 − R ≤ dv dc , the relaxed condition is immediately obtained from Proposition 1.
Remark 3. Note that this result is not only valid for a single burst, but in general for any combination of erased SPs out of the L total SPs, provided that they are at least w apart, i.e., there are at least w − 1 non-erased SPs between two erased SPs. Remark 4. The analysis based on density evolution, e.g., Proposition 1, estimates the "bit error probability" in the limit of M while our main concern is "block error probability" when there is a burst of erasures. It has been proven for LDPC ensembles with d v ≥ 3 that a vanishing bit error probability guarantees a vanishing block error probability over the BEC [4,Lemma 3.166]. Although it might not be true in general, our simulations suggest the same behaviour for SC-LDPC codes when d v ≥ 3 and the channel is affected by a burst of erasures.
A. The Random Regular SC-LDPC Ensemble (C R ) Let P SPBC B denote the average block erasure (decoding failure) probability of the random C R (d v , d c , w, L, M ) ensemble on the SPBC under BP decoding, i.e., the probability that the iterative decoder fails to recover the codeword. For large enough M , size-2 stopping sets (each of which also forms a weight-2 codeword) are the dominant structures in the graph that cause the BP decoder to fail [10]. Hence, the number of size-2 stopping sets per SP, denoted N SP 2 , is a good starting point for analyzing the performance of the ensemble on the SPBC. We introduce the stopping set indicator function U ij with that two variable nodes from a same SP z of this code form a stopping set amounts to (1) Proof. Let v i and v j be two VNs randomly chosen from an SP z of the C R (d v , d v , w, L, M ) ensemble, i.e., i, j ∈ {(z − 1)M + 1, . . . , zM } for z ∈ [L]. Recall that this ensemble contains no parallel edges. We use a combinatorial argument to compute the probability P R that these two VNs form a size-2 stopping set. We label all the sockets of CNs. Let T denote the total number of possible sub-graphs from {v i , v j } and let T ss denote the number of possible sub-graphs in which these VNs form a size-2 stopping set. First, we connect the d v edges of v i to randomly chosen empty sockets of d v distinct CNs as described in Section II-B. A stopping set (and in this case, also a low-weight codeword) is formed if and only if the edges of v j are connected to the same CNs, i.e., N (v i ). Each of these CNs has d c − 1 free distinct sockets. Thus, where d v ! is due to the permutation of edges and (d c − 1) dv is due to the different ways of connecting to free sockets of N (v i ). The counting argument is illustrated by an example in Fig. 2 We get P R P {U ij = 1} = Tss T , simplified further to (1).

Remark 6.
For large enough M , the quantity T in the proof of Lemma 5 can be well approximated by the dominating summand ( = 0) which leads to the following approximations (2) If all variable nodes of a randomly chosen SP are erased, the (average) probability of BP decoding failure is lower-bounded by where P R is the probability that two variable nodes from an SP of the code form a stopping set, given by (1).

Proof. See Appendix A.
Remark 8. Since a size-2 stopping set characterizes a low-weight codeword, Theorem 7 yields a lower-bound on the average block erasure probability of MAP decoding, too. Theorem 7 also implies that for large enough M , Note that following standard arguments [10], [4, Appendix C], for large M , we can also approximate the bound on P SPBC B by modeling N SP 2 as a Poisson distribution with mean λ SP , i.e., We observe that the average block erasure probability scales as O(M 2−dv ).

B. Simulation Examples
To illustrate the accuracy of our bounds, we carried out Monte-Carlo simulations where we randomly erased  that the Poisson ensemble always has a larger probability of size-2 stopping sets than the corresponding random ensemble. Since the ensemble C P is hence shown to be suboptimal compared to C R , we do not consider this ensemble in further discussions. We discussed the simple non-expurgated ensembles here mainly to illustrate the proof technique based on the second moment method and to show that simple lower bounds on the performance exist. The removal of short cycles in the graph, as it is frequently done in practical code constructions, is considered in the next section.

A. Minimal Stopping Set Size
As the performance of SC-LDPC codes over (burst and random) erasure channels is mainly dominated by size-2 stopping sets, it is well known that we can improve the burst erasure correction capability by expurgating the ensemble and thereby removing all small stopping sets. Observing that a size-2 stopping set, as shown in Fig. 2, is built around 4-cycles, we can reduce the size of the minimal stopping sets by removing small cycles from the graph. For example, increasing the girth of the graph to 6 leads to minimal stopping sets of size s min = d v + 1 [24].
In this section, we first show that all size (d v + 1) stopping sets in an LDPC code share a common structure which we will use to find the probability of these stopping sets. Consider a (3, 6) random LDPC code ensemble as an example. We immediately notice that size-3 stopping sets vanish for girth-6 graphs. A size-4 stopping set is shown in Fig. 5 along with its (transposed) bi-adjacency matrix that describes the neighbors of each VN in the corresponding row. We can notice a pattern in this matrix which has been highlighted using dashed lines in the matrix: row i ∈ {1, 2, . . . , d v } has one subset of (d v − (i − 1)) columns with all 1s and an identity matrix I dv−i+1 spanning these columns starting from row i + 1. In the following lemma, we characterize this pattern and relate it to smallest size stopping sets (SSs) in graphs of girth 6.
Lemma 9. In a regular bipartite graph of girth 6 (i.e., without parallel edges), the smallest stopping set is of size neighboring CNs and is characterized by a bi-adjacency matrix that contains as rows all dv+1 Proof. From [24], we know that the smallest stopping set is of size d v + 1. Furthermore the stopping set connects

B. Estimation of Block Error Rate
We can use the same approach as in Lemma 5 to calculate the probability of occurrence of the minimum size stopping sets, characterized by Lemma 9, within a spatial position of a code sampled uniformly from the ensemble.
Lemma 10. For a code sampled uniformly from the expurgated C R (d v , d c , w, L, M ) SC-LDPC ensemble, constructed without allowing cycles of length 4, the probability P R,6 that d v + 1 variable nodes of the same spatial position z form a stopping set is bounded by with )! being constants depending only on the ensemble parameters d v and d c .
randomly chosen VNs from an SP z of a code sampled from the expurgated, Recall that this code contains neither parallel edges nor cycles of length 4. Let T denote the total number of possible sub-graphs from {v i1 , . . . , v i dv +1 } and let T ss denote the number of sub-graphs in which these VNs form a stopping set.
We first compute T ss . Consider the bi-adjacency matrix of a stopping set of size d v + 1 described in Lemma 9. and label the rows and column as shown in Fig. 5. Any column-wise permutation of this matrix represents the biadjacency matrix of another stopping set with the same VNs, and vice versa. Thus, the number of such sub-graphs is equal to the number of distinct "labeled" permutations times the permutation of sockets of each CNs. In other words, where the first term is the number of possibilities to select 1 2 )! counts the number of column-wise permutations of the bi-adjacency matrix. The last term is the number of ways that the edges are connected to two distinct sockets of each CN.
Unfortunately, obtaining an exact expression for T is tedious and does not lead to many new insights. We therefore give upper and lower bounds for T which become tight for large M .
First, T , the total number of sub-graphs from the d v + 1 VNs such that 4-cycles and parallel edges are avoided is upper-bounded by the total number of sub-graphs including 4-cycles. Hence, for every VN, we (randomly) select d v CNs out of wM dv dc CNs. Now, assume that each edge of the VN is paired to one of the chosen d v CNs. For every selected CN, there are at most d c possibilities to select a free socket to place the paired edge from the VN.
Hence, we get the bound We now proceed to the lower bound. Given a set of (d v + 1) randomly chosen VNs v i1 , . . . , v i dv +1 from a spatial position, the VN v i1 has to connect its d v edges to CN sockets without introducing parallel edges or 4-cycles.
which we can further bound as We can also simplify (9) using the fact that which leads to Finally, simplification of P R,6 = Tss T with the bounds (8), (10), and (11) leads to the result. Note that in the counting argument we skipped all (d v + 1)!(d v !) dv+1 permutations of VNs and their sockets as they are included in both T ss and T and henceforth cancel in the final expression.
Remark 11. For a code sampled uniformly from the expurgated C R (d v , d c , w, L, M ) ensemble with girth 6, we can approximate T quite well by (11), which is the dominant term in the expression of T for large enough M and get the approximation We performed Monte Carlo simulations for the expurgated C R (3, 6, 3, L, M ) ensemble and counted 100 decoding failures on the SPBC. Figure 6 illustrates the simulation averages for the block error probability, for varying M , their respective lower and upper bounds (using the bounds of P R,6 from Lemma 10), and the approximation using (12).
It is evident that both the bounds and the approximation become tight very quickly, which reassures that the decoder performance is indeed dominated by minimal stopping sets.
Corollary 12. The expected number of such stopping sets within a SP of the code is λ SP M dv+1 P R,6 . Using similar arguments as in Section III, we have A tight approximation for the average block erasure probability on the SPBC, P SPBC B,6 , is then obtained as We can see from the bounds (6) and (7)   • On the SPBC, block erasure rates less than 10 −15 can be obtained by codes from an expurgated C R (5, 10, 5, L, M ) ensemble, with M as low as 120. This encourages the use of short SC-LDPC codes in applications where single SPs may be erased (e.g., distributed storage of short files) and high reliability is required.

V. ERROR ANALYSIS ON MORE GENERAL BURST CHANNEL MODELS
In this section, we study some other transmission scenarios with less restrictions on the channel model. First, we consider the random burst channel (RBC) model in which the burst has a variable length and not necessarily erases complete SPs. Then, we consider the scenario where there is random background noise in addition to the burst erasure. For simplicity, we assume a binary erasure channel for the background noise and the SPBC model for the burst. We present an extension of the analysis in previous sections to estimate the decoding failure probability in these scenarios. Finally, we consider the scenario of the block erasure channel (BLEC) in which each SP may be erased randomly with some probability. We show how such a channel model can be analyzed using the simple single-burst channel models, e.g. SPBC and RBC.
Although the expurgated ensembles are of more interest, we present the error analysis for the C R (d v , d c , w, L, M ) SC-LDPC ensemble with size-2 stopping sets because of two reasons. First, expurgation leads to very small decoding failure probabilities and it will be more challenging to illustrate the tightness of the error estimations in simulation.
Second, a similar analysis can be conducted for the expurgated ensemble as we have shown for the SPBC in Section IV, but it will be more involved and less insightful.

A. Random Burst Channel (RBC)
We have seen in the previous section that the performance of SC-LDPC ensembles is asymptotically well characterized by stopping sets of size 2. We will now generalize this analysis to the case where there is a single burst of length > M and with a random starting location within the codeword. Such a burst can span over multiple SPs because of its random starting position. In this case, stopping sets formed across coupled SPs will also contribute to decoding failures. We will restrict ourselves to the case of a single burst. This case can then serve as a building block for the more complex case of having multiple random bursts. For instance, the results can be easily generalized to the case with multiple bursts spaced apart by at least w non-affected SPs. We start by first giving a simple asymptotic condition on w for burst erasure recovery. Although it is an asymptotically sufficient condition, we have observed in numerical experiments that it reflects the actual behavior quite well.
where ε z+i is the fraction of VNs erased in SPs z + i. We have (a) as x The substitution y In the remainder of this section, we assume that asymptotic recovery is possible and we are concerned with decoding failures that occur when M is finite. Let S ∈ [M ] denote the random starting VN of the burst at some SP z 0 . We define the normalized quantities s = S M and β = b M . Recall from Section II-C that β max is the largest β asymptotically recoverable. In the case of the RBC, besides stopping sets within a single spatial position, size-2 stopping sets formed across coupled SPs will also cause decoding failures. We first characterize the probability of such stopping sets in the following lemma.
Let v i denote a randomly chosen VN in spatial position z ≤ L, and v j denote a random VN in spatial position z + k, for a non-negative integer k with z + k ≤ L. The probability that these two random VNs form a stopping set of size 2 is independent of z and amounts to where P R is given by (1). For k ≥ w, q k = 0.
Proof. From the definition of the ensemble, we know that N (v i ) is part of SPs {z, z + 1, . . . , z + w − 1} and N (v j ) is part of SPs {z + k, z + k + 1, . . . , z + k + w − 1}. A size-2 stopping set is formed if and only if N (v i ) = N (v j ).
For k ≥ w, this condition cannot be fulfilled and thus, q k = 0. For k < w, all check nodes of N (v i ) must be from a subset {z + k, . . . , z + w − 1}. As the edges of the variable nodes uniformly connect to w neighboring SPs, the probability of such a selection for v i is ( w−k w ) dv . Now, the probability that v j connects exactly to the same CNs as v i , i.e., N (v i ) = N (v j ), is equal to P R (by the same argument as in Lemma 5). Hence, q k = w−k w dv P R . We immediately see that q 0 > q 1 > · · · > q w−1 .
The average number of size-2 stopping sets between VNs lying in SPs z and z + k, where k ∈ [w − 1], is given by Again, we see that Our error estimation is again based on the average number of size-2 stopping sets formed among erased VNs. Let N 2 (S, z 0 , b) denote the number of size-2 stopping sets formed by VNs erased by the burst. BP decoding fails if There are two approaches to justify (i). The first approach is to use arguments similar to Theorem 7 to lower-bound in terms of the average number of size-2 stopping sets and a much smaller correction term.
However, the derivation will be more involved than Theorem 7 and will not lead to new insights, which is why  (16). Then the expected number of size-2 stopping sets formed by VNs erased by the burst is given by Proof. To find an expression for E[N 2 (S, z 0 , b)], we first note that the starting position M (z 0 − 1) + S of the burst is chosen uniformly among the bits in [LM − b + 1]. Then, where ( us justify (iii) using Lemma 14: for a given starting bit 1 ≤ S ≤ M , mz 2 q 0 is the average number of size-2 stopping sets formed between erased VNs in SP z and m z m z+k q k is the average number of size-2 stopping sets formed between erased VNs in all pairs of SP z and z + k, k ∈ [w − 1]. We have (iii) by summing the average number of size-2 stopping sets formed between erased VNs in all pairs of SP z and z + k.
We verify Theorem 15 (and in particular (18)) for some specific choices of b in the following examples.
. This is a generalized version of the SPBC where the starting bit of the burst is not constrained to occur at the exact boundary of the SP. In this case, the nonzero terms of (18) are m1 2 q 0 , m2 2 q 0 and m 1 m 2 q 1 . Then (17) has the following closed form implies that the size-2 stopping sets are the main cause of decoding error. We also observe that the decoding error increases very fast for b/M close to β max . As M increases, the waterfall region becomes sharper around β max .

B. Single Burst Erasure in a BEC (SPBC+BEC)
In a more general scenario, we can consider a communication channel degraded by both memoryless noise and burst erasures. We showed in [2] that SC-LDPC codes are asymptotically immune to a certain maximum burst length, which heavily depends on the distortion amount of the additional memoryless noise. Moreover, we observed that the behavior of these codes is very close on the BEC and the binary-input additive white Gaussian noise channel (BiAWGNC). Here, for simplicity, we characterize the error floor when the channel is a BEC. However, it is to be noted that the error floor on both these channels may not be the same.
Consider a BEC with (random) erasure probability ε that, in addition, also introduces a single burst of erasures.
We assume that the burst erases a complete spatial position, i.e., a scenario similar to the SPBC. For instance, this setup can model a noisy distributed storage system with a single node failure and a noisy channel between storage  The events of forming a stopping set and being erased are independent and thus the probability of having such an erased stopping set amounts to ε 2 q k , where q k is given by (14). Summing over all pairs of VNs (taking into account boundary effects), yields where λ k is the average number of size-2 stopping sets given by (15).
(ii) SPBC and BEC at SP z 0 : The VNs of SP z 0 are all erased. We already counted the contribution of a fraction of these VNs in E (i) by assuming that the BEC erased the bits in SP z 0 equally likely. In particular, a pair of VNs in SP z 0 erased by the BEC will not be considered here. Using (14), the probability that a pair of VNs (in SP z 0 ) is not both erased by BEC, and forms a stopping set is (1 − ε 2 )q 0 . Summing over all M 2 distinct pairs gives (iii) BEC and SPBC between SPs: A VN in SP z 0 , erased by the SPBC and not by the BEC, can also form a stopping set with VNs erased by the BEC in SP z 0 ± k, 1 ≤ k < w. The probability of such a stopping set is ε(1 − ε)q k , and summing over all possible pairs gives Summing all disjoint contributions leads to and thus, In case there is no contribution from the additional BEC ( i.e. ε = 0), E[N 2 (0)] = E[N SP 2 ] and the channel reduces to the SPBC model (E (ii) ). From Sec. III, we know that P B ≈ E[N 2 (0)] for large enough M . The same approximation is also valid if ε ε BP , the BP threshold of the C R (d v , d c , w, L, M ) ensemble [8]. The reason is that size-2 stopping sets become the dominant stopping sets when ε ε BP and M is large (see also [10]).
Moreover, N 2 (ε) converges to a Poisson distribution for large M .
Note that E (i) = O(ε 2 L) and it can become the dominant term when L is large. To see all the contributions, we compute the decoding failure of C R (3, 6, 3, L = 10, M ) ensemble over a combined SPBC and BEC. Two different erasure probabilities are considered: = 0.1 and = 0.2. Fig. 11 illustrates the results of both simulations. We plot the empirical block erasure probabilities as well as its approximation from (19) in terms of M . The simulation results are averaged over 1000 decoder failures. The results suggest that the approximation becomes tight beyond M 150.
If we neglect the contributions of the SPBC (considering only E (i) ), we find an approximation for the error floor of the ensemble over a BEC. For ε ε BP , Similar approximations are shown in [10] for the error floor of particular protograph-based SC-LDPC ensembles over the BEC. Fig. 12 shows the error floor of C R (3, 6 (20). We see that the approximation becomes tight for small ε when, indeed, size-2 stopping sets dominate the performance.

C. Block Erasure Channel (BLEC)
Now we consider a more practical scenario where multiple bursts may simultaneously affect the transmission.
The channel erases (all the VNs lying in) each SP independently with some probability p. We call this model block Assume that L w. Define a segment as the sequence of consecutive SPs such that the last w − 1 SPs are non-erased and those are the only w − 1 consecutive non-erased SPs in the segment. The expected number of spatial positions in a segment is given by The proof is outlined in Appendix C.
denotes the decoding failure probability of segment i, the average probability of decoding failure is where the expectation is taken over different channel realizations and the code ensemble. To simplify the above expression, we apply the tower rule of expectation to get where ( (iii) Finally, we need to estimate P B,seg = E P (1) e , the block error probability of a segment, which can be written as where Q k is the probability of k erased SPs in a segment and P k is the average probability of segment block error given that k SPs (in arbitrary locations) have been erased. While Q k depends mainly on w and the parameter p of the channel, P k is determined by the code ensemble. There exists a k 0 ≥ 1 such that P k tends to zero for large M if k < k 0 , and for k ≥ k 0 , P k is bounded away from zero even asymptotically.
For the sake of clarity, we consider the specific ensemble of C R (3, 6, w = 4, L, M ). The DE analysis of a single-burst channel, shown in Fig. 1, yields β(0) = β max = 2.14 implying that BP decoding is not successful if more than 3 consecutive SPs are erased in the ensemble and thus, P k > 0 for k ≥ 3. However, the BP decoding can be successful for k < 3. In this case, we estimate P k using our single-burst models as where the last equality is the result of Lemma 24 in Appendix C. As a result, Let us now summarize the above analysis. The error events are divided into two subsets: the first subset, named here "finite-length error", includes the error events with vanishing probability in the limit of M . The quantities Q 1 P 1 and Q 2 P 2 are its dominant terms. The second subset, named here "DE error", are the error events that cause the BP decoder to fail always for any value of M . Combining steps (i), (ii), and (iii), we have, where P SPBC B and P RBC B (2M ) are given in (3) and (17), respectively.
We performed Monte Carlo simulations over the BLEC to verify the tightness of the above estimation for the C R (3, 6, 4, 30, M ) ensemble. The simulation results are obtained by counting 100 decoding failures. Fig. 13 illustrates the tightness of approximation (23) in terms of M for two different values of p = 0.01 and p = 0.03.
We observe that the approximation fairly matches the simulations. Note that the approximation requires the RBC estimation for a burst of length 2M . For this purpose, we used the available simulated values in Fig. 9 (β = 2).
Another option would be to use the error-floor expression (17) but it would give a worse approximation for small values of M ≈ 100 as there is large gap between the simulated values and (17) (see Fig. 9).
We also plot the average block error probability in terms of the channel's parameter p in Fig. 14. We see again that the approximations track the actual performance closely for p even as large as 0.1 and for M as small as 100.
The above analysis indicates that the error analysis of a more complex erasure channel model, such as the BLEC(p), is feasible by breaking down the channel model into combinations of single-burst channel models.

VI. CONCLUSIONS
In this paper, we have analyzed random regular SC-LDPC ensembles on burst-erasure channels. Using density evolution, we have shown the asymptotically correctable maximum burst erasure length. However, for finite-length codes, some burst erasures shorter than this length may not be recoverable. The reason is that due to finite-length effects of certain graph structures, known from conventional LDPC decoding, the decoding could stop prematurely.
Based on these structures, we have derived tight lower bounds or approximations on the block erasure probability of SC-LDPC code ensembles when the burst has one of the following characteristics: • it erases a single random spatial position completely, or • it erases a random spatial position completely in addition to a memoryless background noise (e.g. BEC), or • it has a fixed length but starts at a random bit and erases a sequence of spatial positions, or • it erases each spatial position independently with some probability p.
Moreover, we have shown that expurgating the codes can considerably improve the block erasure rates and guarantee virtually error-free performance (e.g. P SPBC B ≈ 10 −15 ) for very short block lengths (e.g. M ≈ 120).
Directions for future research include the construction of new, possibly more structured burst-resilient ensembles based on this analysis and a more detailed analysis of the block erasure channel.

ACKNOWLEDGMENT
We would like to thank the reviewers and the associate editor for their valuable comments and for helping us in improving the quality of presentation. Specifically, we extend our sincere thanks to one of the reviewers for encouraging us to consider an analysis on the block erasure channel.
Proof. We have to distinguish two cases. In the first case, variable nodes v i and v j , j = i form a stopping set of size two and variable nodes v k and v l , l = k = i form another stopping set, where w.l.o.g., we assume k = j, i.e., the two stopping sets share a variable node. In this case, we have where P {U jl = 1|U ij = 1} can be computed using similar arguments as in the proof of Lemma 5, except that some sockets have already been occupied by the edges emerging from the VNs v i and v j and for forming an SS, node v l can choose among d v (d c − 2) sockets. We have .
We upper bound P {U jl = 1|U ij = 1} by considering only the dominant term ( = 0) in the denominator where in (a) we marginalize over the number b of check nodes shared between both size-2 stopping sets {v i , v j } and {v k , v l }, b ≤ d v . Let T ss,b denote the number of favorable sub-graphs from these VNs provided that b check nodes between both stopping sets are shared and letT denote the number of all sub-graphs from these VNs provided where (a) is the application of the second moment method [4, Lemma C.8]. Furthermore, where (a) is due to the fact that 1 1+τ ≥ 1 − τ for τ > −1.

APPENDIX B THE POISSON ENSEMBLE
Lemma 20. Consider a code sampled uniformly from the Poisson ensemble C P (d v , d c , w, L, M ). The probability that two variable nodes from a spatial position form a stopping set amounts to Proof. Let v i and v j be two VNs randomly chosen from an SP z of the C P (d v , d v , w, L, M ) ensemble, i.e., i, j ∈ {(z − 1)M + 1, . . . , zM } for z ∈ [L]. The computation of P P E[U ij ] for this ensemble is much simpler as we do not need to distinguish sockets. Assume that the edges of v j are assigned to CNs sequentially after edges of v i have been assigned to CNs. The first edge can connect to any of the (wM dv dc ) CNs from SPs z, z + 1, . . . , z + w − 1. As we avoid parallel edges in the construction, the second edge has one CN less to choose from, the third edge has two CNs less to choose from and so on. But, there is exactly one way in which the edges can connect exactly to the same CNs as v i , with d v ! possible permutations of the edge arrangements. Hence the probability of v j forming a stopping set with v i is which leads to the statement after simplification.
Theorem 21. Consider the ensembles C R (d v , d c , w, L, M ) and C P (d v , d c , w, L, M ). For two VNs from the same spatial position, the probability that they form a stopping set is larger for the Poisson ensemble, i.e., P P ≥ P R .
Proof. We upper bound (1) as where (a) is due to Vandermonde's identity.
Proof. We follow lines of the proof of Lemma 19. Again, we distinguish two cases. In the first case, variables v i and v j , j = i, form a stopping set of size two and variable nodes v k and v l form another stopping stop, where w.l.o.g., we assume k = j, i.e., the two stopping sets share a variable node. In this case, we have is the number of ways to connect v l to N (v k ), i.e., U kl = 1. We have where d v ! is due to the permutation of labeled edges, and the rest of the expression counts the different ways of choosing CNs. This yields The total number of possibilitiesT can be lower bounded by its subset which is |N (v i ) ∪ N (v k )| = |N (v i ) ∪ N (v l )| = 2d v (no common CNs with v i and v j ), with Using Vandermonde's identity, we have, dv b=0 P Pcorr,b ≤ 1 The statement of the lemma follows by combining both cases.
Theorem 23. Consider a code sampled uniformly from the C P (d v , d c , w, L, M ) ensemble with wM ≥ d 2 c . If a randomly chosen spatial position of this code is completely erased, the (average) probability of BP decoding failure is lower-bounded by where P P is the probability that two variable nodes from a spatial position of the code form a stopping set, given by (25).
Proof. We follow a similar argument as in the proof of Theorem 7. We get with Lemma 22 and by computing E[N SP 2 ] as M 2 P P using Lemma 20.

Proof of Lemma 18:
We use the method of generating functions to compute this quantity. Specifically, we construct a function G(x) where the exponent of x in each term signifies the number of SPs involved in a segment with one erased SP. For convenience, we exclude the final sequence of w − 1 unerased SPs in G(x). So finally we will have to multiply G(x) by (1 − p) w−1 x w−1 to account for these. Let E denote an erased SP and N denote a non-erased SP. Then, starting from the first SP in a segment, we have the following possible outcomes with their respective probabilities and generating function terms: Note that G(x) < 1 ∀ x ≤ 1 and G(1) = 1 − (1 − p) w−1 . Also for k ≥ 0, G(x) k generates all the possible sequences with k SPs erased and where the separation between two consecutive erased SPs is strictly less than w − 1. Hence every possible sequence ending with w − 1 N s can be enumerated as .
Note that F (1) = 1 which implies that we have counted all the possible sequences. Also, implicitly we have set L → ∞ for convenience. In fact, we can rewrite F (x) as where p n is the probability of all sequences of length n. Then we can compute the required quantity as The middle terms guarantee to have 3 consecutive erased SPs. The k 1 and k 2 enumerate all possible erasure sequences that can happen before and after the consecutive erased SPs. Note that we must exclude the event of "E" (only single erased SP) in the k 2 sequences (or, alternatively, in the k 1 sequences) to generate all possible combinations once. As a result,