I. INTRODUCTION

Linear nested codes are error correcting codes where multiple information words are encoded separately and then are algebraically superimposed at the physical layer prior to transmission [2], [3]. Nested codes are commonly used for error correction in wireless multi-terminal networks. In nested coding, each information word is associated with a codeword which belongs to a different code, also called a sub-code. Suppose, for example, there are two information words u 1 and u 2 of length k 1 and k 2 , respectively. A codeword corresponding to each information word, x i ∈ F n 2 , i ∈ {1, 2}, is generated via a generator matrix G i , or parity-check matrix H i , respectively. Here, x i belongs to a different sub-code C i , and the transmitted codeword x is an element of the global code C . For example, the generator matrix G of the global code is obtained by stacking the individual G 1 and G 2 matrices vertically as G1 G2 .

This material is based on work supported by the National Science Foundation under Grant Nos. ECCS-1710920, ECCS-1711056, OIA-1757207, and HRD-1914635. This paper has been presented in part at the 2019 IEEE Information Theory Workshop, Visby, Sweden [1].

The construction of nested regular and irregular low-density parity-check block codes (LDPC-BCs) have been considered in [4] and [5]. Irregular LDPC-BCs can be optimized to outperform regular LDPC-BCs in the waterfall region under belief propagation (BP) decoding; however, they generally suffer from an early onset of an error-floor, a flattening of the bit error rate (BER) performance curve in the high signal-tonoise ratio (SNR) region, and are not implementation friendly [6]. In comparison, regular LDPC-BCs generally have better error-floor performance as a result of their minimum distance and graph properties [7], [8] and lower decoder complexity; however, their performance deteriorates with increasing graph density under BP decoding [9], making them undesirable for the construction of nested codes that require a higher graph density than the non-nested ones.

Spatially coupled LDPC (SC-LDPC) codes [6], [10], on the other hand, are known to approach the capacity of binary input memoryless channels under BP decoding as the graph density increases [11]. Hence, regular SC-LDPC codes are good potential candidates for nested code constructions. SC-LDPC codes are obtained by coupling, or connecting, multiple Tanner graphs corresponding to an underlying LDPC-BC. One potential obstacle of graph-based codes is that Tanner graphs contain small sub-structures called absorbing sets (ABSs) [12] which are known to cause the BP decoder to fail. These failures are responsible for the error-floor phenomenon. However, since spatial coupling is able to reduce or eliminate many of these harmful ABSs [13], SC-LDPC codes have superior errorfloor performance when compared to their BC counterparts.

The optimization of SC-LDPC codes for magnetic recording channels is considered in [14], which generalizes [15] for ABSs of type (4, 4(γ -2)), where γ is the column weight. Moreover, [16] analyzes the conditions to avoid cycles of lengths 6 and 8 in SC-LDPC codes. An array-based (AB) SC-LDPC code is constructed from the Tanner graph of an AB-LDPC-BC by applying an edge-spreading technique [17], [18], [15]. AB-SC-LDPC codes possess a regular quasi-cyclic (QC) structure that makes them more attractive for hardware implementation because different regions on the Tanner graph of AB-LDPC codes can be decoded in parallel, which improves the decoding throughput and lowers the decoding latency. Moreover, their structure also guarantees a certain minimum distance [19] and a girth of 6 (they are free of 4-cycles). These features, in turn, guarantee the non-existence of certain harmful ABSs [12]. Due to these advantages, we investigate the construction of nested AB-SC-LDPC codes, which, to the the column group number and the column number inside a particular column group of an AB-LDPC matrix H(γ, p). Therefore, each row (resp., column) of an AB matrix is given by r = qp+s (resp., c = jp+k). In this way, the location of an entry of an AB matrix (r, c) may be written as (q, s; j, k). Note that when referring to multiple row groups, we use subscripts q 0 , q 1 , . . . , and so on where q i ∈ {0, 1, . . . , γ-1}, with similar subscript use for multiple row numbers, column groups, and column numbers.

B. Array-Based SC-LDPC Codes

AB-SC-LDPC codes can be constructed from AB-LDPC-BCs by coupling L copies of the Tanner graph G H via edge-spreading [25]. In terms of matrices, edge-spreading is equivalent to splitting H(γ, p) into a sum of m+1 component block matrices of the same dimension as H(γ, p), such that H(γ, p) = H 0 + H 1 + • • • + H m , where m denotes the memory of the code. The construction involves a spreading matrix B m ∈ F γ×p m+1 , where an entry g ∈ {0, 1, . . . , m} in position (i, j) of this matrix indicates that the p × p circulant block in row group i, column group j, of H(γ, p) is copied to its corresponding position in H g [18]. The resulting timeinvariant parity-check matrix of a terminated SC-LDPC code is denoted

and is given as

where L > m + 1 is the number of column blocks (each containing p column groups), called the coupling length, and ν = (m + 1)p 2 is the constraint length of H(γ, p, L). We can also label the row and column blocks y ∈ {0, 1, . . . , L+m-1} and v ∈ {0, 1, . . . , L -1} in a similar way to AB-LDPC-BCs, where an individual entry (r, c) in an AB-SC-LDPC code may then be written as (y, q, s; v, j, k).

C. Nested Codes

A nested code consists of a group of M sub-codes

, which is a linear combination of all the codewords x i obtained from each of the sub-codes. The process of obtaining x via nested coding is expressed as

where ⊕ denotes the bitwise XOR operation and In comparison, nested dual codes of the above mentioned codes are defined using parity check matrices H i ∈ F li×n 2 , l i ≥ n -k i , and H ∈ F l×n 2 , l ≥ n -k, corresponding to the nested codes C i and C , respectively, which form the null spaces of matrices H i and H, respectively. Note that the matrices H i , ∀i, and H are considered as (potentially overlapping) sub-matrices of a larger Ĥ ∈ F b×n 2 matrix, where l i < b ≤ n , ∀i, and l < b ≤ n, respectively. The construction details of H i and H from Ĥ are discussed in [4] for LDPC-BCs.

In the remainder of the paper, we consider H i and H to be the parity-check matrices of nested regular LDPC codes. We refer to the column weight ω i (resp., ω) of sub-code C i (resp., global code C ) as the column weight of its corresponding (regular) parity-check matrix H i (resp., H). This is the construction used in the rest of the paper.

D. Absorbing Sets

In G H , suppose X ⊂ V and let N (X) be the set of all neighbors of X. Let O(X) be the set of neighbors of X with odd degree in the subgraph induced by X ∪ N (X).

and the property that each VN in X has strictly fewer neighbors in O(X) than in C \ O(X). An (a, b) ABS is a fully ABS if, additionally, all nodes in V \ X have strictly fewer neighbors in O(X) than in C \ O(X). A minimal (a, b) ABS refers to an ABS which has the smallest possible existing value for a in a given LDPC Tanner graph, and where b is the smallest possible value for the given a. Definition 2. A block k-cycle in an AB-LDPC code is a collection of p cycles of length k, where each cycle in the collection spans the same row and column groups of the parity-check matrix.

Remark 1. A (3, 3) ABS is the minimal ABS that can exist in a column weight-3 AB-LDPC-BC code [12]. For γ = 4, a (4, 4) ABS is the minimal ABS in an AB-LDPC-BC for p = 5, 7; whereas, a (5, 4) ABS is the minimal ABS in an AB-LDPC-BC for the case p = 11, 19; finally, (6,4) ABSs exist in an AB-LDPC-BC for p > 5, and it is the minimal ABS for all p > 19 [12]. For γ = 5, the minimal ABS in AB-LDPC-BCs is of size (4,8), and (5, 9) and (6, 8) ABSs are also dominant [26]. 1From the structure of dominant ABSs discussed in [12], [26], we note the following.

Remark 2. For γ = 3, a (3, 3) ABS in an AB-LDPC code corresponds to a 6-cycle and a (4, 2) ABS consists of two (3, 3) ABSs. Moreover, for γ = 4 (resp., γ = 5), the (4, 4), (5,4) and (6, 4) (resp., (4,8), (5,9) and (6, 8)) ABSs in an AB-LDPC code all contain at least one 6-cycle. Consequently, by minimizing the number of 6-cycles in AB-SC-LDPC codes, we also minimize the related ABSs discussed in Remark 1.

E. Line-counting

A 6-cycle must span three distinct row and column groups of an AB matrix [16], [20]. As shown in Fig. 1, suppose that the columns of a 6-cycle have indices c 1 , c 2 , c 3 and that they exist in distinct column groups j 1 , j 2 , j 3 , respectively. Similarly, suppose that the rows of a 6-cycle have indices r 1 , r 2 , r 3 and they exist in distinct row groups q 1 , q 2 , q 3 , respectively. In [24], (3,3) ABSs are enumerated by computing the area of a 2D polytope lying on the (j, j ) plane, j = j , where a data point (coordinate) in this polytope corresponds to a (3, 3) ABS (and hence a 6-cycle). 2 This technique, however, has two drawbacks: first, it is only applicable to AB-SC-LDPC codes constructed via the cutting-vector scheme [13], and secondly, it only works for column weight-3 AB-LDPC codes. To allow more general codes, such as the ones obtained via general edge-spreadings [18], a (3, 3) ABS enumeration technique, namely line-counting, was proposed in [20] which enumerates (3,3) ABSs by counting 6-cycles on the (c 1 , c 2 ) plane.

In this paper, we propose a variant of line-counting, called adapted line-counting (ALC), in conjunction with an optimization algorithm (more details in Section IV) to recursively optimize the entries of a B m spreading matrix in order to ensure that the resulting H(γ, p, L) matrix contains as few harmful ABSs as possible. In order to facilitate presentation of our ALC scheme later in Section III, the line-counting method of [20] is briefly reviewed. We refer to a matrix region R that consists of at least six (not necessarily contiguous) circulant matrices spread across three row groups and at most p column groups, with one row group being a row group of I matrices only. A row block from a H(γ = 3, p, L) matrix in the case of AB-SC-LDPC codes, contains a row group of I matrices and two row groups consisting of σ f z mod p matrices for 0 ≤ z ≤ p -1 and f = 1, 2. W.l.o.g., for any 6-cycle in R, we have the following [20] (row and column block indices in the case of AB-SC-LDPC codes are fixed and dropped for clarity):

• c 2 > c 1 and w 1 p ≤ c 1 < w 2 p, w 3 p ≤ c 2 < w 4 p, where w 1 , w 2 , w 3 , w 4 are integers satisfying 0

If the 6-cycle row r 1 , incident to columns c 1 and c 2 (see Fig. 1), exists in a row group of I matrices, we obtain c 2 -c 1 = np, where n = {1, 2, . . . , w 4 -w 1 -1};

• αp ≤ c 3 < βp, where α and β are integers satisfying 0 ≤ α ≤ p -1, 1 ≤ β ≤ p, and α < β. The circulant matrix σ z , z ∈ {0, 1, . . . , p -1}, has its nonzero elements located at (s, k), where s = z + k mod p. W.l.o.g., let q 2 (resp., q 3 ) represent the index of the row group containing all the σ 2z mod p (resp., σ z ) circulant matrices (q 2 = 2 and q 3 = 1 in an AB-LDPC-BC). The edges (ones in the parity-check matrix) corresponding to (r 2 , c 3 ) and (r 2 , c 2 ) are in rows s 2 = 2j 3 + k 3 mod p and s 2 = 2j 2 + k 2 mod p within their row group r 2 . Since these rows are identical, 2j 2 + k 2 = 2j 3 + k 3 mod p, which are rearranged as

(2) Now, considering (r 3 , c 1 ), we note that, s 3 = j 1 + k 1 mod p, and s 3 = j 3 + k 3 mod p. Since these rows are also identical, we get j 1 + k 2 = j 3 + k 3 mod p, which are rearranged as

(3) Substituting ( 2) in (3), and after rearranging, we obtain

(4) Now, if the roles of q 2 and q 3 are interchanged, we obtain (via a similar procedure)

(5) Finally, by invoking the inequality α ≤ j 3 ≤ β -1 and by taking into account the corresponding 6-cycle column value c 3 as a function of c 1 and c 2 , we obtain the range of c 3 in R as [20] αp

where the inequalities in (6a) are obtained from (4), and the ones in (6b) are obtained from (5).

Consider Fig. 2 for an illustration. The grey area in Fig. 2(a) is an example of a region R in an H 0 matrix containing a 6cycle (in red) with column (resp., row group) indices c 1 , c 2 , and c 3 (resp., q 1 , q 2 , and q 3 ) of H 0 . The white region in Fig. 2(a) indicates all-zero circulant matrices, and the horizontal arrows represent the range of values of the columns c 1 , c 2 , and c 3 of the 6-cycle. These ranges generate vertical, horizontal and diagonal boundaries, respectively, on the (c 1 , c 2 ) plane in Fig. 2(b), and the area enclosed within these boundaries is shown in grey. In particular, the red diagonal boundaries are obtained from the first inequality in (6a). A 6-cycle with columns c 1 and c 2 exists in R if a coordinate (c 1 , c 2 ) on the line c 2 -c 1 = np lies within the grey region L on the (c 1 , c 2 ) plane. Consequently, the number of 6-cycles in R is determined by the number of integer points on the line c 2c 1 = np within L .

Note that the inequalities in (6a) and (6b) only hold for column weight-3 AB matrices where the circulant matrix shift factor is f = 1, 2. Consequently, the line-counting method of [20] is not applicable for arbitrary column weight-3 AB-LDPC-BC matrices (for the case f > 2), which will be encountered during nested code optimization. To allow for f > 2, we introduce ALC in Section III-E which generalizes these inequalities. This will facilitate the nested code optimization considered in Section IV-B.

III. NESTED AB-SC-LDPC CODES

In this section, we discuss the construction procedure of nested AB-SC-LDPC codes from the corresponding nested AB-LDPC-BCs. For nested AB-SC-LDPC codes with ω i = 3, 4, or 5, whose dominant ABSs are known to contain 6cycles (see Remark 2), ALC can be used directly as a tool in the construction. 3

A. General Construction

We form a nested AB-LDPC-BC sub-code C i , i ∈ {1, 2, . . . , M }, and a global code C from sub-matrices

and H(3, p), respectively, where ω i > 3.

Let Ω i be the number of possible sub-codes C i for column weight ω i ≥ 4. To simplify our analysis, we suppose that

but generalizations of this selection are possible. It follows from the array structure [23] that there are Ω i = γ -ω i + 1, γ ≥ 5, possible sub-codes, and hence γ should be chosen sufficiently large to construct the desired M sub-codes. Note that the design rate R i = 1 -ωi p of C i decreases with increasing ω i . As a result, constructing high rate nested codes with large ω i also requires a relatively large p compared to a nested code with smaller ω i . In turn, this also makes each sub-code optimization more computationally intensive as M increases.

Example 1. We construct the Ĥ(γ, p) AB-LDPC-BC matrix with γ = 5, p = 5, and M = 2, where

There are Ω i = 2 possible sub-codes of column weight ω i = 4 in our construction. This matrix consist of submatrices: H 1 (4, 5) (black and blue row groups 0, 1, 2, and 3, with h 1 = 0), H 2 (4, 5) (black and red row groups 0, 1, 2, and 4, with h 2 = 1), and H(3, 5) (black row groups 0, 1, and 2) with corresponding column weight 4 nested sub-codes C 1 , C 2 , and a column weight-3 global code C , respectively. Explicitly, the resulting nested sub-matrices are

Nested AB-SC-LDPC matrices are constructed in a similar way, with parity-check matrices denoted as H i (ω i , p, L) and H(3, p, L) obtained by edge-spreading H i (ω i , p) and H(3, p) via spreading matrices B i,m ∈ F ωi×p m+1 and B m ∈ F 3×p m+1 , respectively, where the row indices of B i,m correspond to the row group indices of H i (w i , p). Since the codes are nested, the same relationship between H i (w i , p) and H(3, p) also holds for the edge-spreading matrices, i.e., B m is a sub-matrix of B i,m . An example of creating nested AB-SC-LDPC codes from the nested AB-LDPC-BCs in Example 1 is given below in Example 2.

Example 2. For memory m = 1, we first generate an edgespreading matrix

which can be used to form global AB-SC-LDPC matrix H(3, 5, L) with components (see ( 1))

and corresponding global code C . Similarly, H 1 (4, 5) from ( 7) can be used to generate the nested AB-SC-LDPC matrix H 1 (4, 5, L), using the example edge-spreading matrix

with components

and corresponding nested code C 1 . Note that H 1 (4, 5, 2) contains the (global) H(3, 5, 2) matrix, shown in black. The sub-matrix H 2 (4, 5, 2) is constructed in a similar fashion from the spreading matrix

Note that the order of optimization determines how good the sub-codes or the global code will be in terms of the number of harmful ABSs. We will see later in Section IV-B that for column weight-3, 4, or 5 nested AB-SC-LDPC codes, where harmful ABSs are known to contain 6-cycles, ALC can be employed effectively to speed-up the optimization procedure.

The optimization of nested AB-SC-LDPC codes may be performed in several ways. In any method, the spreading of all row groups S = {0, 1, . . . , γ -1} must be determined, but the results will vary depending on the order of the optimization. In the following, we consider two general exemplary methods. An example and a discussion will follow in Section III-B. Method 1: First, optimize the B m matrix, containing row groups S 0 = {0, 1, 2}, to construct the global matrix H(3, p, L) from H(3, p). Then, pick an ordering of {1, 2, . . . , M}, denoted t = (t 1 , t 2 , . . . , t M ), and by incor-porating the constraints given by B m , sequentially optimize for i = 1, 2, . . . , M , the remaining rows of each B ti,m matrix containing row groups S ti ⊆ S, i.e., those row groups S ti ∩ (S \ ∪ i-1 j=1 S tj ) in S ti that have not yet been determined, to construct H ti (ω i , p, L) from H ti (ω i , p). 4Method 2: Again, pick an ordering t = (t 1 , t 2 , . . . , t M ) of {1, 2, . . . , M }. Here, we first optimize the nested B t1,m matrix, with row groups S t1 = {0, 1, 2, . . . , w t1 -2, w t1 -1+h t1 } to construct H t1 (ω t1 , p, L) from H t1 (ω t1 , p) (note that this nested matrix contains the global matrix corresponding to S 0 = {0, 1, 2}, and thus the global code is not independently optimized). Given the constraints of the newly generated B t1,m matrix, sequentially optimize the matrix B ti,m , i = 2, 3, . . . , M , by determining the spreading of any row groups in S ti ∩(S \∪ i-1 j=1 S tj ), to construct H ti (ω ti , p, L) from H ti (ω ti , p).

B. Constrained Optimization

Suppose that B t1,m is optimized first (i.e., without constraints) using Method 2. This unconstrained optimization determines any edge-spreading matrix B ti,m , for i = 1, with a set of row indices S ti ⊂ S t1 , and partially determines any edge-spreading matrix B ti,m , i ∈ {2, 3, . . . , M } with a set of row indices S ti ⊂ S t1 , but S ti ∩ S t1 = ∅. The row(s) of B ti,m that are not optimized yet are determined via constrained optimization. Although the order of constrained optimization may be chosen in an ad hoc manner, the freedom in choosing the entries of B ti,m may diminish as more edge-spreading matrices are determined prior to it. An example is provided in the following to demonstrate the constrained optimization process (which is applicable to both Methods 1 and 2, but shown only for Method 2).

Example 3. Fig. 3 shows the row group indices of four nested AB-LDPC-BC sub-codes using four colored boxes. The indices enclosed within the blue, red, green and black boxes, correspond to respective row groups S 1 = {0, 1, . . . , ω -1}, S 2 = {0, 1, . . . , ω, γ -3}, S 3 = {0, 1, . . . , γ -4, γ -2}, and S 4 = {0, 1, . . . , γ -3, γ -1} of H(γ, p), and they form the respective sub-matrices H 1 (ω, p), H 2 (ω + 2, p), H 3 (γ -2, p), and H 4 (γ -1, p) of H(γ, p), with respective column weights ω, ω +2, γ -2, and γ -1, and corresponding respective nested sub-codes and3 < ω < γ. To construct an associated AB-SC-LDPC code, we select an optimization order, suppose t = (2, 1, 3, 4). First, spreading matrix B 2,m is determined. Note that this determines B 1,m since S 1 ⊂ S 2 . Next, B 3,m is partially determined, but row groups ω + 1, ω + 2, . . . , γ -4, γ -2 must now be optimized. Finally, B 4,m is partially determined by both B 2,m and B 3,m , and the only remaining row group to optimize is γ -1. Note that, here, the global code C corresponds to the sub-matrix H(3, p) of H(γ, p) with row groups 0, 1, and 2. The edge-spreading matrices are now used to construct H 1 (ω, p, L), H 2 (ω +2, p, L), H 3 (γ -2, p, L) and H 4 (γ -1, p, L), respectively, as described in Section IV-A. Recall that the goal of our nested code optimization is to minimize the number of dominant ABSs in the sub-code's Tanner graph. In terms of sub-codes, the constrained optimization order in this example would give the most freedom to code C 2 , and we would expect that code to have relatively fewer harmful ABSs. On the other hand, the nested code C 4 does not have much freedom since it contains only one undetermined row group prior to optimization, and thus it may exhibit relatively more harmful ABSs. Depending on the application, t should be chosen carefully.

C. Terminal Lift

QC codes are well known to facilitate hardware implementation [6]. To simplify our code search for good nested code designs, we choose to apply a circulant-based graph lifting after the steps described in Sections III-A and III-B, which we refer to as a terminal lift with lifting factor J. This results in quasi-cyclic LDPC-BCs (QC-LDPC-BCs) and QC-SC-LDPC codes. A similar lifting procedure has been shown to be very effective for constructing QC codes [27]. The parity-check matrices obtained by applying a terminal lift to H i (ω i , p, L) and H(3, p, L) are denoted as

, i = 1, 2, . . . , M , and

, respectively, with constraint length ν = Jν. A terminal lift serves two purposes: first it helps us generate sufficiently long nested codes to achieve good performance for typical applications, and second, we are able to further reduce the multiplicity of, or even eliminate, any residual ABSs in the nested Tanner graphs of H i (ω i , p, L) and H(3, p, L) that remain after the edgespreading construction. Note that, for comparison, we will also construct a terminally lifted LDPC-BC matrix, denoted as H(γ, p, J(m

, by lifting the block matrix H(γ, p) by a larger lifting factor J(m + 1). By incorporating m + 1 in the lifting factor we ensure that the length (number of columns) of the BC matrix is identical to the constraint length of the SC matrix. This will be helpful for comparing the performances of QC-LDPC-BCs and QC-SC-LDPC codes in Section V.

D. 6-cycles and Dominant ABSs in AB-LDPC Codes

We now state some useful results concerning dominant objects of AB-SC-LDPC codes.

Remark 3. From Remarks 1 and 2 it is easy to note that by eliminating all 6-cycles via spatial coupling, we can also eliminate all the dominant ABSs in γ = 3, 4, 5 AB-SC-LDPC codes.

Note that a 6-cycle in an AB-SC-LDPC matrix spans 3 row groups and it spans at most m+1 contiguous column blocks of (1) [18]. Let µ e , e = 1, 2, . . . , m+1, represent the total number of 6-cycles present in precisely e contiguous column blocks of (1), and let µ be the total number of 6-cycles in H(γ, p, L). From the repeated structure of H(γ, p, L) it follows that the total number of 6-cycles in H(γ, p, L) is µ = m+1 e=1 (L -e + 1)µ e [18].

E. Adapted Line Counting (ALC)

The line-counting method discussed in Section II-E is restricted to the enumeration of 6-cycles in H(3, p, L), i.e., only to row groups 0, 1, and 2. To overcome this shortcoming, we propose an ALC scheme to enable 6-cycle enumeration in general row group triples {0, q 2 , q 3 } of the larger parity-check matrix Ĥ.

1) Choosing Column weight-3 Sub-matrices for ALC: To optimize the nested construction, we need to optimize each row group. Our method involves optimization with row groups of weight-3. We begin by enumerating the required sub-matrices involved in the optimization.

, where each matrix in ζ consists of a common row group 0 and a distinct row group pair (q, q ) from all other elements of ζ . If ω i -1 is odd, there is one more row group that has not appeared in any matrix in ζ , and we need to select an additional matrix H

where either the row group q or q is not shared with a matrix in ζ . The number of possible H

and it follows that we must select T = Z + Z distinct column weight-3 sub-matrices in H i (ω i , p) that have a common row group 0 in order to include all of the row groups of H i (ω i , p). Therefore, to optimize the nested SC matrix H i (ω i , p, L) corresponding to H i (ω i , p), it is sufficient to enumerate 6-cycles in the T sub-matrices of ζ detailed above using ALC (details to follow in Section IV-B).

Example 4. We provide an example for choosing the required column weight-3 sub-matrices in a nested matrix for ALC, with nested column weights ω i = 4 and 5. In the first case, the H i (4, p) matrix has row groups 0, 1, 2, and 3. The set ζ contains Z = 2 column weight-3 sub-matrices with a common row group 0:

i (3, p)}, with respective row groups {0, 1, 2} and {0, 1, 3} of H i (4, p). Hence, we select T = Z + Z = 1 + 1 = 2 matrices to include all row groups, e.g., ζ = {H

i (3, p)}, with respective row groups {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 2, 3}, {0, 2, 4}, and {0, 3, 4} of H i (5, p). We must select T = Z +Z = 2+0 = 2 matrices to include all row groups, e.g.,

2) Description of ALC: Recall from Section II-E that R is contained in a column weight-3 sub-matrix of an AB paritycheck matrix, and c 1 , c 2 , c 3 are the column indices of a 6-cycle in R. We begin by extending (6) to a general column weight-3 matrix containing row group 0. Lemma 1. For ALC, the range of c 3 in R is expressed via c 1 and c 2 as

The proof is given in Appendix A. Note that ( 6) is a special case of ( 14) because, for parameters (λ, q 2 , q 3 ) taking on the values (0, 2, 1), (1, 2, 1), (1, 1, 2), and (0, 1, 2), we recover all inequalities in (6).

Proposition 1. Based on the principles of Cartesian geometry, the total number of 6-cycles in R, N R , is given by

, if some boundary conditionsfoot_6 hold, 0, otherwise,

where the boundary conditions in (15) (stated in (32)) are related to the (c 1 , c 2 ) plane and the line c 2 -c 1 = np, n = 1, 2, . . . , w 4 -w 1 -1, whose length is determined by the points (σ 1x , σ 1y ), (σ 2x , σ 2y ) within these boundaries.

The proof of this proposition, including the boundary conditions, is given in Appendix B. In general, suppose a k-cycle has a row r i , i ∈ {1, 2, . . . , k 2 -1}, in the q 0 row group. If this row is connected to columns c i and c i , i, i ∈ {1, 2, . . . , k 2 -1} and i = i , we can obtain a line c i -c i = np on the (c 1 , c 2 , . . . , c k 2 -1 ) plane, which passes through a ( k 2 -1)dimensional region L, enclosed by the boundaries generated by the k-cycle column values. Thus, any integer point lying on this line will represent that k-cycle, allowing line-counting to be further adapted to detect and enumerate cycles of length longer than six.

Let N denote the number of regions in an AB-LDPC matrix required by ALC to compute all the 6-cycles, which is independent of p but may depend on m. In case of AB-LDPC-BCs, N = 1 as R is the entire parity-check matrix. However, N > 1 for column weight-3 AB-SC-LDPC paritycheck matrices since there are multiple matrix regions with distinct row group triples and no two regions share a 6-cycle. For code optimization, these triples need to be considered only for coupling length L = m + 1, since a 6-cycle does not span more than m + 1 contiguous column blocks of a column weight-3 AB-SC-LDPC parity-check matrix (see Section III-D).

Proposition 2. N is upper bounded by (3m + 2)

The proof is given in Appendix C. An example of determining N in the case of a column weight-3 and memory m = 1 AB-SC-LDPC matrix is provided in the following.

Example 5. Determining N for memory m = 1: Note that in this case, it is necessary to optimize only two contiguous column blocks of a column weight ω = 3 (time-invariant) AB-SC-LDPC matrix H (z) i (3, p, L). Hence, it is sufficient to consider coupling length L = 2. Note that, for L = 2, there are three copies of the distinct row groups 0, q 2 , q 3 from H(γ, p) in H (z) i (3, p, 2). Recall that we locate a copy of a row group by the ordered pair (y, q), where, y ∈ {0, 1, . . . , L + m -1 = 2} is the row block index and q is the row group index. Here, we slightly abuse notation and identify the row group index as q ∈ {0, q 2 , q 3 }, where it is understood that q 2 identifies the second row group in a row block of H (z) i (3, p, 2) and q 3 identifies the third, respectively. We choose to do this because the values of q 2 and q 3 (corresponding to the row groups and circulants of H(γ, p)) will be used in ALC as described in Section III-E2.

There are two possible region configurations. The first is a single column block [H 0 H 1 ] (i.e., matrix (1) with L = 1). Here, a 6-cycle may exist in any of the 8 regions R 1 , R 2 , . . . , R 8 with row group triples {(0, 0), (0, q 2 ), (0, q 3 )}, {(0, 0), (0, q 2 ), (1, q 3 )}, {(0, 0), (0, q 3 ), (1, q 2 )}, {(0, 0), (1, q 2 ), (1, q 3 )}, {(1, 0), (0, q 2 ), (0, q 3 )}, {(1, 0), (0, q 2 ), (1, q 3 )}, {(1, 0), (0, q 3 ), (1, q 2 )}, and {(1, 0), (1, q 2 ), (1, q 3 )}, respectively. Each of these regions span p column groups and can be viewed as a block matrix similar to H(3, p) but with one or more all-zero circulant matrices.

A 6-cycle may also span an "L" shaped matrix region configuration

Seven regions of this category exist, denoted as R 9 , R 10 , . . . , R 15 , with row group triples {(0, 0), (1, q 2 ), (1, q 3 )}, {(0, q 2 ), (1, 0), (1, q 3 )}, {(0, q 3 ), (1, 0), (1, q 2 )}, {(1, 0), (1, q 2 ), (1, q 3 )}, {(1, 0), (1, q 2 ), (2, q 3 )}, {(1, 0), (1, q 3 ), (2, q 2 )}, and {(1, q 2 ), (1, q 3 ), (2, 0)}, respectively, with 2p column groups in each region. The total number of 6-cycles is obtained by enumerating the number of 6-cycles in each of the N = 15 regions as R 1 , R 2 , . . . , R 15 .

Note that, in a column weight-3 AB-LDPC matrix region R, there are at most p 2 -p block cyclesfoot_7 of length 6, and each of them generate a separate "block-cycle region" L y , y ∈ {1, 2, . . . , p 2 -p}, on the (c 1 , c 2 ) plane which the line c 2 -c 1 = np may intersect. The location of L y is determined by the range of values of c 1 , c 2 , and c 3 associated with the corresponding block 6-cycle. If R does not contain allzero matrices, i.e., R is the H(3, p) matrix, then regions L 1 , L 2 , . . . , L p2-p combine to form a single consecutive region L on the (c 1 , c 2 ) plane. Therefore, the total number of 6-cycles in R will be identical to the length of the line c 2 -c 1 = np passing through L , and hence, only a single line computation will be necessary to compute N R . However, if R contains one or more all-zero matrices, i.e., R is one of the matrix regions R 1 , R 2 , . . . , R 15 discussed in Example 5, then, one or more region(s) from L 1 , L 2 , . . . , L p2-p will be eliminated, depending on which block cycle(s) of R is/are eliminated due to the presence of the all-zero matrices(s). Consequently, in this case, N R will be identical to the total number of integer points lying on the line c 2 -c 1 = np within the existing block-cycle regions which may not be consecutive anymore. As a result, multiple line computations may be necessary to determine N R , depending on how many (disjoint) block-cycle regions the line c 2 -c 1 = np intersects.

3) Complexity: The conventional cycle counting method discussed in [28] has computational complexity of 2 /p) = O(gγ 2 p 3 ) for AB-LDPC-BCs, where g is the girth and E = γp 2 is the number of edges in the graph, respectively.

Since a column weight-3 matrix region R generates p 2 -p block-cycle regions on the (c 1 , c 2 ) plane, the number of line computations necessary for determining N R via ALC scales with O(p 2 ) since the number of arithmetic operations involved in a single line computation (corresponding to a single blockcycle region) is independent of the code parameters. Thus, due to a significantly reduced 6-cycle enumeration complexity compared to standard cycle counting algorithms, ALC is more desirable for the optimization of nested codes.

IV. AB-SC-LDPC NESTED CODE OPTIMIZATION PROCEDURE

In this section, we discuss the optimization strategy for nested AB-SC-LDPC codes in example scenarios where the nested codes have column weights ω i = 4 or 5, and the global code has column weight-3. First, a numerical optimization scheme is employed to determine the entries of the edgespreading matrices B i,m and B m to construct parity-check matrices H i (ω i , p, L) and H(ω = 3, p, L) from H i (ω i , p) and H(ω = 3, p), respectively. ALC is used at each optimization step to compute (and minimize) the number of 6-cycles in the nested AB-SC-LDPC parity-check matrices. Finally, a terminal lift is applied to further reduce residual ABSs in the Tanner graphs of optimized H i (ω i , p, L) and H(3, p, L) matrices.

A. ALC-Based Guided Search

An overview of the search mechanism for determining the entries of the spreading matrices is provided in the following. For ease of notation, we refer to a given AB-LDPC-BC paritycheck matrix H (3, p) have been determined by optimization of another nested code (see the constrained optimization discussion in Section III-B) are copied into B and cannot be changed, the remaining entries are initially set to zero (i.e., the corresponding circulants exist in sub-matrix H 0 of ( 1)) and designated to be "unfixed".

In each search iteration , either an unfixed entry of B is determined, or "fixed", referred to as forward-search, or a fixed entry of B is erased and re-evaluated, referred to as back-tracking. In a forward-search step, an integer from the set S = {0, 1, . . . , m-1} is assigned to an unfixed entry (i, j) of B, and the number of 6-cycles in the corresponding H sc matrix is computed via ALC. This procedure is repeated for all the remaining elements in S , and the one that contributes to the least number of 6-cycles in H sc is chosen for entry (i, j) of B and designated fixed. Note that there may be more than one value in S which corresponds to the same number of 6-cycles for entry (i, j). In this case, entry (i, j) is set to be one of those values that minimizes the cycles from S randomly, and the remaining candidates are stored for back-tracking. After each round of forward-search, the number of 6-cycles in H sc is given by the integer ρ . If ρ ≥ ρ -1 , then a back-tracking step is applied. In this phase, the most recently assigned entry (i, j) is designated unfixed, then the forward-search is applied and a new value is chosen for the unfixed entry randomly from the previous set of saved candidates for that The optimization procedure terminates if no more back-tracking is possible, or after a maximum number of search iterations ( max ) elapse, or if ρ = 0, whichever occurs first.

B. Construction of Optimized Nested AB-SC-LDPC Codes

We outline the approach of Method 1 using ALC, which first optimizes H(3, p, L) and then the H ti (ω i , p, L) matrices based on the constraints given by H(3, p, L) and the ordering t, as described in Section III-A. The optimization requires the following three steps:

• Step 1: Inputs to the ALC based optimization algorithm are the H(3, p) matrix and the undetermined B m matrix. The guided search is allowed to run as described in Section IV-A until either the number of 6-cycles in H(3, p, L) obtained in an optimization iteration is 0, or until the number of optimization iterations exceed a predetermined threshold max , whichever occurs first. At the end of this step we obtain B m , and the spreading for row groups 0, 1, and 2 is permanently fixed. • Step 2: For a given sub-code index t i , inputs to the ALC based optimization algorithm are H (z) ti (3, p), consisting of row groups {0, q, q }, and a matrix B (z) ti,m ∈ F 3×p 2 which contains the rows corresponding to row groups {0, q, q } of B ti,m . Note that the row 0 of B (z) ti,m has been fixed already and cannot be changed; if the row(s) corresponding to the row groups q and/or q of B (z) ti,m are/is unfixed, then they/it will be fixed in this step. The guided search algorithm of Section IV-A is now allowed to run until either all the 6-cycles in H ti,m , are eliminated or the number of optimization iterations exceed a threshold max , whichever occurs first. This optimization step is repeated for all possible values of z from {2, 3 . . . , T }. At the end of this step, we obtain the complete B ti,m matrix. This step is repeated until all sub-codes i = 1, 2, . . . , M are set.

• Step 3: Finally, the H i (ω i , p, L) and H(3, p, L) matrices are constructed by edge-spreading according to B i,m . Method 2 largely follows the approach in Method 1, but here H i (ω i , p, L) is optimized first instead of H(3, p, L) (as described in Section III-A). Example 6. We demonstrate ALC based optimization for Method 1 using the AB-LDPC-BC from Example 1 with nested matrix Ĥ(5, 5), coupling length L = 2, and memory m = 1. In Step 1, we input an all-zero 3 × 5 B 1 matrix and return the optimized B 1 matrix shown earlier in (8). This is used to generate the optimized global SC matrix H(3, 5, 2), whose components are shown in (9), from H(3, 5). In Step 2, we select t = (1, 2) and first optimize the matrix B 1,1 that will be used to spread the edges of H 1 (4, 5) from ( 7) to construct the optimized (with constraints) nested AB-SC-LDPC code C 1 . 7 Note that, for this code, H 1 (4, 5) consists of row groups 0, 1, 2, and 3, of which 0, 1, and 2 (black rows) are fixed in Step 1. Here, T = 2 and the two matrices H (z) 1 (3, p), z = 1, 2, can be chosen, say, to have row groups {0, 1, 2} and {0, 2, 3}, respectively. Since H

, p) is completely determined and there is only on row group (with index 3) to fix, we require only one optimization (z = 2). The inputs in Step 2 are the sub-matrix

of H 1 (4, 5) and the matrix B

1,1 , where the first two rows of B

(2) 1,1 , corresponding to row groups 0 and 2, were already determined in Step 1 as rows 0 and 2 of B 1 in (8), and the third row is set to all-zeros. The output is the optimized matrix

The blue row in italics of ( 17) represents the only row of B

that has been optimized in this step. Now, combining B 1 and B

1,1 , all the row groups 0, 1, 2, and 3 have been fixed and we obtain the optimized edge-spreading matrix B 1,1 shown in (11), that is used to construct the optimized nested SC matrix H 1 (4, 5, 2), whose components are shown in (12). The sub-matrix H 2 (4, 5, 2) is constructed in a similar fashion to complete Step 2. Finally, the nested matrices are constructed as described in Step 3.

C. Optimization Complexity

Let x ∈ {1, 2, . . . , ω }, ω ∈ {3, ω i }, be the number of undetermined rows of a B matrix input to the ALC-based optimization scheme. For a given column weight-3 AB-LDPC-BC parity-check matrix H, the scheme needs to search over at most (m + 1) xp possible choices of the xp entries belonging to the undetermined rows of B, to determine the choices that minimize/eliminate the number of 6-cycles in H sc . Moreover, during a search, ALC is invoked for enumerating 6-cycles in H sc . Recall that N column weight-3 matrix regions are taken into account by ALC to compute all the 6-cycles in H sc , and therefore at most p 2 -p line computations may be necessary for each region. Therefore, the complexity of our nested code optimization scheme for a given B is O(N p 2 (m 1) xp ). Due to the high optimization complexity for large p, it may be more beneficial to choose a small value of p and then subsequently apply terminal lifting to design longer SC codes.

D. Terminal Lift

The terminal lifted matrices H i (ω i , p, L, J), i = 1, 2, . . . , M , and H(3, p, L, J ) may now be obtained by lifting the non-zero (resp., zero) entries of H i (ω i , p, L) and H(3, p, L) via randomly generated circulant (resp., all-zero) matrices of size J × J. The goal of the terminal lift is to break as many remaining 6-cycles as possible in the Tanner graphs of H i (ω i , p, L) and H(3, p, L). In this paper, we use an exhaustive search to select circulants for the first m + 1 contiguous column blocks of (1), searching until either all 6cycles are eliminated or a maximum time duration is elapsed. Many other approaches could be considered, e.g., [29], [30]. These permutations are repeated periodically for the remaining L -(m + 1) column blocks to form the complete matrix. This is first performed for any i, i.e., on H i (ω i , p, L, J), and then repeated for the additional row groups in the paritycheck matrices of the remaining nested codes C 1 , C 2 , . . . , C M . Note that terminally lifted QC-LDPC-BC matrices, denoted H(3, p, J(m + 1)) and H i (ω i , p, J(m + 1)), are obtained in similar fashion by lifting the non-zero (resp., zero) entries of H(3, p) and H i (ω i , p) via circulant (resp., zero) matrices with dimension J(m + 1) × J(m + 1).

V. NUMERICAL RESULTS

We now demonstrate the effectiveness of the procedure outlined in Section IV using nested AB-SC-LDPC matrices H(3, p, L), H 1 (4, p, L), and H 4 (5, p, L), with corresponding BC matrices H(3, p), H 1 (4, p), and H 4 (5, p) obtained from row groups {0, 1, 2}, {0, 1, 2, 3} and {0, 1, 2, 3, 4}, respectively, of a nested Ĥ(6, p) AB-LDPC matrix. We provide 6-cycle enumeration results with syndrome former memories m = 1 and 2 in Section V-A, and computer simulation results in Section V-B with m = 2.

A. ALC Enumeration Results

We first present results obtained only with the ALC-based optimization described in Section IV-B, i.e., without a terminal lift. In the case of AB-SC-LDPC codes with memory m, we compute the asymptotic average number of 6-cycles per VN given by A m = lim L→∞ I. The maximum number of search iterations for the ALC based optimization scheme was set to max = 10 4 . The asymptotic average results for random (Ran) nested AB-SC-LDPC matrices (non-optimized) are also presented in Table I, where randomly generated B m and B i,m matrices were selected. As another benchmark for comparison, we compute the asymptotic average number of 6-cycles per VN for AB-LDPC-BCs, given by A (BC) = µ/p 2 , where µ is the total number of 6-cycles in the AB-LDPC-BC. The values of A (BC) in the matrix H(3, p) are computed as 12, 18, and 30, for p = 5, 7, and 11, respectively, for H 1 (4, p) these values are 48, 72, and 120, respectively, whereas for H 4 (5, p), the A (BC) values are 60 and 100, respectively, for p = 7 and 11.

By comparing the results obtained using Method 1 and 2 in Table I to the uncoupled matrices (A (BC) values), we note that spatial coupling is able to significantly reduce the number of 6cycles, and hence dominant ABSs. Moreover, Method 1 results in a lower A m for the global SC-LDPC matrix H(3, p, L), but has a larger A m for the nested SC-LDPC matrices. Using Method 2, on the other hand, shows the opposite behavior -a smaller A m for the nested codes, but a moderate A m for the global code. From the Method 2 results shown in Table I, we also note that, for p = 5 and m = 2, the asymptotic average is zero in all optimized column weight-3 or column weight-4 nested codes. From Table I, we observe that, on average, the randomly generated nested SC-LDPC matrices possess a significantly larger value of A m (and hence they contain a larger number of dominant ABSs) when compared to nested AB-SC-LDPC matrices obtained via ALC based optimization, but still show a significant reduction when compared to AB-LDPC-BCs (A (BC) values). Note that for p = 5, the rate of the column weight-5 nested BC is zero, and hence the results for H 4 (5, 5, L) are excluded.

Finally, we note that by applying the terminal lift described in Section IV-D, even for small J, it is possible to significantly reduce, or even eliminate dominant ABSs. For example, with p = 5, 7, m = 1, 2, and p = 11, m = 2, and a lifting factor of only J = 5, we are able to completely eliminate all 6cycles. This means that, after a terminal lift of the AB-SC-LDPC nested codes obtained via Method 1 and 2 in Table I the corresponding (3, 3), (4,4), (5,4) and (6, 4) ABSs as described in Remark 1 are removed. Note that, by removing 6-cycles in these AB-SC-LDPC codes, we are also able to significantly reduce the number of 8-cycles and any ABSs connected to them.

B. Simulated Code Performance

We now consider the BP decoding performances of terminally lifted column weight-3, 4, and 5 QC-SC-LDPC nested parity-check matrices. To demonstrate the behavior, we construct H(3, p, L = 99, J = 5), H 1 (4, p, L = 99, J = 5), and H 4 (5, p, L = 99, J = 5) nested QC-SC-LDPC codes, with memory m = 2 and p = 7, 11, as described in Section V-A, and compare their performances to random (non-optimized before terminal lift) QC-SC-LDPC codes and terminally lifted nested QC-LDPC-BC parity-check matrices H(3, p, J (m + 1)), H 1 (4, p, J (m + 1)), and H 4 (5, p, J (m + 1)). 8Computer simulation results are obtained over a binary additive white Gaussian noise (AWGN) channel. A sliding window BP decoder is used for decoding nested SC codes [31], where the window attempts to decode one block of p 2 J target symbols in each decoding instant, then the decoder shifts one block right and one block down the parity-check matrix (1), thereby decoding the entire frame after L shifts. The window length W of the decoder was selected as 4ν symbols, and 50 iterations were performed per window position. The terminally lifted QC-LDPC-BCs were decoded with a standard flooding BP decoder with a maximum of 50 iterations and a syndrome check stopping rule. The block length of the short LDPC-BC, obtained using J = 5, is identical to the constraint length ν = p 2 J(m + 1) of the SC code, whereas the long LDPC-BC, obtained using J = 20, has block length equal to the window length 4ν .

The bit error rate (BER) results are shown in Fig. 4. As expected from the enumeration results in Section V-A, the performance of the nested QC-SC-LDPC codes, irrespective of the column weight or construction method, is much better when compared to the performance of the corresponding nested regular QC-LDPC-BCs. We observe a significant gain in the waterfall for the optimized QC-SC-LDPC codes attributed to threshold saturation effect, and no indication of an error floor. The random SC-LDPC codes do appear to display the beginning of an error floor at 2.5 dB for p = 7. When comparing the performance of the two optimization strategies, it is noticeable that both the optimized column weight-4 and 5 nested QC-SC-LDPC codes perform better under Method 2 optimization when compared to Method 1. In case of the column weight-3 code, we see the same behavior for p = 7, which can be attributed in part to the terminal lift and resulting code realization. Note that the lower bound on the decoding error probability of message passing algorithms is known to decrease linearly with the multiplicity of harmful ABSs in SC codes [32]. Hence, the optimized nested QC-SC-LDPC codes are expected to have better error-floor performance when constructed via Method 1 or 2 compared to randomly generated QC-SC-LDPC codes.

VI. CONCLUSION

In this paper, we have considered the construction of finite length nested AB-SC-LDPC codes from nested AB-LDPC-BCs. During code construction, we ensured that each nested SC sub-code and the global code have a small number of dominant ABSs in the Tanner graph when compared to the underlying LDPC-BCs. An ALC based optimization technique was utilized to optimize the design of nested AB-SC-LDPC codes. This optimization scheme allows the enumeration of dominant ABSs (by counting 6-cycles) in arbitrary column weight-3 sub-matrices of the nested parity-check matrices, facilitating a tractable nested code optimization. We demonstrate that, by using ALC, it is possible to minimize/eliminate dominant ABSs in certain nested AB-SC-LDPC codes, irrespective of the row and column weight of the overall parity-check matrix containing all the nested matrices. We also show that, for some specific codes, dominant absorbing sets in the Tanner graphs of all nested codes are completely removed using our proposed optimization strategy. Simulation results verify the improved nested code performance under ALC based optimization.

APPENDIX A PROOF OF LEMMA 1

Recall the labeling of a 6-cycle shown in Fig. 1 in case of AB matrices with parameters q i , j i , and k i , i ∈ {1, 2, 3}. The edges corresponding to (r 2 , c 3 ) and (r 2 , c 2 ) both exist in row s 2 , hence we get s 2 = q 2 j 3 + k 3 mod p = q 2 j 2 + k 2 mod p. As a result, q 2 j 2 + k 2 = q 2 j 3 + k 3 mod p.

Similarly, considering (r 2 , c 3 ) and (r 3 , c 1 ) it is noted that s 3 = q 3 j 1 + k 1 mod p = q 3 j 3 + k 3 mod p, which gives

where j 1 < j 2 . Note that ( 18) and ( 19) can be rearranged as k 3 -k 2 = q 2 j 2 -q 2 j 3 mod p, (20) and k 3 -k 2 = q 3 j 1 -q 3 j 3 mod p, (21) respectively. Equations ( 20) and ( 21) can also be written as

and k 3 -k 2 = q 3 j 1 -q 3 j 3 -λ 2 p,

respectively, where λ 1 , λ 2 ∈ {1 -p, 2 -p, . . . , p -1}. By substituting (22) in (23), and after rearranging we get

where j 2 > j 1 , q 2 , q 3 ∈ {1, 2, . . . , γ -1} and λ = λ 1 -λ 2 .

In general, α ≤ j 3 ≤ β -1, where 0 ≤ α ≤ p -1, 1 ≤ β ≤ p and α < β. Using this inequality and from (24) we have α ≤ q 2 j 2 -q 3 j 1 -λp q 2 -q 3 ≤ β -1. is, σ 1x = max(φ 1x , θ 1x , θ 3x ), σ 1y = max(φ 1y , θ 1y , θ 3y ), σ 2x = min(φ 2x , θ 2x , θ 4x ), σ 2y = min(φ 2y , θ 2y , θ 4y ), where the x and y subscripts indicate the x and y coordinates, respectively, on the (c 1 , c 2 ) plane. Hence, in Figs. 5(a) and (b), σ 1 = θ 3 and σ 2 = θ 2 . From the principles of Cartesian geometry, the number of integer points lying on straight line connecting σ 1 and σ 2 is given as (σ2x-σ1x) 2 +(σ2y-σ1y) 2 2

. Let the y-coordinates of the points of intersection between lines l 4 and l 1 , and lines l 3 and l 2 , be denoted as ν 1 and ν 2 , respectively. Then, the total number of 6-cycles in R is expressed as N R = (σ2x-σ1x) 2 +(σ2y-σ1y) 2 2

, if (32) hold, 0, otherwise.

(

The boundary conditions that ensure line l 7 will intersect the shaded region L in Fig. 5 are θ 1y < ν 2 , θ 2y > ν 1 if q 3 < q 2 , or w 3 p < φ 2y , w 4 p > φ 1y if q 3 > q 2 , and θ 1x ≤ {σ 1x , σ 2x } ≤ θ 2x , θ 1y ≤ {σ 1y , σ 2y } ≤ θ 2y , (32) where ν 1 = αp + (w 2 -α)

Fix a single row group of I (identity) matrices within H , and randomly select a pair of row group indices from the remaining 2(m + 1) non-I matrix row group indices in H to create a triple (representing the row group indices of a column weight-3 sub-matrix in H ). There are 2(m+1) 2 possible ways of generating these triples, with a common row group index of I matrices. However, 2 m+1 2 of these triples contain a pair of non-I matrix row group indices (q, q ) such that q = q mod 3, and row groups with these triples do not contain any 6-cycles. Thus, for a given index of an I-matrix row group in H , we obtain κ = 2(m+1) 2 -2 m+1 2 distinct column weight-3 matrix regions containing 6-cycles. Since there are m + 1 row group of I matrices in H , the total number of distinct column weight-3 matrix regions in H (containing 6-cycles) is (m + 1)κ. Now, note that the combination of the two "L" shaped matrix regions have in total 2m + 1 row groups containing I matrices only, and hence there are (2m + 1)κ column weight-3 matrix regions (containing 6-cycles) which span one or more column blocks of H or H . Since at least one of these regions is already in H , the number of distinct column weight-3 matrix regions (containing 6-cycles) spanning more than one column block of H or H is upper-bounded by (2m+1)κ. Therefore, we obtain N < (m + 1)κ + (2m + 1)κ = (3m + 2)κ.