# An Efficient Algorithm for Counting Cycles in QC and APM LDPC Codes

Mohammad Gholami111Department of Mathematics, Shahrekord University, P.O. Box:
88186-34141, Shahrekord, Iran222Institute for Research in Fundamental Sciences
(IPM), P.O. Box: 19395-5746, Tehran, Iran<EMAIL_ADDRESS>Zahra
Gholami333Department of Mathematics, Shahrekord University, P.O. Box:
88186-34141, Shahrekord, Iran<EMAIL_ADDRESS>
###### Abstract

In this paper, a new method is given for counting cycles in the Tanner graph
of a (Type-I) quasi-cyclic (QC) low-density parity-check (LDPC) code which the
complexity mainly is dependent on the base matrix, independent from the CPM-
size of the constructed code. Interestingly, for large CPM-sizes, in
comparison of the existing methods, this algorithm is the first approach which
efficiently counts the cycles in the Tanner graphs of QC-LDPC codes. In fact,
the algorithm recursively counts the cycles in the parity-check matrix column-
by-column by finding all non-isomorph tailless backtrackless closed (TBC)
walks in the base graph and enumerating theoretically their corresponding
cycles in the same equivalent class. Moreover, this approach can be modified
in few steps to find the cycle distributions of a class of LDPC codes based on
Affine permutation matrices (APM-LDPC codes). Interestingly, unlike the
existing methods which count the cycles up to $2g-2$, where $g$ is the girth,
the proposed algorithm can be used to enumerate the cycles of arbitrary length
in the Tanner graph. Moreover, the proposed cycle searching algorithm improves
upon various previously known methods, in terms of computational complexity
and memory requirements.

###### keywords:

QC-LDPC codes, Tanner graph, girth, counting cycles, backtrackless closed
walks.

††journal: Iranian Journal of Science

##  1 Introduction

Low-density parity-check (LDPC) codes, first discovered by Gallager [1], were
rediscovered about 30 years later to be Shannon limit-approaching codes over
additive white Gaussian noise (AWGN) channels [7],[8]. It is established that
the performance of LDPC codes under iterative decoding depends upon by certain
combinatorial structures such as multiplicities and distribution of short
cycles in the Tanner graph. When there are short cycles in the Tanner graph,
the belief-propagation algorithm (BPA) does not converge to maximum likelihood
performance [3]. Because, a message delivered by a node along a cycle will
propagate back to the node itself after several iterations causing decreasing
of independence in the messages sent afterward.

Large girth, however, is not sufficient to ensure a good graphical model. The
performance of two LDPCs with the same girth, but a different number of short
cycles, can be significantly different. The regularity or non-regularity of
the cycle structure of a graph (i.e., how a randomness effect of the graph
appears) also affects graphical code model quality. For example, the
introduction of irregularity to LDPC designs is known to improve performance
[6]. In summary, good graphical models of codes imply to have large girth,
small number of short cycles, or some cycle structures which are not overly
regular. Based on the connection between the performance of a code and the
properties of its associated graphical model, characterizing the cycle
structure of a graphical model is of great interest. The difficulty in
enumerating and counting cycles and paths in arbitrary graphs may prevent an
efficient search of good LDPC codes with small short cycles. To solve the
problem, this paper presents a new algorithm of counting short cycles by
analyzing the shapes of the cycles of Tanner graph in base matrix for
designing good LDPC codes which is less complex than the existing algorithms.

Unlike the existing algorithms based on matrix multiplication [5], [8] which
cause to high computational complexity and time consuming, the proposed method
has a lower complexity for counting short cycles. In the proposed method,
first all of the chains associated to TBC walks in the protograph of a QC-LDPC
code are classified by a non-isomorphic relation, then each chain corresponds
to some cycles which are enumerated by the period of some sets (in fact, these
sets are the row indices of the nonzero elements in a block which have the
same topological shapes when traversing the walk by starting from each element
of the set). This method can be used effectively to evaluate the performance
of LDPC codes according to their short circle distributions.

Several methods have been investigated the parity-check matrices such that the
associated TGs are free of short cycles [7], [8]. However, LDPC codes are
often designed without explicit constraints on the girth. In [10], a method
for counting cycles of length less than 8 is presented, however, this method
is complex for longer cycles and addresses the restricted problem of counting
the cycles of length $g$, $g+2$ and $g+4$ in bipartite graphs with girth $g$.
In [54], a novel theoretical method is proposed to evaluate the number of
closed paths of different lengths in an all-one base matrix up to closed paths
of length 10. The algorithm in [5], [9], which is capable of counting short
cycles $g,g+1,\cdots,2g-1$ in a general graph, and short cycles of length
$g,g+2,\cdots,2g-2$ in the Tanner graph. The algorithm [9], is based on
performing integer additions and subtractions in the nodes of the graph and
passing extrinsic messages to adjacent nodes. The complexity of the method [9]
is $O(g|E|^{2})$, where $|E|$ is the number of edges in the graph. The
proposed method in [23] is based on the relationship between the number of
short cycles in the graph and the eigenvalues of the directed edge-adjacency
matrix of the graph. In order to find the eigenvalues of the directed edge
matrix of the graph, one needs to find the eigenvalues of $N$ matrices, each
of size $|E_{b}|\times|E_{b}|$. This reduces the complexity from
$O(N^{3}|E_{b}|^{3})$ to $O(N|E_{b}|^{3})$, which $|E_{b}|$ is the number of
directed edges in matrix of the base graph. Compared to the complexity
$O(g|E|^{2})=O(gN^{2}|E_{b}|^{2})$ of the algorithm in [9], the proposed
algorithm is less complex if $gN$ grows faster than $|E_{b}|$. This would be
the case for protograph codes with small base graph and large lifting degree.
In terms of memory requirements, for example, for a regular LDPC code of
variable node degree $d_{u}$, the proposed method needs $N|E_{b}|^{2}$ memory
location eigenvalues of $N$ matrices. The algorithm of [9], on the other hand,
needs $2d_{u}|E|$ locations, which would be less than that of the proposed
method if $|U_{b}|>2$.

For fixed values of $k\leq 13$, there are explicit formula [12], [13] and
[14], expressing the number of cycles of length $k$ through adjacency matrix
graph. The computational complexity of these formulas for $k\leq 7$ is of the
same order as the multiplication of $n\times n$ matrices, and for $k\geq 8$,
it is the amount of $O(n^{[k/2]}\log n)$, where $n$ is the number of vertices.
It is known that the complexity of counting cycles of length $k$ in arbitrary
graphs inevitably increases with $k$ [17]. A number of works devoted counting
short cycles in bipartite graphs LDPC-code is characterized by low density and
the value of the girth $g\geq 6$. The feature most the methods discussed below
is that by limiting the length of the cycle (relative to girth) is achieved
while the $O(n^{4})$. Thus, the authors of [5] (halford) presented an
algorithm for girth $g$ bipartite graph, and count the number of cycles of
length $g,g+2$ and $g+4$ with the same order of complexity that multiplication
$n\times n$ matrices (for fixed $g$). They showed that in addition to the
girth, the number and statistics of short cycles are also important
performance metrics of the code. The complexity of their method is
$O(gn^{3})$, where $n$ is the size of the larger set between the two node
partitions.

In [18], [48], some affine permutation matrices (APM) are used to generate a
class of LDPC codes, called APM-LDPC codes, which are not QC in general.
Unlike Type-I conventional QC-LDPC codes, the constructed $(J,L)$ APM-LDPC
codes with the $J\times L$ all-one base matrix can achieve minimum distance
greater than $(J+1)!$ and girth larger than 12. Moreover, the lengths of the
constructed APM-LDPC codes, in some cases, are smaller than the best known
lengths reported for QC-LDPC codes with the same base matrices. As an
advantage, the constructed APM-LDPC codes are flexible in lengths and rates.
In some cases the lengths of the constructed codes are smaller than the best
known lengths reported for the lengths of QC-LDPC codes in [27], [26], [22],
[29], [35], [31]. Another significant advantage of the constructed APM-LDPC
codes is that they have remarkably fewer cycle multiplicities compared to QC-
LDPC codes with the same base matrices and the same lengths. Simulation
results show that the constructed APM-LDPC codes with lower girth outperform
QC-LDPC codes with larger girth.

This paper is organized as follows. In Section 2, first, some preliminaries
and notations useful for the next sections of the paper, are provided. Then,
cycles of QC-LDPC codes and APM-LDPC codes are investigated in Section 3 by
some modular equations and allowable and non-allowable chains are defined to
estimate the number of cycles in the Tanner graph of a QC (APM) LDPC code.
Finally, for a given binary matrix $B$, an algorithm for counting the cycles
of a QC (APM) LDPC codes is introduced in Section 4 and then, the complexity
of this algorithm is investigated.

##  2 Preliminaries and Definitions

An undirected Graph $G=(V,E)$ is defined as a set of nodes $V$ and a set of
edges $E$, where $E$ is some subset of the pairs $\\{\\{u,v\\}:u,v\in V,u\neq
v\\}$. A walk of length $k$ in $G$ is a sequence of nodes
$v_{1},v_{2},\cdots,v_{k+1}$ in $V$ such that $\\{v_{i},v_{i+1}\\}\in E$ for
all $i\in\\{1,\cdots,k\\}$. Equivalently, a walk of length $k$ can be
described by the corresponding sequence of $k$ edges. A walk is closed if the
two end nodes are identical, i.e., $v_{1}=v_{k+1}$ in the previous
description. A closed walk is backtrackless if $e_{i_{s}}\neq e_{i_{s}+1}$ for
each $1\leq s\leq k$ and it is tailless if $e_{i_{1}}\neq e_{i_{k}}$. Let
$v,k$ be some positive integers and $V=\\{1,2,\ldots,v\\}$. By a $(v,k)$
block-design, we mean a list of $k$ subsets $B_{i}$, $1\leq i\leq k$, of $V$,
denoted by ${\cal B}=[B_{1},B_{2},\ldots,B_{k}]$. In this definition, $B_{i}$,
$1\leq i\leq k$, are called the blocks and the term list is used to allow the
repetition and the ordering of the blocks. To an LDPC code with the parity-
check matrix $H$, a bipartite graph, called Tanner graph TG$(H)$, is
associated which collects variable nodes and check nodes corresponding to the
columns and rows of $H$, respectively, and each edge connects a check node to
a bit node if nonzero entry exists in the intersection of the corresponding
row and column of $H$. The girth of a code with a given parity-check matrix
$H$, denoted by $g(H)$, is the length of a shortest cycle in TG$(H)$ which is
always an even number.

Protograph codes [21] are a class of structured LDPC codes, constructed from a
bipartite graph with relatively small number of variable nodes and check
nodes, called a protograph. In the construction, the first step is to choose a
protograph with a near capacity decoding threshold as a building block and
then to make copies of the chosen protograph and permute the edges of copies
according to certain rules to connect them into a Tanner graph of larger size.
The parity-check matrix of a protograph code can be obtained from the
incidence matrix of protograph with the replacement of each 1 and 0 by some
$m\times m$ permutation and zero matrices, respectively. By considering such
permutations as circulant permutation matrices (CPM) or affine permutation
matrices (APM), two classes of protograph codes, called (Type I) QC-LDPC codes
and APM-LDPC codes, respectively, can be defined. For some integers $m$, $s$
and $a$, satisfying in $0\leq s<m$, $1\leq a<m$ and $\gcd(a,m)=1$, by the APM
$I_{m}^{s,a}$ with slope $s$ and shift $a$, briefly $I^{s,a}$ when $m$ is
known, we mean a $m\times m$ binary matrix $(e_{i,j})_{0\leq i,j<m}$ in which
$e_{i,j}=1$ if and only if $i=aj+s\bmod m$. In fact, $I^{s,a}$ is the $m\times
m$ binary permutation matrix for which the only non-zero element in the first
column occurs in position $s$, and each other column is shifted down by $a$
positions, regard to the previous column. In particular, if $a=1$,
$I_{m}^{s,a}$ is denoted by $I_{m}^{s}$ which is called a CPM of size $m$ and
slope $s$. Hence, APM LDPC codes can be considered as a generalization of QC-
LDPC codes.

Based on the evidence obtained that connecting the performance of a code and
the properties of its associated graphical model, characterizing the cycle
structure of a graphical model is of great interest. The difficulty in
enumerating and counting cycles and paths in arbitrary graphs may prevent an
efficient search of good LDPC codes with small short cycles. To solve the
problem, we first present a new recursive algorithm for counting short cycles
in QC LDPC codes based on analyzing the TBC walks in protograph having less
complexity rather than the other existing methods. Then, we use a modified
version of this algorithm to count the cycles in APM-LDPC codes.

##  3 Cycles in QC $\&$ APM LDPC codes

As QC-LDPC codes can be embraced in the class of APM LDPC codes and for
simplicity of notations, we first set up the notations and terminologies for
the case of APM-LDPC codes, then we apply them for QC-LDPC codes. For some
positive integers $v$, $k$, $v<k$, let $B$ be a $v\times k$ binary matrix and
${\cal B}=[B_{1},B_{2},\ldots,B_{k}]$ be the corresponding $(v,k)$ block-
design with blocks $B_{i}\subseteq V=\\{1,2,\ldots,v\\}$, where each $B_{i}$
is the row-indices of non-zero elements of the $i$th column of $B$. For
positive integer $m$, by a $(m,{\cal B})$-slope vector and a $(m,{\cal B})$
shift vector, we mean two finite sequences $S=(s_{i,j})_{1\leq i\leq v,j\in
B_{i}}$ and $A=(a_{i,j})_{1\leq i\leq v,j\in B_{i}}$, respectively, such that
each $s_{i,j}$ belongs to ${\mathbb{Z}}_{m}$ and $a_{i,j}$ belongs to
${\mathbb{Z}}^{*}_{m}$, where ${\mathbb{Z}}_{m}$ is the ring of integers
modulo $m$ and ${\mathbb{Z}}^{*}_{m}=\\{a\in{\mathbb{Z}}:\gcd(a,m)=1\\}$. Now,
for given $(m,{\cal B})$-slope vector $S$ and $(m,{\cal B})$-shift vector $A$,
let ${\cal H}_{m,{\cal B},S,A}$ be the $vm\times km$ parity-check matrix of an
APM-LDPC code with APM size $m$ obtained by replacing each zero and $(i,j)$
non-zero element of $B$ by the $m\times m$ zero matrix and
$I^{s_{i,j},a_{i,j}}$, respectively. For the case of QC-LDPC codes, i.e. when
$A$ is a fully one matrix, we just use ${\cal H}_{m,{\cal B},S}$ to denote the
corresponding parity-check matrix. Now, the following theorem is very useful
to verify the cycles in the Tanner graph of each APM-LDPC code.

###### Theorem 3.1

([18]) Each $2l-$cycle in TG$({\cal H}_{m,{\cal B},S,A})$ corresponds to a
finite chain $(i_{0},$ ${j_{0}},$ $i_{1},$ ${j_{1}},$ $\ldots,$ $i_{{l-1}},$
${j_{l-1}})$, $i_{l}=i_{0},$ such that for each $1\leq k\leq l$,
$\\{i_{k-1},i_{k}\\}\subseteq B_{j_{k-1}}$, $i_{k-1}\neq i_{k}$, $j_{k-1}\neq
j_{k}$, and for
$A=\sum_{k=0}^{l-1}(p_{k}s_{i_{k},j_{k}}-p_{k+1}s_{i_{k+1,j_{k}}})$, where
$p_{h}=\prod_{k=h}^{l-1}a_{i_{k+1},j_{k}}a_{i_{k},j_{k}}^{-1}\bmod m$, $0\leq
h\leq l-1$, one of the following relations holds:

  1. 1.

$p_{0}=1$ and $A=0$.

  2. 2.

$\gcd(p_{0}-1,m)|A$.

Especially, for QC-LDPC codes, Theorem 3.1 can be simplified as follows.

###### Theorem 3.2

([22]) Each $2l-$cycle in TG$({\cal H}_{m,{\cal B},S})$ corresponds to a
$2l$-cycle chain $(i_{0},$ ${j_{0}},$ $i_{1},$ ${j_{1}},$ $\ldots,$
$i_{{l-1}},$ ${j_{l-1}})$ in which
$\sum_{k=0}^{l-1}(s_{i_{k},j_{k}}-s_{i_{k+1,j_{k}}})=0\pmod{m}$.

Hereinafter, each finite chain $(i_{0},$ ${j_{0}},$ $i_{1},$ ${j_{1}},$
$\ldots,$ $i_{{l-1}},$ ${j_{l-1}})$ satisfying in Theorem 3.1 for APM-LDPC
codes (or Theorem 3.2 for QC LDPC codes) is called a $2l$-cycle chain.

Figure 1: An unallowable 14-cycle sequence.

The converse of Theorem 3.1 is not true in general. In other words, each
$2l-$cycle chain may be induces a cycle in the Tanner graph with length less
than $2l$. In this case, this cycle chain contains a $2k$-cycle chain, for
some $k<l$ and some middle points in the cycle return on their owns. This
situation describes a non-allowable cycle chain, otherwise, i.e. if the cycle
chain doesn’t contain an smaller cycle chain, we say that the cycle chain is
allowable. For example, Fig. 1 shows the cycle chain
$(2,2,0,1,1,2,0,1,1,0,2,2,1,0)$ which is non-allowable, because it contains an
smaller cycle chain $(2,2,0,1,1,0,2,2)$. For non-allowable cycle chains, it is
noticed that the elements of the proper sub-chain are not essentially
successive in the parent cycle chain.

In continue, we give a necessary and sufficient condition for a cycle-chain in
a APM LDPC code to be allowable. Let
$L=(i_{0},{j_{0}},i_{1},{j_{1}},\ldots,i_{{l-1}},{j_{l-1}})$ be a $2l$-cycle
chain in a APM LDPC code with $(m,{\cal B})$-slope vector $S=(s_{i,j})_{1\leq
i\leq v,j\in B_{i}}$ and $(m,{\cal B})$ shift vector $A=(a_{i,j})_{1\leq i\leq
v,j\in B_{i}}$ where ${\cal B}=[B_{1},B_{2},\ldots,B_{k}]$ is a $(v,k)$ block-
design for some $v,k$. Now, for a given $0\leq r\leq m-1$, define the
sequences $(\delta^{\rightarrow,t})_{t=0}^{l-1}$ and
$(\delta^{\uparrow,t})_{t=0}^{l-1}$ recursively, as follows:

$\left\\{\begin{array}[]{ll}\delta^{\rightarrow,0}=r,&\delta^{\rightarrow,t+1}=a_{i_{t+1},j_{t}}a_{i_{t},j_{t}}^{-1}(\delta^{\rightarrow,t}-s_{i_{t},j_{t}})+s_{i_{t+1},j_{t}}\bmod
m,\\\ \\\ \delta^{\uparrow,0}=a_{i_{0},j_{0}}^{-1}(r-s_{i_{0},j_{0}})\bmod
m,&\delta^{\uparrow,t+1}=a_{i_{t+1},j_{t+1}}^{-1}(a_{i_{t+1},j_{t}}\delta^{\uparrow,t}+s_{i_{t+1},j_{t}}-s_{i_{t+1},j_{t+1}})\bmod
m\end{array}\right.$

###### Lemma 3.3

$L$ is allowable if and only if for each $p,q,r$, $0\leq p<q\leq l-1$, $0\leq
r\leq m-1$, we have $\delta^{\rightarrow,q}\neq\delta^{\rightarrow,p}$ when
$i_{p}=i_{q}$, and $\delta^{\uparrow,q}\neq\delta^{\uparrow,p}$ when
$j_{p}=j_{q}$.

Proof. Corresponding to the cycle chain
$L=(i_{0},{j_{0}},i_{1},{j_{1}},\ldots,i_{{l-1}},{j_{l-1}})$, let ${\cal
P}_{r}=v_{1}v_{2}\ldots v_{2l}v_{2l+1}$, $v_{1}=v_{2l+1}$, be the closed path
starting from the point $v_{1}$ having row-index $r$ in the block
$(i_{0},j_{0})$ of the parity-check matrix $H$. Without loss of generality,
let $v_{2}$ be the point having the same column-index with $v_{1}$, therefore
each vertex $v_{k}$, $1\leq k\leq 2l$, with the odd or even index $k$ belongs
to the block $(i_{p},j_{p})$ or $(i_{p},j_{p-1})$, respectively, where
$p=\lfloor\frac{k}{2}\rfloor$. Clearly, the column-index of $v_{1}$ is
$a_{i_{0},j_{0}}^{-1}(r-s_{i_{0},j_{0}})\bmod m$. Moreover, for each $1\leq
k\leq 2l$, it can be seen easily that $\delta^{\rightarrow,k}$ and
$\delta^{\uparrow,k}$ are the row and column indices of the point $v_{k}$,
respectively. Now, if $L$ in not allowable, then for some $0\leq r\leq m-1$
and $1\leq k+1<k^{\prime}\leq 2l$, two middle (not successive) points $v_{k}$
and $v_{k^{\prime}}$ belong to the same column-block of $H$, whereas they have
the same column-indices, i.e. $\delta^{\uparrow,p}=\delta^{\uparrow,q}$ and
$j_{p}=j_{q}$, where
$p=\lfloor\frac{k}{2}\rfloor<q=\lfloor\frac{k^{\prime}}{2}\rfloor$, or $v_{k}$
and $v_{k^{\prime}}$ belong to the same row-block of $H$, while their row-
indices are the same, i.e. $\delta^{\rightarrow,p}=\delta^{\rightarrow,q}$ and
$i_{p}=i_{q}$. Now, the proof is completed. $\square$

For QC-LDPC codes, allowability of cycle-chains in Lemma 3.3 can be simplified
as follows.

###### Lemma 3.4

Let $L=(i_{0},{j_{0}},i_{1},{j_{1}},\ldots,i_{{l-1}},{j_{l-1}})$ be a
$2l$-cycle chain in a QC LDPC code with $(m,{\cal B})$-slope vector
$S=(s_{i,j})_{1\leq i\leq v,j\in B_{i}}$, where ${\cal
B}=[B_{1},B_{2},\ldots,B_{k}]$ is a $(v,k)$ block-design for some $v,k$. Then,
$L$ is allowable if and only if for each $p,q$, $0\leq p<q\leq l-1$, if we
define
$\Delta_{p,q}^{\rightarrow}=\sum_{k=p}^{q}(s_{i_{k+1},j_{k}}-s_{i_{k},j_{k}})\bmod
m$ and
$\Delta_{p,q}^{\uparrow}=\sum_{k=p}^{q}(s_{i_{k+1},j_{k+1}}-s_{i_{k+1},j_{k}})\bmod
m$, then for each $0\leq p<q<l-1$, we have $\Delta_{p,q}^{\rightarrow}\neq 0$
when $i_{p}=i_{q}$, and $\Delta_{p,q}^{\uparrow}\neq 0$, when $j_{p}=j_{q}$.

Figure 2: An allowable $16-$cycle chain $(1,2,0,0,1,1,0,0,1,2,0,0,1,1,0,0)$ in
$H$.

###### Example 3.5

Let $H$ be the parity-check matrix of a QC LDPC code shown in Fig. 2 with
$(10,{\cal B})$-slope vector
$(s_{0,0},s_{1,0},s_{0,1},s_{1,1},s_{0,2},s_{1,2})=(0,0,0,1,0,4),$ where
${\cal B}=[\\{1,2\\},\\{1,2\\},\\{1,2\\}]$. The dash lines indicates the
$16-$cycle chain $(1,2,0,0,1,1,0,0,1,2,0,0,1,1,0,0)$ in $H$ which corresponds
to the relation
$(s_{1,2}-s_{0,2})+(s_{0,0}-s_{1,0})+(s_{1,1}-s_{0,1})+(s_{0,0}-s_{1,0})+(s_{1,2}-s_{0,2})+(s_{0,0}-s_{1,0})+(s_{1,1}-s_{0,1})+(s_{0,0}-s_{1,0})=10=0\pmod{10}$.

Hereinafter, we just consider allowable cycle chains, unless stated otherwise.
By Theorem 3.2, cycles in the Tanner graph of a QC-LDPC code can be enumerated
from cycle-chains. For this purpose, it is enough to count the whole number of
cycles in the Tanner graph which corresponds to a given cycle-chain. First, we
define the following relation on the set of cycle-chains.

###### Definition 3.6

Two $2l$-cycle chains $L_{1}$ and $L_{2}$ are called isomorph if and only if
there exist some $k\in\mathbb{Z}$, such that $\pi^{2k}(L_{1})=L_{2}$, where
$\pi$ is the cyclic permutation $(1,2,\ldots,2l)$ and for each permutation
$\sigma\in S_{k}$, $\sigma(i_{1},i_{2},\ldots,i_{k})$ is defined as
$(i_{\sigma(1)},i_{\sigma(2)},\ldots,i_{\sigma(k)})$. In fact, each two cycle
chains are isomorph if and only if they traverse the same blocks of the
parity-check matrix by reading the chains by starting from different points in
directions left-to-right or right-to-left. For example, in Fig. 3, two
12-cycle chains $(1,2,0,0,1,2,0,1,1,0,0,1)$ and $(1,2,0,1,1,0,0,1,1,2,0,0)$
are isomorphic.

Clearly, the isomorph relation in Definition 3.6 is an equivalence relation,
which defines isomorph classes. For counting the cycles, we just consider non-
isomorph cycle-sequences, which are not included in the same class.

###### Definition 3.7

Let $(i_{0},j_{0},i_{1},j_{1},\ldots,i_{l-1},j_{l-1})$ be a $2l$-cycle
sequence. For each $0\leq q\leq l-1$, $p=q$ or $q+1$, define $A(i_{p},j_{q})$
to be the set of all values
$\sum_{k=0}^{t}(s_{i_{k},j_{k}}-s_{i_{k+1,j_{k}}})\bmod m$, in which the index
$t$ is a nonnegative integer less than $l$ satisfied in
$(i_{t},j_{t})=(i_{p},j_{q})$. In fact, $A(i_{p},j_{q})$ is the row-index set
of all points of the cycle when it pass from the $(i_{p},j_{q})$ block of the
parity-check matrix. For example, in Fig. 2, $A(0,0)=A(1,0)=\\{0,4,5,9\\}$,
$A(0,1)=A(1,2)=\\{4,9\\}$ and $A(0,2)=A(1,1)=\\{0,5\\}$.

###### Definition 3.8

For positive integer $m$, the period of each subset
$A\subseteq\mathbb{Z}_{m}$, denoted by $p_{m}(A)$, is defined as the smallest
positive number $T$ with $A+T=A$, where $A+T:=\\{a+T\pmod{m}:a\in A\\}$. For
example, $\\{0,2,4\\}$ is a subset of $\mathbb{Z}_{6}$ of period 2.

###### Lemma 3.9

If $A\subseteq\mathbb{Z}_{m}$ is of period $p_{m}(A)$, then $A$ can be written
as the union of disjoint sets $<a_{i}>$, for some $a_{1},\ldots,a_{k}\in A$,
where $<a>=\\{a+ip_{m}(A)\bmod m:1\leq i\leq t\\}$ in which $t$ is the
smallest non-negative integer satisfying $tp_{m}(A)=0\bmod m$.

Proof. For each $a\in A$, we have $a+p_{m}(A)\pmod{m}\in A$, because
$A=A+p_{m}(A)$, so $<a>\subseteq A$. On the other hand, $a\in<a>$, so
$A=\cup_{a\in A}<a>$. Now, for each two elements $a,b\in A$, we have $<a>=<b>$
or $<a>\cap<b>=\emptyset$. Because, if $c\in<a>\cap<b>$, then
$c=a+i_{1}p_{m}(A)=b+i_{2}p_{m}(A)$, for some $1\leq i_{1},i_{2}\leq t$.
Hence, $a=b+(i_{2}-i_{1})p_{m}(A)\in<b>$ or equivalently $<a>\subseteq<b>$.
Similarly, we have $<b>\subseteq<a>$, so $<a>=<b>$. Finally, $A$ can be
written as union of disjoint sets $<a_{i}>$, for some $a_{1},\ldots,a_{k}\in
A$. $\square$

It is noticed that the elements $a_{i}$, $1\leq i\leq k$ in Lemma 3.9 are not
necessarily unique. For example, for $m=6$ and $A=\\{0,2,4\\}$, we have
$A=<0>=<2>=<4>$. Now, let us mention two important consequences of the above
lemma.

###### Remark 3.10

For each $A\subseteq\mathbb{Z}_{m}$, $p_{m}(A)|m$ and for each $a\in A$, if
$t=|<a>|$, then we have $p_{m}(A)t=m$ and $t|\gcd(m,|A|)$. Moreover, $A=<a>$,
for some $a\in A$, if and only if $p_{m}(A)|A|=m$.
Proof. If $p_{m}(A)\not|m$, then there are some $q\in\mathbb{Z}$ and
$0<r<p_{m}(A)$ such that $m=p_{m}(A)q+r$. Now, we have $A+r=A-qp_{m}(A)=A$,
since $A+p_{m}(A)=A$, which is a contradiction with definition of $p_{m}(A)$.
Now, $t$ is the smallest positive number with $tp_{m}(A)=0\bmod m$, which
implies that $tp_{m}(A)=m$, because $p_{m}(A)|m$. Similarly, for $t=|<a>|$, if
$t\not|m$, then $m=tq+r$, for some $q\in\mathbb{Z}$ and $0<r\leq t$. Now,
$rp_{m}(A)=(m-tq)p_{m}(A)=0\bmod m$ which is a contradiction with definition
of $t$, as the smallest positive integer satisfying $tp_{m}(A)=0\bmod m$. So,
$t|m$. On the other hand, $|A|=\sum_{i=1}^{k}|<a_{i}>|=\sum_{i=1}^{k}t=kt$, so
$t\mid|A|$, then, we have $t|\gcd(m,|A|)$. On the other hand, $A=<a>$, for
some $a\in A$, if and only if $|A|=|<a>|=t$, or $|A|p_{m}(A)=m$. $\square$

###### Remark 3.11

If $m$ is prime and $A\subseteq\mathbb{Z}_{m}$, then by Remark 3.10, we have
$p_{m}(A)|m$, so $p_{m}(A)=1$ or $p_{m}(A)=m$. However, $p_{m}(A)=1$ if and
only if $A=\mathbb{Z}_{m}$, in this case $A=<a>$, for each $a\in A$.

Proof. If $p_{m}(A)=1$, then $t=m$, because $tp_{m}(A)=m$. So in this case,
for each $a\in A$, $<a>=\\{a+1\bmod m,a+2\bmod m,\ldots,a+m\bmod
m\\}=\mathbb{Z}_{m}$. $\square$

###### Definition 3.12

Let $L=(i_{0},j_{0},i_{1},j_{1},\ldots,i_{l-1},j_{l-1})$ be a $2l$-cycle
chain. If $e$, $1\leq e\leq l-1$, is the first number such that
$(i_{e+p},j_{e+p})=(i_{p},j_{p})$, for all $0\leq p\leq l-1$, where all
indices $e+p$ are reduced in modulo of $l$, then define
$I(L)=\\{(i_{k},j_{k}),(i_{k+1},j_{k}):0\leq k\leq e-1\\}$. Otherwise, if no
such $e$ exists, then define $I(L)$ to be the empty set. In fact, $I(L)$ is
the set of all pairs $(i_{k},j_{k})$, $1\leq k\leq l-1$ such that the cycle
chain $L$ which starts from $(i_{0},j_{0})$ traverses the same points if it
starts from $(i_{k},j_{k})$. Clearly, if $I(L)\neq\emptyset$, then $e|l$, so
$n(L):=l/e$ is defined as the number of occurrence of $I(L)$ in the chain $L$,
otherwise, we set $n(L)=1$. In fact, each $2l-$cycle ${\cal
C}=v_{1}v_{2}\ldots v_{2l+1}$ ($v_{2l+1}=v_{1}$) in the Tanner graph (of the
QC LDPC code with the parity-check matrix $H$) corresponding to the $2l-$cycle
chain $L$, can be decomposed to $n(L)$ distinct paths ${\cal
P}_{k}=v_{2e(k-1)+1}v_{2e(k-1)+2}\ldots v_{2ek+1}$, $1\leq k\leq n(L)$, such
that for each $1\leq i\leq 2e$, all of the vertices $v_{i}$, $v_{2e+i}$,
$\ldots$, $v_{2(n(L)-1)e+i}$ are in the same block of $H$.

Figure 3: Two allowable 8-cycles in the parity-check matrix of Example 3.13.

###### Example 3.13

Let $H$ be the parity-check matrix of a QC LDPC code shown in Fig. 3 with
$(6,{\cal B})$-slope vector
$(s_{0,0},s_{1,0},s_{0,1},s_{1,1},s_{0,2},s_{1,2})=(0,5,0,5,0,2),$ where
${\cal B}=\\{\\{1,2\\},\\{1,2\\},\\{1,2\\}\\}$. The dash lines in parts $(a)$
and $(b)$ indicate two $8-$cycle chains $L_{1}=(1,2,0,1,1,2,0,1)$ and
$L_{2}=(1,2,0,0,1,2,0,1)$, respectively. It can be seen easily that
$I(L_{1})=\\{(1,2),(0,2),(0,1),(1,1)\\}$ and $I(L_{2})=\emptyset$. For the
chain $L_{1}$, we have $n(L_{1})=2$, because $L_{1}$ includes two copy of the
subchain $C=(1,2,0,1)$, i.e $L_{1}=(C|C)$, moreover, $n(L_{2})=1$.

We are now thus led to a theorem which gives the number of all distinct cycles
in the Tanner graph of a QC-LDPC code corresponding to a given cycle-chain.
First, we have two following lemmas.

###### Lemma 3.14

Let $m,s$ be two positive integers such that $s\leq m$. Then,
$\mathbb{Z}_{m}$, under the equivalence relation $a\sim b\Leftrightarrow
s|b-a$, can be partitioned to $a$ disjoint classes $[0]$, $[1]$, $\ldots$,
$[a-1]$, $a=\gcd(s,m)$, each class has $m/a$ elements.

Proof. Clearly, the equivalence classes from the partition of integer ring
under the given relation are $[0]$, $[1]$, $\ldots$, $[s-1]$. On the other
hand, in ring of the integers modulo of $m$, for each $i$, $0\leq i\leq a-1$,
$a=\gcd(s,m)$, we have $[i]=[a+i]=[2a+i]=\ldots$, because $a=\alpha s+\beta
m$, for some integers $\alpha$, $\beta$, so $a+i=\alpha s+\beta m+i=\alpha
s+i$ in $\mathbb{Z}_{m}$. Hence, $a$ is divisible by $s$ in $\mathbb{Z}_{m}$
and so $[i]=[a+i]$. Therefore, all of the disjoint classes in $\mathbb{Z}_{m}$
are $[0]$, $[1]$, $\ldots$, $[a-1]$. $\square$

###### Lemma 3.15

For each $2l$-cycle chain $L$, we have $n(L)|m$ and if $I(L)\neq\emptyset$,
for each $(i,j)\in I(L)$, the set $A(i,j)$ has the period $m/n(L)$.

Proof. Let $L=(i_{0},j_{0},\cdots)$ be $n(L)$ copy of the subchain
$C=(i_{0},j_{0},\cdots)$, i.e. $L=(C|C|\ldots|C)$ and ${\cal C}$ be the cycle
in the Tanner graph corresponding to the chain $L$. Moreover, let ${\cal
P}_{k}$, $1\leq k\leq n(L)$, be the segment of $\cal C$ corresponding to the
$k$th copy $C$ of $L$ which is a path in $\cal C$ with the starting and ending
points in the $(i_{0},j_{0})$th block. It can be seen easily that the row-
index difference of the end points in each path ${\cal P}_{k}$ is fixed, say
the value $s\in\mathbb{Z}_{m}$. However, $\bigcup_{k=1}^{n(L)}{\cal P}_{k}$ is
the cycle ${\cal C}$ with the same endpoints, so $n(L)s=0\pmod{m}$. On the
other hand, $s\neq 0$ and $n(L)$ is the smallest number satisfying in
$n(L)s=0\pmod{m}$, so $n(L)s=m$ which indicates $n(L)|m$. Now, for each
$(i,j)\in I(L)$ and each path ${\cal P}_{k}$, $1\leq k\leq n(L)$, let
$\\{r^{(i,j)}_{1},\cdots,r^{(i,j)}_{l}\\}$ be the set of the row-indices of
the points in the $(i,j)$th block. Clearly,
$A(i,j)=\bigcup_{k=1}^{l}[r_{k}^{(i,j)}]$, where
$[r_{k}^{(i,j)}]=\\{r_{k}^{(i,j)}+ts\bmod m:0\leq t<n(L)\\}$, because among
the points of $\cal C$ belong to the $(i,j)$th block, $s$ is the row-index
difference of each point in ${\cal C}_{k}$ with the corresponding point in
${\cal C}_{k+1}$, for each $1\leq k\leq n(L)$ (clearly, the amount of $s$ is
independent from $k$ and the selected points of ${\cal C}_{k}$). Now, the
period of each $[r_{k}^{(i,j)}]$ is $s$, so $A(i,j)=A(i,j)+s\bmod m$. However,
by the first part of the proof, we have $n(L)s=m$, so $s=m/n(L)$. Now, if
$p=p_{m}(A(i,j))<s$, then $p$ is divisible by $s$, and the chain composing of
$p$ subchain $C$ is a $2k-$cycle chain in $L$, for some $k<l$, which is a
contradiction. $\square$

###### Example 3.16

For $L=(1,2,0,0,1,1,0,0,1,2,0,0,1,1,0,0)$ in Fig .2, we have
$I(L)=\\{(i,j):0\leq i\leq 1,0\leq j\leq 2\\}$ and $n(L)=2$ which is divisible
by $m=10$. On the other hand, $A(0,0)=A(1,0)=\\{0,4,5,9\\}$,
$A(0,1)=A(1,2)=\\{4,9\\}$ and $A(0,2)=A(1,1)=\\{0,5\\}$, so
$p_{10}(A(i,j))=5=m/n(L)$, for each $(i,j)\in I(L)$.

###### Theorem 3.17

Each allowable $2l$-cycle chain
$L=(i_{0},j_{0},i_{1},j_{1},\ldots,i_{l-1},j_{l-1})$ corresponds to $r=r(L)$
cycles of length $2l$ in the Tanner graph, where $r=m/n(L)$.

Proof. Let ${\cal C}_{1},{\cal C}_{2},\ldots,{\cal C}_{r}$ be the all
different $2l$-cycles in the Tanner graph corresponding to the cycle chain
$L$. Moreover, let $L=(C|C|\ldots|C)$ be $n(L)$ copy of the subchain $C$ and
for each $1\leq t\leq r$ and $1\leq k\leq n(L)$, let path ${\cal
P}_{k}^{(t)}=v^{(t)}_{2(k-1)e+1}v^{(t)}_{2(k-1)e+2}\ldots v^{(t)}_{2ke+1}$,
$e=l/n(L)$, be the segment of ${\cal C}_{t}=v^{(t)}_{1}v^{(t)}_{2}\ldots
v^{(t)}_{2l}v^{(t)}_{2l+1}$, $v^{(t)}_{1}=v^{(t)}_{2l+1}$, corresponding to
the $k$’th copy $C$ of $L$. Now, providing that $I(L)\neq\emptyset$, for each
point $(i,j)\in I(L)=\\{(i_{k},j_{k}),(i_{k+1},j_{k}):0\leq k\leq l-1\\}$, let
$v^{(t)}_{f}$, $1\leq t\leq r$, be the first point of ${\cal P}_{1}^{(t)}$
belong to the $(i,j)$’th block of $H$ and $R^{(t)}(i,j)$ be the row indices of
the points $v^{(t)}_{f}$, $v^{(t)}_{f+2e}$, $\ldots$,
$v^{(t)}_{f+2(n(L)-1)e}$. Now, for each $1\leq t\leq r$,
$p_{m}(R^{(t)}(i,j))=m/n(L)$, for each $1\leq t\leq r$. On the other hand,
$\mathbb{Z}_{m}=\bigcup_{t=1}^{r}R^{(t)}(i,j)$, otherwise, there is a new
$2l-$cycle corresponding to the chain $L$ starting from the point with the row
index in $\mathbb{Z}_{m}\setminus\bigcup_{t=1}^{r}R^{(t)}(i,j)$. Hence, if we
define $s:=p_{m}(R^{(t)}(i,j))=m/n(L)$, then $\mathbb{Z}_{m}$ can be
partitioned to $r$ disjoint classes $R^{(t)}(i,j)$, $1\leq t\leq r$,
therefore, by Lemma 3.14, we have $r=\gcd(m,s)=m/n(L)$. On the other hand,
$I(L)=\emptyset$, then each cycle ${\cal C}_{t}$, $1\leq t\leq r$, can be
uniquely determined from the starting point of the cycle in the block
$(i_{0},j_{0})$ of $H$. Hence, if the starting points change, we have
different cycles, so in this case $r=m=m/n(L)$ and the proof is completed.
$\square$

Figure 4: The 16-cycle chain $(1,2,0,0,1,1,0,0,1,2,0,0,1,1,0,0)$ with
$A(0,0)=A(1,0)=\\{0,4,5,9\\}$, $A(0,1)=A(1,2)=\\{4,9\\}$ and
$A(0,2)=A(1,1)=\\{0,5\\}$ of period 5.

To clarify the proof of Theorem 3.17, we give the following example.

###### Example 3.18

In Fig. 4, the 16-cycle ${\cal C}_{1}=v^{(1)}_{1}v^{(1)}_{2}\ldots
v^{(1)}_{16}$ is given which corresponds to the 16-cycle chain
$L=(1,2,0,0,1,1,0,0,1,2,0,0,1,1,0,0)$. In fact, ${\cal C}_{1}$ can be
partitioned to paths ${\cal P}^{(1)}_{1}=v^{(1)}_{1}v^{(1)}_{2}\ldots
v^{(1)}_{9}$ and ${\cal P}^{(1)}_{2}=v^{(1)}_{9}v^{(1)}_{10}\ldots
v^{(1)}_{16}v^{(1)}_{1}$. Then, $R^{(1)}(0,0)=R^{(1)}(1,0)=\\{0,5\\}$,
$R^{(1)}(0,1)=\\{9\\}$, $R^{(1)}(1,2)=\\{4\\}$ and
$R^{(1)}(0,2)=R^{(1)}(1,1)=\\{0\\}$. Similarly, for the cycle ${\cal C}_{2}$
starting from the $v_{1}^{(2)}$, we have
$R^{(2)}(0,0)=R^{(2)}(1,0)=\\{1,6\\}$, $R^{(1)}(0,1)=\\{0\\}$,
$R^{(1)}(1,2)=\\{5\\}$ and $R^{(1)}(0,2)=R^{(1)}(1,1)=\\{1\\}$. Counting this
process, $R^{(t)}(i,j)=R^{(1)}(i,j)+t\bmod 10$, for each $(i,j)\in I(L)$ and
$1\leq t\leq 5$, therefore, ${\mathbb{Z}}_{10}=\bigcup_{t=1}^{5}R^{(t)}(0,0)$.

Now, the following result can be obtained obviously from Theorem 3.17.

###### Remark 3.19

If $m$ is prime, then $r=1$ or $r=m$ (in Theorem 3.17). In this case, if
$m\geq l$, then $n(L)<m$, so $r=m$. Therefore, the number of $2l-$cycles in
the QC LDPC code with CPM-size $m$ ($m$ is a prime not less than $l$), is $m$
times of the number of corresponding $2l-$cycle chains in the base matrix.

Hereinafter, to simplify the notations, by the cycle distribution of an LDPC
code with girth $2g$, we mean the polynomial
$\lambda(x)=\sum_{i=g}^{\infty}\lambda_{2i}x^{2i}$, in which $\lambda_{2i}$ is
the number of $2i$-cycles in the Tanner graph of the code.

###### Example 3.20

Let $H$ be the following parity-check matrix corresponding to a (3,4) QC-LDPC
code with girth 12 and CPM-size 100.

$H=\left(\begin{array}[]{cccc}{\cal I}&{\cal I}&{\cal I}&{\cal I}\\\ {\cal
I}&{\cal I}^{1}&{\cal I}^{7}&{\cal I}^{30}\\\ {\cal I}&{\cal I}^{3}&{\cal
I}^{19}&{\cal I}^{75}\\\ \end{array}\right)$

Using the algorithm given in next section, the cycle distribution of the code
is
$\lambda(x)=6000x^{12}+24400x^{14}+99825x^{16}+550500x^{18}+3052200x^{20}+12793400x^{22}+21587550x^{24}+\cdots$.
As it can be seen from Theorem 3.17, to find the cycle distribution, first we
must find all of the allowable (non-isomorph) cycle chains. For example, all
of the 12-cycle chains in $H$ are provided in Table 1. Although, for each
12-cycle chain $L$, we have $r(L)=m=100$, this is not true in general for
cycle chains with greater length. For example, we have 1000 allowable (non-
isomorph) 16-cycle chains which just there of them have $r<m$, i.e.
$L_{1}=(2,3,0,0,2,3,0,0,2,3,0,0,2,3,0,0)$,
$L_{2}=(2,3,0,2,1,1,0,2,2,3,0,2,1,1,0,2)$ and
$L_{3}=(2,3,1,2,0,0,1,1,2,3,1,2,0,0,1,1)$, with $r(L_{1})=25$, $r(L_{2})=50$
and $r(L_{3})=50$.

$\begin{array}[]{c|c|c}\begin{array}[]{c|c}{\rm num}&12-{\rm
cycle\,\,chain}\\\ \hline\cr\hline\cr 1&(2,1,0,0,1,1,2,0,0,1,1,0)\\\ \hline\cr
2&(2,1,1,0,0,1,1,0,0,1,1,0)\\\ \hline\cr 3&(1,2,0,0,1,1,0,2,1,0,0,1)\\\
\hline\cr 4&(1,2,0,1,2,0,0,1,2,0,0,1)\\\ \hline\cr
5&(2,2,0,0,1,2,2,0,0,2,1,0)\\\ \hline\cr 6&(2,2,0,0,2,1,0,2,2,0,0,1)\\\
\hline\cr 7&(2,2,0,1,1,2,2,1,0,2,1,1)\\\ \hline\cr
8&(2,2,1,0,0,1,2,0,0,2,1,1)\\\ \hline\cr 9&(2,2,1,0,0,2,1,1,2,0,0,1)\\\
\hline\cr 10&(2,2,1,0,2,1,1,2,2,0,1,1)\\\ \hline\cr
11&(2,2,1,1,0,2,1,1,0,2,1,0)\\\ \hline\cr 12&(2,2,1,1,2,0,0,2,1,0,0,1)\\\
\hline\cr 13&(1,3,0,0,1,1,0,3,1,0,0,1)\\\ \hline\cr
14&(1,3,0,0,1,2,0,3,1,0,0,2)\\\ \hline\cr 15&(1,3,0,1,1,2,0,3,1,1,0,2)\\\
\hline\cr 16&(1,3,0,1,1,2,2,0,0,2,2,1)\\\ \hline\cr
17&(1,3,0,2,1,0,0,2,2,1,0,2)\\\ \hline\cr 18&(1,3,0,2,2,0,0,1,1,2,2,1)\\\
\hline\cr 19&(1,3,0,2,2,1,0,2,1,0,0,2)\\\ \hline\cr
20&(1,3,0,2,2,1,1,2,2,0,0,1)\end{array}&\begin{array}[]{c|c}{\rm num}&12-{\rm
cycle\,\,chain}\\\ \hline\cr\hline\cr 21&(2,3,0,0,1,1,0,2,2,3,1,1)\\\
\hline\cr 22&(2,3,0,0,1,1,2,0,1,3,0,1)\\\ \hline\cr
23&(2,3,0,0,1,1,2,3,1,1,0,2)\\\ \hline\cr 24&(2,3,0,0,1,3,0,1,2,0,1,1)\\\
\hline\cr 25&(2,3,0,0,1,3,2,0,0,3,1,0)\\\ \hline\cr
26&(2,3,0,0,2,1,0,3,2,0,0,1)\\\ \hline\cr 27&(2,3,0,0,2,1,1,3,0,2,1,0)\\\
\hline\cr 28&(2,3,0,0,2,2,0,1,1,2,0,0)\\\ \hline\cr
29&(2,3,0,0,2,2,0,3,2,0,0,2)\\\ \hline\cr 30&(2,3,0,1,1,0,0,1,1,3,0,1)\\\
\hline\cr 31&(2,3,0,1,1,0,0,2,2,3,1,0)\\\ \hline\cr
32&(2,3,0,1,1,0,2,3,1,0,0,2)\\\ \hline\cr 33&(2,3,0,1,1,2,0,0,2,2,0,0)\\\
\hline\cr 34&(2,3,0,1,1,3,0,1,1,0,0,1)\\\ \hline\cr
35&(2,3,0,1,1,3,2,1,0,3,1,1)\\\ \hline\cr 36&(2,3,0,1,2,0,1,3,0,0,1,1)\\\
\hline\cr 37&(2,3,0,1,2,2,0,1,2,2,1,0)\\\ \hline\cr
38&(2,3,0,1,2,2,0,3,2,1,0,2)\\\ \hline\cr 39&(2,3,0,1,2,2,1,0,2,2,0,1)\\\
\hline\cr 40&(2,3,0,1,2,3,0,1,2,3,0,2)\end{array}&\begin{array}[]{c|c}{\rm
num}&12-{\rm cycle\,\,chain}\\\ \hline\cr\hline\cr
41&(2,3,0,2,1,0,2,1,1,3,0,0)\\\ \hline\cr 42&(2,3,0,2,1,3,0,0,2,1,1,0)\\\
\hline\cr 43&(2,3,0,2,1,3,2,2,0,3,1,2)\\\ \hline\cr
44&(2,3,0,2,2,0,1,2,2,3,0,2)\\\ \hline\cr 45&(2,3,0,2,2,3,1,0,0,1,1,0)\\\
\hline\cr 46&(2,3,0,2,2,3,1,1,0,0,1,1)\\\ \hline\cr
47&(2,3,1,0,0,1,2,0,0,3,1,2)\\\ \hline\cr 48&(2,3,1,0,0,3,1,2,2,0,0,1)\\\
\hline\cr 49&(2,3,1,0,2,1,0,3,1,1,0,2)\\\ \hline\cr
50&(2,3,1,0,2,1,1,3,2,0,1,1)\\\ \hline\cr 51&(2,3,1,0,2,2,1,0,2,3,1,1)\\\
\hline\cr 52&(2,3,1,0,2,2,1,1,2,3,1,0)\\\ \hline\cr
53&(2,3,1,0,2,2,1,3,2,0,1,2)\\\ \hline\cr 54&(2,3,1,0,2,3,1,1,2,2,1,0)\\\
\hline\cr 55&(2,3,1,1,0,2,2,1,0,3,1,0)\\\ \hline\cr
56&(2,3,1,1,0,3,1,0,2,1,0,2)\\\ \hline\cr 57&(2,3,1,1,2,2,1,3,2,1,1,2)\\\
\hline\cr 58&(2,3,1,2,0,3,1,2,2,1,1,2)\\\ \hline\cr
59&(2,3,1,2,2,0,0,3,1,0,0,1)\\\ \hline\cr
60&(2,3,1,2,2,1,1,2,0,3,1,2)\end{array}\end{array}$ Table 1: All of the (non-
isomorph) allowable 12-cycle chains in Example 3.20

In continue, using Theorem 3.17, an algorithm is proposed which efficiently
finds the cycles (with arbitrary lengths not less than the girth) in the
Tanner graph of a QC-LDPC code by investigating the cycle chains. To do this,
first we pursue the cycle chains in the parity-check matrix column by column,
from the top to the bottom, then Theorem 3.17 is used to find the number of
cycles corresponding to each cycle chain.

##  4 An Efficient Algorithm for Counting the Cycles

For given positive integers $b$, $v$ and $k$, let $B$ be a $v\times k$ binary
matrix with the corresponding $(v,k)-$design ${\cal B}=[B_{1},\ldots,B_{k}]$.
Moreover, let $m\geq 1$ be an integer and $S$ be a $(m,{\cal B})-$slope vector
such that the girth of the QC LDPC code with the parity-check matrix ${\cal
H}_{m,{\cal B},S}$ is $2g$. Here, we propose a deterministic algorithm to
enumerate all of the cycles in TG$({\cal H}_{m,{\cal B},S})$ up to $2l$ in
which $l$ is an arbitrary positive integer not less than $g$. It is noticed
that, unlike the known counting algorithms which count the cycles up to length
at most $2g-2$, the proposed algorithm is capable to count cycles of length
$2l$, for each $l\geq 2$. In the algorithm, to classify non-isomorphic cycle
chains and in order to speed up the process, for a given cycle chain
$L=(i_{0},j_{0},i_{1},j_{1},\cdots,i_{l-1},j_{l-1})$, we use the functions
$b^{\to}(L)$ and $b^{\leftarrow}(L)$ to be the $k$-adic representation of $L$
to the right and left, respectively, i.e.
$b^{\to}(L)=\sum_{t=0}^{l-1}(i_{t}+j_{t}k)k^{2t}=i_{0}+j_{0}k+i_{1}k^{2}+j_{2}k^{3}+\cdots+i_{l-1}k^{2l-2}+j_{l-1}k^{2l-1}$
and
$b^{\leftarrow}(L)=\sum_{t=0}^{l-1}(i_{l-t}+j_{l-t-1}k)k^{2t}=i_{0}+j_{l-1}k+i_{l-1}k^{2}+j_{l-2}k^{3}+\cdots+j_{0}k^{2l-1}$.
Now, it can be seen easily that two $2l$-chains $L_{1}$ and $L_{2}$ are
isomorphic if and only if $b^{\to}(L_{1})=k^{2t}b^{\to}(L_{2})\pmod{k^{2l}-1}$
or $b^{\to}(L_{1})=k^{2t}b^{\leftarrow}(L_{2})\pmod{k^{2l}-1}$, for some
$0\leq t\leq l-1$. In the algorithm, by ${\cal B}^{(e)}$, $1\leq
e\leq\sum_{i=1}^{k}(|B_{i}|-1)$, we mean the first $e$ elements of $\cal B$,
when the elements in the blocks (except the first element in each block) are
enumerated one by one from the left to the right. On the other hand, ${\cal
B}^{(e)}=[B_{1},\cdots,B_{p-1},B^{\prime}_{p}]$, where $p$ is the largest
positive integer satisfying in $\sum_{i=1}^{p-1}(|B_{i}|-1)<e$, and
$B^{\prime}_{p}$ is the first $e+1-\sum_{i=1}^{p-1}(|B_{i}|-1)$ elements of
$B_{p}$. For example, if ${\cal B}=[\\{1,2,3\\},\\{3,4,5,6\\}]$, then ${\cal
B}^{(1)}=[\\{1,2\\}]$, ${\cal B}^{(2)}=[\\{1,2,3\\}]$, ${\cal
B}^{(3)}=[\\{1,2,3\\},\\{3,4\\}]$, ${\cal B}^{(4)}=[\\{1,2,3\\},\\{3,4,5\\}]$
and ${\cal B}^{(5)}=[\\{1,2,3\\},\\{3,4,5,6\\}]={\cal B}$. Now, the outline of
the algorithm is as follows.

###### Algorithm 4.21

$n\leftarrow\sum_{i=1}^{k}(|B_{i}|-1)$ and ${\cal A}\leftarrow\emptyset$

for $e$ from 1 to $n$ do

Let ${\cal B}^{(e)}=[B_{1},\cdots,B_{p-1},B^{\prime}_{p}]$, where
$B^{\prime}_{p}=\\{b_{0},b_{1},\cdots,b_{u}\\}\subseteq B_{p}$, for
$u=e-\sum_{i=1}^{p-1}(|B_{i}|-1)$.

for $i$ from $0$ to $u$ do

for $j$ from $i+1$ to $u$ do

Let $L=(b_{i},p,b_{j},\cdots)$ be a $2l-$alowable cycle chain in ${\cal
B}^{(e)}$ starting from $(b_{i},p,b_{j})$.

if $L$ is not isomorphic with elements of $\cal A$ then

${\cal A}\leftarrow{\cal A}\cup\\{L\\}$.

end if

end for

end for

end for

return $\sum\limits_{L\in{\cal A}}r(L)$ as the number of $2l$ cycles.

In fact, Algorithm 4.21 counts the cycles of length $2l$ by $2l-$cycle chains
sequentially from the first $e$, $1\leq e\leq n$, elements of $\cal B$,
denoted by ${\cal B}^{(e)}$. For this, first, Lemma 3.4 is used to investigate
allowability of the constructed cycle chain. Then, each of the previousely
constructed allowable $2l-$cycle chains is compared with $L$ to be non-
isomorphic. This process is the only part of the algorithm which needs some
times for running, causing a complexity. For this problem, as mentioned above,
$b^{\to}(L)$ and $b^{\leftarrow}(L)$ can be useful to speed up this process of
the algorithm. Finally, Theorem 3.17 is used to find $2l-$cycles corresponding
to each $2l-$cycle chain. It is noticed that in $e$th step of the algorithm,
to find the allowable cycle chains and corresponding $2l$ cycles, we just
consider the parity-check matrix ${\cal H}^{(e)}$, which is a submatrix of
$\cal H$ constructed in step $e$ based on the design ${\cal B}^{(e)}$.

###### Example 4.22

In this example, we use Algorithm 4.21 to count the short cycles in the Tanner
graph of some standard QC-LDPC codes. The outputs were obtained by a C$\sharp$
programming applied on a computer with a 2.2-GHz CPU and 6 GB of RAM. Consider
two LDPC codes adopted in IEEE 802.11 standard [51] with rate-2/3. These codes
are two irregular (1296, 432) and (1944,648) QC-LDPC codes denoted by $A$ and
$B$, respectively. Applying Algorithm 4.21, Table 2 provides the multiplicity
of $2l-$cycles, $2\leq l\leq 6$, denoted by $N_{2l}$. Moreover, the running
time is compared with the time of a counting algorithm in [25]. While the
algorithm in [25] can only compute $N_{4}$, $N_{6}$ and $N_{8}$, the proposed
algorithm can enumerate ${2l}-$cycle multiplicities, for each $l\geq 2$.
Moreover, the running time of Algorithm 4.21 is remarkably less than the time
of Algorithm in [25]. In fact, for codes $A$ and $B$, the running times of
Algorithm 4.21 are 0.046 and 0.048 seconds, respectively, while the consumed
time in [25] are about 0.5 and 1 seconds, respectively.

|  | Number of Cycles
---|---|---
Code | Length | $N_{4}$ | $N_{6}$ | $N_{8}$ | $N_{10}$ | $N_{12}$
$A$ | 1296 | 108 | 7830 | 237627 | 6884028 | 198486018
$B$ | 1944 | 81 | 6399 | 251667 | 7071624 | 211628106
Table 2:  Cycle multiplicities of codes $A$ and $B$ in Example 4.22.

###  4.1 The Complexity of The Algorithm

There is a main problem to verify the complexity of Algorithm 4.21 as the main
conclusion of the paper. First, let $L=\sum_{i=1}^{k}(|B_{i}|-1)$ be the
number of steps which must be passed to reach the solution. In fact, $L$ is
the number of 1’s in the base matrix except the first ones in the columns when
traversing the base matrix from up to down. In step $e$, we must find all non-
isomorphic chains starting from $(b_{i},p,b_{j})$, inquires checking all
(allowable) chains $(i_{0},j_{0},i_{1},j_{1},\cdots,i_{l-1},j_{l-1})$ with
$(i_{l},j_{l})=(i_{0},j_{0})=(b_{i},p)$, $i_{1}=b_{j}$ and
$\\{i_{k},i_{k+1}\\}\subseteq B_{j_{k}}$, $1\leq k\leq l-1$. In this case, if
$b_{\max}=\max_{1\leq i\leq k}|B_{i}|$, then such chains can be examined in at
most $(b_{\max}-1)^{l-2}(p-1)^{l-1}$ which are compared with at most
$2l\sum_{p^{\prime}=1}^{p}(b_{\max}-1)^{l-2}(p^{\prime}-1)^{l-1}$ chains to
verify the non-isomorphic relation. Thus, the overall complexity to find all
non-isomorphic chains are at most
$2l\sum_{p=1}^{k}(b_{\max}-1)^{l-2}(p-1)^{l-1}\sum_{p^{\prime}=1}^{p}(b_{\max}-1)^{l-2}(p^{\prime}-1)^{l-1}=2l\sum_{p=1}^{k}\sum_{p^{\prime}=1}^{p}(b_{\max}-1)^{2l-4}(p-1)^{l-1}(p^{\prime}-1)^{l-1}\in
O(lb_{\max}^{2l}k^{2l})$ which is polynomial by $k$, i.e. the number of
blocks, if $l$ and $b_{\max}$ are given.

##  5 Conclusion

In this paper, an efficient algorithm for counting short cycles in the Tanner
graph of a QC-LDPC code is presented. Although, the known counting algorithms
can enumerate cycles up to $2g-2$, where $g$ is the girth of the code, the
proposed algorithm is capable of counting any (even) cycles of length at least
$g$ in the Tanner graph. Interestingly, for QC-LDPC codes lifted from a
protograph $G$, the complexity of the algorithm is based on the number of
edges in $G$, independent from the lifting degree of the constructed codes.
Finally, applying the proposed algorithm for some standard codes, the overall
complexity improves rather than the known algorithms, in terms of
computational complexity and memory requirements.

##  6 Acknowledgments

We would like to thank the anonymous referees for their helpful comments. This
work was supported in part by the research council of Shahrekord university.

## References

  * [1] Gallager, R. G.: ‘Low density parity-check codes’, IRE Trans. Inf. Theory, 1962, IT-8, (1), pp. 21–28[1]
  * [2] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 498–519, Feb. 2001.
  * [3] T. Richardson and R. Urbanke, “The capacity of low-density paritycheck codes under message passing decodiong,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 599-619, Feb. 2001.
  * [4] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf. Theory, vol. IT-27, no. 5, pp. 533–547, Sep. 1981.
  * [5] T. R. Halford and K. M. Chugg, “An algorithm for counting short cycles in bipartite graphs,” IEEE Trans. Inf. Theory, vol. 52, no. 1, pp. 287–292, Jan. 2006.
  * [6] T. Richardson, M. A. Shokrollahi, and R. Urbanke, “Design of capacityapproaching irregular low-density parity check codes,” IEEE Trans. Information Theory, vol. 47, no. 2, pp. 619–637, Feb. 2001.
  * [7] Y. Mao and A. H. Banihashemi, “A heuristic search for good low-density parity-check codes at short block lengths,” in Proc. IEEE ICC 2001, June 2001, Helsinki, Finland, pp. 41-44.
  * [8] X.-Y. Hu, E. Eleftheriou, and D. M. Arnold, “Regular and irregular progressive edge-growth Tanner graphs,” IEEE Trans. Inf. Theory, vol. 51, no. 1, pp. 386-398, Jan. 2005.
  * [9] M. Karimi Dehkordi and A. H. Banihashemi, “A message-passing algorithm for counting short cycles in a graph,” in Proc 2010 IEEE Inform. Theory Workshop.
  * [10] N. Alon, R. Yuster, and U. Zwick, “Finding and counting given length cycles,” Algorithmica, vol. 17, no. 3, pp. 209–223, 1997.
  * [11] Y. Mao and A. H. Banihashemi, “A heuristic search for good low-density parity-check codes at short block lengths,” in Proc. Int. Conf. Communications, vol. 1, Helsinki, Finland, Jun. 2001, pp. 41–44.
  * [12] Harary F., Manvel B. “On the Number of Cycles in a Graph”, Matematick’y casopis, 1971, vol. 21, no. 1, pp. 55–63.
  * [13] Chang Y.C., Fu H.L. “The Number of 6-Cycles in a Graph,” The Bulletin of the Institute of Combinatorics and Its Applications, 2003, vol. 39, pp. 27–30.
  * [14] Perepechko S.N., Voropaev A.N. The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths. International Conference, Mathematical Modeling and Computational Physics (MMCP2009). Dubna : JINR, 2009, pp. 148–149.
  * [15] R. Chen, H. Huang, and G. Xiao, “Relation between parity-check matrices and cycles of associated Tanner graphs,” IEEE Commun. Lett., vol. 11, no. 8, pp. 674–676, Aug. 2007.
  * [16] J. Fan and Y. Xiao, “A method of counting the number of cycles in LDPC codes,” in Proc. 2006 Int. Conf. Signal Proc., vol. 3, pp. 2183–2186.
  * [17] J. Flum and M. Grohe, “The parameterized complexity of counting problems,” in Proc. 2002 IEEE Symp. Foundations of Computer Science, pp. 538–547.
  * [18] M. Gholami and M. Alinia, High-Performance Binary and Nonbinary LDPC Codes Based on Affine Permutation Matrices, IET Commun., 2015, Vol. 6, pp. 1750–1756
  * [19] MacKay, D. J. C., Neal, R. M.: “Near Shannon limit performance of low density parity-check codes,” IEEE Electron. Lett., 1996, 32, pp. 1645–1646
  * [20] Richardson, T. J., Shokrollahi, M. A., Urbanke, R.L.: “Design of capacity-approaching low-density parity-check codes,” IEEE Trans. Inf. Theory, 2001, 47, (2), pp. 619–637
  * [21] J. Thorpe, “Low-density parity-check (LDPC) codes constructed from protograph,” IPN Progr. Rep. 42–154, JPL, Aug. 2003.
  * [22] Fossorier, M. P. C.: ‘Quasi-cyclic low-density parity-check codes from circulant permutation matrices’, IEEE Trans. Inf. Theory, 2004, 50, (8), pp. 1788–1793
  * [23] O’Sullivan, M., Brevik, J., Wolski, R.: ‘The Performance of LDPC codes with Large Girth’. Proc. 43rd Allerton Conference on Communication, Control and Computing, Univ. Illinois, 2005.
  * [24] Gholami, M., Raeis, G.: ‘Large Girth Column-Weight Two and Three LDPC Codes’, IEEE Commun. Lett., 2014, 18, (10), pp. 1671–1674
  * [25] Karimi, M. and Banihashemi, A.H., 2012. Counting short cycles of quasi cyclic protograph LDPC codes. IEEE Communications Letters, 16(3), pp.400-403.
  * [26] Karimi, M., Banihashemi, A. H.: ‘On the girth of quasi cyclic protograph LDPC codes’, IEEE Trans. Inf. Theory, 2013, 59, (7), pp. 4542–4552
  * [27] Bocharova, I. E., Hug, F., Johannesson, R., Kudryashov, B. D., Satyukov, R. V.: ‘Searching for voltage graph-based LDPC tailbiting codes with large girth’, IEEE Trans. Inf. Theory, 2012, 58, pp. 2265–2279
  * [28] Sobhani, R.: ‘Approach to the construction of regular low-density parity-check codes from group permutation matrices’, IET Commun., 2012, 6, pp. 1750–1756
  * [29] O’Sullivan, M. E.: ‘Algebraic construction of sparse matrices with large girth’, IEEE Trans. Inf. Theory, 2006, 52, (2), pp. 718–727
  * [30] Wang, J., Zhang, G., Zhou, Q., Yang, Y., Sun, R.: ‘Explicit Constructions for Type-1 QC-LDPC Codes with Girth at Least Ten’, IEEE Information Theory Workshop (ITW), Hobart,TAS, 2014, pp.436–440
  * [31] Esmaeili, M., Gholami, M.: ‘Structured QC-LDPC codes with girth 18 and column-weight J$\geq$3’, Int. J. Electron. Commun. (AEUE), 2010, 64, pp. 202–217
  * [32] Gholami, M., Samadieh, M., Raeisi, G.: ‘Column-Weight Three QC-LDPC Codes with Girth 20’, IEEE Commun. Lett., 2013, 17, pp. 1439–1442
  * [33] Wang, Y., Draper, S. C., Yedidia, J. S.: ‘Hierarchical and high-girth QC-LDPC codes’, IEEE Trans. Inf. Theory, 2013, 59, (7), pp. 4553–4583
  * [34] Pusane, A. E., Smarandache, R., Vontobel, P. O., Costello, D. J.: ‘Deriving good LDPC convolutional codes from LDPC block codes’, IEEE Trans. Inf. Theory, 2011, 57, (2), pp. 835–857
  * [35] Gholami, M., Samadieh, M.: ‘Design of binary and nonbinary codes from lifting of girth-8 cycle codes with minimum lengths’, IEEE Commun. Lett., 2013, 17, (4), pp. 777–780
  * [36] O’Sullivan, M. E., Greferath, M., Smarandache, R.: ‘Construction of LDPC codes from affine permutation matrices’, in 40th Allerton Conf. on Communication, Control, and Computing, (Allerton House, Monticello, Illinois, USA), 2002
  * [37] Kamiya, N.: ‘High-rate quasi-cyclic low-density parity-check codes derived from finite affine planes’, IEEE Inf. Theory, 2007, 53, (4), pp. 1444–1459
  * [38] Nguyen, D. V., Vasic, B., Marcellin, M., Chilappagari, S.K.: ‘Structured LDPC codes from permutation matrices free of small trapping sets’. Information Theory Workshop (ITW), 2010, pp. 1–5
  * [39] Hu, X. Y., Eleftheriou, E., Arnold, D. M.: ‘Regular and irregular progressive edge growth Tanner graphs’, IEEE Trans. Inf. Theory, 2005, 51, pp. 386–398
  * [40] Smarandache, R., Vontobel, P.: ‘Quasi Cyclic LDPC Codes: Influence of Proto- and Tanner-Graph Structure on Minimum Hamming Distance Upper Bounds’, IEEE Trans. Inf. Theory, 2012, 58, (2), pp. 585–607
  * [41] Gholami, M., Esmaeili, M., Samadieh, M.: ‘Quasi-cyclic low-density parity-check codes based on finite set systems’, IET Commun., 2014, 8, (10), pp. 1837–1849.
  * [42] Song, S., Zeng, L., Lin, S., Abdel-Ghaffar, K.: ‘Algebraic constructions of nonbinary quasi-cyclic LDPC codes’. IEEE ISIT 2006, Seattle, USA, pp. 83–87
  * [43] Davey, M.C., MacKay, D.: ‘Low-density parity check codes over GF$(q)$’, IEEE Commun. Lett., 1998, 2, (6), pp. 165–167
  * [44] Hu, X.-Y., Eleftheriou, E.: ‘Binary representation of cycle Tanner graph GF$(2^{b})$ codes’. Proc. IEEE ICC, 2004.
  * [45] Huang, J., Liu, L., Zhou, W., Zhou, S.: ‘Large-girth nonbinary QC-LDPC codes of various lengths’, IEEE Trans. Commun., 2010, 58, (11)
  * [46] Xu, J., Chen, L., Djurdjevic, I., Lin, S., Abdel-Ghaffar, K.: ‘Construction of regular and irregular LDPC codes: geometry decomposition and masking’, IEEE Trans. Inf. Theory, 2007, 53, (1), pp. 121–134
  * [47] Zhou, B., Zhang, L., Huang, Q., Lin, S., Xu, M.: ‘Constructions of high performance non-binary quasi-cyclic LDPC codes’. Inform. Theory Workshop, 5–9 May 2008, pp. 71–75.
  * [48] Myung, S., Yang, K., Park, D. S.: ‘A combining method of structured LDPC codes from affine permutation matrices’. ISIT 2006, Seatle, USA, pp. 674–678
  * [49] Baldi, M., Bambozzi, F., Chiaraluce, F.: ‘On a family of circulant matrices for quasi-cyclic low-density generator matrix codes’, IEEE Trans. Inf. Theory, 2011, 57, (9), pp. 6052–6067
  * [50] Li, J., Lin, S., and Abdel-Ghaffar, K. 2015, June. Improved message-passing algorithm for counting short cycles in bipartite graphs. In Information Theory (ISIT), 2015 IEEE International Symposium on (pp. 416-420). IEEE.
  * [51] IEEE-802.11n, Wireless LAN Medium Access Control and Physical Layer Specifications: Enhancements for Higher Throughput, P802.11n/D3.07, Mar. 2008
  * [52] Yang, K., Zhang, B., Zhan, Y., and Guo, D. (2017). Design and Analysis of Efficient Algorithm for Counting and Enumerating Cycles in LDPC Codes. In Information Technology and Intelligent Transportation Systems (pp. 131–137). Springer, Cham.
  * [53] Dehghan, A. and Banihashemi, A.H., 2017. On the Tanner graph cycle distribution of random LDPC, random protograph-based LDPC, and random quasi-cyclic LDPC code ensembles. arXiv preprint arXiv:1701.02379.
  * [54] Jiang, S., Lau, FC. (2018) An Approach to Evaluating the Number of Closed Paths in an All-One Base Matrix. IEEE Access, 6, pp. 22332–22340.


# Inducing chiral superconductivity on honeycomb lattice systems

Abdulrhman M. Alsharari<EMAIL_ADDRESS>Department of Physics,
University of Tabuk, Tabuk, 71491, SA  Sergio E. Ulloa  Department of Physics
and Astronomy, and Nanoscale and Quantum Phenomena Institute, Ohio University,
Athens, Ohio 45701, USA  Center for Quantum Devices, Niels Bohr Institute,
University of Copenhagen, DK-2100 Copenhagen, Denmark  Center for
Nanostructured Graphene, DTU Physics, Technical University of Denmark, DK-2800
Kongens Lyngby, Denmark

###### Abstract

Superconductivity in graphene-based systems has recently attracted much
attention, as either intrinsic behavior or induced by proximity to a
superconductor may lead to interesting topological phases and symmetries of
the pairing function. A prominent system considers the pairing to have chiral
symmetry. The question arises as to the effect of possible spin-orbit coupling
on the resulting superconducting quasiparticle spectrum. Utilizing a
Bogolyubov-de Gennes (BdG) Hamiltonian, we explore the interplay of different
interaction terms in the system, and their role in generating complex Berry
curvatures in the quasiparticle spectrum, as well as non-trivial topological
behavior. We demonstrate that the topology of the BdG Hamiltonian in these
systems may result in the appearance of edge states along the zigzag edges of
nanoribbons in the appropriate regime.

##  I Introduction

The intriguing properties of topological matter, especially superconductivity,
have greatly motivated the ongoing search for such behavior in different
material classes [1, 2]. Among these searches, interest in two-dimensional
(2D) materials has been intense [3]. Graphene-based 2D systems promise unusual
properties and applications in a variety of spintronic designs. Achieving this
behavior involves non-trivial properties, such as the quantum anomalous Hall
effect, topological phases with complex Berry curvature and associated Chern
numbers, helical states that may support Majorana fermion excitations, as well
as possible chiral currents along the edges of 2D ribbons [4, 5, 6, 7].

The quantum anomalous Hall (QAH) regime has received a great deal of attention
at the level of single-particle behavior. An intrinsic magnetization in the
system resembles to some extent the effect of a magnetic field on the
electronic dynamics with peculiar results [8, 9, 10]. In particular, the
magnetization breaks time reversal symmetry (TRS) and lifts the spin
degeneracy. A quantized charge Hall conductance characterizes this phase,
displaying an insulating state in the bulk and edge states at the boundary of
a nanoribbon system.

The addition of superconducting correlations on a QAH system has been
predicted to give rise to intriguing new properties and possible Majorana edge
states which may be used as robust platforms in quantum computation [11]. The
induced pairing correlations have naturally a direct impact on the appearance
and specifics of these properties [2]. The symmetries of the resulting pairing
channel are closely related to underlying lattice symmetries as well as to the
mechanism mediating the interaction. This is turn produces different
quasiparticle spectra with markedly different features.

In contrast, the proximitized honeycomb lattice of graphene may result in
broken lattice inversion symmetry and strong spin-orbit coupling that induces
an effective Ising (or Zeeman-like) spin field that preserves TRS. Such an
effect results in the spin projection perpendicular to the plane being a good
quantum number but with opposite value in each valley to preserve TRS [12, 13,
14, 15, 16]. Such a situation could be induced in graphene deposited on a
transition metal dichalcogenide substrate, for example [14, 15, 16].
Considering the effect of superconducting correlations on such Zeeman-like
system is expected to provide non-trivial Chern numbers and complex Berry
curvatures that should affect the resulting symmetries of the quasiparticle
excitations [10].

The classification of superconducting pairing symmetries residing on the
honeycomb lattice has been discussed previously [2, 4, 7, 17]. Although
deciding which symmetry dominates remains somewhat controversial, an
intriguing possibility of superconductivity induced onto proximitized graphene
is the appearance of chiral pairing symmetries and their associated broken
TRS. For instance, analysis of various symmetry channels in a Hubbard model on
a honeycomb lattice shows that a singlet ‘d+id’-wave is the dominant pairing
symmetry [18]. Highly doped monolayer graphene has been proposed to exhibit
these features, with unusual different properties [19, 20, 21, 22,
[Fordiscussionandreferencesonthistopicsee]Scherer2020].

The study of either a QAH or a Zeeman-like sytem in the presence of induced
chiral d-wave superconductivity has received little attention, and we focus on
this issue here. Our primary interest is to explore the relationship between
the chiral superconducting pairing functions and topological properties of the
corresponding Bogoliubov-de Gennes (BdG) Hamiltonian that couples electron and
hole subsystems through the superconducting pairing. We explore this effect
with a focus on inducing topologically nontrivial character in the
proximitized system. We study the quasiparticle (QP) band spectra of the
superconducting states, and demonstrate that the topology of the BdG
Hamiltonian is different from the constituent subsystems. To this end, we
study the topological properties using both the Berry curvature of the QP
dispersion and their relation to the appearance of edge states in finite
nanoribbon systems. For suitable chemical potential and superconducting
pairing strength, we find the appearance of robust midgap states at zigzag
edges, well protected by large excitation gaps and momentum transfer.

In Sec. II below we describe the low-energy electronic Hamiltonian for the QAH
and Zeeman-like regimes of the honeycomb lattice system, and describe the main
features and differences of the resulting single-particle band structure. We
then discuss the effect of spatial range on chiral superconducting pairing in
Sec. II.2, by considering coupling for nearest and next-nearest-neighbors in
the lattice, and what symmetry this entails. Section III explores the main
features of the QP spectra for the different regimes and superconducting
symmetries, including the appearance of topologically protected edge states on
zigzag-terminated nanoribbons. Section III.4 is devoted to a discussion of
realistic model parameters and the possibility of realizing the discussed
topological phases experimentally. Finally, we discuss the importance and the
prospects of these findings in the concluding section.

##  II Microscopic Model

###  II.1 Electronic states of proximitized honeycomb lattice

The Bogoliubov-de Gennes (BdG) Hamiltonian for superconducting pairing on the
graphene honeycomb lattice is described in momentum space as [24]

$\mathcal{H}_{BdG}(k)=\left(\begin{matrix}\mathcal{H}_{e}(k)-\eta&&\Gamma(k)\\\
\Gamma^{\dagger}(k)&&\eta-s_{y}\mathcal{H}^{*}_{e}(-k)s_{y}\\\
\end{matrix}\right),$ (1)

where $s_{y}$ is a Pauli matrix acting on spin space, $\eta$ is the chemical
potential of the system, and $\mathcal{H}_{e}$ is the effective electronic
Hamiltonian for proximitized graphene (without superconductivity), which in
the basis $\Phi=({A\uparrow,}{B\uparrow,}{A\downarrow,}{B\downarrow})^{T}$ can
be written as [15, 16]

$\mathcal{H}_{e}(k)=\left(\begin{matrix}A+Z(k)&&T(k)&&0&&R(k)\\\
T^{*}(k)&&A+Z(k)&&R(-k)&&0\\\ 0&&R^{*}(-k)&&-A-Z(k)&&T(k)\\\
R^{*}(k)&&0&&T^{*}(k)&&-A-Z(k)\\\ \end{matrix}\right).$ (2)

Here, $k$ is the 2D momentum vector, and

$\begin{split}T(k)&=t\,(1+e^{ik\cdot a_{1}}+e^{ik\cdot a_{2}}),\\\
R(k)&=\frac{R}{3i}(1+e^{-i\frac{2\pi}{3}}e^{ik\cdot
a_{1}}+e^{i\frac{2\pi}{3}}e^{ik\cdot a_{2}}),\\\
Z(k)&=\frac{-2\lambda}{3\sqrt{3}}\left(\sin(k\cdot a_{1})-\sin(k\cdot
a_{2})+\sin(k\cdot a_{3})\right),\\\ \end{split}$ (3)

where $a_{1}$, $a_{2}$, and $a_{3}$ are the real-space vectors of graphene
(defined explicitly in the next section). The $A$ constant in Eq. (2)
represents the effect of a uniform magnetic or exchange field that induces the
system to be in a QAH regime. This term is in clear competition with the
effective Zeeman field $Z(k)$ induced by the spin-orbit coupling constant
$\lambda$ that embodies the underlying lattice structure and preserves TRS.
The $R$ constant represents a possible Rashba spin-orbit coupling, allowed as
well by the broken inversion symmetry. For convenience, we set the nearest
neighbor hopping as the unit of energy, $t=1$, throughout the paper.

We now illustrate the differences between the QAH and Ising spin-orbit
honeycomb systems before the onset of superconductivity. The electronic
Hamiltonian in the QAH regime, which we will denote as an A-System, uses
$A=0.05$ and $\lambda=0$. Similarly, we will look at a Z-System, where
$\lambda=0.05$ and $A=0$. In both cases we assume the presence of a Rashba
field with $R=0.05$, which has as main effect to mix different spins,
splitting their degeneracy (increasing the Rashba coupling does not produce a
transition to a topological phase [25]). The parameters chosen capture the
essential characteristics of each regime; systems with other coupling constant
values exhibit the same qualitative behavior presented here. We note that
other terms in the Hamiltonian may exist in a proximitized graphene system,
such as that produced by a difference between A and B sublattices (the
‘staggered’ field) or an intrinsic spin-orbit coupling term. However, we have
verified that as long as such parameters remain small, as it is typical in
these structures, their inclusion in the model has only a small quantitative
effect, with no change in the qualitative behavior.

Figure 1: (Color online) Panels (a) and (b) show band structure of the
electronic part of the BdG Hamiltonian for two different regimes. (a) A
Z-System is the structure that results in the presence of Ising spin-orbit
coupling, here $\lambda=0.05t$. (b) An A-System results when a uniform
magnetic (or intrinsic exchange) field leads to appearance of QAH effect; here
$A=0.05t$. Panels (c) NNN, and (d) NN, show phase factors in real space
introduced by the chiral superconducting pairing function in each case.
Corresponding $|\Gamma(k)|$ function shown in reciprocal space for (e) NNN,
and (f) NN. Note drastically different symmetries in both cases.

Panels (a) and (b) of Fig. 1 show the electronic band structure of both the Z-
and A-Systems, with their corresponding spin $S_{z}$-projection, along the
K-M-K’ path in the Brillouin zone. Notice that K and K’ states have the same
spin ordering in the A-System whereas the spin is reversed in the Z-System.
This is understood since QAH breaks TRS, whereas this symmetry is preserved by
the Ising spin-orbit coupling in the Z-System. As we will see below, the
presence of chiral superconducting order parameters makes the BdG Hamiltonian
of the Z-System odd under time-reversal. A chiral gap function breaks TRS and
hence allows splitting of bands that were once degenerate.

###  II.2 Superconducting pairing function

We want to consider a chiral pairing amplitude $\Gamma(k)$ that breaks time-
reversal symmetry in Eq. 1. Moreover, we want to explore the differences on
superconducting QP spectra arising from either nearest neighbor (NN) and next
nearest neighbor (NNN) coupling, as the spatial content results in different
momentum-space pairing symmetries. The pairing intensities are accompanied
with different variables/factors for different directions, as shown in Fig.
1(c) and (d). As a result, the non-zero elements of $\Gamma(k)$ in Eq. (1) for
d${}_{x^{2}-y^{2}}+i$dxy superconducting order can be expressed as

$\begin{split}\Gamma^{NN}_{A\uparrow,B\downarrow}(k)&=\gamma\left(e^{-ik\cdot\delta_{1}}+e^{i\frac{2\pi}{3}}e^{ik\cdot\delta_{2}}+e^{i\frac{4\pi}{3}}e^{ik\cdot\delta_{3}}\right),\\\
\Gamma^{NNN}_{A\uparrow,A\downarrow}(k)&=2\gamma\left(\cos\left(k_{x}\right)-\cos\left(\frac{k_{x}}{2}\right)\cos\left(\frac{\sqrt{3}k_{y}}{2}\right)\right.\\\
&\,\,\,\,\,-i\left.\sqrt{3}\sin\left(\frac{k_{x}}{2}\right)\sin\left(\frac{\sqrt{3}k_{y}}{2}\right)\right),\end{split}$
(4)

where $k=(k_{x},k_{y})$, and the graphene lattice constant $a$ is set to 1. We
have defined the honeycomb vectors connecting nearest neighbors (sublattice A
to sublattice B) as

$\begin{split}\delta_{1}&=a(0,\frac{1}{\sqrt{3}})\\\
\delta_{2,3}&=\frac{a}{2}(\pm 1,\frac{1}{\sqrt{3}}).\end{split}$ (5)

The corresponding lattice vectors connecting sublattice A (or B) to its NNN
are given by $a_{1}=\delta_{2}-\delta_{3}$, $a_{2}=\delta_{1}-\delta_{3}$, and
$a_{3}=a_{1}-a_{2}$.

Notice that the symmetries of the singlet pairing function dictate that

$\begin{split}\Gamma^{NN}_{A\uparrow,B\downarrow}(k)&=\Gamma^{NN}_{B\uparrow,A\downarrow}(-k),\\\
\Gamma^{NNN}_{A\uparrow,A\downarrow}(k)&=\Gamma^{NNN}_{A\downarrow,A\uparrow}(-k),\\\
\Gamma^{NNN}_{A\uparrow,A\downarrow}(k)&=\Gamma^{NNN}_{B\uparrow,B\downarrow}(k).\\\
\end{split}$ (6)

Figure 1(e) and (f) show the $k$-dependent map of the superconducting pairing
amplitude for NNN and NN couplings, respectively. Notice that the d-wave
chiral amplitude has nodal points or lines when the pairing amplitude
transitions between negative and positive values in momentum space. In both
cases, the $\Gamma(k)$ function has at least C3 symmetry with respect to the
$\Gamma$ point [26]. However, the symmetry at the K and K’ valleys is very
different in both pairings. This would have significant impact on the QP
spectra and associated Berry curvature, as will be seen below.

We study the role of the chemical potential in the QP spectrum as the
superconducting pairing strength changes. We focus on energies close to the
Dirac points and keep both $\eta$ (chemical potential) and $\gamma$
(superconducting pairing strength) relatively small, $\eta$, $\gamma<t/4$.
This focuses on doping in the vicinity of the K valleys. Notice that heavy
doping requires a more complicated structure, with consideration of different
regions in momentum space. For large doping, the topological properties are
dependent on the $\Gamma$ and/or M points near van Hove singularities, as well
as possible band renormalization effects [7, 6, 23].

##  III Results and discussion

###  III.1 Quasiparticle spectra in different regimes

As illustrated in Fig. 1(a) and (b), both the A\- and Z-systems exhibit an
insulating gap around the charge neutrality point that is proportional to the
relevant structure parameter ($A$, $\lambda$ and $R$). To understand the
effect of the chemical potential and superconducting pairing function on the
different phases of the BdG Hamiltonian, Eq. (1), we show a map of the
excitation gap (minimal electron-hole excitation, regardless of its momentum
position) near the chemical potential (zero excitation energy) level. Notice
that the gap can close at one of the symmetry points (K or K’) of the
Brillouin zone or away from them, and either way appear gapless in the map.

Figure 2: (Color online) Gap phase diagram and QP band structure of systems
with NN and NNN chiral coupling. Heat maps show the minimal excitation gap for
different systems as function of chemical potential $\eta$ and superconducting
coupling $\gamma$; gap scale shown at lower right. Black regions indicate
gapless states that may signal a transition between different topological
phases, as discussed in text. The total BdG Chern number is shown in gray for
each distinctive phase separated by gapless regions. For each system, panels
on right display QP spectra and corresponding density of states for selected
parameter values (color dots), as indicated by colored frames. Red to blue
shading of dispersion curves indicate $S_{z}$ projection as function of
momentum; spin values shown in upper right scale.

Figure 2 shows the gap behavior in different regimes as function both of
chemical potential $\eta$ and superconducting strength $\gamma$. Although the
latter is set by the structure and pairing mechanism involved in a given
material system, $\eta$ could be modified somewhat by direct doping or even
applied gate voltages. As the gap diagram is symmetric around zero with
respect to both $\eta$ and $\gamma$, we plot only the positive quadrant for
each case. For $\gamma=0$, the gapless states reflect the single-particle
spectral gap seen in Fig. 1(a) and (b). As either $\eta$ or $\gamma$ increase,
however, the gap behavior changes substantially for the different regimes. The
systems studied show distinct, separate regions with contrasting QP behavior.

In the NNN A-System, an excitation gap persists even for large $\gamma$, as
long as the chemical potential is close to zero, Fig. 2(a). Increasing $\eta$
leads to gapless phases, as the pairing function nodal structure dominates.
Larger $\eta$ and $\gamma$, however, allows other states to participate in the
pairing correlations, which results in extended phases with gap size that is
proportional to $\eta$ and $\gamma$, both exceeding the value of $A$ ($=0.05$
here).

To further distinguish/identify the characteristic features of these phases,
we plot the QP band structure at selected parameters in these regions in Fig.
2. We focus on one valley for clarity and show band structure and density of
states (DOS) of selected points. Each panel to the right of panel Fig. 2(a)
corresponds to different $(\eta,\gamma)$ values as indicated by the blue/red
dots and associated frames. The rightmost panel in each case shows the total
density of states (DOS) for each spectrum. The dispersion is shown along the
$\Gamma$-K-M path and curves are colored according to their $S_{z}$ spin
projection. The excitation spectra in all systems here is symmetric around
zero, as dictated by particle-hole symmetry. As the A-System is constructed to
break TRS, this is carried over after the onset of superconducting
correlations, and we find that the spin of electrons and holes are the same at
each K valley, although reversed in opposite valleys about the M point (not
shown).

Figure 2(b) shows the gap map for the NNN Z-System; an excitation gap in the
superconducting phase appears immediately as either chemical potential or
$\gamma$ increases, with a non-monotonic dependence on $\eta$. However, beyond
$\eta\gtrsim 0.05=\lambda$, the superconducting phase has a gap that increases
with either $\eta$ or $\gamma$. The non-monotonic gap dependence, especially
the appearance of a gap closing at $\eta\simeq\lambda$, suggests that the
system goes through a phase transition. We will analyze this statement further
below, as it relates to changes in Berry curvature and Chern numbers. As
before, the right frames in Fig. 2(b) show typical QP dispersion and DOS for
two cases, indicated by the red/blue dots. Notice how the gap at
$(\eta,\gamma)=(0.06,0.2)$, blue dot, appears right at the K point, while for
(0.15, 0.15), red dot, the gap has shifted away, suggesting band inversion in
the QP states. Notice that since the Z-System preserves TRS even as the
pairing sets in, the spin states of the bands around the zero energy are
reversed in the K and K’ valleys.

In the case of NN coupling shown in Fig. 2(c) and (d) the scenario is
different. For NN-coupling in the A-System, Fig. 2(c) shows that the normal
single-particle gap closes for small values of $\eta$ and $\gamma$, while a
gapless regime persists for $\eta\lesssim A$ and all values of pairing
strength $\gamma$. For larger $\eta$, a superconducting gap emerges and grows
with both $\eta$ and $\gamma$ values, similar to the Z-System. This indicates
that in these regimes the bands near the Fermi level couple strongly through
the pairing potential, opening a sizable superconducting gap. The opening
large gap as the chemical potential increases can be seen as arising from the
overlap of single-particle states with different symmetry. These bands couple
through the pairing function and open a broad QP excitation gap.

The Z-System in 2(d) exhibits a sizable gap that persists for all non-zero
superconducting coupling and small chemical potential, $\eta<\lambda=0.05$;
the gap is associated with the single-particle gap in Fig. 1(b). In other
words, this system exhibits no phase transition for small $\eta$ as the
pairing strength increases. Notice that even though there are gapless lines,
they do not fully enclose/surround a region. One could then continuously
change these parameters without having to close the excitation gap. As $\eta$
increases beyond $\lambda$, the system closes the single-particle gap and
reopens in a superconducting phase with a gap that increases monotonically as
both $\eta$ and $\gamma$ increase.

The QP band structure behaves differently as well. The bands around zero
excitation energy are nearly fully spin-polarized around the K (or K’) valley,
whereas bands at higher energies mix. This is a direct consequence of the NN
pairing that couples A and B sublattices. The total density of states acquires
sharp peaks around the Fermi level, as well as for energies $\simeq\gamma$,
indicating the emergence of low-dispersive bands, as shown on the right panel
of 2(d).

Comparison of the QP dispersions in both regimes further illustrates
differences, such as the spin content of the states. While the A-System shows
strongly mixed states, the QP bands in the Z-System are fully polarized,
except around zero energy, where the states mix due to the Ising and Rashba
spin-orbit coupling terms. As we will see below, the superconducting gap that
appears on opposite sides of gap closing regimes have different
characteristics.

Since the pairing function $\Gamma(k)$ has nodal points in the first BZ, Fig.
1, shifting $\eta$ to regions in the spectrum with overlapping particle and
hole bands leads to gapless phases in Fig. 2. It is also understandable from
the symmetry of particle and hole bands that large regions are gapless, even
for non-zero coupling parameter $\gamma$. Lastly, notice that the chiral NNN
d-wave coupling appears to have small effect on the bands of the A-System at
small $\eta$ regimes, i.e., the QP band structure does not change much as a
function of $\gamma$.

Notice the expected enhancement of the DOS near the superconducting QP gap,
generally larger in the Z-System than in the A-System. [The latter is not
evident in Fig. 2, as the DOS are enlarged for clarity in the A-Systems to
emphasize qualitative behavior.] The larger DOS is accompanied by low band
velocity (flatter QP dispersion).

###  III.2 Topological properties

Figure 3: (Color online) Berry curvature of QP dispersion at K’ valley for BdG
Hamiltonian at selected parameters corresponding to those in Fig. 2, as
indicated in each legend. The top (middle) panels describe the NNN singlet
superconducting A-System (Z-System) Berry curvature, whereas the bottom panels
describe NN coupling of A- and Z-Systems. Insets show heat maps of the total
Berry curvature for holes. Notice circular symmetry of the NNN pairing in both
systems, whereas a 3-fold symmetry is evident for NN coupling.

We analyze further the topological properties of these systems using the Berry
curvature of the QP dispersions. Differences in Berry curvature would help us
distinguish their physical features, as it has implications on the linear
response and overall spintronic and valleytronic behavior [27]. One can
analyze the Berry curvature of the hole bands per valley,
$\Omega_{n}(\bm{k})$, using [27]

$\displaystyle\Omega_{n}(\bm{k})$ $\displaystyle=$
$\displaystyle-\sum_{n^{\prime}\neq n}\frac{2\,{\rm
Im}\langle\Psi_{n^{\prime}\bm{k}}|v_{x}|\Psi_{n\bm{k}}\rangle\langle\Psi_{n\bm{k}}|v_{y}|\Psi_{n^{\prime}\bm{k}}\rangle}{(\epsilon_{n}-\epsilon_{n^{\prime}})^{2}},$

where ${v}_{x}({v}_{y})$ is the velocity operator along the $x(y)$ direction,
and $n,n^{\prime}$ are band numbers [15, 27, 28]. The resulting Berry
curvature for each of the hole QP bands for the systems in Fig. 2, as well as
the total hole curvature near the valley at $K^{\prime}=(-4\pi/3a,0)$ are
displayed in Fig. 3. The total Berry curvature $\Omega_{tot}$ shows clear
changes in structure, associated with each gap closing event and change in the
topological character of the bands seen in Fig. 2. As the BdG Hamiltonian of
these systems has particle-hole symmetry by construction, the curvature plots
for the other valley are simply related as
$\Omega_{tot}$(K-valley$)=\Omega_{tot}$(K’-valley).

The total hole Berry curvature in the NNN phases is circularly symmetric,
reflecting the symmetry of the corresponding superconducting pairing functions
near the K valleys. In contrast, the three-fold symmetry of the NN pairing
function is reflected in the total Berry curvature for those structures, both
in the A- or Z-System, as seen in Fig. 3(e) and (f).

As stated earlier, at this level of doping the physics of the honeycomb
lattice system is controlled by the two nonequivalent valleys, with identical
Berry curvature content. One can calculate the Chern number per valley and
double it, or equivalently define the total Chern number by integrating over
the entire Brillouin zone,

$\displaystyle C_{BdG}$ $\displaystyle=$
$\displaystyle\dfrac{\pi}{2}\int_{BZ}d^{2}\bm{k}\,\Omega(\bm{k})\,.$ (8)

We notice that in systems of low-doping graphene, the BdG Chern number changes
by even numbers across topological phase transitions. This typically indicates
the appearance (or suppression) of pairs of propagating edge states whenever a
gap closing transition occurs. 111The topological characteristics of models
that break TRS while preserving particle-hole symmetry, such as the ones we
have here, belong to class D [28]. In the systems we study, despite the gap-
closing transitions in the NNN A-System, we find that $C_{BdG}=4$ remains
unchanged for all gapped phases. This is the result of the single-particle QAH
regime having a Chern number of 2, which doubles with the inclusion of the
hole sector. After the gap closing topological transition in Fig. 2 one still
gets $C_{BdG}=4$ but with a different nature, as we explain below in the
corresponding edge state analysis.

The NNN Z-System shows $C_{BdG}=0$ for small $\gamma$ values, which then
changes to $C_{BdG}=2$ at higher $\eta$ over a small window, and finally goes
to $C_{BdG}=4$ after gap opening at higher $\eta$. Similarly, both the NN A-
and Z-Systems show a BdG Chern number of 4 after the gap closing transition.

One finds in the Z-System that the gapped region at low $\eta$ yields zero
Chern number–in contrast to the A-System–as expected from the single-particle
picture that respects TRS; the chiral superconducting parameter seems to
produce an effective weak electron-hole coupling.

###  III.3 Edge states

The Chern number in single-particle systems represents the number of chiral
fermionic edge states [30]. Similarly, the BdG Chern number indicates the
number of chiral edge states in a finite size superconducting system [10]. To
better identify the topology of these systems, we have studied the
corresponding edge states in a finite ribbon with edges along the zigzag
direction.

It is known that a QAH system with onsite superconducting singlet pairing
yields a topological phase with edge states in a finite size system that cross
the excitation gap [6]. An interesting open question is whether the
topological phase can be destroyed by the introduction of chiral pairing
interactions. As we will see, these systems exhibit edge states in different
regimes.

Figure 4: (Color online) Edge states of BdG Hamiltonian at selected
superconducting coupling and chemical potential values for the A- and
Z-Systems. Top panels (a) and (b) are for NNN A-Systems; (c) and (d) NNN
Z-Systems. Bottom panels show edge states of (e) A-System and (f) Z-System for
NN coupling. The corresponding $\eta$ and $\gamma$ values are shown in each
panel, with corresponding band structures for phases in Fig. 2. Color of each
curve indicates spatial distribution of states across the nanoribbon; red and
blue indicate states located at opposite edges, whereas gray indicates the
‘bulk’ middle of the nanoribbon. The BdG Chern number for holes of each phase
is also shown, indicating the number of propagating states on each side of the
ribbon.

In the NNN pairing for the A-System, the region of the phase diagram in Fig.
2(a) near $\eta\simeq 0$ has small gaps and show no well-developed midgap edge
states. This is shown in Fig. 4(a), where the QP dispersions for a zigzag
nanoribbon with $(\eta,\gamma)=(0,0.2)$ shows a small gap and edge states (as
indicated by color, blue = rightmost, red = leftmost) that promptly hybridize
with the bulk states. Well-defined edge states appear after the first gap-
closing transition in the system, illustrated in Fig. 4(b) for
$(\eta,\gamma)=(0.2,0.2)$. The edge states connect particle and hole bands as
two right- and left-mover modes localized around each of the K and K’ points.
The existence of edge modes in the NNN A-System does not depend on the
specific coupling parameter set (i.e., $\gamma$, $\eta$, $R$, and $A$), once
the system is in the upper right sector of Fig. 2(a), which highlights their
topological origin. The modes are robust and propagate in opposite direction
on alternate edges of the nanoribbon, overlapping spatially without coupling.
We emphasize that this results in four (two per valley) co-propagating modes
on each side of the ribbon.

The states change drastically for the NNN Z-System. Although edge-less for
most of the phases shown here, this regime shows a complex structure of edge
states for large $\gamma$ values, as seen in Fig. 4(c) and (d). The small gap
in (c) is due mostly to the presence of Rashba coupling. It is then expected
that this structure would not be as robust against perturbation, and that its
edge states (either 2 or 4) would be easily perturbed/gapped in the presence
of impurities or other perturbations.

A more complicated edge state configuration is found in cases of NN pairing.
In both A- and Z-Systems, edge states are present, dispersing across the gap
and connecting the two non-equivalent valleys, before eventually merging with
the bulk bands. The edge states are well protected by the bulk excitation gap,
which makes them robust against perturbations. The phase appears to be
topological for large enough values of $\eta$ and $\gamma$ that drive the
system through the gap-closing phase transition.

There are four edge states crossing the gap, with wave-functions localized at
the left (right) boundaries of the nanoribbon, as shown by the red (blue)
colors in Fig. 4(e) and (f), i.e., there are four modes propagating on the
same edge and the same direction. These states are protected by the large
momentum and space separation, as well as sizable gap.

###  III.4 Experimentally feasible systems

Experimental realization of chiral topological superconductors is actively
pursued. New opportunities to study and observe topological superconductivity
have been identified in different material systems, especially in 2D crystals.
Localized Majorana states exist at the boundaries of topological
superconductors, and can be created by placing chains or islands of magnetic
atoms on an s-wave superconductor [31, 32]. Realization of superconductivity
by proximity using hybrid systems, combining magnetism and strong spin orbit
coupling, creates novel quasi-particle excitations that open new possibilities
for the realization of topological superconductor phases in experiments [33,
34, 35, 36]. The ability to control and tune different phases can be
experimentally achieved, allowing their characterization through measurements
such as magneto-resistance and related transport probes.

Superconducting states at low electron doping are observed below 1 K in WTe2
monolayers [37]. Similarly, superconductivity in high-quality 2M-WS2 single
crystals has been reported by several groups experimentally [38, 39]. This
unsual material is predicted to exhibit topological nodeless
superconductivity, with probable Majorana states bound to vortex cores.
Similarly promising chiral-triplet superconductivity is predicted in heavy-
fermion dichalcogenide UTe2 [40]. Possible topological superconductivity is
predicted theoretically in other 2D transition metal dichalcogenides, as well
as other correlated 2D materials [41].

Hybrid systems such as WSe2/bilayer-graphene/ WSe2 [42] have been shown to
exhibit helical edge states arising from the strong spin-orbit orbit under
proper gate and displacement field conditions. As bilayer graphene can be made
superconducting, this arrangement may result in unusual phases with very
interesting properties, similar to those we discuss here. Our estimates
suggest reaching doping levels $\eta\gtrsim 0.1t\simeq 0.3$ eV, which might be
possible with electrolyte-gating techniques.

These works and others continue to open novel possibilities for topological
superconductivity in van der Waals materials with spin-orbit coupling,
representing promising platforms to realize and probe non-trivial phases as
the ones we have discussed.

##  IV Conclusions

Starting from graphene-like honeycomb lattice models, we study systems with
singlet chiral superconductivity to explore the interplay between different
topological phases and superconducting range. The NNN correlations result in
pairing channels that are rotationally symmetric in momentum space near each
valley, whereas for NN correlations the symmetry is three-fold. The chiral
superconducting pairing function studied here is the result of the complex
orbital combination of dxy and d${}_{x^{2}-y^{2}}$. This combination breaks
time reversal symmetry and is shown to be the preferred channel in some
graphene models, including those with strong doping (or intercalation).

Tuning the chemical potential produces possible phase transitions that are
accompanied by gapless regimes. The topological aspects of these phases are
identified and studied by looking into the formation of edge states in finite
size systems, as well as their connection to the Berry curvature of the quasi-
particle spectrum and associated Chern numbers in the 2D bulk. Across
topological transition points, the system changes between trivial and non-
trivial phases, with different features of edge states in different parameter
ranges. We trust the present work would lead to further interest and work in
these systems. The general nature of the model suggests that it can be
applicable, with suitable variations, to a wide class of honeycomb lattice
systems that involve different proximity effects.

## Acknowledgments

SEU appreciates the hospitality at CNG/DTU and NBI/KU, as well as the support
of Nordea Fonden and the Otto Moensted Visiting Professorship Program.

## References

  * Sato and Ando [2017] M. Sato and Y. Ando, Rep. Prog. Phys. 80, 076501 (2017).
  * Varona  _et al._ [2018] S. Varona, L. Ortiz, O. Viyuela, and M. A. Martin-Delgado, J. Phys.: Conden. Matt. 30, 395602 (2018).
  * Kane and Mele [2005a] C. L. Kane and E. J. Mele, Phys. Rev. Lett. 95, 226801 (2005a).
  * Faye  _et al._ [2015] J. P. L. Faye, P. Sahebsara, and D. Sénéchal, Phys. Rev. B 92, 085121 (2015).
  * Volovik and Yakovenko [1989] G. E. Volovik and V. M. Yakovenko, J. Phys.: Conden. Matt. 1, 5263 (1989).
  * Wang and Wu [2016] L. Wang and M. W. Wu, Phys. Rev. B 93, 054502 (2016).
  * Dutreix  _et al._ [2014] C. Dutreix, M. Guigou, D. Chevallier, and C. Bena, Eur. Phys. J. B 87, 296 (2014).
  * Qiao  _et al._ [2012] Z. Qiao, H. Jiang, X. Li, Y. Yao, and Q. Niu, Phys. Rev. B 85, 115439 (2012).
  * Tse  _et al._ [2011] W.-K. Tse, Z. Qiao, Y. Yao, A. H. MacDonald, and Q. Niu, Phys. Rev. B 83, 155447 (2011).
  * Högl  _et al._ [2020a] P. Högl, T. Frank, D. Kochan, M. Gmitra, and J. Fabian, Phys. Rev. B 101, 245441 (2020a).
  * Fu and Kane [2008] L. Fu and C. L. Kane, Phys. Rev. Lett. 100, 096407 (2008).
  * Zhou  _et al._ [2019] B. T. Zhou, K. Taguchi, Y. Kawaguchi, Y. Tanaka, and K. T. Law, Communications Physics 2, 1 (2019).
  * Liu  _et al._ [2013a] G.-B. Liu, W.-Y. Shan, Y. Yao, W. Yao, and D. Xiao, Phys. Rev. B 88, 085433 (2013a).
  * Högl  _et al._ [2020b] P. Högl, T. Frank, K. Zollner, D. Kochan, M. Gmitra, and J. Fabian, Phys. Rev. Lett. 124, 136403 (2020b).
  * Alsharari  _et al._ [2016] A. M. Alsharari, M. M. Asmar, and S. E. Ulloa, Phys. Rev. B 94, 241106 (2016).
  * Alsharari  _et al._ [2018] A. M. Alsharari, M. M. Asmar, and S. E. Ulloa, Phys. Rev. B 98, 195129 (2018).
  * Black-Schaffer  _et al._ [2014] A. M. Black-Schaffer, W. Wu, and K. Le Hur, Phys. Rev. B 90, 054521 (2014).
  * Ying and Wessel [2018] T. Ying and S. Wessel, Phys. Rev. B 97, 075127 (2018).
  * Chern [2016] T. Chern, AIP Advances 6, 085211 (2016).
  * Nandkishore  _et al._ [2012] R. Nandkishore, L. Levitov, and A. Chubukov, Nat. Phys. 8, 158 (2012).
  * Gong  _et al._ [2017] X. Gong, M. Kargarian, A. Stern, D. Yue, H. Zhou, X. Jin, V. M. Galitski, V. M. Yakovenko, and J. Xia, Sci. Adv. 3, e1602579 (2017).
  * Liu  _et al._ [2013b] F. Liu, C.-C. Liu, K. Wu, F. Yang, and Y. Yao, Phys. Rev. Lett. 111, 066804 (2013b).
  * Scherer [2020] M. M. Scherer, Physics 13, 161 (2020).
  * Alsharari and Ulloa [2020] A. M. Alsharari and S. E. Ulloa, Phys. Rev. B 102, 104509 (2020).
  * Kane and Mele [2005b] C. L. Kane and E. J. Mele, Phys. Rev. Lett. 95, 146802 (2005b).
  * Qi  _et al._ [2020] Y. Qi, L. Fu, K. Sun, and Z. Gu, Phys. Rev. B 102, 245140 (2020).
  * Xiao  _et al._ [2010] D. Xiao, M.-C. Chang, and Q. Niu, Rev. Mod. Phys. 82, 1959 (2010).
  * Qi and Zhang [2011] X.-L. Qi and S.-C. Zhang, Rev. Mod. Phys. 83, 1057 (2011).
  * Note [1] The topological characteristics of models that break TRS while preserving particle-hole symmetry, such as the ones we have here, belong to class D [28].
  * Xiao  _et al._ [2007] D. Xiao, W. Yao, and Q. Niu, Phys. Rev. Lett. 99, 236809 (2007).
  * Kreisel  _et al._ [2021] A. Kreisel, T. Hyart, and B. Rosenow, (2021), arXiv:2102.12502 [cond-mat.supr-con] .
  * Ptok  _et al._ [2020] A. Ptok, D. J. Alspaugh, S. Głodzik, A. Kobiałka, A. M. Oleś, P. Simon, and P. Piekarz, Phys. Rev. B 102, 245405 (2020).
  * Manna  _et al._ [2020] S. Manna, P. Wei, Y. Xie, K. T. Law, P. A. Lee, and J. S. Moodera, PNAS 117, 8775 (2020).
  * Wei  _et al._ [2019] P. Wei, S. Manna, M. Eich, P. Lee, and J. Moodera, Phys. Rev. Lett. 122, 247002 (2019).
  * Cao  _et al._ [2018] Y. Cao, V. Fatemi, S. Fang, K. Watanabe, T. Taniguchi, E. Kaxiras, and P. Jarillo-Herrero, Nature 556, 43 (2018).
  * Kobayashi  _et al._ [2019] S. Kobayashi, A. Yamakage, Y. Tanaka, and M. Sato, Phys. Rev. Lett. 123, 097002 (2019).
  * Sajadi  _et al._ [2018] E. Sajadi, T. Palomaki, Z. Fei, W. Zhao, P. Bement, C. Olsen, S. Luescher, X. Xu, J. A. Folk, and D. H. Cobden, Science 362, 922 (2018).
  * Yuan  _et al._ [2019] Y. Yuan, J. Pan, X. Wang, Y. Fang, C. Song, L. Wang, K. He, X. Ma, H. Zhang, F. Huang, W. Li, and Q.-K. Xue, Nat. Phys. 15, 1046 (2019).
  * Samarawickrama  _et al._ [2021] P. Samarawickrama, R. Dulal, Z. Fu, U. Erugu, W. Wang, J. Ackerman, B. Leonard, J. Tang, T. Chien, and J. Tian, ACS Omega 6, 2966 (2021).
  * Jiao  _et al._ [2020] L. Jiao, S. Howard, S. Ran, Z. Wang, J. O. Rodriguez, M. Sigrist, Z. Wang, N. P. Butch, and V. Madhavan, Nature 579, 523 (2020).
  * Lane and Zhu [2020] C. Lane and J.-X. Zhu, Phys. Rev. B 101, 155135 (2020).
  * Island  _et al._ [2019] J. O. Island, X. Cui, C. Lewandowski, J. Y. Khoo, E. M. Spanton, H. Zhou, D. Rhodes, J. C. Hone, T. Taniguchi, K. Watanabe, L. S. Levitov, M. P. Zaletel, and A. F. Young, Nature 571, 85 (2019).