---
abstract: 'In this paper, we propose new coupled codes constructed by overlapping circular spatially-coupled low-density parity-check (SC-LDPC) codes, which show better asymptotic and finite-length decoding performance compared to the conventional SC-LDPC codes. The performance improvement comes from the property that the proposed codes effectively split into two separated SC-LDPC codes with shorter chain length during the decoding process. We verify that the property of the proposed codes is valid in asymptotic setting via analysis tools such as the density evolution and the expected graph evolution. Experimental results show that the proposed codes also outperform the conventional SC-LDPC codes in terms of the finite-length performance under belief propagation decoding.'
author:
- 'Heeyoul Kwak, Bohwan Jun, Pilwoong Yang, Jong-Seon No, , and Dong-Joon Shin, [^1][^2]'
title: 'New Coupled Codes Constructed by Overlapping Circular SC-LDPC Codes'
---

Circular spatially-coupled low-density parity-check codes, density evolution, expected graph evolution, finite-length performance, low-density parity-check (LDPC) codes, spatially-coupled LDPC (SC-LDPC) codes.

Introduction {#Sec:Introduction}
============

-coupled low-density parity-check (SC-LDPC) codes have attracted many attentions in recent years due to their ability to achieve the Shannon limit of binary memoryless symmetric (BMS) channels under iterative decoding [@Kudekar]. The research on the SC-LDPC codes was started with the advent of convolutional LDPC codes by Felstrom and Zigangirov [@Felstrom]. There have been lots of research results on construction and analysis of the convolutional LDPC codes [@Sridharan]–[@Mitchell]. Especially, Sridharan *et al.* [@Sridharan] derived the belief propagation (BP) threshold which is a theoretical performance limit of the iterative decoding for the convolutional LDPC codes and Lentmaier *et al.* [@Lentmaier] empirically showed that the BP thresholds of convolutional LDPC codes are close to the MAP thresholds of the underlying regular block LDPC codes. This remarkable improvement of the BP thresholds was named as [*threshold saturation*]{} which was analytically proved in [@Kudekar], [@Kudekar1]. Recently, proving the threshold saturation effect has been done through many different approaches such as a potential function [@Yedla], [@Yedla2] and an one-dimensional continuous coupled system [@Kudekar3]. These approaches utilize the unique decoding process of SC-LDPC codes; the reliable messages are propagated from the both ends to the center on the Tanner graph in a [*[wave-like manner]{}*]{}.

SC-LDPC codes are constructed by coupling $L$ disjoint LDPC codes with the boundary condition which causes the wave-like propagation. However, at the cost of the wave-like propagation, the boundary condition reduces the overall code rate compared with that of underlying codes, where the rate loss converges to zero at a speed $1/L$. Thus, we can obtain a capacity approaching code ensemble for large chain length because the rate loss is vanished while the wave-like decoding process is still successful even for extremely large chain lengths, provided that the iteration number increases with the chain length. In a practical situation, however, SC-LDPC codes with too large $L$ imply a large number of iterations for the wave-like propagation in the BP decoding [@Kudekar1]. Furthermore, an in-depth analysis regarding a scaling law of SC-LDPC ensembles shows that large $L$ is not good for the finite-length performance [@Olmos]. On the other hand, SC-LDPC ensembles with short $L$ have good decoding properties such as high BP thresholds, low required numbers of iterations for the wave-like propagation, and good finite-length performances but it show large rate loss.

Some modifications of SC-LDPC ensembles have been studied to achieve performance improvement in practical situations. Among them, we focus on the modification by properly connecting multiple SC-LDPC ensembles. The idea of coupling is not limited to connection of several LDPC ensembles into a chain (an SC-LDPC ensemble) but also extended to connection of several chains to overcome some problems that a single chain cannot solve. For example, the multi-dimensional SC-LDPC codes [@Ohashi] were considered for their robustness against burst erasures and the parallelly connected SC-LDPC chains [@Liu] were proposed to obtain asymptotically good code ensembles with wide rate range. Especially, in [@Truhachev]–[@Olmos2], a loop ensemble obtained by connecting two SC-LDPC chains was proposed with improved BP thresholds and finite-length performances. At the connecting points in the loop ensemble, consecutive positions consisting of high degree variable nodes, so called protected region, are created and reliable messages are emitted from the protected region. Due to these reliable messages, the loop ensemble is decoded as two independent SC-LDPC chains with short chain length and achieves performance improvements. However, in [@Olmos2], it is shown that the loop ensemble shows worse finite-length performance than the SC-LDPC ensemble for long chain length.

The proposed coupled ensemble, called overlapped circular SC-LDPC (OC-LDPC) ensemble, is obtained based on the idea to connect multiple chains, but it is different from the loop ensemble in the sense that the OC-LDPC ensemble is constructed from two circular SC-LDPC ensembles rather than two SC-LDPC ensembles. Since there is no reliable position initiating decoding waves in the symmetric structure of the circular SC-LDPC ensemble [@Kudekar1], the performance improvement by coupling does not appear in the circular SC-LDPC ensemble. To make a protected region from which decoding waves start to propagate in the circular ensemble, our proposed approach is overlapping some variable nodes in two circular SC-LDPC ensembles, which introduces high-degree variable nodes. Since high-degree variable nodes in LDPC codes are successfully decoded with high probability, a protected region is formed by the introduced high-degree variable nodes like the loop ensemble. Similar to the loop ensemble, the OC-LDPC ensemble behaves as two [*[split]{}*]{} short SC-LDPC chains which are separately decoded with improved decoding performance and small number of iterations in the decoding process. Since the performance improvement of the loop and OC-LDPC ensembles comes from almost the same effect, these ensembles look similar. However, in terms of degree distribution of the protected region, we will show that the protected region of the OC-LDPC ensemble is more protected compared to the protected region of the loop ensemble, and thus the OC-LDPC ensemble behaves as two split short SC-LDPC chains regardless of the chain length unlike the loop ensemble.

Contrary to the randomly defined ensemble, codes from protograph-based ensembles [@Thorpe] are well suited for designing practical codes with several advantages such as good finite-length performance and an implementation-friendly structure. Also, protograph-based SC-LDPC ensembles have good minimum distance properties as well as capacity approaching BP thresholds [@Mitchell2]. Thus, we design finite-length OC-LDPC codes based on protograph and numerical results show that the proposed codes provide better finite-length performance than the conventional SC-LDPC codes for both short and long chain lengths. Furthermore, it is also verified that a construction method called precoding [@Divsalar] is applicable to the proposed ensemble to further improve the performance.

The remainder of the paper is organized as follows. Section \[Sec:Construction\] gives construction methods of coupled ensembles such as SC-LDPC, loop, and OC-LDPC ensembles. In Section \[Sec:Analysis\], the behavior of the OC-LDPC ensemble in the decoding process is analyzed by the density evolution (DE) and the expected graph evolution. In Section \[Sec:Protograph\], the protograph-based ensembles for the proposed coupled ensembles are presented. Finally, the conclusion is given in Section \[Sec:Conclusion\].

Code Construction of Coupled Ensembles {#Sec:Construction}
======================================

Construction of SC-LDPC Ensembles
---------------------------------

Let $d_l$ and $d_r$ denote variable and check node degrees of regular LDPC ensembles, respectively. We consider the SC-LDPC ensemble in [@Kudekar1] denoted by the ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ ensemble, where $L$ and $w$ are called the chain length and the coupling length, respectively. The ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ ensemble consists of $M$ variable nodes of degree $d_l$ located at each $L$ variable node positions with $Md_l/d_r$ check nodes of degree $d_r$ located at each $L+w-1$ check node positions.

Each of the $d_l$ edges of a variable node at position $i$ is uniformly at random and independently connected to check nodes at the positions $i+j$ for $j=0,\ldots,w-1$. In [@Olmos2], the connectivity between the positions in the graph is represented by a $P\times Q$ connectivity matrix ${\bf T}$ where $P$ and $Q$ are the number of check and variable node positions, respectively. $[{\bf T}]_{u,v}$ equals to $1$ if a variable node at position $v$ is connected to some check nodes at position $u$. Then the connectivity matrix ${\bf T}_{\rm SC}(L,w)$ of the ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ ensemble is represented as $$\begin{aligned}
[{\bf T}_{\rm SC}(L,w)]_{u,v}=\begin{cases} 
1 \textrm{, if $u\in [v,v+w-1]$} & \\
0 \textrm{, otherwise}
 \end{cases}\label{Eq:T_SC}\end{aligned}$$ and $P=L+w-1$, $Q=L$.

The total number of variable nodes $V$ and check nodes $C$ in the graph are $V=QM=LM$ and $C=PM{d_l}/{d_r}=(L+w-1){d_l}/{d_r}$, respectively. However, some check nodes at the leftmost $w-1$ and rightmost $w-1$ boundary positions cannot be connected to any variable node in the ensemble by the randomness of the connectivity. The expected number of check nodes $\overline{C}$ with at least one connection to the variable nodes in the graph is [@Kudekar1] $$\overline{C}=\bigg(L+w-1-2\sum_{i=0}^{w-1}\Big(\frac{i}{w}\Big)^{d_r}\bigg)M\frac{d_l}{d_r},$$ which is less than $C=(L+w-1)Md_l/d_r$. Thus, the design rate $R_{\rm SC}$ of the ${\mathcal C}_{\rm SC}$$(d_l,d_r,L,w)$ ensemble is given as [@Kudekar1 Lemma 3] $$\begin{aligned}
R_{\rm SC}&=1-\frac{\overline{C}}{V}\nonumber\\
&=\bigg(1-\frac{d_l}{d_r}\bigg)-\frac{d_l}{d_r}\frac{w-1}{L}+\frac{d_l}{d_r}\frac{2\sum\limits_{i=0}^{w-1}(\frac{i}{w})^{d_r}}{L} \label{Eq:SC_Design_Rate}\end{aligned}$$ where the first term is the design rate of the underlying regular LDPC ensemble, the second term represents the rate loss by coupling, and the third term represents the rate gain by the unconnected check nodes. Since the third term is small in comparison with the second term, the design rate of the SC-LDPC ensemble is reduced from the first term, but it converges to the first term as $L$ increases.

Construction of Loop Ensembles
------------------------------

Let ${\mathcal C}_{\rm L}(d_l,d_r,L,w)$ denote the loop ensemble [@Truhachev]–[@Olmos2]. As in [@Truhachev]–[@Olmos2], we mainly consider the loop ensemble for the trivial case when $d_l=3, d_r=6,$ and $w=3$. The ${\mathcal C}_{\rm L}(3,6,L,3)$ ensemble is constructed by connecting two independent ${\mathcal C}_{\rm SC}(3,6,L,3)$ ensembles. The connectivity matrix of the ${\mathcal C}_{\rm L}(3,6,L,3)$ ensemble is $${\bf T}_{\rm L}(L,3)=
\left[
\begin{array}{c;{3pt/3pt}c}
{\bf T}_{\rm SC}(L,3) & {\bf L}_2\\\hdashline[3pt/3pt]
{\bf L}_1 & {\bf T}_{\rm SC}(L,3)
\end{array}
\right]$$ where the $(L+w-1)\times L$ matrix ${\bf L}_1$ has ones at the entries $(1,\ceil{L/3}-1)$, $(1,\ceil{L/3})$, and $(2,\ceil{L/3}+1)$ and the $(L+w-1)\times L$ matrix ${\bf L}_2$ has ones at the entries $(L+1,\floor{2L/3})$, $(L+2,\floor{2L/3}+1)$, and $(L+2,\floor{2L/3}+2)$ [@Olmos2]. Then, the size of ${\bf T}_{\rm L}(L,3)$ becomes $P\times Q=2(L+2)\times 2L$ which is two times the size of ${\bf T}_{\rm SC}(L,3)$. The number of variable nodes $V$ and check nodes $C$ in the graph are $V=QM=2LM$ and $C=PMd_l/d_r=(L+2)M$, respectively. Since all check nodes in the ${\mathcal C}_{\rm L}(3,6,L,3)$ ensemble are connected to the variable nodes contrary to the ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ ensemble, the design rate of $R_{\rm L}$ of the ${\mathcal C}_{\rm L}(3,6,L,3)$ ensemble is given as

$$R_{\rm L}=1-\frac{C}{V}=\frac{1}{2}-\frac{1}{L}.$$

Construction of OC-LDPC Ensembles
---------------------------------

Before introducing construction method of OC-LDPC ensembles, we first consider the circular SC-LDPC ensemble ${\mathcal C}_{\rm C}(d_l,d_r,L,w)$ presented in [@Kudekar1]. Let $\left<i,j\right> = (i-1 {\rm~mod~} j)+1$ and $[i,j]$ be a set of integers between $i$ and $j$ for integers $i$, $j$. In the ${\mathcal C}_{\rm C}(d_l,d_r,L,w)$ ensemble, both of variable and check nodes are placed at the positions in $[1,L+w-1]$ with $M$ variable nodes and $Md_l/d_r$ check nodes at each position. Then, each of $d_l$ edges of a variable node at position $i$ is uniformly at random and independently connected to check nodes at the positions $\left<i+j,L+w-1\right>$ for $j\in[1,w-1]$. The connectivity matrix of the ${\mathcal C}_{\rm C}(d_l,d_r,L,w)$ ensemble becomes $$\begin{aligned}
[{\bf T}_{\rm C}(L,w)]_{u,v}=\begin{cases} 
1 \textrm{, if $u\in \{\left<v,L+w-1\right>,\ldots,\left<v+w-1,L+w-1\right>\}$} & \\
0 \textrm{, otherwise}.
 \end{cases}\label{Eq:T_C}\end{aligned}$$

Let ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ denote the OC-LDPC ensemble. To construct the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble, we first construct two independent ${\mathcal C}_{\rm C}(d_l,d_r,L_s,w)$ ensembles for positive integer $L_s$ such that $L=2L_s+w-1$. Next, divide the variable node positions of each ${\mathcal C}_{\rm C}(d_l,d_r,L_s,w)$ ensembles into two parts; the first part consists of variable node positions from $1$ to $L_s$ and the second part consists of the remaining variable node positions. Then, we can also separate the connectivity matrix ${\bf T}_{\rm C}(L_s,w)$ into two parts such as $${\bf T}_{\rm C}(L_s,w)=\left[\begin{array}{c;{2pt/4pt}c}{\bf T}_{\rm SC}(L_s,w)&{\bf T}_{\rm C,R}(L_s,w)\end{array}\right]\label{Eq:T_C}$$ where the matrix ${\bf T}_{\rm SC}(L_s,w)$ given in (\[Eq:T\_SC\]) corresponds to the first part and the $(L_s+w-1)\times (w-1)$ matrix ${\bf T}_{\rm C,R}(L_s,w)$ corresponds to the second part. Then, connect two circular SC-LDPC ensembles by overlapping each pair of variable nodes located in the second part of each circular SC-LDPC ensembles. More precisely, connect the check nodes, which are connected with the $t$th variable node at position $i$ in the second ${\mathcal C}_{\rm C}(d_l,d_r,L_s,w)$ ensemble, to the $t$th variable node at position $i$ in the first ${\mathcal C}_{\rm C}(d_l,d_r,L_s,w)$ ensemble for $t\in[1,M]$ and $i\in [L_s+1,L_s+w-1]$ while removing the last $(w-1)$ variable node positions in the second ${\mathcal C}_{\rm C}(d_l,d_r,L_s,w)$ ensemble. Then $(w-1)M$ variable nodes of degree $2d_l$ are generated at the positions from $L_s+1$ to $L_s+(w-1)$ in the first ${\mathcal C}_{\rm C}(d_l,d_r,L_s,w)$ ensemble. The order of the positions is rearranged from the positions of the first circular ${\mathcal C}_{\rm C}(d_l,d_r,L_s,w)$ ensemble to the positions of the second ${\mathcal C}_{\rm C}(d_l,d_r,L_s,w)$ ensemble. By following the above procedures, the connectivity matrix ${\bf T}_{\rm OC}(L,w)$ of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble is obtained as $${\bf T}_{\rm OC}(L,w)=
\left[
\begin{array}{c;{3pt/3pt}c;{3pt/3pt}c}
{\bf T}_{\rm SC}(L_s,w) &{\bf T}_{\rm C,R}(L_s,w) &  \\\hdashline[3pt/3pt]
            & {\bf T}_{\rm C,R}(L_s,w) & {\bf T}_{\rm SC}(L_s,w)
\end{array}
\right].\label{Eq:T_OC}$$ For example, ${\bf T}_{\rm OC}(8,3)$ is represented as $${\bf T}_{\rm OC}(8,3)=\left[
\begin{tabular}{ccc;{3pt/3pt}cc;{3pt/3pt}ccc}
$1$ & $0$ & $0$ & $1$ & $1$ & $0$ & $0$ & $0$ \\
$1$ & $1$ & $0$ & $0$ & $1$ & $0$ & $0$ & $0$ \\
$1$ & $1$ & $1$ & $0$ & $0$ & $0$ & $0$ & $0$ \\
$0$ & $1$ & $1$ & $1$ & $0$ & $0$ & $0$ & $0$ \\
$0$ & $0$ & $1$ & $1$ & $1$ & $0$ & $0$ & $0$ \\\hdashline[3pt/3pt]
$0$ & $0$ & $0$ & $1$ & $1$ & $1$ & $0$ & $0$ \\
$0$ & $0$ & $0$ & $0$ & $1$ & $1$ & $1$ & $0$ \\
$0$ & $0$ & $0$ & $0$ & $0$ & $1$ & $1$ & $1$ \\
$0$ & $0$ & $0$ & $1$ & $0$ & $0$ & $1$ & $1$ \\
$0$ & $0$ & $0$ & $1$ & $1$ & $0$ & $0$ & $1$
\end{tabular}\right].$$

Clearly, the size of ${\bf T}_{\rm OC}(L,w)$ is $$\begin{aligned}
P\times Q&=2(L_s+w-1)\times (2L_s+w-1)\\
&=(L+w-1)\times L,\end{aligned}$$ which is equal to the size of ${\bf T}_{\rm SC}(L,w)$ in (\[Eq:T\_SC\]). Since the numbers of variable and check nodes are $V=QM=LM$ and $C=PMd_l/d_r=(L+w-1)Md_l/d_r$, the design rate of ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble is given as $$R_{\rm OC}=1-\frac{C}{V}=\bigg(1-\frac{d_l}{d_r}\bigg)-\frac{d_l}{d_r}\frac{w-1}{L}. \label{Eq:OC_Design_Rate}$$ As an example, we include the graphical representations of ${\bf T}_{\rm SC}(8,3)$, ${\bf T}_{\rm L}(8,3)$, and ${\bf T}_{\rm OC}(8,3)$ in Fig. \[Fig:Graph\].

Comparison of Design Rate and Degree Distribution {#Sec:Comparison}
-------------------------------------------------

Compared to the design rate of the ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ ensemble in (\[Eq:SC\_Design\_Rate\]), the design rate of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble in (\[Eq:OC\_Design\_Rate\]) is slightly lower by the rate gain from the unconnected check nodes for given $L$. On the other hand, the design rates of the ${\mathcal C}_{\rm L}(3,6,L,3)$ and ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensembles are the exactly the same for the trivial case $d_l=3, d_r=6, w=3$.

In terms of degree of variable node at each position, the three coupled ensembles (SC-LDPC, loop, OC-LDPC) have different degree distributions. Let ${\bf D}_{\mathcal A}$ be a degree distribution vector of an ensemble ${\mathcal A}$ where $[{\bf D}_{\mathcal A}]_{i}$ is the degree of variable node at position $i$. For the ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ ensemble, all variable nodes in the ensemble have $d_l$ edges, i.e., $[{\bf D}_{\rm SC}]_i=d_l$ for all $i$. On the contrary, the ${\mathcal C}_{\rm L}(3,6,L,3)$ ensemble has the irregular degree distribution $$[{\bf D}_{\rm L}]_i=\begin{cases} 
4,& \textrm{if $i\in {\mathcal R}_{\rm L, 1}\cup{\mathcal R}_{\rm L, 2}$}  \\
3,&\textrm{otherwise}
 \end{cases}$$ where ${\mathcal R}_{\rm L, 1}=\{ \ceil{L/3}-1, \ceil{L/3}, \ceil{L/3}+1\}$ and ${\mathcal R}_{\rm L, 2}=\{L+\floor{2L/3}, L+\floor{2L/3}+1, L+\floor{2L/3}+2\}$ which indicate the positions where high degree variable nodes exist. Similarly, the degree distribution of the variable nodes in the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble is irregular such as $$[{\bf D}_{\rm OC}]_i=\begin{cases} 
2d_l,&\textrm{if $i\in {\mathcal R}_{\rm OC}$}  \\
d_l,&\textrm{otherwise}
 \end{cases}\label{Eq:Degree_OC}$$ where ${\mathcal R}_{\rm OC}=\{L_s+1,{\ldots},L_s+w-1\}$.

As discussed in [@Olmos2], the ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ ensemble has two protected regions at each boundary position that are protected by the connected low degree check nodes. For the ${\mathcal C}_{\rm L}(3,6,L,3)$ ensemble, there are four protected regions; two of them at the boundary positions are formed by the connected low degree check nodes like the ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ ensemble and the other two protected regions are ${\mathcal R}_{\rm L, 1}$ and ${\mathcal R}_{\rm L, 2}$. On the other hand, the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble has one protected region ${\mathcal R}_{\rm OC}$. Although the protected regions ${\mathcal R}_{\rm L, 1}$, ${\mathcal R}_{\rm L, 2}$, and ${\mathcal R}_{\rm OC}$ are similar because they are formed by high-degree variable nodes, the degree of variable node in the protected region ${\mathcal R}_{\rm OC}$ is higher than that in ${\mathcal R}_{\rm L, 1}$ or ${\mathcal R}_{\rm L, 2}$ for $d_l=3,~d_r=6$, which implies that ${\mathcal R}_{\rm OC}$ is more protected.

Analysis of Coupled Ensembles {#Sec:Analysis}
=============================

Density Evolution of Coupled Ensembles
--------------------------------------

In this paper, the channel is assumed to be the binary erasure channel (BEC) with erasure probability $\epsilon$. The DE is often used as an analytical tool for the decoding performance of LDPC codes in the asymptotic setting such as infinite codeword length and infinite iteration numbers. For the coupled ensembles, the DE keeps track of the average erasure probability of messages at each variable node position. Let $x_i^{(l)}$ denote the average erasure probability of messages emitted from the variable nodes at position $i$ at the iteration $l$. Set the initial conditions as $x_i^{(0)}=1$ for all $i$. Given a $P\times Q$ connectivity matrix ${\bf T}$ and degree distribution vector ${\bf D}$, the evolution of ${\bf x}^{(l)}\triangleq(x_1^{(l)},{\ldots},x_{Q}^{(l)})^{\top}$ can be expressed in vector form as

$${\bf x}^{(l)}={\bf f}\Big({\bf T}^{\top}{\bf g}({\bf T}{\bf x}^{(l-1)})\Big)\label{Eq:DE}$$

where $(.)^{\top}$ denotes the transpose and $$\begin{aligned}
[{\bf g(x)}]_i&=\frac{(1-(1-{x_i})^{(d_r-1)})}{\sum\limits_{t=1}^{Q}[{\bf T}]_{i,t}}, {\rm~for~} i\in[1,P]\\
[{\bf f(x)}]_i&=\frac{\epsilon{x_i}^{[{\bf D}]_i-1}}{\sum\limits_{t=1}^{P}[{\bf T}]_{t,i}}, {\rm~for~} i\in[1,Q].\end{aligned}$$

With the DE equation, we can obtain the BP threshold as a measure of decoding performance which is defined as below.

The BP threshold $\epsilon^{\rm BP}_{\mathcal A}$ of a coupled ensemble ${\mathcal A}$ is defined as $$\epsilon_{\mathcal A}^{\rm BP}=\textrm{sup}\{\epsilon~\vert~\lim_{l \to \infty}x_i^{(l)}=0 {\rm~for~all~} i\}. \nonumber$$

An asymptotically good ensemble with good BP decoding performances has a large BP threshold. The BP threshold, however, assumes an infinite number of iterations which is infeasible in a practical situation. Thus, we include the required number of iterations as another measure of performance to design a practically good ensemble that works properly with the limited number of iterations.

The required number of iterations $I_{\mathcal A}(\epsilon_r)$ of a coupled ensemble ${\mathcal A}$ is defined as $$I_{\mathcal A}(\epsilon_r)={\rm min}\{ l~\vert~x_{i}^{(l)}=0 {\rm~for~all~} i {\rm~and~} \epsilon=\epsilon_r \}.\nonumber$$

Denote the BP and the MAP thresholds of the $(d_l,d_r)$-regular LDPC ensemble by $\epsilon^{\rm BP}(d_l,d_r)$ and $\epsilon^{\rm MAP}(d_l,d_r)$, respectively. For the BEC with $\epsilon_r<\epsilon^{\rm BP}(d_l,d_r)$, where the variable nodes at each position of ${\mathcal C}_{\rm SC}(d_l,d_r,L,w)$ are decoded without the wave-like propagation, $I_{\rm SC}(\epsilon_r)$ is independent of $L$. We focus on the required number of iterations when $\epsilon^{\textrm{BP}}(d_l,d_r)\le\epsilon_r<\epsilon^{\textrm{MAP}}(d_l,d_r)$. In that range of erasure probability, the required number of iterations means the minimum decoding time such that the variable nodes at all positions are successfully decoded via the propagation of reliable messages. Thus, the required number of iterations $I_{\rm SC}(\epsilon_r)$ increases proportionally to $L$.

![The design rate, BP threshold, the required number of iterations for ${\mathcal C}_{\textrm{SC}}(3,6,L,3)$ ensembles.[]{data-label="fig:SC_D_R_R"}](SC_Measures.pdf)

In Fig. \[fig:SC\_D\_R\_R\], we observe how the measures of the ${\mathcal C}_{\rm SC}(3,6,L,3)$ ensemble behave as the chain length $L$ increases which is summarized as follows

i)  The design rate increases and approaches to the design rate of the underlying regular LDPC ensemble.

ii) The BP threshold decreases for a while and then approaches to the MAP threshold of the underlying regular LDPC ensemble.

iii) The required number of iterations for $\epsilon_r=0.48$ gradually increases almost linearly with $L$.

As the chain length $L$ increases, we obtain capacity approaching SC-LDPC ensembles due to the steadily increasing design rates and the saturated thresholds. However, the SC-LDPC ensemble with short chain length are expected to show good decoding performance because they have higher BP thresholds and lower required number of iterations.

Asymptotic Behavior of the Loop and OC-LDPC Ensembles for Small $L$
-------------------------------------------------------------------

In [@Truhachev]–[@Olmos2], it is shown that the asymptotic performance of the ${\mathcal C}_{\rm L}(3,6,L,3)$ ensemble is comparable to that of the SC-LDPC ensemble with short chain length $\floor{2L/3}$. That is because the positions from $1$ to the first position in ${\mathcal R}_{\rm L,1}$ and from the last position in ${\mathcal R}_{\rm L,2}$ to $2L$, called the outer segment in [@Olmos2], are almost surely decoded over the BP threshold of the short SC-LDPC chain with $L=\floor{2L/3}$. Similar to the ${\mathcal C}_{\rm L}(3,6,L,3)$ ensemble, the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble shows asymptotic performance comparable to the SC-LDPC ensemble with short chain length $L_s$ for $L=2L_s+w-1$.

Recall that the DE equation in (\[Eq:DE\]) is formulated if a connectivity matrix ${\bf T}$ and a degree distribution vector ${\bf D}$ are given. Consider the DE equation of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble with ${\bf T}_{\rm OC}(L,w)$ and ${\bf D}_{\rm OC}$ in (\[Eq:Degree\_OC\]). From the symmetry of ${\bf T}_{\rm OC}(L,w)$ and ${\bf D}_{\rm OC}$, it is obvious that $x_{i}^{(l)}=x_{i+L_s+w-1}^{(l)}$ for $i\in[1,L_s]$ and thus it is sufficient to keep track of the evolution of $x_{i}^{(l)}$ for $i\in[1,L_s+w-1]$. The evolution of ${\bf x}^{(l)}=\{x_1^{(l)},{\ldots},x_{L_s+w-1}^{(l)}\}$ is expressed using only the upper half part of ${\bf T}_{\rm OC}(L,w)$ in (\[Eq:T\_OC\]), which is equal to ${\bf T}_{\rm C}(L_s,w)$ in (\[Eq:T\_C\]), with the degree distribution given $$[{\bf D}_{\rm OC,2}]_i=\begin{cases} 
2d_l,&\textrm{if $i\in [L_s+1,L_s+w-1]$} \\
d_l,&\textrm{if $i\in [1,L_s]$}.
 \end{cases}\label{Eq:Degree_OC2}$$

On the other hand, the evolution of ${\bf x}^{(l)}=\{x_1^{(l)},{\ldots},x_{L_s}^{(l)}\}$ of the ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ ensemble can also be obtained from the segment of the evolution of ${\bf x}^{(l)}=\{x_1^{(l)},{\ldots},x_{L_s+w-1}^{(l)}\}$ which is derived by the DE equation with the connectivity matrix ${\bf T}_{\rm C}(L_s,w)$ and the degree distribution such as $$[{\bf D}_{\rm SC,2}]_i=\begin{cases} 
\infty,& \textrm{if $i\in [L_s+1,L_s+w-1]$}\\
d_l,& \textrm{if $i\in [1,L_s]$}.
 \end{cases}\label{Eq:Degree_SC2}$$ The degree $\infty$ of the positions in $[L_s+1,L_s+w-1]$ imposes the boundary condition on ${\bf x}^{(l)}=\{x_1^{(l)},{\ldots},x_{L_s+w-1}^{(l)}\}$ by setting $x_{i}^{(l)}=0$ for $i\in[L_s+1,L_s+w-1]$ at each iteration. To sum up, in terms of the DE equation, the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ and ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ ensembles are quite similar except for the variable node operation at the last $w-1$ positions, where known variable nodes exist for the ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ ensemble while high-degree variable nodes exist for the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble. The following lemmas show this similarity.

The solution of the DE equation of the ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ ensemble satisfies the following properties [@Kudekar1], [@Yedla2].

i)  $x_i^{(l)}=x_{L_s+1-i}^{(l)}, \textrm{ for } 1\le i \le \frac{L_s+1}{2} \textrm{ and } l\ge 0 $ \[Lemma:SC\_1\]

ii) $x_i^{(l)}\le x_{i+1}^{(l)}, \textrm{ for } 1\le i \le \frac{L_s+1}{2} \textrm{ and } l\ge0$. \[Lemma:SC\_2\]

\[Lemma:SC\]

The solution of the DE equation of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble satisfies the following properties:

i)  $x_i^{(l)}=x_{L_s+1-i}^{(l)}, \textrm{ for } 1\le i \le \frac{L_s+1}{2} \textrm{ and } l\ge 0 $ \[Lemma:OC\_1\]

ii) $x_{L_s+i}^{(l)}=x_{L_s+w-i}^{(l)}, \textrm{ for }1\le i \le \frac{w}{2} \textrm{ and } l\ge 0$ \[Lemma:OC\_2\]

iii) $x_{i}^{(l)}\le x_{i+1}^{(l)},\textrm{ for } 1\le i \le \frac{L_s+1}{2} \textrm{ and } l\ge0$ \[Lemma:OC\_3\]

iv) $x_{L_s+i}^{(l)}\ge x_{L_s+i+1}^{(l)}, \textrm{ for } 1\le i \le \frac{w}{2} \textrm{ and } l\ge0$ \[Lemma:OC\_4\]

v)  $x_{L_s-1}^{(l)}\ge x_{L_s}^{(l)}, \textrm{ for } l\ge0.$ \[Lemma:OC\_5\]

\[Lemma:OC\]

We prove this lemma by a similar method used for the proof of Lemma \[Lemma:SC\] in [@Yedla2]. All the properties are satisfied for $l=0$ by the initial condition. Suppose that the properties are satisfied for the inductive step $k>0$. Consider the DE equation with $
{\bf T}_{\rm C}(L_s,w)=\left[\begin{array}{c;{2pt/4pt}c}{\bf T}_{\rm SC}(L_s,w)&{\bf T}_{\rm C,R}(L_s,w)\end{array}\right]
$ and ${\bf D}_{\rm OC, 2}$ in (\[Eq:Degree\_OC2\]). Note that $[{\bf g(x)}]_i=(1-(1-x_i))^{(d_r-1)}/w$ and $[{\bf f(x)}]_i=\epsilon x_i^{[{\bf D}_{\rm OC, 2}]_i-1}/w$ are monotonic functions operating on each element $x_i$.

Define an $s\times s$ permutation matrix ${\bf M}_{s}$ such as $[{\bf M}_{s}]_{i,j}=1$ if $j=s-i+1$. Considering the definition of $
{\bf T}_{\rm C}=\left[\begin{array}{c;{2pt/4pt}c}{\bf T}_{\rm SC}&{\bf T}_{\rm C,R}\end{array}\right]
$ in (\[Eq:T\_C\]), ${\bf T}_{\rm SC}$ and ${\bf T}_{\rm C,R}$ are symmetric under simultaneous row-column reversal (i.e., $[{\bf T}_{\rm SC}]_{i,j}=[{\bf T}_{\rm SC}]_{L_s+w-i,L_s+1-j}$ and $[{\bf T}_{\rm C,R}]_{i,j}=[{\bf T}_{\rm C,R}]_{L_s+w-i,w-j})$ and this implies that ${\bf T}_{\rm SC}{\bf M}_{L_s}={\bf M}_{L_s+w-1}{\bf T}_{\rm SC}$ and ${\bf T}_{\rm C,R}{\bf M}_{w-1}={\bf M}_{L_s+w-1}{\bf T}_{\rm C,R}$. Define $\overline{{\bf M}}$ as $$\overline{{\bf M}}=\left[
\begin{array}{c;{3pt/3pt}c}
{\bf M}_{L_s} &  \\\hdashline[3pt/3pt]
            & {\bf M}_{w-1}
\end{array}
\right].$$ Then, the properties i) and ii) for step $k$ imply $\overline{{\bf M}}{\bf x}^{(k)}={\bf x}^{(k)}$ and $$\begin{aligned}
{\bf T}_{\rm C}\overline{{\bf M}}
&=\left[\begin{array}{c;{3pt/3pt}c}
{\bf T}_{\rm SC} & {\bf T}_{\rm C, R}
\end{array}\right]\left[
\begin{array}{c;{3pt/3pt}c}
{\bf M}_{L_s} &  \\\hdashline[3pt/3pt]
            & {\bf M}_{w-1}
\end{array}
\right] \\
&=\left[\begin{array}{c;{3pt/3pt}c}
{\bf T}_{\rm SC}{\bf M}_{L_s} & {\bf T}_{\rm C, R} {\bf M}_{w-1}
\end{array}\right]\\
&=\left[\begin{array}{c;{3pt/3pt}c}
{\bf M}_{L_s+w-1}{\bf T}_{\rm SC} & {\bf M}_{L_s+w-1}{\bf T}_{\rm C, R} 
\end{array}\right]\\
&={\bf M}_{L_s+w-1}{\bf T}_{\rm C}.\end{aligned}$$ Then, the inductive step for $k+1$ follows from $$\begin{aligned}
{\bf x}^{(k+1)}&={\bf f}\Big({\bf T}_{\rm C}^{\top}{\bf g}({\bf T}_{\rm C}{\bf x}^{(k)})\Big)={\bf f}\Big({\bf T}_{\rm C}^{\top}{\bf g}({\bf T}_{\rm C}\overline{\bf M}{\bf x}^{(k)})\Big)\\
&={\bf f}\Big({\bf T}_{\rm C}^{\top}{\bf g}({\bf M}_{L_s+w-1}{\bf T}_{\rm C}{\bf x}^{(k)})\Big)={\bf f}\Big({\bf T}_{\rm C}^{\top}{\bf M}_{L_s+w-1}{\bf g}({\bf T}_{\rm C}{\bf x}^{(k)})\Big)\\
&={\bf f}\Big(\overline{\bf M}^{\top}{\bf T}_{\rm C}^{\top}{\bf g}({\bf T}_{\rm C}{\bf x}^{(k)})\Big)\stackrel{(a)}{=}\overline{\bf M}{\bf f}\Big({\bf T}_{\rm C}^{\top}{\bf g}({\bf T}_{\rm C}{\bf x}^{(k)})\Big)\\
&=\overline{\bf M}{\bf x}^{(k+1)}\end{aligned}$$ where (a) follows from $\overline{\bf M}^{\top}=\overline{\bf M}$ and the fact that ${\bf D}_{\rm OC, 2}$ of $[{\bf f(x)}]_i=\epsilon x_i^{[{\bf D}_{\rm OC, 2}]_i-1}/w$ is separated into two parts.

Due to the symmetry, the properties iii), iv), and v) for the $k$th inductive step can be expressed as $x_{i}^{(k)}\ge x_{i+1}^{(k)}$ for $\frac{L_s+1}{2}\le i \le L_s+\frac{w}{2}$, i.e., $x_{i}^{(k)}$ is monotonically decreasing for $\frac{L_s+1}{2}\le i \le L_s+\frac{w}{2}$. For $[{\bf T}_{\rm C}{\bf x}^{(k)}]_{i}$, we have $$\begin{aligned}
[{\bf T}_{\rm C}{\bf x}^{(k)}]_{i}-[{\bf T}_{\rm C}{\bf x}^{(k)}]_{i+1}&=\sum_{j=0}^{w-1}x^{(k)}_{\left<i-j,L_s+w-1\right>}-\sum_{j=0}^{w-1}x^{(k)}_{\left<i+1-j,L_s+w-1\right>}\\
&=(x^{(k)}_{i-(w-1)}-x^{(k)}_{i+1})\ge 0\end{aligned}$$ if $L_s+1-(i-(w-1))\le i+1$ or $i-(w-1)\le 2L_s+w-(i+1)$ and this is equivalent to $\frac{L_s+w-1}{2}\le i \le L_s+w-1$. Thus, $[{\bf T}_{\rm C}{\bf x}^{(k)}]_{i}$ is decreasing for $\frac{L_s+w-1}{2}\le i \le L_s+w-1$. Since ${\bf g(x)}$ does not affect the monotonicity, $[{\bf g}({\bf T}_{\rm C}^{\top}{\bf x}^{(k)}]_i$ is also decreasing over the same interval. We can also show that $[{\bf T}_{\rm C}^{\top}{\bf g}({\bf T}_{\rm C}^{\top}{\bf x}^{(k)})]_i$ is decreasing for $\frac{L_s+1}{2}\le i \le L_s+\frac{w}{2}$ in a similar manner with $[{\bf T}_{\rm C}{\bf x}^{(k)}]_{i}$. Lastly, considering the definition of ${\bf D}_{\rm OC, 2}$, $[{\bf f}({\bf T}_{\rm C}^{\top}{\bf g}({\bf T}_{\rm C}^{\top}{\bf x}^{(k)}))]_{i}$ also decreasing for $\frac{L_s+1}{2}\le i \le L_s+\frac{w}{2}$ and thus the properties iii), iv), and v) for step $k+1$ are satisfied.

From the properties i) and iii) in Lemma \[Lemma:OC\], we can see that a vector $\{x_1^{(l)},{\ldots},x_{L_s}^{(l)}\}$ of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble is unimodal, which is the same as that of the ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ ensemble shown in Lemma \[Lemma:SC\]. On the other hand, for the last $w-1$ positions of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble, there exists another unimodal vector $\{x_{L_s+1}^{(l)},{\ldots},x_{L_s+w-1}^{(l)}\}$ corresponding to ${\mathcal R}_{\rm OC}$. If the high-degree variable nodes of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble are decoded, i.e., $x_i^{(l)}=0$ for $i\in{\mathcal R}_{\rm OC}$, the DE equations of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ and ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ ensembles are exactly identical and then two ensembles have the same BP threshold and required number of iterations. However, these two performance measures of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble are bounded by those of the ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ ensemble as described in the following theorem.

For the ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ and the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensembles for $L=2L_s+(w-1)$, we have

i)  $\epsilon^{\textrm{BP}}_{\textrm{OC}}\le \epsilon^{\textrm{BP}}_{\textrm{SC}}$

ii) $I_{\textrm{OC}}(\epsilon_r)\ge I_{\rm SC}(\epsilon_r).$

For $i\in\{L_s+1,{\ldots},L_s+w-1\}$, $x_i^{(l)}\ge 0$ for the DE equation of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble while $x_i^{(l)}=0$ for the DE equation of the ${\mathcal C}_{\rm SC}(d_l,d_r,L_s,w)$ ensemble. Thus, the solutions of the DE equations for the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble are lower bounded by the solutions of the DE equations for the ${\mathcal C}_{\rm SC}(d_l,d_r,L_S,w)$ ensemble, which implies the theorem.

\[Theorem:Bounds\]

The bounds in Theorem \[Theorem:Bounds\] are achieved when $x_i^{(l)}=0$ for $i\in{\mathcal R}_{\rm OC}$, but erasure probabilities are always larger than zero before the evolution of the DE equation is successfully completed. However, the erasure probabilities of ${\mathcal R}_{\rm OC}$ are less than or equal to the minimum erasure probability of variable nodes in the remaining positions from the property v) in Lemma \[Lemma:OC\]. Also, through extensive numerical experiments, we observe that erasure probabilities of ${\mathcal R}_{\rm OC}$ rapidly converge to zero after some iterations and the bounds in Theorem \[Theorem:Bounds\] are almost achieved.

Table \[Table:Small L\] shows the design rate $R$, BP threshold $\epsilon^{\textrm{BP}}$, and the required number of iterations $I(\epsilon_r=0.48)$ for each of ${\mathcal C}_{\rm SC}(3,6,L,3)$, ${\mathcal C}_{\rm L}(3,6,L,3)$ and ${\mathcal C}_{\rm OC}(3,6,L,3)$ ensembles for various values of $L$ up to $20$. As discussed before, the loop and OC-LDPC ensembles suffer from additional rate loss compared to the SC-LDPC ensemble for the same $L$. However, the BP thresholds of the loop and OC-LDPC ensembles are improved compared to the corresponding SC-LDPC ensemble. Regarding the required number of iterations, the loop and OC-LDPC ensembles significantly outperform the SC-LDPC ensembles. Such improvement comes from the property that asymptotic behaviors of the loop and OC-LDPC ensembles with chain length $L$ converge to that of the short SC-LDPC chain with chain length $\floor{2L/3}$ and $(L-2)/2$, respectively. For example, $\epsilon^{\textrm{BP}}$ and $I(\epsilon_r=0.48)$ of the ${\mathcal C}_{\rm L}(3,6,18,3)$ and ${\mathcal C}_{\rm OC}(3,6,18,3)$ ensembles are comparable to those of the ${\mathcal C}_{\rm SC}(3,6,12,3)$ and ${\mathcal C}_{\rm SC}(3,6,8,3)$ ensembles, respectively.

                      $L$                  8        9        10       12       14       15       16       18       20
  ------ ------------------------------ -------- -------- -------- -------- -------- -------- -------- -------- --------
                  $R_{\rm SC}$           0.3861   0.3988   0.4089   0.4241   0.4349   0.4393   0.4431   0.4494   0.4545
    SC    $\epsilon^{\rm BP}_{\rm SC}$   0.5019   0.4961   0.4926   0.4893   0.4884   0.4882   0.4881   0.4881   0.4881
                  $I_{\rm SC}$             31       39       49       75      103      117      132      160      189
                  $R_{\rm L}$            0.3750   0.3889   0.4000   0.4167   0.4286   0.4333   0.4375   0.4444   0.4500
   Loop   $\epsilon^{\rm BP}_{\rm L}$    0.5536   0.5331   0.5262   0.5073   0.5001   0.4953   0.4953   0.4904   0.4893
                  $I_{\rm L}$              23       27       31       41       53       62       71       94      121
                  $R_{\rm OC}$           0.3750            0.4000   0.4167   0.4286            0.4375   0.4444   0.4500
    OC    $\epsilon^{\rm BP}_{\rm OC}$   0.5243            0.5218   0.5211   0.5209            0.5109   0.5018   0.4961
                  $I_{\rm OC}$             17                20       24       27                32       39       47

\[Table:Small L\]

Asymptotic Behavior of Loop and OC-LDPC Ensembles for Large $L$
---------------------------------------------------------------

In Table \[Table:Large L\], we compare the ${\mathcal C}_{\rm SC}(3,6,L,3)$, ${\mathcal C}_{\rm L}(3,6,L,3)$, and ${\mathcal C}_{\rm OC}(3,6,L,3)$ ensembles for large $L$. Contrary to the case for short $L$, the loop and OC-LDPC ensembles for large $L$ show no significant BP threshold gain because, even if the loop and OC-LDPC ensembles behave as the short SC-LDPC chain, the corresponding short SC-LDPC chain still has saturated BP threshold to $\epsilon^{\rm MAP}(3,6)$. For the required number of iterations, the loop and OC-LDPC ensembles show different result, that is, the loop ensemble shows degraded result for $L\ge 30$ while the OC-LDPC ensemble still shows significantly improved the required number of iterations as the case for short $L$.

                      $L$                  30       40       50      100
  ------ ------------------------------ -------- -------- -------- --------
                  $R_{\rm SC}$           0.4696   0.4772   0.4818   0.4909
    SC    $\epsilon^{\rm B}_{\rm SC}$    0.4881   0.4881   0.4881   0.4881
                  $I_{\rm SC}$            333      477      621      1341
                  $R_{\rm L}$            0.4667   0.4750   0.4800   0.4900
   Loop   $\epsilon^{\rm BP}_{\rm L}$    0.4881   0.4881   0.4881   0.4881
                  $I_{\rm L}$             294      494      681      1646
                  $R_{\rm OC}$           0.4667   0.4750   0.4800   0.4900
    OC    $\epsilon^{\rm BP}_{\rm OC}$   0.4884   0.4881   0.4881   0.4881
                  $I_{\rm OC}$            111      183      255      615

  : Comparison of the ${\mathcal C}_{\rm SC}(3,6,L,3)$, ${\mathcal C}_{\rm L}(3,6,L,3)$, and ${\mathcal C}_{\rm OC}(3,6,L,3)$ ensembles.

\[Table:Large L\]

We can figure out the reason by comparing the evolution of erasure probabilities. Fig. \[fig:Evolution\] compares the evolution of erasure probabilities $x_i^{(l)}$ for each position obtained by (\[Eq:DE\]) for the ${\mathcal C}_{\rm L}(3,6,50,3)$ and ${\mathcal C}_{\rm OC}(3,6,50,3)$ ensembles over $\epsilon=0.48$. First, for the ${\mathcal C}_{\rm L}(3,6,50,3)$ ensemble, we observe that the erasure probabilities in $l=20$ at two protected regions ${\mathcal R}_{\rm L,1}=\{16, 17, 18\}$, and ${\mathcal R}_{\rm L,2}=\{83, 84, 85\}$ show lower value. However, the erasure probabilities of ${\mathcal R}_{\rm L,1}$ and ${\mathcal R}_{\rm L,2}$ remain unchanged up to $l=200$ and then goes to zero only after the wave-like propagations come from the boundary positions. In other words, the outer segment is also decoded in a wave-like manner as the other positions, which means that there is no significant improvement in the required number of iterations.

On the contrary, for the ${\mathcal C}_{\rm OC}(3,6,50,3)$ ensembles, the erasure probabilities of ${\mathcal R}_{\rm OC}=\{25, 26\}$ go to zero after a few iterations $l=20$ without help of wave-like propagations and then the erasure probabilities evolve in a similar way with two independent short SC-LDPC chains. That is because ${\mathcal R}_{\rm OC}$ is more protected than ${\mathcal R}_{\rm L,1}$ and ${\mathcal R}_{\rm L,2}$ as discussed in Section \[Sec:Comparison\]. Thus, for large $L$, there is still improvement in $I_{\rm OC}$ due to the same effect for short $L$ such that the OC-LDPC ensemble is effectively split into two short SC-LDPC chains during the decoding process.

Fig. \[fig:Simulation\] compares the design rate, BP threshold, and the required number of iterations of ${\mathcal C}_{\rm SC}(3,6,L,3)$, ${\mathcal C}_{\textrm{L}}(3,6,L,3)$, and ${\mathcal C}_{\textrm{OC}}(3,6,L,3)$ ensembles for various values of $L$. Fig. \[fig:Simulation\_Rate\] shows that the design rate of the ${\mathcal C}_{\rm SC}(3,6,L,3)$ ensemble is slightly higher than those of the ${\mathcal C}_{\textrm{L}}(3,6,L,3)$ and ${\mathcal C}_{\textrm{OC}}(3,6,L,3)$ ensembles due to the rate gain from the unconnected check nodes. However, the ${\mathcal C}_{\textrm{OC}}(3,6,L,3)$ ensemble offers an increased BP threshold compared with the ${\mathcal C}_{\rm SC}(3,6,L,3)$ ensemble for $10\le L\le30$ and the BP thresholds of these two ensembles are close to $\epsilon^{\rm MAP}(3,6)$ for large $L$ as in Fig. \[fig:Simulation\_Threshold\]. Compared to the ${\mathcal C}_{\textrm{L}}(3,6,L,3)$ ensemble, the ${\mathcal C}_{\textrm{OC}}(3,6,L,3)$ ensemble still shows improved BP threshold for $12\le L\le30$. Furthermore, the ${\mathcal C}_{\textrm{OC}}(3,6,L,3)$ ensemble allows a significant reduction in the required number of iterations as in Fig. \[fig:Simulation\_Iteration\]. Such improvements in the BP threshold and required number of iterations are resulted from splitting the ${\mathcal C}_{\textrm{OC}}(3,6,L,3)$ ensemble into two short SC-LDPC chains ${\mathcal C}_{\textrm{SC}}(3,6,L_s,3)$ for $L=2L_s+w-1$, which is verified by comparing $\epsilon_{\textrm{OC}}^{\textrm{BP}}$ and $I_{\textrm{OC}}$ for the ${\mathcal C}_{\textrm{OC}}(3,6,L,3)$ ensemble with $\epsilon_{\textrm{SC}}^{\textrm{BP}}$ and $I_{\textrm{SC}}$ for the ${\mathcal C}_{\textrm{SC}}(3,6,L_s,3)$ ensemble, respectively. The above comparison shows that the bounds described in Theorem \[Theorem:Bounds\] are almost achieved.

Splitting of the OC-LDPC ensemble
---------------------------------

We observe that the improvement in the decoding performance does not occur for OC-LDPC ensembles with different degree distributions such as $(d_l,d_r)=(4,8)$. To figure out the reason, we define a definition of splitting by formula and derive a theorem.

We say that [*splitting*]{} the ${\mathcal C}_{\textrm{OC}}(d_l,d_r,L,w)$ ensemble into the ${\mathcal C}_{\textrm{SC}}(d_l,d_r,L_s,w)$ occurs if $$\epsilon_{\textrm{SC}}^{\textrm{BP}}(d_l,d_r,L_s,w)-\epsilon_{\textrm{OC}}^{\textrm{BP}} (d_l,d_r,L,w)<\delta_s$$ where $L=2L_s+w-1$ and $\delta_s$ is sufficiently small value.

For example, splitting occurs for the ${\mathcal C}_{\textrm{OC}}(3,6,20,3)$ ensemble and $\delta_s=10^{-4}$ because the BP thresholds of the ${\mathcal C}_{\textrm{OC}}(3,6,20,3)$ and ${\mathcal C}_{\textrm{SC}}(3,6,9,3)$ ensembles are the same up to four decimal digits according to Table \[Table:Small L\].

A necessary condition to show splitting of the ${\mathcal C}_{\rm OC}(d_l,d_r,L,w)$ ensemble is $$\epsilon^{\textrm{BP}}_{\textrm{SC}} (d_l,d_r,L_s,w)<\epsilon^{\textrm{BP}}(2d_l,d_r)+\delta_s.$$ \[theorem:splitting\]

Consider the erasure probability $x_{u}^{(l)}$, where $u=L_s+\lfloor w/2\rfloor$. It is the minimum erasure probability from Lemma \[Lemma:OC\], i.e., $x_{i}^{(l)}\ge x_{u}^{(l)}$ for $i\in[1,L_s+w-1]$. Let ${\bf x}^{(l)}=\{x_1^{(l)},{\ldots},x_{L_s+w-1}^{(l)}\}$ and $\overline{\bf x}^{(l)}=\{x_u^{(l)},{\ldots},x_{u}^{(l)}\}$. From the DE equation in (\[Eq:DE\]) with ${\bf T}_{\rm C}(L_s,w)$ and ${\bf D}_{\rm OC, 2}$, we have the DE equation for $x_{u}$ as $$\begin{aligned}
x_{u}^{(l)}&=[{\bf f}({\bf T}_{\rm C}^{\top}{\bf g}({\bf T}_{\rm C}{\bf x}^{(l-1)}))]_u\\
&\stackrel{(a)}{\ge} [{\bf f}({\bf T}_{\rm C}^{\top}{\bf g}({\bf T}_{\rm C}{\overline{\bf x}}^{(l-1)}))]_u \\
&=\epsilon \bigg(1-\Big(1-x_{u}^{(l-1)}\Big)^{d_r-1}\bigg)^{2d_l-1} \nonumber\end{aligned}$$ where (a) follows from the monotonicity of $[{\bf f(x)}]_i=\epsilon x_i^{[{\bf D}_{\rm OC, 2}]_i-1}/w$ and $[{\bf g(x)}]_i=(1-(1-x_i))^{(d_r-1)}/w$. Thus, $x_{u}^{(l)}$ converges to a non-zero value as $l$ goes to infinity over $\epsilon=\epsilon_{\textrm{SC}}^{\textrm{BP}}(d_l,d_r,L_s,w)-\delta_s$ if $\epsilon_{\textrm{SC}}^{\textrm{BP}}(d_l,d_r,L_s,w)-\delta_s\ge\epsilon^{\textrm{BP}}(2d_l,d_r)$, which implies that $$\epsilon_{\textrm{OC}}^{\textrm{BP}}(d_l,d_r,L,w)\le \epsilon_{\textrm{SC}}^{\textrm{BP}}(d_l,d_r,L_s,w)-\delta_s$$ or equivalently $$\epsilon_{\textrm{SC}}^{\textrm{BP}}(d_l,d_r,L_s,w)-\epsilon_{\textrm{OC}}^{\textrm{BP}}(d_l,d_r,L,w)\ge\delta_s$$ i.e., the splitting does not occur.

Theorem \[theorem:splitting\] implies that splitting does not occurs if the local decoding performance around the reliable region, which is associated with $\epsilon^{\textrm{BP}}(2d_l,d_r)$, is worse than the decoding performance of the short SC-LDPC chain, which is associated with $\epsilon_{\textrm{SC}}^{\textrm{BP}}(d_l,d_r,L_s,w)$. As an example of the case when the splitting does not occurs due to the higher $\epsilon_{\textrm{SC}}^{\textrm{BP}}(d_l,d_r,L_s,w)$, consider the ${\mathcal C}_{\textrm{OC}}(3,6,10,3)$ ensemble. In this case, the necessary condition in Theorem \[theorem:splitting\] is not satisfied because $\epsilon_{\textrm{SC}}^{\textrm{BP}}(3,6,4,3)=0.5891$ is higher than $\epsilon^{\textrm{BP}}(6,6)+\delta_s=0.5819$ for $\delta_s=10^{-4}$. Thus, from Theorem \[theorem:splitting\], splitting does not occur. Actually, $\epsilon_{\textrm{OC}}^{\textrm{BP}}(3,6,10,3)=0.5218$ is quite lower than $\epsilon_{\textrm{SC}}^{\textrm{BP}}(3,6,4,3)=0.5891$.

\[Ex:splitting1\]

As an example of the case when the splitting does not occurs due to the lower $\epsilon^{\textrm{BP}}(2d_l,d_r)$, consider the degree distribution $(d_l,d_r)=(4,8)$. The BP threshold $\epsilon^{\textrm{BP}}(8,8)=0.4876$ is lower than $\epsilon^{\textrm{BP}}_{\textrm{SC}}(4,8,L\to \infty,3)\approx\epsilon^{\textrm{MAP}}(4,8)=0.497$. Since the BP threshold of the SC-LDPC ensemble is a non-increasing function of $L$, the necessary condition in Theorem \[theorem:splitting\] is not satisfied for the ${\mathcal C}_{\textrm{OC}}(4,8,L,3)$ ensemble over any range $L$. Indeed, the BP threshold $\epsilon_{\textrm{OC}}^{\textrm{BP}} (4,8,L,3)$ does not converge to $\epsilon^{\textrm{MAP}}(4,8)=0.497$ but a lower value $0.4433$ as shown in Table \[Table:Threshold\_(4,8)\].

               $L$                  10       14       18       22       50
  ------------------------------ -------- -------- -------- -------- --------
           $R_{\rm OC}$           0.4000   0.4286   0.4444   0.4545   0.4800
   $\epsilon^{\rm BP}_{\rm OC}$   0.4440   0.4434   0.4433   0.4433   0.4433

  : Design rates and BP thresholds of the ${\mathcal C}_{\textrm{OC}}$$(4,8,L,3)$ ensemble

\[Table:Threshold\_(4,8)\]

In order to construct a capacity approaching OC-LDPC ensemble whose BP threshold is comparable to $\epsilon^{\textrm{BP}}_{\textrm{SC}}(4,8,L,w)$, we propose to construct OC-LDPC ensembles by coupling irregular LDPC ensembles [@Richardson]. Let $L(x)$ be the normalized variable degree distribution from a node perspective [@Richardson]. Consider an irregular variable degree distribution $L(x)=\frac{19}{20}x^3+\frac{1}{20}x^{23}$ and a regular check node degree $8$ used in [@Aref]. Since the average degree of $L(x)$ is $4$, such degree distribution can be compared with the case $(d_l,d_r)=(4,8)$. In [@Aref], the SC-LDPC ensemble based on such irregular degree distribution shows increased convergence speed compared to the $\mathcal{C}_{\textrm{SC}}(4,8,L,3)$ ensemble without sacrificing capacity approaching BP thresholds. We observe that the BP threshold of the OC-LDPC ensemble based on the given irregular degree distribution $L(x)$ for $L=22,~w=3$ is $0.5035$ which is identical to the BP threshold of the SC-LDPC ensemble based on the same degree distribution for $L=10$. In other words, the splitting occurs for $L=22$. Also it is observed that the OC-LDPC ensemble satisfies the necessary condition and splitting occurs from $L=22$ for $\delta_s=10^{-4}$.

Expected Graph Evolution of Coupled Ensembles
---------------------------------------------

In [@Olmos], [@Olmos2], it is introduced how to predict the finite-length performance of SC-LDPC codes by the scaling law. The scaling law of SC-LDPC ensemble[^3] depends on the scaling parameters derived by analyzing the decoding process of the peeling decoder. The peeling decoder sequentially decodes an unknown variable node which is connected to a degree-one check node at each iteration and removes the decoded variable node along with the connected degree-one check node from the graph. As the peeling decoding progresses, the number of nodes in the graph decreases and becomes zero if the codeword is successfully decoded. In other words, successful decoding is achieved if at least one degree-one check node remains alive in the graph until all unknown variable nodes are recovered. Thus, the finite-length performance of a code ensemble is related to the evolution of the number of degree-one check nodes in the graph.

Let $r_1({\tau})$ be the fraction of degree-one check nodes in the graph, where $\tau$ is the normalized number of iterations by $M$, i.e., $\tau=l/M$. In [@Olmos], [@Olmos2], a closed-form expression of the expected fraction $\hat{r}_{1}(\tau)$ of degree-one check nodes is derived for coupled ensembles given the connectivity matrix $\bf{T}$. Based on the evolution of $\hat{r}_{1}(\tau)$, it is figured out which factors affect the finite-length performance of coupled ensembles. The first factor is whether the expected evolution $\hat{r}_{1}(\tau)$ has a critical point or critical phase. The critical point is defined as $\tau$, where $\hat{r}_{1}(\tau)$ shows a single local minimum and the critical phase indicates the interval of $\tau$, where $\hat{r}_{1}(\tau)$ stays equal at the local minimum. Since the number of degree-one check nodes of a code instance is mostly prone to fall down to $0$ at the local minimum of $\hat{r}_{1}(\tau)$ [@Olmos], the cumulative probability of decoding failure is higher for the case when the critical phase exists than the case when the critical point exists. Next, among the cases when the critical phase exists, the decoding failure is more likely to occur if the evolution of $\hat{r}_1({\tau})$ has longer critical phase or lower local minimum value. Thus, duration of the critical phase and the local minimum value of $\hat{r}_{1}(\tau)$ are important factors for the finite-length performance.

The behavior of the OC-LDPC ensemble during the decoding process can also be investigated by the expected graph evolution. In Fig. \[fig:Evolution\_L50\], the evolution curves of $\hat{r}_1(\tau)$ for the ${\mathcal C}_{\textrm{SC}}(3,6,50,3)$ and ${\mathcal C}_{\textrm{OC}}(3,6,50,3)$ ensembles are plotted at $\epsilon=0.48$. First, we figure out that the evolution of $\hat{r}_1(\tau)$ for the ${\mathcal C}_{\textrm{OC}}(3,6,50,3)$ ensemble begins with lower value than $\hat{r}_1(\tau)$ for the ${\mathcal C}_{\textrm{SC}}(3,6,50,3)$ ensemble because there is no low-degree check node in the initial structure of the ${\mathcal C}_{\textrm{OC}}(3,6,50,3)$ ensemble without decoding. Then, $\hat{r}_1(\tau)$’s for both ensembles gradually decrease and have reached the critical phase. Compared with $\hat{r}_1(\tau)$ for the ${\mathcal C}_{\textrm{SC}}(3,6,50,3)$ ensemble, $\hat{r}_1(\tau)$ for the ${\mathcal C}_{\textrm{OC}}(3,6,50,3)$ ensemble has two times larger value and shows shorter duration at the critical phase. That is because the ${\mathcal C}_{\textrm{OC}}(3,6,50,3)$ ensemble is effectively split into two separate independent ${\mathcal C}_{\textrm{SC}}(3,6,24,3)$ ensembles (denoted by $2\times {\mathcal C}_{\textrm{SC}}(3,6,24,3)$ ensembles), which can be verified by comparing with $\hat{r}_1(\tau)$ for the $2\times {\mathcal C}_{\textrm{SC}}(3,6,24,3)$ ensembles. Note that we shift $\hat{r}_1(\tau)$ to $\hat{r}_1(\tau-\Delta/M)$ for the $2\times {\mathcal C}_{\textrm{SC}}(3,6,24,3)$ ensembles for easy comparison with $\hat{r}_1(\tau)$ for the ${\mathcal C}_{\textrm{OC}}(3,6,50,3)$ ensemble. In addition, the average of normalized number of the variable nodes in ${\mathcal R}_{\rm OC}$, denoted by $v_*(\tau)$, is also included. In Fig. \[fig:Evolution\_L50\], it is observed that $v_*(\tau)$ is almost zero at the beginning of the critical phase for two split SC-LDPC chains, which enables $\hat{r}_1(\tau)$ of the ${\mathcal C}_{\textrm{OC}}(3,6,50,3)$ ensemble to follow the shifted $\hat{r}_1(\tau-\Delta/M)$ of $2\times {\mathcal C}_{\textrm{SC}}(3,6,24,3)$ during the critical phase. As a result, the finite-length performance of the OC-LDPC ensemble is expected to be similar to that of two independent split SC-LDPC chains.

For $L=20$ and $\epsilon=0.48$ shown in Fig. \[fig:Evolution\_L20\], $\hat{r}_1(\tau)$’s for the ${\mathcal C}_{\textrm{OC}}(3,6,20,3)$ ensemble and $2\times {\mathcal C}_{\textrm{SC}}(3,6,9,3)$ show a critical point. However, evolutions of these two ensembles look somewhat different because $v_*(\tau)$ is not sufficiently close to zero at the beginning of the critical point. Nevertheless, $\hat{r}_1(\tau)$ for the ${\mathcal C}_{\textrm{OC}}(3,6,20,3)$ ensemble shows better property than for the ${\mathcal C}_{\textrm{SC}}(3,6,20,3)$ ensemble which has a critical phase.

Protograph based ensembles {#Sec:Protograph}
==========================

Since the ${\mathcal C}_{\textrm{SC}}(d_l,d_r,L,w)$ ensemble in Section \[Sec:Construction\] has randomly connected edges, the ${\mathcal C}_{\textrm{SC}}(d_l,d_r,L,w)$ ensemble is called random-based SC-LDPC ensemble. Contrary to the random-based SC-LDPC ensemble, a protograph-based SC-LDPC ensemble has been considered in [@Mitchell] and [@Mitchell2]. Since code instances from the protograph-based ensemble are well designed to be used with good finite-length performance [@Stinner], [@Stinner2], a protograph-based OC-LDPC ensemble will also be proposed in this section. In addition, analysis of the random-based OC-LDPC ensemble ${\mathcal C}_{\textrm{OC}}(d_l,d_r,L,w)$ is mostly applicable to the analysis of the protograph-based OC-LDPC ensemble because the protograph-based ensemble is a special case of the random-based ensemble with edge connection constraints determined by the protograph.

LDPC codes based on protograph were introduced in [@Thorpe]. Assume that a protograph consists of $N_p$ variable nodes and $M_p$ check nodes. Tanner graph of a particular LDPC code instance is obtained from the protograph by lifting [@Thorpe]. The lifting operation is proceeded by copying the protograph $z$ times and permuting the edges among the $z$ replicas, where $z$ is referred as a lifting factor. Each of $z$ replicas of a variable node in the protograph should be connected to one of $z$ replicas of the check node which is connected to that variable node in the protograph. Although each code instance is obtained via different permutations, each code instance maintains the original graph structure of the protograph. Hence, a protograph represents an LDPC code ensemble.

A protograph can be described by an ${M_p\times N_p}$ base matrix $\mathbf{B}$, where the entry $B_{i,j}$ is the number of edges between the $i$th variable node and the $j$th check node. The lifting operation is equivalent to replacing each entry $B_{i,j}$ of the base matrix with the sum of $B_{i,j}$ distinct $z \times z$ permutation matrices to obtain a parity-check matrix.

Protograph-Based SC-LDPC Ensembles
----------------------------------

Let ${\mathcal P}_{\textrm{SC}}(L,w)$ denote the protograph-based SC-LDPC ensemble. The base matrix of the ${\mathcal P}_{\textrm{SC}}$$(L,w)$ ensemble, ${\mathbf{B}}_{\textrm{SC}}(L,w)$ is constructed from a ${b\times c}$ arbitrary base matrix ${\mathbf{B}}$ [@Mitchell]. The base matrix ${\mathbf{B}}_{\textrm{SC}}(L,w)$ consists of $L$ variable node positions where each position takes $c$ columns and $L+w-1$ check node positions, where each position takes $b$ rows. At each variable node position, $w$ component base matrices ${\mathbf{B}}_1,{\ldots},{\mathbf{B}}_w$ satisfying the edge spreading constraint such as ${\mathbf{B}}={\mathbf{B}}_1+{\ldots}+{\mathbf{B}}_w$ are aligned as $${\mathbf{B}}_{\textrm{SC}}(L,w)=\,\,\,
\overset{cL}{\overbrace{\!\!\!
\begin{bmatrix}
~~{\mathbf{B}}_1& & & \!\!\\
~~{\mathbf{B}}_2&{\mathbf{B}}_1& &\!\!\\
~~\vdots& {\mathbf{B}}_2&\ddots&&\!\!\\
~~ {\mathbf{B}}_w&\vdots &\ddots&{\mathbf{B}}_1&\!\!\\
~~ & {\mathbf{B}}_w &\ddots& {\mathbf{B}}_2\\
~~ & & \ddots &\vdots \\~~ & & & {\mathbf{B}}_w\!\!\end{bmatrix}\!\!\!}}\,\,\,.$$ Since the size of the base matrix ${\mathbf{B}}_{\textrm{SC}}(L,w)$ is $M_p \times N_p=b(L+w-1) \times cL$, the design rate of the ${\mathcal P}_{\textrm{SC}}(L,w)$ ensemble is given as $$R_{{\mathcal P},{\rm SC}}=\bigg(1-\frac{b}{c}\bigg)-\frac{b}{c}\frac{w-1}{L}
\label{Eq:P_SC_Design_Rate}$$ where the second term is the rate loss by coupling. Note that the rate gain by the unconnected check nodes in (\[Eq:SC\_Design\_Rate\]) does not exist in the design rate of the protograph-based SC-LDPC ensemble because check nodes must have at least one connection to the variable nodes.

Protograph-Based OC-LDPC Ensembles
----------------------------------

The protograph-based circular SC-LDPC ensemble is introduced as a tail-biting (TB) SC-LDPC ensemble in [@Tavares]. The base matrix of the protograph-based circular SC-LDPC ensemble ${\mathbf{B}}_{\textrm{C}}(L,w)$ for $L\ge w$ is obtained from ${\mathbf{B}}_{\textrm{SC}}(L+w-1,w)$ by adding the last $b(w-1)$ rows to the first $b(w-1)$ rows. Then ${\mathbf{B}}_{\textrm{C}}(L,w)$ is divided into two parts as $$\begin{aligned}
{\mathbf{B}}_{\textrm{C}}(L,w)&=\left[\begin{array}{c;{2pt/4pt}c}{{\mathbf{B}}_{\rm SC}(L,w)}&{{\mathbf{B}}_{\rm C,R}(L,w)}\end{array}\right]\nonumber\\
&=
\,\,\,\overset{cL}{\overbrace{\!\!\!\left[\begin{array} {ccc}
{\mathbf{B}}_1     &        &                    \\
\vdots             & \ddots &                    \\
{\mathbf{B}}_{w-1} & \ddots & {\mathbf{B}}_1     \\
{\mathbf{B}}_{w}   & \ddots & \vdots             \\
                   & \ddots & {\mathbf{B}}_{w-1} \\
                   &        & {\mathbf{B}}_{w}  
\end{array}\right.}} 
\overset{c(w-1)}{\overbrace{\left.\begin{array} {;{3pt/3pt}ccc}
{\mathbf{B}}_{w}     & \cdots & {\mathbf{B}}_{2}     \\
                   & \ddots & \vdots             \\
                   &        & {\mathbf{B}}_w     \\
{\mathbf{B}}_{1}     &        &                    \\
\vdots             & \ddots &                    \\
{\mathbf{B}}_{w-1} & \cdots & {\mathbf{B}}_1    
\end{array}\right]\!\!\!}}.\label{Eq:Base_C}\end{aligned}$$

Let ${\mathcal P}_{\textrm{OC}}(L,w)$ denote the protograph-based OC-LDPC ensemble. The base matrix of the ${\mathcal P}_{\textrm{OC}}(L,w)$ ensemble is obtained from two ${\mathbf B}_{\rm C}(L_s,w)$, where $L=2L_s+w-1$ as

$${\mathbf{B}}_{\textrm{OC}}(L,w)= 
\left[\begin{array}{c;{3pt/3pt}c;{3pt/3pt}c}
{\mathbf B}_{\rm SC}(L_s,w) &  {\mathbf B}_{\rm C, R}(L_s,w)&  \\\hdashline[3pt/3pt]
 &{\mathbf B}_{\rm C, R}(L_s,w)  &{\mathbf B}_{\rm SC}(L_s,w) \\
\end{array} \right].$$

Since the size of the resulting base matrix is $M_p \times N_p=b(2L_s+2\Delta) \times c(2L_s+w-1)$, the design rate of ${\mathcal P}_{\textrm{OC}}$$(L,w)$ ensemble is given as $$R_{{\mathcal P},{\rm OC}}=\bigg(1-\frac{b}{c}\bigg)-\frac{b}{c}\frac{w-1}{L}.
\label{Eq:P_OC_Design_Rate}$$ Thus, the design rates of ${\mathcal P}_{\textrm{SC}}$$(L,w)$ ensemble in (\[Eq:P\_SC\_Design\_Rate\]) and ${\mathcal P}_{\textrm{OC}}$$(L,w)$ ensemble in (\[Eq:P\_OC\_Design\_Rate\]) are identical.

Protograph-Based OC-LDPC Ensembles With Precoding
-------------------------------------------------

As discussed about the ${\mathcal C}_{\textrm{OC}}(d_l,d_r,L,w)$ ensemble, the variable nodes in ${\mathcal R}_{\rm OC}$ have to be decoded to split a long chain into two short chains. To improve the decoding performance of the variable nodes in ${\mathcal R}_{\rm OC}$, we consider the OC-LDPC with precoding (OCp-LDPC) ensemble, denoted by ${\mathcal P}_{\textrm{OCp}}(L,w)$, which uses the precoding technique [@Divsalar]. The precoding to a high-degree variable node is placing a check node between a newly added degree-1 variable node and the high-degree variable node in the protograph, where the high-degree variable node is punctured to maintain the design rate. Since the OC-LDPC ensemble has high-degree variable nodes, we can apply the precoding technique to the high-degree variable nodes in ${\mathcal R}_{\rm OC}$ so that the splitting of the OC-LDPC ensemble occurs well.

In [@Divsalar], the case that the only one variable node is punctured for precoding is considered. For the ${\mathcal P}_{\textrm{OCp}}(L,w)$ ensemble, however, a general case such that multiple variable nodes are punctured is considered. The following theorem gives a necessary condition for the successful decoding of an ensemble when multiple variable nodes are punctured.

Let ${\mathcal S}$ denote the set of variable nodes in a protograph such that all check nodes, which are connected to ${\mathcal S}$, are connected to ${\mathcal S}$ at least twice or with multiple edges[^4]. Then, decoding of codes lifted from the protograph always fails over non-zero channel erasure probability if there exists a set ${\mathcal S}$ in the set of punctured variable nodes in the protograph. \[Theorem:Punctured\_node\_condition\]

Let $\overline{\mathcal S}$ be the set of variable nodes lifted from ${\mathcal S}$. Then $\overline{\mathcal S}$ becomes the stopping set [@Richardson] because all check nodes, which are connected to $\overline{\mathcal S}$, are connected to $\overline{\mathcal S}$ at least twice by the definition of ${\mathcal S}$. Also, the variable nodes in $\overline{\mathcal S}$ have no channel information because they are punctured. Thus, the decoding always fails.

The base matrix of the ${\mathcal P}_{\textrm{OCp}}$$(L,w)$ ensemble, ${\mathbf{B}}_{\textrm{OCp}}(L,w)$ is represented as $${\mathbf{B}}_{\textrm{OCp}}(L,w)= 
\left[\begin{array}{c;{3pt/3pt}c;{3pt/3pt}c;{3pt/3pt}c}
{\mathbf B}_{\rm SC}(L_s,w) &  {\mathbf B}_{\rm C, R}(L_s,w)& &  \\\hdashline[3pt/3pt]
 &{\mathbf B}_{\rm C, R}(L_s,w) &{\mathbf B}_{\rm SC}(L_s,w)  &\\\hdashline[3pt/3pt]
 &              {\mathbf P}                     &                                     & I
\end{array} \right] \label{Eq:Base_OCp}$$ where ${\mathbf{P}}$ is a ${p\times c\Delta}$ matrix and $I$ is the $p\times p$ identity matrix. The variable nodes corresponding to the non-zero columns in ${\mathbf{P}}$ are punctured and the matrix $\mathbf{P}$ is designed so that the punctured variable nodes in ${\mathbf{B}}_{\textrm{OCp}}(L,w)$ do not include ${\mathcal S}$ mentioned in Theorem \[Theorem:Punctured\_node\_condition\].

For the ${\mathcal P}_{\textrm{OCp}}(L,3)$ ensemble with ${\mathbf{B}}_1={\mathbf{B}}_2={\mathbf{B}}_3=[1\,\,\,1]$, the set ${\mathcal S}$ defined in Theorem \[Theorem:Punctured\_node\_condition\] does not exist in the set of punctured variable nodes if we choose $p=2$ and ${\mathbf{P}}=\begin{bmatrix}0 & 1 & 1& 0\\ 0& 1 & 1 & 0\end{bmatrix}$, i.e., two high-degree variable nodes are applied to the precoding technique. We use this base matrix as a representative of the ${\mathcal P}_{\textrm{OCp}}(L,3)$ ensemble for the following simulations. If the precoding technique is applied to more than two variable nodes, i.e., $p=3$ or $p=4$, we find out that the set ${\mathcal S}$ in the set of punctured variable nodes always exist for every possible matrix ${\bf P}$.\[Ex:OCp\]

Let $w=3$ and ${\mathbf{B}}_1={\mathbf{B}}_2={\mathbf{B}}_3=[1\,\,\,1]$. Table \[Table:Comparison\_Proto\] compares the BP thresholds of the ${\mathcal P}_{\textrm{SC}}(L,3)$, ${\mathcal P}_{\textrm{OC}}(L,3)$, and ${\mathcal P}_{\textrm{OCp}}(L,3)$ ensembles. We use the DE equation for protograph-based ensembles in [@Lentmaier], [@Thorpe], [@Mitchell2] to obtain the BP thresholds. From Table \[Table:Comparison\_Proto\], the design rates are identical for all ensembles for the same $L$. However, the ${\mathcal P}_{\textrm{OC}}(L,3)$ ensemble for $L\ge 14$ has higher or equal BP thresholds compared with those of the ${\mathcal P}_{\textrm{SC}}(L,3)$ ensemble. Also, the ${\mathcal P}_{\textrm{OCp}}(L,3)$ ensemble shows much improved BP threshold. In [@Truhachev]–[@Truhachev3], the BP thresholds of the protograph-based loop ensemble are obtained, e.g., the BP thresholds of the loop ensembles with $L=12$ and $L=18$ are $0.5237$ and $0.4989$, respectively. Thus, compared to the loop ensemble, the BP threshold of the ${\mathcal P}_{\textrm{OCp}}(L,3)$ ensemble is lower for $L=12$ and higher for $L=18$.

                  $L$                     12       14       18       20       50
  ------------------------------------ -------- -------- -------- -------- --------
   ${\mathcal P}_{\textrm{SC}}(L,3)$    0.4954   0.4910   0.4884   0.4882   0.4881
   ${\mathcal P}_{\textrm{OC}}(L,3)$    0.4993   0.4967   0.4946   0.4942   0.4881
   ${\mathcal P}_{\textrm{OCp}}(L,3)$   0.5077   0.5072   0.5069   0.5069   0.4881

  : Comparison of BP thresholds of the ${\mathcal P}_{\textrm{SC}}(L,3)$, ${\mathcal P}_{\textrm{OC}}(L,3)$, and ${\mathcal P}_{\textrm{OCp}}(L,3)$ ensembles for $\mathbf{B}_1=\mathbf{B}_2=\mathbf{B}_3=[1\,\,1]$

\[Table:Comparison\_Proto\]

Finite-Length Simulation Results
--------------------------------

Fig. \[fig:Simulation\_FER\] compares the block error rate of particular code instances lifted from the ${\mathcal P}_{\textrm{SC}}(L,3)$, ${\mathcal P}_{\textrm{OC}}(L,3)$, and ${\mathcal P}_{\textrm{OCp}}(L,3)$ ensembles for $\mathbf{B}_1=\mathbf{B}_2=\mathbf{B}_3=[1\,\,1]$ with lifting factor $z=500$ and the loop ensemble in [@Truhachev]–[@Truhachev3] with lifting factor $z=250$. All codes have an equal number of transmitted bits as $18,000$ for $L=18$ and $50,000$ for $L=50$. In addition, we include the simulation result of two independent SC-LDPC codes with $L=L_s$ (denoted by $2\times$SC $L=L_s$) as the performance bounds of the OC-LDPC and OCp-LDPC codes with $L=2L_s+w-1$. The decoder uses the BP algorithm and runs the algorithm until the state of all variable nodes stays the same. In other words, we restrict the maximum number of iterations $I_{\rm max}$ to $\infty$.

For a short chain length $L=18$, it is shown in Fig. \[fig:Simulation\_FER\_L18\] that the OC-LDPC code shows improved block error rate compared with the SC-LDPC and loop codes. In addition, the OCp-LDPC code shows further improved performance which is close to the performance of two independent SC-LDPC codes with $L=8$. For a long chain length $L=50$ in Fig. \[fig:Simulation\_FER\_L50\], the performance improvement has also been observed as the case of $L=20$ although the SC-LDPC ensemble has the same BP threshold as the OC-LDPC and OCp-LDPC ensembles for $L=50$. This is predicted by the expected graph evolution of the SC-LDPC and the OC-LDPC ensembles analyzed in Section \[Sec:Analysis\].

Meanwhile, the OCp-LDPC code also shows the same performance as the OC-LDPC code because the OC-LDPC code already achieves the performance bound, which means that the precoding technique is not required for large $L$. Furthermore, when the maximum number of iterations is restricted to $I_{\rm max}=100$, the block error rate of the codes for $L=50$ is compared in Fig. \[fig:Simulation\_FER\_L50\_iter100\], which shows a noticeable improvement of the OC-LDPC code. The additional performance improvement comes from the low required number of iterations $I_{\rm OC}(\epsilon_r)$ discussed in Section \[Sec:Analysis\].

Conclusions {#Sec:Conclusion}
===========

In this paper, a new coupled ensemble constructed by overlapping two circluar SC-LDPC ensembles is proposed. A key property of the proposed ensemble called OC-LDPC ensemble is that it behaves as two SC-LDPC ensembles with shorter chain lengths during the decoding process. Since the SC-LDPC ensemble is more easily decoded as the chain length decreases, the OC-LDPC ensemble gives more improved BP thresholds compared with the SC-LDPC ensemble. As a measurement of the decoding complexity, we use the required number of iterations which is an important measure to design practically usable codes. The numerical results show that the OC-LDPC ensemble reduces the required number of iterations compared with the SC-LDPC ensemble. The construction method of random-based ensembles can be extended to protograph-based ensembles. From the numerical analysis, we also verify that the performance improvement of the OC-LDPC codes can be achieved not only for asymptotic performances but also for finite-length performances.

[10]{} S. Kudekar, T. J. 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. 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–2190, Sep. 1999. A. Sridharan, M. Lentmaier, D. J. Costello Jr., and K. S. Zigangirov, “Convergence analysis of a class of LDPC convolutional codes for the erasure channel,” [*in Proc. Allerton Conf. Commun. Control Comput.*]{}, Monticello, IL, Oct. 2004, pp. 953–962. R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello, Jr., “LDPC block and convolutional codes based on circulant matrices,” [*IEEE Trans. Inf. Theory*]{}, vol. 50, no. 12, pp. 2966–2984, Dec. 2004. A. Pusane, A. J. Feltstrom, A. Sridharan, M. Lentmaier, K. S. Zigangirov, and D. J. Costello, Jr., “Implementation aspects of LDPC convolutional codes,” [*IEEE Trans. Commun*]{}., vol. 56, no. 7, pp. 1060–1069, Jul. 2008 M. Lentmaier, A. Sridharan, D. J. Costello, Jr., and K. Sh. Zigangirov, “Iterative decoding threshold analysis for LDPC convolutional codes,” [*IEEE Trans. Inf. Theory*]{}, vol. 56, no. 10, pp. 5274–5289, Oct. 2010. A. E. Pusane, R. Smarandache, P. O. Vontobel, and D. J. Costello, Jr., “Deriving good LDPC convolutional codes from LDPC block codes,” [*IEEE Trans. Inf. Theory*]{}, vol. 57, no. 2, pp. 835–857, Feb. 2011. D. G. M. Mitchell, A. E. Pusane, and D. J. Costello, Jr., “Minimum distance and trapping set analysis of protograph-based LDPC convolutional codes,” [*IEEE Trans. Inf. Theory*]{}, vol. 59, no. 1, pp. 254–281, Jan. 2013. 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. A. Yedla, Y.-Y. Jian, P. S. Nguyen, and H. D. Pfister, “A simple proof of threshold saturation for coupled scalar recursions,” in [*Proc. 7th Int. Symp. Turbo Codes Iterative Inf. Process. (ISTC)*]{}, Gothenburg, Sweden, Aug. 2012, pp. 51–55. ——, “A simple proof of Maxwell saturation for coupled scalar recursions,” [*IEEE Trans. Inf. Theory*]{}, vol. 60, no.11, pp. 6943–6965, Nov. 2014. S. Kudekar, T. J. Richardson, and R. L. Urbanke, “Wave-like solutions of general 1-D spatially coupled systems,” [*IEEE Trans. Inf. Theory*]{}, vol. 61, no. 8, pp. 4117–4157, Aug. 2015. P. M. Olmos and R. Urbanke, “A scaling law to predict the finite-length performance of spatially coupled LDPC codes,” [*IEEE Trans. Inf. Theory*]{}, vol. 61, no. 6, pp. 3164–3184, Jun. 2015. R. Ohashi, K. Kasai, and K. Takeuchi, “Multi-dimensional spatially coupled codes,” in [*Proc. IEEE Int. Symp. Inf. Theory (ISIT)*]{}, Istanbul, Turkey, Jul. 2013, pp. 2448–2452. Y. Liu, Y. Li, and Y. Chi, “Spatially coupled LDPC codes constructed by parallelly connecting multiple chains,” [*IEEE Commun. Lett.*]{}, vol. 19, no. 9, Sep. 2015. D. Truhachev, D. G. M. Mitchell, M. Lentmaier, and D. J. Costello, Jr, “Connecting spatially coupled LDPC code chains,” in [*Proc. IEEE Int. Conf Commun (ICC)*]{}, Ottawa, Canada, Jun. 2012, pp. 2176–2180. ——, “New codes on graphs constructed by connecting spatially coupled chains,” in [*Proc. IEEE ITA*]{}, 2012, pp. 392–397. ——, “New codes on graphs constructed by connecting spatially coupled chains,” \[Online\]. Available: http://arxiv.org/abs/1312.3368 P. M. Olmos, D. G. M. Mitchell, D. Truhachev, and D. J. Costello, Jr., “Improving the finite-length performance of spatially coupled LDPC codes by connecting multiple code chains,” \[Online\]. Available: http://arxiv.org/abs/1402.7170 ——, “Improving the finite-length performance of long SC-LDPC code chains by connecting consecutive chains,” in [*Proc. IEEE ISTC*]{}, Aug. 2014, pp. 72–76. S. Kudekar, C. Measson, T. J. Richardson, and R. L. Urbanke, “Threshold saturation on BMS channels via spatial coupling,” in [*Proc. 6th Int. Symp. Turbo Codes Iterative Inf. Process. (ISTC)*]{}, Brest, France, Sep. 2010, pp. 309–313. J. Thorpe, “Low density parity check (LDPC) codes constructed from protographs,” JPL, California Inst. Technol. (CALTECH), CA, USA, Tech. Rep. 42–154, 2003. D. G. M. Mitchell, M. Lentmaier, and D. J. Costello, Jr., “Spatially coupled LDPC codes constructed from protographs,” [*IEEE Trans. Inf. Theory*]{}, vol. 61, no. 9, pp. 4866–4889, Sep. 2015. D. Divsalar, S. Dolinar, C. R. Jones, and K. Andrews, “Capacity approaching protograph codes,” [*IEEE J. Sel. Areas Commun.*]{}, vol. 27, no. 6, pp. 876–888, Aug. 2009. T. J. Richardson and R. Urbanke, [*Modern Coding Theory*]{}. Cambridge, U.K.: Cambridege Univ. Press, 2008. V. Aref, L. Schmalen, and S. ten Brink, “On the convergence speed of spatially coupled LDPC ensembles,” in [*Proc. 51st Annu. Allerton Conf. Commun., Control, Comput. (Allerton)*]{}, Monticello, IL, USA, Oct. 2013, pp. 342–349. M. Stinner and P. M. Olmos, “Analyzing finite-length protograph-based spatially coupled LDPC codes,” in [*Proc. IEEE Int. Symp. Inf. Theory (ISIT)*]{}, Honolulu, HI, USA, Jun./Jul. 2014, pp. 891–895. ——, “On the waterfall performance of finite-length SC-LDPC codes constructed from protographs,” in [*IEEE J. Sel. Areas Commun.*]{}, vol. 34, no. 2, pp. 345–361, Feb. 2016. M. B. Tavares, K. S. Zigangirov, and G. P. Fettweis, “Tail-biting LDPC convolutional codes,” in [*Proc. IEEE Int. Symp. Inf. Theory (ISIT)*]{}, Nice, France, Jun. 2007, pp. 2341–2345.

[^1]: H. Kwak, B. Jun, P. Yang, and J.-S. No are with the Department of Electrical and Computer Engineering, INMC, Seoul National University, Seoul 08826, Korea (e-mail: ghy1228@ccl.snu.ac.kr, netjic@ccl.snu.ac.kr, yangpw@ccl.snu.ac.kr, jsno@snu.ac.kr).

[^2]: D.-J. Shin is with the Department of Electronic Engineering, Hanyang University, Seoul 133-791, Korea (e-mail: djshin@hanyang.ac.kr).

[^3]: The definition of coupled ensemble in [@Olmos], [@Olmos2] is somewhat different from the definition in [@Kudekar1]. As mentioned in [@Olmos], the definition in [@Olmos], [@Olmos2] imposes structure on connections of variable nodes such that a variable node at position $v$ has exactly one connection to a check node at position $u$ if $[{\bf T}]_{u,v}=1$. Since the scaling law is easily derived by using the definition in [@Olmos], [@Olmos2], we will follow the definition in [@Olmos], [@Olmos2] for the analysis of the scaling law.

[^4]: The set ${\mathcal S}$ is analogous to the stopping set defined in Tanner graph [@Richardson].
