IEEE TRANSACTIONS ON COMMUNICATIONS

1

Finite-Length Construction of High
Performance Spatially-Coupled Codes via

arXiv:1802.06481v1 [] 19 Feb 2018

Optimized Partitioning and Lifting
Homa Esfahanizadeh, Student Member, IEEE, Ahmed Hareedy, Student
Member, IEEE, and Lara Dolecek, Senior Member, IEEE
Abstract
Spatially-coupled (SC) codes are a family of graph-based codes that have attracted significant
attention thanks to their capacity approaching performance and low decoding latency. An SC code is
constructed by partitioning an underlying block code into a number of components, and coupling their
copies together. In this paper, we first introduce a general approach for the enumeration of detrimental
combinatorial objects in the graph of finite-length SC codes. Our approach is general in the sense
that it effectively works for SC codes with various column weights and memories. Next, we present a
two-stage framework for the construction of high performance binary SC codes optimized for additive
white Gaussian noise channel; we aim at minimizing the number of detrimental combinatorial objects
in the error floor regime. In the first stage, we deploy a novel partitioning scheme, called the optimal
overlap partitioning, to produce optimal partitioning corresponding to the smallest number of detrimental
objects. In the second stage, we apply a new circulant power optimizer to further reduce the number
of detrimental objects in the lifted graph. An SC code constructed by our new framework has nearly 5
orders of magnitudes error floor performance improvement compared to the uncoupled setting.

H. Esfahanizadeh, A. Hareedy, and L. Dolecek are with the Department of Electrical and Computer Engineering, University
of California, Los Angeles, Los Angeles, CA 90095 USA (e-mail: {hesfahanizadeh, ahareedy}@ucla.edu; dolecek@ee.ucla.edu).
Parts of the paper were presented at the IEEE International Symposium on Information Theory (ISIT) 2017 [1], and the IEEE
Information Theory Workshop (ITW) 2017 [2]. Research supported in part by a grant from ASTC-IDEMA and NSF-CCF grant
No. CCF-1150212.

February 20, 2018

DRAFT

2

IEEE TRANSACTIONS ON COMMUNICATIONS

Fig. 1: The parity-check matrix of an SC code with parameters L and m.

I. I NTRODUCTION
Spatially-coupled (SC) codes are graph-based codes constructed by coupling together a series
of disjoint block codes into a single coupled chain [3], [4]. This operation can be viewed as
partitioning the parity-check matrix H of a block code into component matrices Hi , where
i ∈ {0, 1, · · · , m}, and piecing L copies of component matrices together to obtain the paritycheck matrix HSC of an SC code, as shown in Fig. 1. The parameters m and L are called the
memory and coupling length, respectively. Here, as the underlying block codes, we consider
circulant-based (CB) LDPC codes, where all circulants are non-zero [5].
Significant recent research on SC codes has been devoted to the asymptotic analysis, i.e., where
the code length approaches infinity, e.g., [6]–[10]. While the asymptotic analysis is important,
the results cannot be immediately translated to the finite-length case, because the underlying
assumptions on the code structure, e.g., being cycle-free, are different. There are several works
that have studied the finite-length analysis and design of SC codes in the error floor area, e.g.,
[11]–[15]. These works, while promising, have some limitations: In [11], [12], and [13], authors
consider SC codes with memory m = 1 and focus on a restricted partitioning technique of cutting
vectors. In [14], a construction method is presented for the the class of array-based (AB) SC
codes with column weight γ = 3 and for different memories. In [15], an approach is presented
for improving the girth properties of SC codes.
In this paper, we propose a new combinatorial framework for the finite-length analysis and
design of circulant-based SC (CB-SC) codes. We aim at constructing SC codes with the minimum
number of problematic objects in the error floor regime. These problematic objects are certain
DRAFT

February 20, 2018

SUBMITTED PAPER

3

configurations in the graph of codes that depend on both the code specifications as well as
the channel model [16]–[19]. We first introduce a new enumeration approach that exploits the
structure of SC codes in order to efficiently enumerate combinatorial objects of interest. Our
new approach is more general than our previous work [13], since it can be applied to SC codes
constructed by an arbitrary partitioning and with memories m ≥ 1.
Next, we present a systematic scheme for partitioning the underlying block code and constructing SC codes with a superior performance in the error floor regime over additive white Gaussian
noise (AWGN) channels. We operate on the protograph of the SC code, and express the number
of subgraphs we want to minimize in terms of the overlap parameters, which characterize the
partitioning. Then, we solve this discrete optimization problem to determine the optimal overlap
parameters. We call this new partitioning scheme the optimal overlap (OO) partitioning.
OO partitioning scheme is in particular suitable for code optimization in the regime outside
the reach of brute force methods, since it finds the optimal partitioning in a systematic way and
does not require to search among a set of possible choices. We demonstrate that the new scheme
shows much better performance compared to the existing approach of partitioning by cutting
vectors [11], [12]. More importantly, our partitioning scheme is presented for general memory
m and column weight γ. Given the optimal partitioning, we then apply a new heuristic program
to optimize the circulant powers of the underlying block code to further reduce the number of
problematic objects. We call this heuristic program the circulant power optimizer (CPO).
The rest of the paper is organized as follows. In Section II, we introduce the preliminaries.
In Section III, we propose our general enumeration approach. In Section IV, we propose our
optimal overlap partitioning scheme and circulant power optimizer to construct SC codes. Our
simulation results are given in Section V. Finally, the conclusion appears in Section VI.
II. P RELIMINARIES
In this section, we describe CB-SC codes. Then, we review the definition of problematic
objects causing the error floor degradation for SC/block codes over AWGN channels.
February 20, 2018

DRAFT

4

IEEE TRANSACTIONS ON COMMUNICATIONS

A. Circulant-Based SC Codes
CB codes are a class of structured regular (γ, κ) LDPC codes, where γ is the column weight
of the parity-check matrix (variable node degree in the graph), and κ is the row weight (check
node degree). CB codes can offer simple hardware implementation thanks to their structure [5].
Suppose p is the size of the constituent circulants. The parity-check matrix H of a CB code is
constructed as follows:




f0,0

f0,1

σ
 σ

 f1,0
σ f1,1
 σ

H=
..
..

.
.


σ fγ−1,0 σ fγ−1,1

...
...
...

σ

f0,κ−1

σ f1,κ−1
..
.

. . . σ fγ−1,κ−1





.





Here, σ denotes the p × p circulant matrix obtained by cyclically shifting the columns of
an identity matrix one unit to the left. Each column of H corresponds to one variable node
(VN) and each row corresponds to one check node (CN). In the parity-check matrix H, let i,
0 ≤ i ≤ γ − 1, be the row group index and j, 0 ≤ j ≤ κ − 1, be the column group index. The
circulant powers are the non-negative integer values denoted by fi,j . For example, the choice of
fi,j = ij and κ = p results in the class of AB codes [20].
SC codes have parity-check matrices, HSC , with a band-diagonal structure. A CB-SC code is
constructed by partitioning the κγ circulants in the parity-check matrix H of a block code into
component matrices Hi , 0 ≤ i ≤ m, where m is referred to as memory. Each component matrix
Hi has the same size as H. A component matrix contains a subset of circulants in H, and the
rest of its elements are zero. Every circulant in H is assigned to exactly one of the component
P
matrices, and m
i=0 Hi = H. Given the component matrices Hi and the coupling length L, one
can construct HSC as shown in Fig. 1.
Approaches for constructing SC codes with underlying structured block codes were previously
proposed in [11], [12], and [14]. The work in [11] and [12] is based on a cutting vector
scheme. In this scheme, the underlying block code is partitioned via a so-called cutting vector
DRAFT

February 20, 2018

SUBMITTED PAPER

5

ζ = [ζ0 ζ1 . . . ζγ−1 ] into component matrices H0 and H1 . The cutting vector ζ is a vector of
ascending natural numbers. Matrix H0 is constructed by copying all circulants of H with row and
column group indices in {(i, j)|j < ζi } to the same coordinates in H0 , and setting all remaining
elements of H0 to 0. Matrix H1 is then simply H1 =H−H0 . The cutting vector partitioning
approach could be generalized to construct SC codes with higher memories by using several
cutting vectors to partition the underlying block code. In this paper, we introduce a new scheme
for partitioning the block code that notably outperforms the cutting vector based method. A new
partitioning scheme is recently introduced in [14] which is developed for memories m = 1, 2;
however, the contribution is limited to column weight γ = 3 and AB codes as the underlying
block codes.
B. Combinatorial Objects of Interest
Under iterative decoding algorithms, certain structures in the graph of graph-based codes cause
the error floor phenomenon. These structures are error-prone, and the errors resulting from them
are not necessarily codeword errors. We review the key definitions of these objects.
Definition 1. Consider a subgraph induced by a subset V of VNs in the graph of a binary LDPC
code. The set V is said to be an (a, b) trapping set (TS) if the size of V is a and the number of
odd degree CNs connected to V is b [16], [21].
Definition 2. Consider a subgraph induced by a subset V of VNs in the graph of a binary LDPC
code. Let C e be the set of even degree CNs connected to V, and let C o be the set of odd degree
CNs connected to V. The set V is said to be an (a, b) absorbing set (AS) if the size of V is a,
the size of C o is b, and each VN in V is connected to strictly more CNs in C e than in C o [17].
Fig. 2 depicts the configuration of (3, 3), (4, 2), and (5, 3) ASs which are problematic objects
for SC/block codes with column weight γ = 3 over AWGN channels. Clearly, the class of TSs
subsumes the class of ASs. While TSs that are not ASs are usually harmless (as for the AWGN
channel, these configurations are typically unstable under iterative decoding), we purposely recall
February 20, 2018

DRAFT

6

IEEE TRANSACTIONS ON COMMUNICATIONS

the definition here. The reason is, as we shall see later in the paper, a systematic elimination of
multiple problematic ASs can be deftly achieved by focusing on the elimination of the common
sub-structure that these ASs share. In some cases, these common structures will be certain TSs
that on their own do not appear as decoding errors.

(a)

(b)

(c)

Fig. 2: (a) (3, 3) AS; (b) (4, 2) AS; (c) two non-isomorphic configurations for (5, 3) AS.

III. A G ENERAL A PPROACH FOR THE E NUMERATION OF P ROBLEMATIC O BJECTS
In this section, we introduce our new approach to enumerate combinatorial objects in the
graph of SC codes. This approach can be applied to SC codes with any underlying CB code,
partitioning, memory, and column weight. Our main result is stated in Theorem 1. We first state
the necessary auxiliary results and definitions.
Definition 3. Consider an SC code with parameters p, κ, γ, m, and L. The replica Rr , r ∈
{1, · · · , L}, is a collection of columns in the matrix HSC and is defined as:
Rr = HSC [0 : (L + m)γp − 1][(r − 1)κp : rκp − 1].

(1)

Fig. 1 illustrates the replicas on the parity-check matrix HSC of an SC code. The notation
HSC [ρ1 : ρ2 ][ν1 : ν2 ] refers to a submatrix of HSC with rows {ρ1 , ρ1 + 1, · · · , ρ2 } and columns
{ν1 , ν1 + 1, · · · , ν2 }. Because of the structure of SC codes, the non-zero part of Rr is the same
for any r ∈ {1, · · · , L}:
Rr [(r − 1)γp : (r + m)γp − 1][0 : κp − 1] = [HT0 HT1 · · · HTm ]T .

(2)

Remark 1. Each VN corresponds to one unique column and each CN corresponds to one unique
row in the parity-check matrix. We thus interchangeably say that an (a, b) AS/TS exists in the
matrix/ exists in the graph of the code.
DRAFT

February 20, 2018

SUBMITTED PAPER

7

Let the shortest path that connects any two VNs of an (a, b) AS/TS include at most λ VNs.
Given the configuration of an AS/TS, one can find the parameter λ by known methods, e.g.,
Dijkstra’s algorithm. In the case that there exists at least one cycle that spans all VNs, λ is
 
upper-bounded by a2 + 1 (see [13]). We say two VNs are adjacent if they are connected via
a CN. A (3, 3(γ − 2)) AS/TS has λ = 2, because any two VNs are adjacent.
Lemma 1. For an SC code with memory m, all VNs of an (a, b) AS/TS belong to at most χ
consecutive replicas, where
χ = (λ − 1)m + 1.

(3)

Proof: As we can see in Fig. 1, the maximum number of consecutive replicas with the
property that their non-zero parts have some row group indices in common is (m + 1). As a
result, any two adjacent VNs must be within at most (m + 1) consecutive replicas. Among the
VNs of the (a, b) AS, let v1 be the VN with the lowest index (the index of the corresponding
column in HSC ), and vf be the VN with the highest index. These two VNs are connected on
a shortest path that includes at most λ VNs. These VNs belong to at most λ different replicas,
and there can be at most (m − 1) different replicas between the replicas in which two adjacent
VNs exist. Consequently, v1 and vf must belong to a window of at most χ consecutive replicas,
where χ is defined as follows: χ = (λ − 1)(m − 1) + λ = (λ − 1)m + 1. The rest of VNs of
the AS/TS must also belong to these χ consecutive replicas since they have indices between v1
and vf .
We say an (a, b) AS/TS starts in replica Rr if among all it’s VNs, the one with the lowest
associated column index belongs to Rr .
Definition 4. The matrix Πkr , r ∈ {1, · · · , L} and k ∈ {1, · · · , L − r + 1}, is a submatrix of
HSC , and is defined as follows:
k
k
Πkr = HSC [ukr,1 : ukr,2 ][vr,1
: vr,2
],

February 20, 2018

ukr,1 = (r − 1)γp,

ukr,2 = (r + m + k − 1)γp − 1,

k
vr,1
= (r − 1)κp,

k
vr,2
= (r + k − 1)κp − 1.

(4)

DRAFT

8

IEEE TRANSACTIONS ON COMMUNICATIONS

Lemma 2. For an (a, b) AS/TS that starts in replica Rr and spans k consecutive replicas, all VNs
and all their neighboring CNs have corresponding row and column indices within the submatrix
Πkr of HSC .
Proof: An AS/TS that starts in replica Rr and spans k consecutive replicas must have its
VNs in the replicas {Rr , · · · , Rr+k−1 }. Based on (1) and (2), the smallest submatrix of HSC
that spans all non-zero parts of these r replicas is Πkr .
Theorem 1. Consider an SC code with parameters m and L. Let F be the total number of
(a, b) ASs/TSs, and F1k be the number of (a, b) ASs/TSs that start in R1 and span k consecutive
replicas,
F =

χ
X

(L − k + 1)F1k .

(5)

k=1

Proof: By summing up the number of (a, b) ASs/TSs over all possible starting replicas and
spanning sizes, the total number of (a, b) ASs/TSs can be written as:
F =

χ L−k+1
X
X
k=1

According to Lemma 2,

Frk

Frk .

(6)

r=1

is equivalent to the number of objects of interest inside matrix Πkr .

Consider the matrix Πkr+1 , r ∈ {1, · · · , L − k}:
k
k
Πkr+1 = HSC [ukr+1,1 : ukr+1,2 ][vr+1,1
: vr+1,2
],

ukr+1,1 = ukr,1 + γp,

ukr+1,2 = ukr,2 + γp,

k
k
vr+1,1
= vr,1
+ κp,

k
k
vr+1,2
= vr,2
+ κp.

Because of the repetitive structure of SC codes (see also Fig. 1), the following equality holds
for the parity-check matrix HSC :
HSC [i + pγ][j + pκ] = HSC [i][j].
Then,
k
k
k
k
Πkr+1 = HSC [ukr,1 + γp : ukr,2 + γp][vr,1
+ κp : vr,2
+ κp] = HSC [ukr,1 : ukr,2 ][vr,1
: vr,2
] = Πkr .

Consequently,
k
Πkr+1 = Πkr =⇒ Fr+1
= Frk .
DRAFT

February 20, 2018

SUBMITTED PAPER

9

By means of induction, we can infer that:
Frk = F1k

∀r ∈ {1, 2, · · · , L − k + 1}.

(7)

Combining (6) and (7), yields the final result in (5).
The utility of Theorem 1 is to significantly reduce the search size by seeking the enumeration
over Πk1 , k ∈ {1, · · · , χ}, rather than HSC ; the latter can be easily computed even with an
exhaustive search. In Section IV, we present a new scheme to efficiently find the quantities F1k ’s
for the protograph of SC codes (SC codes with p = 1).
IV. F INITE -L ENGTH C ONSTRUCTION OF SC CODES
For CB codes simulated over AWGN channels, certain types of ASs are dominant in the error
floor regime. For γ = 3 codes, (3, 3), (4, 2), and (5, 3) ASs are the dominant objects [12], [22],
see Fig. 2. For γ = 4 codes, the dominant objects are (4, 4) and (6, 4) ASs [12], [22]. There are
several non-isomorphic configurations for the (6, 4) AS. The configuration of (4, 4) AS and one
of the configurations of (6, 4) AS are illustrated in Fig. 3. For γ = 5 codes, the dominant objects
are (4, 8) and (8, 6) ASs [22]. The configuration of (4, 8) AS and one of the configurations of
(8, 6) AS are illustrated in Fig. 4.
According to Figs 2-4, our extensive simulations, and the literature [12], [22], (3, 3(γ − 2))
AS/TSs appear as the subgraph of dominant problematic configurations for CB codes with
column weight γ. We call the (3, 3(γ − 2)) AS/TS the common denominator, which is a cycle
of length 6 (cycle-6). For γ = 3, 4, and 5, the common denominators are (3, 3) AS, (3, 6)
TS, and (3, 9) TS, respectively. In order to design high performance SC codes, we seek to
significantly reduce the number of dominant ASs. To efficiently perform this task, we aim at
minimizing the number of common denominator instances. In fact, by minimizing the population
of the common denominator instances as sub-structures, we reduce the number of all superstructures and improve the code performance. Moreover, the common denominator has a simpler
combinatorial characteristics, and thus it is easier to locate and operate on.
In this section, we present a two-stage framework to design high performance SC codes.
February 20, 2018

DRAFT

10

IEEE TRANSACTIONS ON COMMUNICATIONS

(a)

(b)

(c)

Fig. 3: (a) (4, 4) AS; (b) one configuration for (6, 4) AS; (c) (3, 6) TS as the common denominator.

(a)

(b)

(c)

Fig. 4: (a) (4, 8) AS; (b) one configuration for (8, 6) AS; (c) (3, 9) TS as the common denominator.

1) In the first stage, we operate on the protograph of the SC code, and express the number of
cycles-6 in terms of the overlap parameters, which characterize the partitioning of the block
code. Then, we solve this discrete optimization problem to determine the optimal overlap
parameters. We call this new partitioning scheme the optimal overlap (OO) partitioning.
2) In the second stage, given the optimal partitioning obtained in the first stage, we apply a
new heuristic program to optimize the circulant powers of the underlying block code to
further reduce the number of cycles-6 in the graph of the SC code. We call this heuristic
program the circulant power optimizer (CPO).
The next two subsections describe these stages in details.
A. The Optimal Overlap Partitioning Scheme
We propose a novel combinatorial scheme, called Optimal Overlap (OO), for partitioning the
underlying block code and constructing SC codes. In OO partitioning, the resulting components
do not necessarily each comprise a contiguous set of circulants. This property is in contrast
with the scheme of partitioning with cutting vectors in which components – by design – have
DRAFT

February 20, 2018

SUBMITTED PAPER

11

large overlaps [11], [12], which is an undesirable feature for the finite-length design as we show
later. For constructing SC codes, we partition κγ circulants of an underlying code into (m + 1)
components, and piece copies of them together to construct an SC code. The ultimate goal in the
partitioning step is to construct SC codes that have the minimum number of problematic objects
(cycles-6). This is achieved via a careful selection of the overlap parameters, as we show here.
The protograph of a CB matrix, Hp , is the matrix resulting from replacing each p×p non-zero
circulant in H with 1, and each p × p zero circulant with 0. The protographs of H0 , H1 , · · · ,
Hm are Hp0 , Hp1 , · · · , Hpm , respectively, and they are all of size γ × κ. The protograph of HSC
is HpSC , and it is of size (L + m)γ × Lκ. This HpSC also has L replicas, Rr , 1 ≤ r ≤ L, but
with 1 × 1 circulants. The procedure of generating HSC from HpSC is called lifting.
A cycle-6 in the graph of HpSC (the protograph of the SC code), which is defined by the
non-zero entries {(h1 , l1 ), (h1 , l2 ), (h2 , l2 ), (h2 , l3 ), (h3 , l3 ), (h3 , l1 )} in HpSC , results in p cycles-6
in the graph of HSC if and only if [23], [24]:
fh1 ,l1 + fh2 ,l2 + fh3 ,l3 ≡ fh1 ,l2 + fh2 ,l3 + fh3 ,l1 (mod p),

(8)

where fh,l is the power of the circulant indexed by (h, l) in HpSC . Otherwise, this cycle results
in 0 cycle-6 in the graph of HSC [23], [24]. Moreover, a cycle-6 in the final (lifted) graph of
an SC code can only be generated from a cycle-6 in the protograph.
Motivated by the above fact, our OO partitioning aims at deriving the overlap parameters of
Hp that result in the minimum number of common denominator instances in the graph of HpSC ,
which is the protograph of the SC code. Then, we run the CPO to further reduce the number
of common denominator instances in the graph of HSC by breaking the condition in (8) for as
many cycles in the optimized graph of HpSC as possible.
The goal here is to minimize the number of cycles-6 in the protograph of the SC code via
the OO partitioning of Hp , which is also the OO partitioning of H. To achieve this goal, we
establish a discrete optimization problem by expressing the number of cycles-6 in the graph of
HpSC as a function of the overlap parameters and standard code parameters. We first introduce
February 20, 2018

DRAFT

12

IEEE TRANSACTIONS ON COMMUNICATIONS

the overlap parameters:
1
Definition 5. From Definition 4, Π1,p
1 of size (m + 1)γ × κ is the protograph of matrix Π1 =

[HT0 · · · HTm ]T . A degree-d overlap t{i1 ,··· ,id } , 0 ≤ i1 , · · · , id < (m + 1)γ, is defined as the overlap
among d distinct rows of Π1,p
1 specified by the set {i1 , · · · , id }, i.e., the number of positions in
which all the d rows have 1’s simultaneously. A degree-1 overlap ti1 , 0 ≤ i1 < (m + 1)γ, is
defined as the number of 1’s in row i1 of Π1,p
1 .
Remarks 2 and 3 discuss the properties of the overlap parameters in Definition 5.
Remark 2. For an SC code with column weight γ, the maximum degree for an overlap parameter
with non-zero value is γ. This is simply because there are exactly γ 1’s in any column of Π1,p
1 ,
thus there is no position in a set of d > γ rows such that all the rows have 1’s simultaneously.
Remark 3. Consider a set of rows {i1 , · · · , id } of Π1,p
and d > 1. If there is at least one
1
pair of distinct row indices (iu , iv ) such that iu , iv ∈ {i1 , · · · , id } and iu ≡ iv (mod γ); then,
t{i1 ,··· ,id } = 0. This is because of the fact that the matrix Hp is partitioned into Hp0 , · · · , Hpm ,
thus there is zero overlap between similar rows of (protographs of) component matrices.
Based on Definition 5 and Remarks 2 and 3, the set of non-zero overlap parameters is:
O = {t{i1 ,··· ,id } |1 ≤ d ≤ γ, 0 ≤ i1 , · · · , id < (m+1)γ, ∀{iu , iv } ⊂ {i1 , · · · , id } iu 6≡ iv (mod γ)}.
(9)
Example 1. For an SC code with γ = 3 and m = 1, the set of non-zero overlap parameters is:
O = {t{i1 ,··· ,id } |1 ≤ d ≤ 3, 0 ≤ i1 , · · · , id < 6, ∀{iu , iv } ⊂ {i1 , · · · , id } iu 6≡ iv (mod 3)}
= {t0 , t1 , t2 , t3 , t4 , t5 , t{0,1} , t{0,2} , t{0,4} , t{0,5} , t{1,2} , t{1,3} , t{1,5} , t{2,3} , t{2,4} , t{3,4} , t{3,5} , t{4,5} ,
t{0,1,2} , t{0,1,5} , t{0,2,4} , t{0,4,5} , t{1,2,3} , t{1,3,5} , t{2,3,4} , t{3,4,5} }.
There are 26 non-zero overlap parameters.
The non-zero overlap parameters in (9) are not independent. In fact, some overlap parameters
are linear combinations of other overlap parameters. Lemma 3 introduces independent non-zero
overlap parameters. As we see later in this section, the number of cycles-6 can be expressed in
DRAFT

February 20, 2018

SUBMITTED PAPER

13

terms of the overlap parameters. Thus, the significance of Lemma 3 is to reduce the complexity
of the discrete optimization problem that specifies the optimum values for the overlap parameters,
and consequently, the optimal partitioning.
Lemma 3. The set of independent non-zero overlap parameters Oind is:
Oind = {t{i1 ,··· ,id } |1 ≤ d ≤ γ, 0 ≤ i1 , · · · , id < mγ, ∀{iu , iv } ⊂ {i1 , · · · , id } iu 6≡ iv (mod γ)}.
(10)
The other overlap parameters not included in Oind are either zero or functions of the overlap
parameters in Oind . Let 0 ≤ i1 , · · · , id1 < mγ, mγ ≤ j1 , · · · , jd2 < (m+1)γ, and 1 ≤ (d1 +d2 ) ≤
γ. Then, t{i1 ,··· ,id1 ,j1 ,··· ,jd2 } ∈ O \ Oind is a linear function of the overlap parameters in Oind :

d2
P
P



t
+
(−1)α
tI∪{x1 γ+j 0 ,··· ,xα γ+jα0 } , I =
6 ∅,
I

1

0 }⊂J

α=1
{j10 ,··· ,jα


[x1 ,··· ,xα ]∈{0,··· ,m−1}α
t{i1 ,··· ,id1 ,j1 ,··· ,jd2 } =
(11)
d
2
P
P

α

κ
+
(−1)
,
I
=
∅,
t
0

0 }
{x1 γ+j1 ,··· ,xα γ+jα

0 }⊂J

α=1
{j10 ,··· ,jα



[x1 ,··· ,xα ]∈{0,··· ,m−1}α
where I = {i1 , · · · , id1 }, J = {j1 , · · · , jd2 }, and j = (j mod γ).
We note that row xγ +j, where x ∈ {0, · · · , m−1} and j ∈ J , belongs to the x’th component
1,p
matrix of Π1,p
1 , and corresponds to row j of Π1 .

Proof: The proof is given in Appendix A.
Example 2. The set of independent non-zero overlap parameters for an SC code with parameters
m = 1 and γ = 3 is:
Oind = {t0 , t1 , t2 , t{0,1} , t{0,2} , t{1,2} , t{0,1,2} }.
According to (11), the overlap parameters not in Oind are functions of the 7 overlap parameters
in Oind as follows:
t3 = κ − t0 ,

t{3,4} = κ − t0 − t1 + t{0,1} ,

t4 = κ − t1 ,

t{3,5} = κ − t0 − t2 + t{0,2} ,

t5 = κ − t2 ,

t{4,5} = κ − t1 − t2 + t{1,2} ,

February 20, 2018

DRAFT

14

IEEE TRANSACTIONS ON COMMUNICATIONS

t{0,4} = t0 − t{0,1} ,

t{0,1,5} = t{0,1} − t{0,1,2} ,

t{0,5} = t0 − t{0,2} ,

t{0,2,4} = t{0,2} − t{0,1,2} ,

t{1,3} = t1 − t{0,1} ,

t{0,4,5} = t0 − t{0,1} − t{0,2} + t{0,1,2} ,

t{1,5} = t1 − t{1,2} ,

t{1,2,3} = t{1,2} − t{0,1,2} ,

t{2,3} = t2 − t{0,2} ,

t{1,3,5} = t1 − t{0,1} − t{1,2} + t{0,1,2} ,

t{2,4} = t2 − t{1,2} ,

t{2,3,4} = t2 − t{0,2} − t{1,2} + t{0,1,2} ,

t{3,4,5} = κ − t0 − t1 − t2 + t{0,1} + t{0,2} + t{1,2} − t{0,1,2} .
Lemma 4 describes the number of elements in Oind .
Lemma 4. The number of independent non-zero overlap parameters described in Lemma 3 is:
 
γ
X
d γ
Nind = |Oind | =
m
.
(12)
d
d=1
Proof: The set Oind can be partitioned into γ disjoint subsets as follows:
γ
[
d
Oind =
Oind
,
(13)

d=1
d
Oind
= {t{i1 ,··· ,id } |0 ≤ i1 , · · · , id < mγ, ∀{iu , iv } ⊂ {i1 , · · · , id } iu 6≡ iv (mod γ)}.

Consequently,
Nind =

γ
X

k
|Oind
|.

(14)

d=1
d
According to (13), |Oind
| is the number of subsets of the set S = {0, 1, · · · , mγ − 1} with size

d such that no two elements in the same subset have the same values mod γ. We first partition
the set S as follows:
S = {0, γ, · · · , (m−1)γ}∪{1, γ +1, · · · , (m−1)γ +1}∪· · ·∪{γ −1, 2γ −1, · · · , mγ −1}. (15)
All elements of a partition in (15) have the same value mod γ. Thus, we have to pick at most
one element from each partition to form a subset with the specified characteristics. For choosing
{i1 , · · · , id } such that all conditions in (13) are satisfied, we first choose d partitions from γ
partitions in (15), and then we choose one element from each partition (all partitions are of size


P
d
m). As a result, |Oind
| = md γd and Nind = γd=1 md γd .
DRAFT

February 20, 2018

SUBMITTED PAPER

15

Fig. 5: Examples of cycles-6 on HpSC with parameters κ = 5, γ = 3, m = 2, L = 3. The cycles with solid lines, dash lines,
and dash-dot lines are spanning one, two, and three replicas, respectively. Component matrices are illustrated in gray.

Example 3. The number of independent non-zero overlap parameters for γ = 3 and m = 1
is |Oind | = 7, while the number of non-zero overlap parameters is |O| = 26 (see Example 1
and 2). This comparison shows the importance of Lemma 3 in reducing the size of necessary
overlap parameters. This number, as we show later, determines the size of a discrete optimization
problem that produces optimal partitioning.
Next, we show that the number of common denominator instances for a protograph of an
SC code can be expressed as a function of the independent non-zero overlap parameters, i.e.,
Oind . As we noted, a cycle-6 is the common denominator of several problematic objects for CB
codes with different column weights over AWGN channels. A cycle-6 is formed of three distinct
overlaps, and each overlap corresponds to one VN in the graph of the code, see Fig. 5.
Lemma 5. Consider the protograph of an SC code with parameters m, L, and O, and let
[x]+ = max{x, 0}. We partition cycles-6 with specific CNs into three categories, and enumerate
them separately. Three VNs of a cycle-6 belong to one, two, or three different replicas. Let the
cycle-6 starts in Rr and c1 = (r − 1)γ + i1 , c2 = (r − 1)γ + i2 , and c3 = (r − 1)γ + i3 be CNs.
1) The number of cycles-6 with all VNs in one replica, say Rr , and CNs c1 , c2 , and c3 , is:
A(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 ,i3 } ) = t{i1 ,i2 ,i3 } [t{i1 ,i2 ,i3 } − 1]+ [t{i2 ,i3 } − 2]+
+ t{i1 ,i2 ,i3 } (t{i1 ,i3 } − t{i1 ,i2 ,i3 } )[t{i2 ,i3 } − 1]+



+





(16)
+ (t{i1 ,i2 } − t{i1 ,i2 ,i3 } )t{i1 ,i2 ,i3 } [t{i2 ,i3 } − 1]


+ (t{i1 ,i2 } − t{i1 ,i2 ,i3 } )(t{i1 ,i3 } − t{i1 ,i2 ,i3 } )t{i2 ,i3 } .
February 20, 2018

DRAFT

16

IEEE TRANSACTIONS ON COMMUNICATIONS

2) The number of cycles-6 with VNs in two replicas, say two VNs in Rr and one VN in Rq ,
and CNs c1 , c2 , and c3 , is:
B(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 +(r−q)γ,i3 +(r−q)γ} )
= t{i1 ,i2 ,i3 } [t{i1 ,i3 } − 1]+ t{i2 +(r−q)γ,i3 +(r−q)γ}



(17)


+ (t{i1 ,i2 } − t{i1 ,i2 ,i3 } )t{i1 ,i3 } t{i2 +(r−q)γ,i3 +(r−q)γ} ,
where c2 and c3 are the CNs connected via the VN that belongs to Rq .
3) The number of cycles-6 with VNs in three replicas, say Rr and Rq and Rs (r < q < s),
and CNs c1 , c2 , and c3 , is:
C(t{i1 ,i2 } , t{i1 +(r−q)γ,i3 +(r−q)γ} , t{i2 +(r−s)γ,i3 +(r−s)γ} )
(18)
=t{i1 ,i2 } t{i1 +(r−q)γ,i3 +(r−q)γ} t{i2 +(r−s)γ,i3 +(r−s)γ} ,
where c1 and c2 are connected via the VN that belongs Rr , c1 and c3 are connected via
the VN that belongs to Rq , and c2 and c3 are connected via the VN that belongs to Rs .
Proof: The proof is given in Appendix B.
Remark 4. For the enumeration of cycles-6, we only need overlap parameters of at most degree
three, since the three constituent overlaps of a cycle-6 are defined over the three rows involved
in the cycle regardless of the column weight.
Theorem 2 expresses the number of cycles-6 in the protograph of an SC code as a function
the overlap parameters. We recall that given the independent non-zero overlap parameters, the
rest of non-zero overlap parameters can be found using Lemma 3, and i = (i mod γ).
Theorem 2. The number of cycles-6 in the protograph of an SC code with parameters κ, γ, m,
L, and Oind is:
F =

m+1
X

(L − k + 1)F1k ,

(19)

k=1

and

F1k ,

DRAFT

1 ≤ k ≤ (m + 1), is formulated as follows:

February 20, 2018

SUBMITTED PAPER

17

X

F11 =

A(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 ,i3 } ).

{i1 ,i2 ,i3 }⊂{0,··· ,(m+1)γ−1}
i1 6=i2 ,i1 6=i3 , i2 6=i3

X

F12 =

B(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 −γ,i3 −γ} )

i1 ∈{0,··· ,(m+1)γ−1}
{i2 ,i3 }⊂{γ,··· ,(m+1)γ−1}
i1 6=i2 ,i1 6=i3 , i2 6=i3

X

+

B(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 +γ,i3 +γ} ).

i1 ∈{0,··· ,(m+1)γ−1}
{i2 ,i3 }⊂{0,··· ,mγ−1}
i1 6=i2 ,i1 6=i3 , i2 6=i3

X

F1k≥3 =

B(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 +(1−k)γ,i3 +(1−k)γ} )

(20)

i1 ∈{0,··· ,(m+1)γ−1}
{i2 ,i3 }⊂{(k−1)γ,··· ,(m+1)γ−1}
i1 6=i2 ,i1 6=i3 , i2 6=i3

X

+

B(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 +(k−1)γ,i3 +(k−1)γ} )

i1 ∈{0,··· ,(m+1)γ−1}
{i2 ,i3 }⊂{0,··· ,(m−k+2)γ−1}
i1 6=i2 ,i1 6=i3 , i2 6=i3

+

k−1
X

X

C(t{i1 ,i2 } , t{i1 +(1−q)γ,i3 +(1−q)γ} , t{i2 +(1−k)γ,i3 +(1−k)γ} )

q=2 i1 ∈{(q−1)γ,··· ,(m+1)γ−1}
i2 ∈{(k−1)γ,··· ,(m+1)γ−1}
i3 ∈{(k−1)γ,··· ,(m+q)γ−1}
i1 6=i2 ,i1 6=i3 , i2 6=i3

The functions A, B, and C are defined in Lemma 5.
Proof: The proof is given in Appendix C.
Now, define F ∗ to be the minimum number of cycles-6 for HpSC . Thus, our discrete optimization problem is formulated as follows:
F ∗ = min F.
Oind

(21)

The constraints of our optimization problem are the conditions under which the overlap parameters are valid.
Example 4. For an SC code with parameters γ = 3, and m = 1, the constraints of the
optimization problem in (21) are the conditions under which the independent non-zero overlap
parameters are valid. Thus, these constraints on the 7 parameters are (see Example 2):

February 20, 2018

DRAFT

18

IEEE TRANSACTIONS ON COMMUNICATIONS

0 ≤ t0 ≤ κ,

0 ≤ t{0,1} ≤ t0 ,

t{0,1} ≤ t1 ≤ κ − t0 + t{0,1} ,

0 ≤ t{0,1,2} ≤ t{0,1} ,

t{0,1,2} ≤ t{0,2} ≤ t0 − t{0,1} + t{0,1,2} , t{0,1,2} ≤ t{1,2} ≤ t1 − t{0,1} + t{0,1,2} ,

(22)

t{0,2} + t{1,2} − t{0,1,2} ≤ t2 ≤ κ − t0 − t1 + t{0,1} + t{0,2} + t{1,2} − t{0,1,2} ,
b 3κ
c ≤ t0 + t1 + t2 ≤ d 3κ
e.
2
2
The last constraint in (22) guarantees balanced partitioning between Hp0 and Hp1 .
Consider an underlying block code with parameters κ and γ. Each circulant of the paritycheck matrix H of this code can belong to any of (m + 1) components, leading to (m + 1)κγ
possible s. We want to choose a partitioning that results in the least number of cycles-6 in
the protograph of an SC code. Considering all possible ways of partitioning in a brute force
fashion to find the optimal one is not practical. We reduced the problem of finding an optimum
partitioning for the protograph of an SC code, which results in the minimum number of cycles-6,
into an optimization problem over a number of overlap parameters described in (10). Example 5
summarizes all necessary steps for finding the optimal partitioning of an SC code with parameters
κ, γ = 3, m = 1, and L.
Example 5. Using Theorem 2, the number of cycles-6 in the protograph of an SC code with
parameters κ, γ = 3, m = 1, and L is described in terms of the 7 overlap parameters in
Oind = {t0 , t1 , t2 , t{0,1} , t{0,2} , t{1,2} , t{0,1,2} }:
F = LF11 + (L − 1)F12 ,
where F11 and F12 are:
F11 = A(t{0,1,2} , t{0,1} , t{0,2} , t{1,2} ) + A(t{0,1,5} , t{0,1} , t{0,5} , t{1,5} ) + A(t{0,2,4} , t{0,2} , t{0,4} , t{2,4} )
+ A(t{0,4,5} , t{0,4} , t{0,5} , t{4,5} ) + A(t{1,2,3} , t{1,2} , t{1,3} , t{2,3} ) + A(t{1,3,5} , t{1,3} , t{1,5} , t{3,5} )
+ A(t{2,3,4} , t{2,3} , t{2,4} , t{3,4} ) + A(t{3,4,5} , t{3,4} , t{3,5} , t{4,5} ),
(23)
DRAFT

February 20, 2018

SUBMITTED PAPER

19

F12 = B(t{0,4,5} , t{0,4} , t{0,5} , t{1,2} ) + B(t{3,4,5} , t{3,4} , t{3,5} , t{1,2} ) + B(t{1,3,5} , t{1,3} , t{1,5} , t{0,2} )
+ B(t{3,4,5} , t{3,4} , t{4,5} , t{0,2} ) + B(t{2,3,4} , t{2,3} , t{2,4} , t{0,1} ) + B(t{3,4,5} , t{3,5} , t{4,5} , t{0,1} )
+ B(t{0,1,2} , t{0,1} , t{0,2} , t{4,5} ) + B(t{1,2,3} , t{1,3} , t{2,3} , t{4,5} ) + B(t{0,1,2} , t{0,1} , t{1,2} , t{3,5} )
+ B(t{0,2,4} , t{0,4} , t{2,4} , t{3,5} ) + B(t{0,1,2} , t{0,2} , t{1,2} , t{3,4} ) + B(t{0,1,5} , t{0,5} , t{1,5} , t{3,4} ).
(24)
We note that all the overlap parameters in (23) and (24) are linear combinations of the 7
independent non-zero overlap parameters in Oind , see Example 2. The functions A and B are
defined in Lemma 5. Our discrete optimization problem is formulated as follows:
F∗ =

min

t0 ,t1 ,t2 ,t{0,1} ,t{0,2} ,t{1,2} ,t{0,1,2}

F.

(25)

The constraints of the optimization problem are found in Example 4. The solution of our
optimization problem is not unique. However, since all the solutions result in the same number
of OO partitioning choices and the same F ∗ , we work with one of these solutions, and call it
i
h
an optimal vector, t∗ = t∗0 , t∗1 , t∗2 , t∗{0,1} , t∗{0,2} , t∗{1,2} , t∗{0,1,2} .
B. Circulant Power Optimization
After picking an optimal vector t∗ to partition Hp and construct HpSC , we run our heuristic
CPO to further reduce the number of (3, 3(γ −2)) ASs/TSs (the common denominator instances)
in the graph of HSC with column weight γ. Recall that in codes that have no cycle-4, a cycle-6
is a (3, 3(γ − 2)) AS/TS. The steps of the CPO are:
1) Initially, assign circulant powers as in AB codes, i.e., fi,j = ij, 0 ≤ i ≤ γ − 1 and
0 ≤ j ≤ κ − 1, to all the γκ 1’s in Hp (results in no cycle-4 in H and HSC ).
2) Construct Πχ,p
1 , which contains χ = m + 1 replicas and has the size (2m + 1)γ × (m + 1)κ
(see Definition 4), using Hp and t∗ . (Recall that the VNs of a cycle-6 span at most
χ = m + 1 consecutive replicas.) Circulant powers of the 1’s in Πχ,p
are copied from the
1
1’s in Hp .
February 20, 2018

DRAFT

20

IEEE TRANSACTIONS ON COMMUNICATIONS

3) Define a counting variable θi,j , 0 ≤ i ≤ γ − 1 and 0 ≤ j ≤ κ − 1, for each of the 1’s in Hp .
Define another counting variable θi00 ,j 0 , 0 ≤ i0 ≤ (2m + 1)γ − 1 and 0 ≤ j 0 ≤ (m + 1)κ − 1,
for each of the elements in Πχ,p
1 . Initialize all the variables in this step with zeros. Notice
that only (m + 1)γκ counting variables of the form θi00 ,j 0 are associated with 1’s in Πχ,p
1
(the remaining counting variables will remain zeros).
4) Locate all the cycles-4 and cycles-6 in Πχ,p
1 .
5) Specify the cycles-6 in Πχ,p
that have (8) satisfied, and call them active cycles. Let F1k,a ,
1
k ∈ {1, . . . , m + 1}, be the number of active cycles starting at the first replica and having
their VNs spanning k consecutive replicas in Πχ,p
1 . Thus, from (5), the number of active
cycles having their VNs spanning k consecutive replicas in Πχ,p
is (m − k + 2)F1k,a . (For
1
example, for k = 1, (m + 1)F11,a is the number of active cycles having their VNs spanning
one replica in Πχ,p
1 .)
6) Compute the number of (3, 3(γ − 2)) ASs/TSs in HSC using the following formula (see
(5) and (8)):
FSC =

m+1
X

(L − k +

1)F1k,a



p.

(26)

k=1

7) Count the number of active cycles each 1 in Πχ,p
is involved in. Assign weight wk =
1
(m+1)/(m−k+2) to the number of active cycles having their VNs spanning k consecutive
replicas in Πχ,p
1 (see Remark 5 for more clarification). Store the weighted count associated
0 0
0
with each 1 in Πχ,p
1 , which is indexed by (i , j ), in θi0 ,j 0 . (For example, for k = m + 1,

the weight of the number of active cycles having their VNs spanning m + 1 consecutive
replicas is (m + 1).)
8) Calculate the counting variables θi,j , ∀i, j, associated with the 1’s in Hp from the counting
variables θi00 ,j 0 associated with the 1’s in Πχ,p
(computed in step 7) using the following
1
formula:
θi,j =

DRAFT

X

X

i0 :i0γ =i

j 0 :jκ0 =j
0
0
Πχ,p
1 [i ][j ]6=0

θi00 ,j 0 ,

(27)

February 20, 2018

SUBMITTED PAPER

21

where i0γ = (i0 mod γ) and jκ0 = (j 0 mod κ). Sort these γκ 1’s of Hp in a list descendingly according to the counts in θi,j , ∀i, j.
9) Pick a subset of 1’s from the top of this list, and change the circulant powers associated
with them.
10) Using these interim new powers, do steps 5 and 6.
11) If FSC is reduced while maintaining no cycle-4 in HSC , update FSC and the circulant
powers, then go to step 7. Otherwise, return to step 9 to pick a different set of circulant
powers or/and a different subset of 1’s (from the 1’s in Hp ).
12) Iterate until the target FSC (set by the designer) is achieved, or the CPO gain in FSC
approaches zero.
Note that step 9 is performed heuristically.
Remark 5. A cycle-6 starting at the first replica and spanning k consecutive replicas is repeated
exactly (m−k +2) times, ∀k ∈ {1, . . . , m+1}, in Πχ,p
1 . Here, we assume that L >> χ−1 = m,
which is the case for practical settings. Consequently, cycles spanning k consecutive replicas,
∀k ∈ {1, . . . , m + 1}, should be treated the same way in steps 7 and 8 in the CPO algorithm;
because they have approximately the same contribution to FSC in (26). In order to perform this
task, a cycle spanning k consecutive replicas, which involves a 1 in Πχ,p
indexed by (i0 , j 0 ), is
1
counted exactly (m − k + 2)wk = (m + 1) times in θi00 ,j 0 (and in the corresponding θi,j ), leading
to the weighting factors used in steps 7 and 8.
Remark 6. A (3, b0 ) configuration, where b0 <= 3(γ − 2), in the protograph of the SC code
can result in (3, 3(γ − 2)) ASs/TSs in the final (lifted) graph depending on the circulant power
arrangement. That is the reason why we enumerate all cycles-6 (even those that are (3, b0 )
configurations, b0 < 3(γ − 2)) in the protograph, and minimize their number. Note that typically
the protograph does have cycles-4.
Example 6. Suppose we want to design an SC code with κ = p = 7, γ = 4, m = 1, and L = 30
February 20, 2018

DRAFT

22

IEEE TRANSACTIONS ON COMMUNICATIONS

(a)

(b)

p

Fig. 6: (a) The OO partitioning of H (or H) of the SC code in Example 6. Entries with circles (resp., squares) are assigned
to Hp0 (resp., Hp1 ); (b) The circulant power arrangement for the circulants in Hp .

using OO-CPO (OO partitioning and CPO algorithm). Solving the optimization problem in (21)
yields the following optimal overlap parameters:


t∗ = t∗0 , t∗1 , t∗2 , t∗3 , t∗{0,1} , t∗{0,2} , t∗{0,3} , t∗{1,2} , t∗{1,3} , t∗{2,3} , t∗{0,1,2} , t∗{0,1,3} , t∗{0,2,3} , t∗{1,2,3}
= [3, 4, 3, 4, 0, 1, 2, 2, 2, 0, 0, 0, 0, 0],
which results in F ∗ = 4, 680 cycles-6 in the graph of HpSC . Fig 6(a) shows how the partitioning
is applied on Hp (or H). Next, we apply the CPO algorithm to obtain the parity-check matrix
HSC . Fig 6(b) shows the circulant power arrangement of HSC using CPO algorithm. We note
that the uncoupled case with AB circulant power arrangement (H0 = H, H1 = 0, and fi,j = ij)
results in HSC with 35, 280 cycles-6, OO partitioning with AB circulant power arrangement
(only stage 1) results in HSC with 5, 747 cycles-6, and the OO-CPO approach (both stages)
results in HSC with 2, 870 cycles-6.
V. S IMULATION R ESULTS
In this section, we compare the error floor performance of SC codes constructed by the OOCPO framework with uncoupled block codes and SC codes constructed by the previous method
of partitioning by cutting vectors [11], [12]. First, we demonstrate the reduction of the number
of detrimental objects achieved by the OO-CPO framework via Table I. Then, we show the
performance gain via BER curves provided in Figs. 8 and 9. In our simulations, we consider
AWGN channels, and SC codes with memories m ∈ {1, 2} and γ ∈ {3, 4}.
All the codes we simulated are binary CB-SC codes with κ = p = 17, L = 30, length 8, 670
bits, and constructed by different methods. Uncoupled Codes 1 and 2 are uncoupled AB codes
(SC codes with m = 0, H0 = H, and fi,j = ij), and have γ = 3 and 4, respectively. SC Codes 13 have m = 1 and γ = 3, SC Codes 4-6 have m = 1 and γ = 4, and SC Codes 7 has m = 2
DRAFT

February 20, 2018

SUBMITTED PAPER

23

(a)

(b)

(c)
Fig. 7: OO partitioning (left panel) and circulant power arrangement obtained by CPO (right panel) for SC Codes 3, 6, and 7.
Subfigures are organized as follows: (a) SC Codes 3; (b) SC Codes 6; (c) SC Codes 7.

and γ = 3. SC Codes 1 and 4 are constructed by the optimal cutting vectors ζ = [4, 9, 13] and
[3, 7, 11, 15], respectively, and AB circulant powers [12]. SC Codes 2 and 5 are constructed by
OO partitioning and AB circulant powers. SC Codes 3, 6, and 7 are constructed by the OO-CPO
framework (see Fig. 7).
Table I shows the number of cycles 6 for Uncoupled Codes 1-2 and SC Codes 1-7. According
to our results, an SC code constructed by the optimal cutting vector, achieves about 57% reduction
in the number of cycles-6 ASs compared to the uncoupled case for m = 1 and γ ∈ {3, 4}. This
reduction becomes 80% when the memory is m = 2. When we apply our new OO-CPO approach
for m = 1 and γ ∈ {3, 4}, the reduction in the population of cycles-6 compared to the uncoupled
case reaches up to 89%, which is even better than the partitioning with optimal cutting vectors
with m = 2. For the OO-CPO approach with m = 2 and γ = 3, the number of cycles-6 (the
common denominator instances) is 0 which means all cycles-6 are removed using our approach,
and the girth of the code becomes 8. We present the results for κ = p = 17 in this section;
however, our simulation results (which we do not report here because of space limitation) show
similar gains for p = 7, p = 11, and p = 13 as well.
Next, we compare the performance of SC codes constructed using different methods over
AWGN channels. Fig 8(a) shows the BER curves in the error floor area for Uncoupled Codes 1
February 20, 2018

DRAFT

24

IEEE TRANSACTIONS ON COMMUNICATIONS

TABLE I: Comparison of the population of cycles-6 for SC codes with p = κ = 17, L = 30, and different construction schemes.
Construction scheme

m

Uncoupled case
AB circulant arrangement

–

Cutting vector partitioning
AB circulant arrangement

Optimal overlap partitioning
Circulant power optimization

γ

No. cycles 6

3

138, 720

4

554, 880

1

3

59, 024

2

3

27, 880

1

4

238, 697

1

3

14, 960

2

3

0

1

4

91, 494

and SC Codes 1-3. All these codes have κ = p = 17, γ = 3, m = 1, and L = 30. SC Code 1 is
constructed using the cutting vector partitioning, SC Code 2 is constructed by employing only
the first stage of our framework, and SC Code 3 is constructed by applying the two stages. The
figure demonstrates that our method outperforms the cutting vector scheme by more than 2 orders
of magnitude, and that each stage of the framework is necessary to achieve this improvement.
Fig 8(b) shows similar findings for γ = 4 SC codes. Based on our results, the performance improvement of our two-stage framework relative to the cutting vector scheme is more pronounced
when we increase the column weight. Additionally, SC Code 6 constructed by the OO-CPO
framework achieves nearly 5 orders of magnitude performance improvement in the early error
floor area and up to 1.5 dB SNR gain compared to the uncoupled setting.
Fig. 9 shows the BER performance in the error floor area for SC codes with parameters
κ = p = 17, γ = 3, L = 30, constructed by the OO-CPO framework, and for different memories.
Here, we consider the uncoupled case as an SC code with m = 0 (no coupling). As we see,
increasing the memory notably improves the error floor performance of SC codes.
VI. C ONCLUSION
In this paper, we presented a new combinatorial approach for the finite-length analysis and
design of circulant-based SC codes. We exploited the structure of SC codes to present a new
DRAFT

February 20, 2018

SUBMITTED PAPER

25

10 -4

10 0
Uncoupled Codes 1
SC Code 1, CV
SC Code 2, OO
SC Code 3, OO-CPO

10 -5

Uncoupled Codes 2
SC Code 4, CV
SC Code 5, OO
SC Code 6, OO-CPO

10 -2

10

-7

10

-8

10

10 -6

10 -9
10

-4

BER

BER

10 -6

-10

10

-8

10 -11
10 -12

5

5.5

6

6.5

10 -10

7

3

3.2

3.4

3.6

3.8

4

4.2

4.4

4.6

4.8

SNR (dB)

SNR (dB)

(a)

(b)

Fig. 8: BER Curves over AWGN channel for SC codes with length 8, 670 bits, memory m = 1, and constructed with different
methods: (a) γ = 3; (b) γ = 4.
10 -4
Uncoupled Codes 1, m=0
SC Code 3, OO-CPO, m=1
SC Code 7, OO-CPO, m=2

10 -5

BER

10 -6
10 -7
10 -8
10 -9
10 -10
10 -11

5

5.2

5.4

5.6

5.8

6

6.2

6.4

SNR (dB)

Fig. 9: BER Curves over AWGN channel for SC codes with length 8, 670 bits, γ = 3, and different memories.

methodology for the enumeration of combinatorial objects that can be applied to SC codes
constructed by a wide variety of partitioning schemes and memories. Next, we introduced a
novel partitioning scheme that operates on the protograph of an SC code to minimize the number
of detrimental objects. Then, we proposed a heuristic approach for circulant power optimization
that further reduces the population of these problematic objects in the final graph. The proposed
OO-CPO approach is an effective tool to construct SC codes that have a notably better error floor
performance over other existing construction techniques. A promising research direction is to
investigate the SC codes constructed by our new approach in modern dense storage applications.
VII. A PPENDICES
A. Proof of Lemma 3
Proof: From Definition 5, t{i1 ,··· ,id1 ,j1 ,··· ,jd2 } is the number of overlaps (column indices in
which all the rows {i1 , · · · , id1 , j1 , · · · , jd2 } in Π1,p
1 have 1’s simultaneously).
February 20, 2018

DRAFT

26

IEEE TRANSACTIONS ON COMMUNICATIONS

•

I=
6 ∅:
To have an overlap at position (column index) y ∈ {1, · · · κ}, 1) the rows in I of Π1,p
1 must
have 1’s at position y, 2) all rows in the first m component matrices of Π1,p
1 corresponding to
the rows in J must have 0’s at position y. In other words, the rows {x1 γ+j1 , · · · , xd2 γ+jd2 }
d2
of Π1,p
1 must have 0’s at position y, where [x1 , · · · , xd2 ] ∈ {0, · · · , m − 1} . Aided by the

principle of inclusion-exclusion:
tI∪J = tI +

d2
X

tI∪{x1 γ+j 0 ,··· ,xα γ+jα0 } .
1

0 }⊂J
{j10 ,··· ,jα
[x1 ,··· ,xα ]∈{0,··· ,m−1}α

α=1

•

X

(−1)α

I = ∅:
To have an overlap at position (column index) y ∈ {1, · · · κ}, all rows in the first m
component matrices of Π1,p
1 corresponding to the rows in J must have 0’s at position y.
In other words, the rows {x1 γ + j1 , · · · , xd2 γ + jd2 } of Π1,p
1 must have 0’s at position y,
where [x1 , · · · , xd2 ] ∈ {0, · · · , m − 1}d2 . Aided by the principle of inclusion-exclusion:
tJ = κ +

d2
X
α=1

X

(−1)α

0 }⊂J
{j10 ,··· ,jα
[x1 ,··· ,xα ]∈{0,··· ,m−1}α

t{x1 γ+j 0 ,··· ,xα γ+jα0 } .
1

B. Proof of Lemma 5
Proof: A cycle-6 is formed of three distinct overlaps as illustrated in Fig. 5. To avoid overcounting, we must consider degree-3 overlaps in order to guarantee that the overlaps of a cycle-6
that belong to one replica have distinct indices.
1) Because of the structure of SC codes, an overlap between rows ((r−1)γ+i1 , (r−1)γ+i2 ) in
Rr corresponds to an overlap between rows (i1 , i2 ) in Π1,p
1 . Similarly, an overlap between
rows ((r − 1)γ + i1 , (r − 1)γ + i3 ) in Rr corresponds to an overlap between rows (i1 , i3 )
in Π1,p
1 , and an overlap between rows ((r − 1)γ + i2 , (r − 1)γ + i3 ) in Rr corresponds to
an overlap between rows (i2 , i3 ) in Π1,p
1 . If t{i1 ,i2 ,i3 } = 0, the number of ways we can pick
the overlaps is t{i1 ,i2 } t{i1 ,i3 } t{i2 ,i3 } . Since we must consider the degree-3 overlap among
the rows i1 , i2 , and i3 of Π1,p
1 , we partition the enumeration into the following four cases:
DRAFT

February 20, 2018

SUBMITTED PAPER

•

27

The overlap between rows (i1 , i2 ) is chosen from t{i1 ,i2 ,i3 } overlaps among the three
rows, and the overlap between rows (i1 , i3 ) is chosen from other (t{i1 ,i2 ,i3 } −1) overlaps
among the three rows (if possible; that is why we use [t{i1 ,i2 ,i3 } − 1]+ ).

•

The overlap between rows (i1 , i2 ) is chosen from t{i1 ,i2 ,i3 } overlaps among the three
rows, and the overlap between rows (i1 , i3 ) is chosen from (t{i1 ,i3 } −t{i1 ,i2 ,i3 } ) overlaps
that are exclusively between these two rows.

•

The overlap between rows (i1 , i2 ) is chosen from (t{i1 ,i2 } − t{i1 ,i2 ,i3 } ) overlaps that are
exclusively between these two rows, and the overlap between rows (i1 , i3 ) is chosen
from t{i1 ,i2 ,i3 } overlaps among the three rows.

•

The overlap between rows (i1 , i2 ) is chosen from (t{i1 ,i2 } − t{i1 ,i2 ,i3 } ) overlaps that are
exclusively between these two rows, and the overlap between rows (i1 , i3 ) is chosen
from (t{i1 ,i3 } − t{i1 ,i2 ,i3 } ) overlaps that are exclusively between these two rows.

These four cases correspond to the four terms in (16).
2) Because of the structure of SC codes, an overlap between rows ((r −1)γ +i1 , (r −1)γ +i2 )
in Rr , an overlap between rows ((r −1)γ +i1 , (r −1)γ +i3 ) in Rr , and an overlap between
rows ((r−1)γ+i2 , (r−1)γ+i3 ) in Rq correspond to overlaps between pairs of rows (i1 , i2 ),
(i1 , i3 ), and (i2 + (r − q)γ, i3 + (r − q)γ) in Π1,p
1 , respectively. The overlaps between rows
(i1 , i2 ) and between rows (i1 , i3 ) belong to the same replica and must have distinct indices.
The third overlap belongs to another replica and automatically has a distinct index. The
number of options for the third overlap is ti2 +(r−q)γ,i3 +(r−q)γ . We partition the enumeration
into the following two cases:
•

The overlap between rows (i1 , i2 ) is chosen from t{i1 ,i2 ,i3 } overlaps among the three
rows, and the overlap between rows (i1 , i3 ) is chosen from the [t{i1 ,i3 } − 1]+ remaining
options.

•

The overlap between rows (i1 , i2 ) is chosen from (t{i1 ,i2 } − t{i1 ,i2 ,i3 } ) overlaps that are
exclusively between these two rows, and the overlap between rows (i1 , i3 ) is chosen

February 20, 2018

DRAFT

28

IEEE TRANSACTIONS ON COMMUNICATIONS

from the t{i1 ,i3 } options.
These two cases correspond to the two terms in (17).
3) Because of the structure of SC codes, an overlap between rows ((r −1)γ +i1 , (r −1)γ +i2 )
in Rr , ((r − 1)γ + i1 , (r − 1)γ + i3 ) in Rq , and ((r − 1)γ + i2 , (r − 1)γ + i3 ) in Rs
correspond to overlaps between pairs of rows (i1 , i2 ), (i1 + (r − q)γ, i3 + (r − q)γ), and
(i2 + (r − s)γ, i3 + (r − s)γ) in Π1,p
1 , respectively. These overlaps belong to different
replicas and thus have distinct indices. Consequently, the number of cycles-6 in this case
is the number of ways that we can choose these three overlaps, which is given in (18).

C. Proof of Theorem 2
Proof: For a cycle-6, all the three VNs are adjacent (connected to each other via one distinct
CN). As a result, for an SC code with memory m, a cycle-6 spans at most χ = m+1 consecutive
replicas, and (19) directly follows from (5).
1) For k = 1, we look for the number of cycles-6 having all the three VNs in replica R1
of HpSC . Based on Lemma 5, the number of cycles-6 with CNs i1 , i2 , and i3 and VNs in
R1 is A(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 ,i3 } ). Then, we just need to find all possible choices
for the CNs i1 , i2 , and i3 . First, all the CNs must belong to the non-zero part of R1 ,
i.e., {0, · · · , (m + 1)γ}. Second, the rows correspond to these CNs must have non-zero
overlaps, i.e., i1 6= i2 , i1 6= i3 , i2 6= i3 (see Remark 3). Putting this together results in F11
in (20).
2) For k = 2, we look for the number of cycles-6 spanning the two replicas R1 and R2 of
HpSC , such that either two VNs are in R1 and one VN is in R2 , or vice versa. Based on
Lemma 5, the number of cycles-6 with two VNs in R1 , one VN in R2 , and CNs i1 , i2 , and
i3 is B(t{i1 ,i2 ,i3 } , t{i1 ,i2 } , t{i1 ,i3 } , t{i2 −γ,i3 −γ} ). Then, we just need to find all possible choices
for CNs i1 , i2 , and i3 . Two CNs i2 and i3 are connected to VNs in replicas R1 and R2 ,
thus they must belong to {γ, · · · , (m + 1)γ}, and CN i1 is connected to VNs in R1 , thus
DRAFT

February 20, 2018

SUBMITTED PAPER

29

it must belong to {0, · · · , (m + 1)γ}. Putting this together results in the first summation
F12 in (20). The second summation, which is for the case when one VN belongs to R1
and two VNs belong to R2 , can be found similarly.
3) For 3 ≤ k ≤ (m + 1), we look for the number of cycles-6 spanning k replicas of HpSC
starting from R1 . Then, the first VN belongs to R1 , the last VN belongs to Rk , and the
middle VN belongs to Rq , (1 ≤ q ≤ k). The first two summations in the expression
of F1k in (20) correspond to the cases q = 1 and q = k (the proof is similar to the
previous case). For the case of 2 ≤ q ≤ (k − 1) and based on Lemma 5, the number of
cycles-6 with one VN in R1 , one VN in Rq , one VN in Rk , and CNs i1 , i2 , and i3 is
C(t{i1 ,i2 } , t{i1 +(1−q)γ,i3 +(1−q)γ} , t{i2 +(1−k)γ,i3 +(1−k)γ} ). The CN i1 is connected to VNs in R1
and Rq , therefore it must belong to {(q − 1)γ, · · · , (m + 1)γ}. The CN i2 is connected
to VNs in R1 and Rk , therefore it must belong to {(k − 1)γ, · · · , (m + 1)γ}. The CN i3
connected to VNs in Rq and Rk , therefore it must belong to {(k − 1)γ, · · · , (m + q)γ}.
Putting this together results in the third summation of F1k in (20).
R EFERENCES
[1] H. Esfahanizadeh, A. Hareedy, and L. Dolecek, “A novel combinatorial framework to construct spatially-coupled codes:
Minimum overlap partitioning,” in IEEE Int. Symp. Info. Theory (ISIT), Jun. 2017, pp. 1693–1697.
[2] A. Hareedy, H. Esfahanizadeh, and L. Dolecek, “High performance non-binary spatially-coupled codes for flash memories,”
in IEEE Info. Theory Workshop (ITW), Nov. 2017.
[3] A. J. Felstrom and K. S. Zigangirov, “Time-varying periodic convolutional codes with low-density parity-check matrix,”
IEEE Trans. Inf. Theory, vol. 45, no. 6, pp. 2181–2191, Sep. 1999.
[4] A. R. Iyengar, P. H. Siegel, R. L. Urbanke, and J. K. Wolf, “Windowed decoding of spatially coupled codes,” IEEE Trans.
Inf. Theory, vol. 59, no. 4, pp. 2277–2292, Apr. 2013.
[5] R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello, “LDPC block and convolutional codes based on
circulant matrices,” IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 2966–2984, Dec. 2004.
[6] M. Lentmaier, A. Sridharan, D. J. Costello, and K. S. Zigangirov, “Iterative decoding threshold analysis for LDPC
convolutional codes,” IEEE Trans. Inf. Theory, vol. 56, no. 10, pp. 5274–5289, Oct. 2010.
[7] S. Kudekar, T. J. Richardson, and R. L. Urbanke, “Threshold saturation via spatial coupling: Why convolutional LDPC
ensembles perform so well over the BEC,” IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 803–834, Feb. 2011.
February 20, 2018

DRAFT

30

IEEE TRANSACTIONS ON COMMUNICATIONS

[8] S. Kudekar, T. Richardson, and R. L. Urbanke, “Spatially coupled ensembles universally achieve capacity under belief
propagation,” IEEE Trans. Inf. Theory, vol. 59, no. 12, pp. 7761–7813, Dec. 2013.
[9] L. Wei, T. Koike-Akino, D. G. M. Mitchell, T. E. Fuja, and D. J. Costello, “Threshold analysis of non-binary spatiallycoupled LDPC codes with windowed decoding,” in IEEE Int. Symp. Info. Theory (ISIT), Jun. 2014, pp. 881–885.
[10] I. Andriyanova and A. A. i Graell, “Threshold saturation for nonbinary SC-LDPC codes on the binary erasure channel,”
IEEE Trans. Inf. Theory, vol. 62, no. 5, pp. 2622–2638, May 2016.
[11] D. G. M. Mitchell, L. Dolecek, and D. J. Costello, “Absorbing set characterization of array-based spatially coupled LDPC
codes,” in IEEE Int. Symp. Info. Theory (ISIT), Jun. 2014, pp. 886–890.
[12] B. Amiri, A. Reisizadehmobarakeh, H. Esfahanizadeh, J. Kliewer, and L. Dolecek, “Optimized design of finite-length
separable circulant-based spatially-coupled codes: An absorbing set-based analysis,” IEEE Trans. Commun., vol. 64, no. 10,
pp. 4029–4043, Oct. 2016.
[13] H. Esfahanizadeh, A. Hareedy, and L. Dolecek, “Spatially coupled codes optimized for magnetic recording applications,”
IEEE Trans. Magn., vol. 53, no. 2, pp. 1–11, Feb. 2017.
[14] D. G. M. Mitchell and E. Rosnes, “Edge spreading design of high rate array-based SC-LDPC codes,” in IEEE Int. Symp.
Info. Theory (ISIT), Jun. 2017, pp. 2940–2944.
[15] L. Chen, S. Mo, D. J. Costello, D. G. M. Mitchell, and R. Smarandache, “A protograph-based design of quasi-cyclic
spatially coupled LDPC codes,” in IEEE Int. Symp. Info. Theory (ISIT), Jun. 2017, pp. 1683–1687.
[16] T. Richardson, “Error floors of LDPC codes,” in Proc. 41st Annual Allerton Conf. Commun., Control and Comp., Oct.
2003, pp. 1426–1435.
[17] L. Dolecek, Z. Zhang, V. Anantharam, M. J. Wainwright, and B. Nikolic, “Analysis of absorbing sets and fully absorbing
sets of array-based LDPC codes,” IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 181–201, Jan. 2010.
[18] C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, and R. L. Urbanke, “Finite-length analysis of low-density parity-check
codes on the binary erasure channel,” IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1570–1579, Jun. 2002.
[19] A. Hareedy, C. Lanka, and L. Dolecek, “A general non-binary LDPC code optimization framework suitable for dense flash
memory and magnetic storage,” IEEE Journal on Selected Areas in Commun., vol. 34, no. 9, pp. 2402–2415, Sep. 2016.
[20] J. L. Fan, “Array codes as low-desity parity-check codes,” Int. Symp. Turbo Codes, pp. 543–546, Sep. 2000.
[21] M. Karimi and A. H. Banihashemi, “On characterization of elementary trapping sets of variable-regular LDPC codes,”
IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5188–5203, Sep. 2014.
[22] J. Wang, L. Dolecek, and R. D. Wesel, “The cycle consistency matrix approach to absorbing sets in separable circulant-based
LDPC codes,” IEEE Trans. Inf. Theory, vol. 59, no. 4, pp. 2293–2314, Apr. 2013.
[23] M. P. C. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant permutation matrices,” IEEE Trans. Inf.
Theory, vol. 50, no. 8, pp. 1788–1793, Aug. 2004.
[24] A. Bazarsky, N. Presman, and S. Litsyn, “Design of non-binary quasi-cyclic LDPC codes by ACE optimization,” in IEEE
Info. Theory Workshop (ITW), Sep. 2013, pp. 1–5.
DRAFT

February 20, 2018

