Zipper Codes

Zipper codes are a framework for describing spatially-coupled product-like codes. Many well-known codes, such as staircase codes and braided block codes, are subsumed into this framework. New types of codes such as tiled diagonal and delayed diagonal zipper codes are introduced along with their software simulation results. Stall patterns that can arise in iterative decoding are analyzed, giving a means of error floor estimation.

This paper provides a general overview of zipper codes, organized as follows. The structure and main ingredients of a zipper code are discussed in Sec. II. Several important code families that can be described as zipper codes are given in Sec. III. Software simulation results for a few example zipper code designs are given in Sec. IV. Finally, "stall patterns," a type of error event for zipper codes, are discussed and analyzed in Sec. V.
Throughout this paper, we will assume that all codes are defined over the binary field F 2 = {0, 1}; however, analogous formulations can be made for the non-binary case. For any positive integer q, we let [q] = {0, 1, . . . , q − 1}. The cardinality (number of elements) of a finite set A is denoted as |A|.

A. Constituent Codes, Buffer, Zipping Pair
Let C 0 , C 1 , . . . be any sequence of binary linear constituent codes indexed by i ∈ N, where the ith code has length n i and dimension k i . Denote any (fixed) information set of C i as I i ⊆ [n i ]; necessarily |I i | = k i . Codeword symbols in positions indexed by I i are called information symbols of C i , while codeword symbols in the complementary positions (indexed by [n i ]\I i ) are called parity symbols. In practice, we will usually have C i in systematic form, in which case I i = [k i ] (the first k i positions of a codeword hold information symbols and the last n i − k i positions hold parity symbols).
A buffer associated with a given sequence of constituent codes is any sequence of binary row vectors c = c 0 , c 1 , . . . such that c i ∈ F ni 2 for each i ∈ N. Thus, a buffer is a sequence of rows, with the ith row having n i positions, possibly (but not necessarily) forming a codeword of C i . For any i ∈ N and any j ∈ [n i ] the jth symbol of the ith row of c is denoted as c i,j ; this symbol is said to have position (i, j) within buffer c. For purposes of initialization (i.e., to establish suitable boundary conditions), we extend the set of buffer positions to allow for negative row indices by defining c i,j = 0 for all i < 0 and all j ∈ N. Thus if we refer to a buffer symbol with a negative row index, that symbol necessarily has value zero. When i < j we will say that row i is older than row j (or, equivalently, that row j is newer than row i).
As illustrated in Fig. 1, we will partition each row of a buffer c as follows. For each i ∈ N, let A i ⊆ I i be any The filled regions show the location of parity symbols. The two tiles connected by arrows represent the two coordinates prescribed by the interleaver map. In this example, we have φ(13, 2) = (1,12) and c 13,2 = c 1,12 = 1. Each row is a codeword of C. Rows with lower row indices correspond to "older" rows while those with higher indices are regarded as "newer." soon see, only real symbols are transmitted over the channel; each virtual symbol of a constituent codeword is a copy of a real symbol from some other constituent codeword. When C i is in systematic form, we will usually take A i = [m i ] for some m i ≤ k i , thus designating the first m i positions as virtual positions. Let denote the positions of the virtual symbols and the real symbols, respectively. We refer to (A, B) as a zipping pair. The set {c i,j : (i, j) ∈ A} is called the virtual buffer, and the set {c i,j : (i, j) ∈ B} is called the real buffer. The set B * = B ∪ {(i, j) : i ∈ {−1, −2, . . .}, j ∈ N} is an index set for an extended real buffer where negative row indices are permitted. As already noted, symbols located in rows with a negative row index have value zero.

B. Interleaver Map
An interleaver map associated with a zipping pair (A, B) is any function φ : A → B * . For each virtual position (i, j) ∈ A, the interleaver map gives a real position φ(i, j) ∈ B * from which to copy a symbol.
We will often be interested in the row index from which a real symbol is copied. To this end, we define coordinate functions φ 1 and φ 2 such that φ(i, j) = (φ 1 (i, j), φ 2 (i, j)). Thus φ 1 (i, j) returns the row index from which the virtual symbol at position (i, j) is copied. If φ 1 (i, j) < 0, then the copied symbol is necessarily zero.
Equipped with a sequence C 0 , C 1 , . . . of constituent codes, a zipping pair (A, B), and an interleaver map φ, we say that a buffer c = c 0 , c 1 , . . . forms a valid zipper codeword if 1) c i,j = c φ(i,j) for all (i, j) ∈ A, and 2) c i ∈ C i for all i ∈ N. In other words, each virtual symbol of a valid zipper codeword must be a copy of a real symbol as prescribed by the interleaver map φ, and each row of a valid zipper codeword must be a codeword of the corresponding constituent code. Fig. 1 illustrates a zipper codeword in a zipper code specified in terms of a sequence of constituent codes having fixed length n = n i = 14 and fixed dimension k = k i = 11. The constituent codes are assumed to be in systematic form, so that parity symbols fall into the last r = n − k = 3 positions in each row. The first m i positions in each row are the virtual positions, while the last n − m i positions are the real positions. Note that m i is permitted to vary from row to row. As illustrated, the interleaver map φ determines the position at which to look up the value of a virtual symbol.
It is clear that the interleaver map determines the degree of coupling among the various constituent codes. We will usually focus on interleaver maps that are periodic and causal.
To support a ν-periodic interleaver map, we will require that the zipping pair (A, B) is also ν-periodic in the sense that n ν+i = n i , and A ν+i = A i for all i ∈ N. Most often we will then also have C ν+i = C i for all i ∈ N. Definition 2. An interleaver map φ is said to be causal if φ 1 (i, j) ≤ i for all (i, j) ∈ A and strictly causal if the inequality is strict.
In other words, under a causal interleaver map, virtual symbols are never copied from later rows.
Some important classes of zipper codes (such as staircase codes) have the property that each real symbol is copied exactly once into some virtual position, i.e., the inverse image φ −1 (i, j) of every real position (i, j) ∈ B under mapping by φ is a singleton set {(i , j )} for some (i , j ) ∈ A. In this situation we refer to the interleaver map as being bijective.

C. Encoding Zipper Codes
Recall that I i ⊆ [n i ] denotes an information set with |I i | = k i for the constituent code C i of length n i and dimension k i , and that A i ⊆ I i is an index set for the virtual positions of the ith buffer row c i . To encode c i , we assume that all rows c j with j < i have already been encoded. This will be true even for c 0 , since previous rows are then all-zero by assumption. Under the assumption of a causal interleaver map, the encoding of zipper codes is easily accomplished by the following procedure: 1) Fill in the positions indexed by B i ∩ I i with message symbols. 2) Fill in the virtual symbols by duplicating symbols from the positions prescribed by the interleaver map, i.e., for by assumption, c φ(i,j) is a symbol from a row already encoded, or a symbol from the current row which was input in the first step.) 3) Complete the row by filling in the parity symbols in positions indexed by [n i ] \ I i using an appropriate encoder for C i , thereby fulfilling the condition that c i ∈ C i . In the zipper code of Fig. 1, for example, the shaded tiles in row i are filled with symbols drawn from previous rows, the unshaded tiles correspond to message symbols, and the filled tiles correspond to parity symbols computed using the encoder for C i .

D. Code Rate
We will always assume that only the symbols in the real buffer, i.e., in positions indexed by B, are transmitted over the channel, in some well-defined order from oldest to newest. The symbols in the virtual buffer, which are needed for purposes of encoding and decoding, are not transmitted. As usual, let m i = |A i | denote the number of virtual symbols in row i. Under the assumption of that only the real buffer is sent, the rate of a zipper code is given as where, assuming the limits exist, For example, staircase codes with staircase block size m × m uses a fixed constituent code of length 2m and dimension k. Thus, n = 2m, k = k, and m = m, thereby achieving a rate R = k m − 1 (assuming k m > 1).

E. Decoding
Suppose that we transmit real symbols in positions indexed by B. At the receiver we can form a buffer c by filling in the real positions from symbols received at the output of the channel, and filling in virtual positions by copying real received symbols as prescribed by the interleaver map φ. We generally assume a hard-decision channel, i.e., we assume that the channel outputs are elements of F 2 , though it is possible to consider more general situations with various amounts of reliability information in the form of erasures or log-likelihood ratios. The received buffer c is not necessarily a zipper codeword, since, due to channel noise or other impairments causing detection errors, the rows aren't necessarily codewords of the corresponding constituent codes. Ideally, the aim of the decoder would be to recover a valid zipper codeword while making as few changes to c as possible. However, such optimal minimum Hamming distance decoding is often too complicated to implement, so in practice some form of iterative decoding is used, making changes to the rows one at a time using the constraints imposed only by the constituent code that constrains that row, and usually revisiting each row a number of times.
Decoding is typically performed within a sliding window of M consecutive rows c i−M +1 , c i−M +2 , . . . , c i from the received buffer. Many of the virtual symbols in these rows will, however, be copies of symbols from outside the sliding window (which, ideally, will have been corrected by previous decoding iterations). The decoder operates by decoding the rows within the decoding window. When the decoder performs correction operations (flipping the value of one or more bits in a row), all copies of the affected bits within the decoding window (as determined by the interleaver map) will also need to be flipped. After a number of iterations have been performed, the sliding window can be advanced (by one or, more usually, several rows), and the corrected information symbols leaving the window can be delivered as the decoder output. Numerous variations of this basic scheme are possible.
In one round of so-called exhaustive decoding, every row in the decoding window is visited (exactly once) by the corresponding constituent decoder. Each bit is decoded (in a round) as many times as it appears in the window. Exhaustive decoding can be performed in serial fashion (one row at a time), or in parallel (usually under the constraint that decoders operating in parallel don't operate on the same bits).
In one round of so-called pipelined decoding, only a subset of the rows in the decoding window (every Lth row, say, for some parameter L) are visited by constituent decoders. This method may be faster than exhaustive decoding, but, depending on the interleaver map, some bits may not be visited by a decoder at all. Thus, pipelined decoding is suitable only for certain types of interleaver maps that ensure that as many bits as possible are visited by the constituent decoders. Similar to exhaustive decoding, pipelined decoding can be done in series or parallel.
Under both of these decoding methodologies, decoding can be performed in multiple rounds, until no more errors can be corrected or until some maximum number of allowed decoding rounds is reached.
Additional strategies can also be applied to these decoding procedures.
In chunk decoding, rather than advancing the sliding window one row at a time, the window is advanced only after a specified number of new rows, called a chunk, is received.
In decoding with fresh/stale flags, a "fresh/stale" status indicator is maintained for each buffer row. The indicator is set to "fresh" whenever a change is made to the row (for example, if the row is newly arrived, or a bit has been flipped in that row due to a correction elsewhere); otherwise, after a decoding it is set to "stale". In each iteration, decoders can skip over stale rows (since nothing has changed in that row since the previous iteration, and therefore the row has either been corrected or has been determined to be uncorrectable).
In decoding with periodic truncation, a fraction of the message positions are reserved to be set to known values (for example, zero). The known symbols do not need to be transmitted, as they can be filled in perfectly at the receiver. One approach would be to alternate between sending data in, say, J consecutive rows, and not sending data (or, more precisely, sending only parity symbols) in τ consecutive rows. We call J and τ the transmission length and truncation length, respectively. This method is a generalization of staircase code "termination" discussed in [26], and is a form of code "shortening" as defined in coding theory. The shortened code will have a lower code rate than the zipper code from which it is derived.
In dynamic decoding, the decoder is implemented with a number of constituent decoders that can operate in parallel and that can be assigned dynamically (according to a scheduling module) to the rows to be decoded. Equipping a decoding engine with the flexibility to assign decoders to the rows where work needs to be done results in increased hardware utilization (reduced computational idling). Dynamic decoding can achieve similar decoding performance with fewer computational resources than without dynamic decoding [27].

III. EXAMPLES
This section gives some examples of related spatiallycoupled codes that can be described as zipper codes. Due to space constraints, only a few codes will be described in detail, but other codes that can be described as zipper codes include those in [5]- [9].

A. Staircase Codes
Staircase codes [3] are characterized by having an infinite sequence of matrices of size m × m: S 0 , S 1 , . . . such that, for each i ∈ N, every row of S T i S i+1 is a codeword of a systematic constituent code C of length 2m, where S T i is the transpose of S i . The initial block S 0 is all zero (and not transmitted). The codes are so named because the sequence of matrices form a staircase-like pattern when arranged as shown in Fig. 2 (left), in which each row and each column must be a codeword of C, and where the dark-filled regions hold parity symbols.
Staircase codes correspond to zipper codes with a fixed (systematic) constituent code C of length 2m, and a zipping pair with A i = [m] for all i ∈ N, i.e., the virtual positions comprise the first m positions in each row. The interleaver map φ is m-periodic and defined to perform a transposition operation, i.e., The resulting buffer then forms the pattern shown in Fig. 2 (right).

B. Braided Block Codes
Braided block codes [4] are a type of convolutional code whose codewords can be represented as a subarray of an infinite two dimensional array constrained by two interacting constituent codes, one providing constraints on rows and the other providing constraints on columns. An example of a codeword from a rate 1/7 tightly braided block code from [4] is shown in Fig. 3 (left). In this example, each row and each column in the diagram must form a codeword of the binary This tightly braided block code corresponds to a zipper code with fixed (7, 4) Hamming constituent code. The zipping pair is defined so that A i = [3] when i is even, and A i = [4] when i is odd. The interleaver map is given as where the last case corresponds to copying an information symbol from the row above. In this example, only evennumbered rows contain an information symbol. The name "zipper code" derives from the buffer pattern formed in this example.

C. Diagonal Zipper Codes
In this subsection, we introduce two interleaver maps that couple the bits of a zipper code in a regular ("hardwarefriendly") fashion. These interleaver maps generalize those of staircase codes.
1) Tiled Diagonal Zipper Codes: Tiled diagonal zipper codes are a generalization of staircase codes that are defined defined in terms of w × w "tiles" of symbols, a fixed (systematic) constituent code C with length 2Lw, and a zipping pair with A i = [Lw] (so that virtual positions comprise the first Lw positions in each buffer row), where the parameter L is a positive integer. The interleaver map is defined so that each w × w tile within the virtual buffer is the transpose of some w × w tile within the real buffer, as illustrated in Fig. 4. Fig. 4. Tiled diagonal zipper code with L = 3, tile size w×w, and interleaver map as described in (2).
To specify the interleaver map precisely, we must introduce a coordinate system for tiles. For a buffer c, for any s ∈ [2L] and for any q ∈ N, let The w ×w matrix T q,s is a tile located within the buffer whose top left entry has position (wq, ws). When s < L, such a tile comprises only virtual symbols, and therefore it is called a virtual tile; otherwise it is a real tile. For fixed q, the set of tiles {T q,s : s ∈ [2L]} are said to form the qth tile row.
For any s ∈ [L] (indexing a virtual tile), we would like to have T q,s = T T q−s−1,L+s . Thus the first virtual tile in tile row q is the transpose of the first real tile located one tile row earlier, the second virtual tile in tile row q is the transpose of the second real tile located two tile rows earlier, and so on. The interleaver map that accomplishes this task is given as φ(wq + i, ws + j) = (w(q − s − 1) + j, w(L + s) + i). (2) Fig. 4 shows an example of a tiled diagonal zipper code with L = 3.
When w = 1 (the case of 1 × 1 tiles) tiled diagonal zipper codes recover the interleaving pattern of the continuously interleaved BCH (CI-BCH) codes described in [6]. When L = 1, tiled diagonal zipper codes are staircase codes.
2) Delayed Diagonal Zipper Codes: Delayed diagonal zipper codes are variants of tiled diagonal zipper codes with w = 1 and an added "delay" in the interleaver map. Specifically, the interleaver map is given by where the positive integer δ is the delay parameter. When δ = 1, the interleaver map is identical to the interleaver map (2) with w = 1. Fig. 5 illustrates the buffer of a delayed diagonal zipper code with m = 8. As will show in Section V, the introduction of delay in the interleaver map reduces the multiplicity of minimal stall patterns. Delayed diagonal zipper codes can be generalized to the case of w×w tiles, with w > 1, in the obvious way.

IV. DESIGN EXAMPLES
In this section, we present software simulation results for several tiled diagonal and delayed diagonal zipper code design examples.

A. Simulation Setup
We simulate transmission of zipper codewords over a binary symmetric channel with crossover probability p. This corresponds to binary antipodal signalling over an additive white Gaussian noise channel (Bi-AWGN) with hard-decision detection, but it may also model other communications scenarios that give rise to independent and symmetrically distributed bit errors. The Shannon limit at rate R for such a channel is the largest crossover probability p for which it is theoretically possible to communicate at rate R (bit/channel use) with arbitrarily small probability of error. For the Bi-AWGN, this value of p is achieved at some particular signal-to-noise ratio (SNR). A code of finite length will achieve sufficiently small error probability only at some crossover probability smaller than the Shannon limit, corresponding to a larger Bi-AWGN SNR. The "gap to the Shannon limit" is then defined as the difference (in decibels) between the Bi-AWGN SNR corresponding to the Shannon limit and the Bi-AWGN SNR at which the code achieves sufficiently small error probability.
By "sufficiently small error probability" we mean a postcorrection (post-FEC) bit error rate (BER) of 10 −15 or smaller. As we cannot reliably measure such low error rates in any reasonable amount of time using software simulations, we use a least-squares fit linear extrapolation (on the log-log scale) of our measured error rates, in order to estimate the BSC crossover probability p * at which the post-FEC BER achieves 10 −15 .
In all of our design examples, we use shortened t-errorcorrecting (n, k) BCH constituent codes, where n = 2m. We made no attempt to optimize the positions at which the code is shortened. The virtual buffer and the real buffer both have width m. We use a causal, periodic, bijective interleaver map that implements a diagonal or delayed diagonal zipper code.
Decoding is performed using exhaustive decoding, with at most five rounds per window of size M rows (thus containing M m real symbols). We use chunk decoding with chunk size m, fresh/stale flags, and periodic truncation with transmission length J = 995m and τ = 5m.

B. Varying Decoding Window Sizes
We simulated a rate 0.97 tiled diagonal zipper code with w = 1 and m = 1200, (corresponding to a CI-BCH code [6]) having a (2400, 2364, t = 3) shortened BCH constituent code, over varying decoding window sizes. As shown in Fig. 6, we observe an improvement in the decoding performance as well as disappearing error flare as we increase the decoding window sizes. This is due to the fact that larger decoding windows provide each symbol with a larger number of decoding rounds. However, as expected, we see a diminishing return as the window size increases, with only slight improvement when increasing the decoding window size from 4m 2 = 5.76 Mb to 5m 2 = 7.20 Mb. Simulation results for a variety of different tiled diagonal zipper codes indicate that choosing the window size near 5m 2 gives nearly best possible decoding performance.

C. Different Code Rates
As shown in Fig. 7, we simulated the decoding of tiled diagonal zipper codes with tile size w = 1 having different code rates, as summarized in Table I. The decoding window size was set to 5m 2 in all cases. We see that the gap to the Shannon limit decreases as the rate increases, which is consistent with the theoretical analysis of [12].

D. Tiled Diagonal and Delayed Diagonal Zipper Codes
We simulated rate 0.967 codes with m = 1000, based on a (2000, 1967, t = 3) shortened BCH constituent code, with 5 Mb decoding window size. Various tiled and delayed diagonal zipper codes having a variety of tile sizes w and delay parameter δ, as summarized in Table II, were simulated. Performance curves for the tiled diagonal codes are shown in Fig. 8 and those for the delayed diagonal codes are shown in Fig. 9.
In both cases, increasing w or δ helps improve the decoding with an improvement to the gap to the Shannon limit of 0.028 ∼ 0.039 dB when compared to the δ = w = 1 case. A stall pattern analysis for tiled diagonal and delayed diagonal zipper codes, which may provide theoretical justification for these performance improvements, is given in Sec. V.

E. Performance versus Complexity
Let us define the performance of a zipper code as its gap to the Shannon limit at 10 −15 output bit error rate, and its complexity as the decoding radius t of its constituent code. (A more appropriate complexity measure might be t 2 , as it is known that the power consumption of a Berlekamp-Masseybased BCH decoder circuits grows as O(t 2 ) [35].) Fig. 10   performance versus complexity for various rate 0.96 diagonal zipper codes. As expected, the gap to the Shannon limit is reduced by increasing the complexity of the constituent code, but with diminishing returns.

V. STALL PATTERN ANALYSIS
This section will describe how error events in zipper decoders are characterized via error and stall patterns. For simplicity, throughout this section we will be focusing on zipper codes whose interleaver maps are bijective.

A. Graph Representation of Zipper Codes
Due to the spatially-coupled structure of zipper codes, it can be helpful to describe them as codes defined on graphs. Following the notation of Sec. II, we consider a zipper code corresponding to constituent code sequence C 0 , C 1 , . . ., with respective information sets I 0 , I 1 , . . .. For each i ∈ N, the virtual symbols in the ith row of a buffer are indexed by the set A i ⊆ I i . Fix a bijective interleaver map φ = (φ 1 , φ 2 ). Let be the set of row indices from which the virtual symbols in row i are copied (excluding any negative row indices).
Define a graph G = (V, E) whose vertex set V = N is the set of natural numbers, and whose edge set The vertices then correspond to constituent codes, with an edge joining two vertices if the corresponding codes have a symbol in common. Parallel edges are permitted, thus we interpret the edge set as a multiset (a set in which elements may have multiplicity greater than one). The number of edges between two vertices is then equal to the number of symbols that the corresponding codes have in common. Allowing for parallel edges, the degree of vertex i is equal to n i , the blocklength of C i , unless some virtual symbols in row i are copied from rows with negative row index, in which case the corresponding edges are missing. Vertices m, m + 1, m + 2, . . . therefore have degree n = 2m. The graph of a tiled diagonal zipper code with m = 4, w = 1 is shown in Fig. 11.
Graph representations for zipper codes in which symbols are copied more than once (i.e., when the interleaver map is non-bijective) can be defined by appealing to hypergraphs (in which hyperedges comprise more than two vertices), to a bipartite representation such as a factor graph, or by introducing additional constituent repetition-code constraints. We will not pursue such representations in this paper.

B. Error and Stall Patterns
Recall that B is a set containing the positions of all real symbols in a buffer. An error pattern S ⊆ B is any nonempty subset of B containing the positions of erroneous symbols in the real part of a received buffer. For any error pattern S, we define to be the complete set of positions of errors and their duplicates in the virtual set, and we define π(S * ) = {i : (i, j) ∈ S * } to be the set of affected rows.
For simplicity, throughout this section we assume that the constituent code is identical for all rows, i.e., C i = C with decoding radius t i = t for all i ∈ N. In addition, we assume that we use a genie-aided, miscorrection-free constituent decoder. Such a decoder is able to correct up to t errors in a row, but always fails to decode (never miscorrecting) when the number of errors in a row exceeds t. We assume that this genie-aided decoder visits rows in a decoding window as many times as is needed, reducing the error pattern size until no further correction is possible. Should some errors remain after this decoding procedure, we call the remaining errors a stall pattern. In a stall pattern, we must have at least t + 1 errors in every remaining affected row.
We will consider only strictly causal interleaver maps that induce at most one shared symbol between any two distinct rows of a zipper code. This means that the resulting graph is simple, i.e., it contains no parallel edges or self-loops. Each edge of a such a simple graph corresponds to one codeword symbol. We refer to such an interleaver map as scattering.

C. Decoding on a Graph
Assuming a scattering interleaver map, an error pattern S can be represented as a subgraph of the graph representing the zipper code. If the zipper code has graph representation G = (V, E), the graph representation of S is G S = (V S , E S ), where V S = π(S * ) ⊆ V (i.e., the vertex set of S contains vertices corresponding to the rows affected by S) and E S = {{i, j} : (i, k) ∈ S, j ∈ φ −1 1 (i, k)} (i.e., the edges in E s correspond to symbols in error). From this construction, the number of edges in G S is exactly the cardinality of S. We call |S| = |E S | the size of the error pattern S.
Suppose that the constituent code C can correct up to t errors. The action of the genie-aided decoder can then be described as an edge-peeling process in the error pattern graph G S = (V S , E S ): 2) Repeat step 1 until either the graph is empty or all remaining vertices have degree t + 1 or higher. This procedure will terminate either in an empty graph (successful decoding), or in a (t + 1)-core of G S -the largest induced subgraph of G S with the property that all vertices have degree at least t + 1. Sometimes, though not always, the (t + 1)-core will form a (t + 2)-clique, i.e., a subgraph of G S comprising t + 2 vertices all of which are neighbours (a complete subgraph). Such a pattern is uncorrectable by the genie-aided decoder. More generally, we call G S a stall pattern if each vertex in G S has degree at least t + 1, making it uncorrectable.
The following example illustrates error and stall patterns in both array and graph representations. Example 2. Consider a zipper code with a constituent code C capable of correcting t = 2 errors. Suppose that we receive an error pattern with seven errors as shown in Figure 12. Since rows 1, 3, 6, and 8 have at least 3 errors each, we cannot correct them. However, we can still correct row 4, which has only one error. Thus we will remove the error from row 4 and its corresponding entry in row 6, or equivalently, we remove vertex 4 and its incident edges. However, the remaining errors cannot be corrected and so those errors form a stall pattern. The 4-clique formed by vertices 1, 3, 6, and 8 is a stall pattern and it is also the 3-core of the error pattern graph from which we started.

D. Properties of Stall Patterns of Zipper Codes
The following theorem bounds the size of a stall pattern in a zipper code with a bijective and scattering interleaver map. Theorem 1. A stall pattern S for a zipper code with a terror-correcting constituent code and having a bijective and scattering interleaver map satisfies |S| ≥ 1 2 (t + 1)(t + 2). Proof: Let G S = (V S , E S ) be the graph representation of stall pattern S, and let v be any vertex in V S . Then, since Hence, there must be at least deg(v) + 1 ≥ t + 2 vertices in G S with each vertex having degree t + 1 or higher. By the handshaking lemma of graph theory, we have |S| = |E S | ≥ (t+1)(t+2) 2 .
It is worth noting that 1 2 (t+1)(t+2) is precisely the number of edges of a complete graph with t + 2 vertices. In fact, we will now show that the existence of a (t + 2)-clique in the graph representation of the zipper code is a necessary and sufficient condition for the existence of a stall pattern of size 1 2 (t + 1)(t + 2). Proposition 1. Let G = (V, E) be the graph representation of a zipper code with a t-error-correcting constituent code and a bijective and scattering interleaver map. Then the code has a stall pattern S of size 1 2 (t + 1)(t + 2) if and only if G contains a (t + 2)-clique.
Proof: (⇐) Every (t + 2)-clique corresponds to a stall pattern of size 1 2 (t + 1)(t + 2). (⇒) Suppose by way of contradiction that a stall pattern S of size 1 2 (t + 1)(t + 2) has a graph G S with more than t + 2 vertices. The average degree of the vertices is then less than 2|S|/(t + 2) = t + 1, which implies implies that V S contains at least one vertex of degree t or lower, contradicting the fact that S is a stall pattern. On the other hand, if G S contains fewer than t + 2 vertices, then there exists a vertex in V S with degree greater than t + 1, which is impossible in a simple graph.
An example of an interleaver map that yields a stall pattern of size 1 2 (t + 1)(t + 2) is the tiled diagonal zipper code with tile size 1 (or delayed diagonal with delay 1). Fig. 13 shows an example of a tiled diagonal zipper code with w = 1, m = 3, t = 2.
Theorem 1 can be generalized to strictly causal nonscattering interleaver maps that allow constituent codes to have up to b bits in common, so that the resulting graph representation has up to b parallel edges connecting any two vertices.
Theorem 2. For a zipper code with t-error-correcting constituent code having a strictly causal interleaver map that allows up to b parallel edges between any pair of vertices in its graph, the number of errors in a stall pattern is at least Proof: Any vertex in a stall pattern graph must have at least (t + 1)/b neighbours. The result then follows from the same argument as in the proof of Theorem 1.

E. Error Floor Approximation
The presence of stall patterns creates so-called "error floors" in the performance curves of zipper codes. We may approximate the location of the error floor using a union bound technique similar that used in [3]. We consider a decoding window of size M × m, and denote the set of all stall patterns in the decoding window to be S. We determine the error floor estimate by enumeration of S, evaluating (an upper bound on) the probability that the particular error pattern arises at the output of a binary symmetric channel with crossover probability p. This then gives Suppose that we could determine exactly the sizes of stall patterns that can occur in a decoding window. We could then rewrite (3) as where L denotes the set of all stall-pattern sizes that can occur in the decoding window of size M m and N denotes the number of occurrences of stall patterns of size . Note that since we only consider stall patterns that can fit in the decoding window, we have ≤ M m.
The possible sizes and the number of occurrences of stall patterns of certain size depend on the interleaver map. For example, it is possible to construct stall patterns of size 1 2 (t + 1)(t+2) in tiled diagonal zipper codes with tile size 1, but not in staircase codes, whose smallest stall pattern size is (t + 1) 2 [3], [36].
Given a decoding window, a set L of possible stall pattern sizes that can fit in the window, and crossover probability p, we call the stall patterns of size * ∈ L to be dominant if N * p * ≥ N p for all ∈ L. In general, the minimum-sized stall patterns may not be dominant since it is possible that the multiplicity of larger stall patterns causes a dominant N p term. However, for sufficiently small p, we can assume that stall patterns of minimum size are dominant. The error floor can be then further approximated as the contribution of just the minimum-sized stall patterns, i.e., the right hand side of (4) is approximately N * p * , where * = min L.

F. Eliminating Small-Sized Stall Patterns of Diagonal Zipper Codes
We will now describe a few strategies to eliminate stall patterns of size 1 2 (t + 1)(t + 2) in tiled and delayed diagonal zipper codes. 1) Tiled Diagonal: Our first observation is that we can reduce the multiplicity stall patterns of size 1 2 (t + 1)(t + 2) by increasing the tile size. To see this, we will first count the occurrences of stall patterns of size 1 2 (t+1)(t+2). Denote the tile size as w and assume that m = wL, M = wK (K > L), and L ≥ t + 1. In order to construct a stall pattern of size 1 2 (t + 1)(t + 2), we first pick t + 1 tiles from the same row. We then select a row index at which to place the errors. For each of the t + 1 tiles, pick one column index at which to place an error. Those errors will correspond to errors in t + 1 other rows. The positions of the remaining 1 2 t(t + 1) errors in those rows are then forced. Thus, the number of stall patterns of size 1 2 (t + 1)(t + 2) is given by Having larger tile size will make the values for K and L lower assuming that the decoding window size is fixed. This will in turn reduce the multiplicity of stall patterns of size 1 2 (t + 1)(t + 2) given by (5). Furthermore once L ≤ t, it is impossible to form a stall pattern of size 1 2 (t + 1)(t + 2). 2) Delayed Diagonal: In delayed diagonal zipper codes, the occurrences and size of the minimum-sized stall patterns depends on δ. In particular, we will show that having larger delay reduces the multiplicity of stall patterns of size 1 2 (t + 1)(t + 2).
Proposition 2. For a delayed diagonal zipper code with terror-correcting constituent code and delay parameter δ, there exists a stall pattern of size 1 2 (t + 1)(t + 2) if and only if δ ≤ m−1 t . Proof: Without loss of generality, let the first affected row index of the stall pattern be zero. (⇐) We claim that we can form a stall pattern of size 1 2 (t + 1)(t + 2) whose set of row indices is given by I = {0, δ, 2δ, . . . , (t + 1)δ}. To see this, first observe that (t + 1)δ = tδ + δ ≤ m + δ − 1. The neighbours of row i in the full zipper code graph are then indexed by Thus, i + (t + 1)δ ≤ max(N (i)) and max{0, i − (t + 1)δ} ≥ min(N (i)), so I ⊆ N (i) for all i ∈ I. It follows that the rows in I are connected with each other and so it is possible to form a (t + 2)-clique from I. (⇒) Let I = {0, i 1 , . . . , i t+1 } with 0 < i i < . . . < i t+1 be the row indices of a stall pattern of size 1 2 (t + 1)(t + 2). Then it must be true that . . . i t+1 ≥ i t + δ ≥ (t + 1)δ.
In a decoding window with M rows, the number of possible combinations is therefore at most M m − tδ + t t + 1 .
Example 3. Figure 14 shows the number of stall patterns of size 1 2 (t + 1)(t + 2) involving the first row of the decoding window in delayed diagonal zipper codes for m = 1000 and t = 3, 4, 5. Observe that when δ = 1 and t = 3, there are 1000 4 ≈ 4.14 × 10 10 possible configurations involving the first row. However, there is only one possible configuration for δ = 333 and stall patterns of size 1 2 (t + 1)(t + 2) do not exist for δ ≥ 334.

VI. CONCLUSIONS
Zipper codes provide a convenient framework for describing a wide variety of product-like spatially-coupled codes. Such codes are of interest in high-throughput communication systems because they can be decoded iteratively using lowcomplexity power-efficient constituent decoders while achieving a gap to the Shannon limit on the binary symmetric channel of 0.5 dB or less at high code rates. We have introduced tiled diagonal and delayed diagonal interleaver maps that couple the constituent codes in regular (hardware-friendly) patterns. These interleaver maps provide flexibility in trading off decoding window size and code performance. A combinatorial analysis of stall patterns that arise with such interleaver maps shows that increasing tile size or delay can indeed have a beneficial effect on reducing the error floor of the code.
Further research on zipper codes is needed to address the design of interleaver maps that give rise to codes with large minimum Hamming distance or large dominant stall-pattern size. Tradeoffs between code performance and decoding latency should be better characterized. Can soft-decision (or soft-aided) decoding methods be introduced without excessive increase in decoding complexity and decoder power consumption? No doubt many further interesting questions can be formulated.