# Cyclic Group Projection for Enumerating Quasi-Cyclic Codes Trapping Sets

Vasiliy Usatyuk  R&D Department, T8
Email<EMAIL_ADDRESS>Yury Kuznetsov  R&D Department, T8
Email<EMAIL_ADDRESS>Sergey Egorov  Computer Science Department, South-West
State University
Email<EMAIL_ADDRESS>
###### Abstract

This paper introduces a novel approach to enumerate and assess Trapping sets
in quasi-cyclic codes, those with circulant sizes that are non-prime numbers.
Leveraging the quasi-cyclic properties, the method employs a tabular technique
to streamline the importance sampling step for estimating the pseudo-codeword
weight of Trapping sets. The presented methodology draws on the mathematical
framework established in the provided theorem, which elucidates the behavior
of projection and lifting transformations on pseudo-codewords.

##  I Introduction

The incorporation of graph models as a theoretical framework has sparked a
revolutionary impact across a wide array of domains, notably in areas such as
forward error correction, source coding, compressed sensing, classical and
quantum machine learning/computation, quasi-optimal electrical power and
transport networks, post-quantum cryptography.

In the publication [1], a noteworthy connection has been revealed between
sophisticated Deep Neural Network (DNN) architectures, exemplified by state-
of-the-art models such as Mega and ChordMixer Transformers in Natural Language
Processing, and the Generalized Irregular Repeat Accumulate and Cage-graph
graph models. Delving into the intricacies of the approximate landscape of
Bethe-Hessian (Bethe-permanent) and Quasi-Newton landscape Hessian (permanent)
in deep neural networks goes beyond the conventional lazy regime, sparking
inquiries into the symmetry and asymmetry of statistical manifolds within
arbitrary non-linear channels [2]. This exploration reignites discussions on
the capacity of graph models under non-linear data channels in high noise
environments, with a specific emphasis on the generalized covariance evolution
describing linear size Trapping sets (TS) and low noise conditions for
sublinear linear size TS. A notable discovery relates to certain nonlinear
data channels, where the clarification of ground states (barycenter, [3, 4])
involves embedding tori and circular hyperboloids, revealing their equivalence
to quasi-cyclic codes. The count of energy minima corresponds to the size of
the circulant, underscoring the crucial role of quasi-cyclic codes in
linearization, [1]. As a result, advancing neural network architectures and
establishing highly reliable, length-adaptive error correction codes based on
quasi-cyclic graphs necessitates the development of efficient algorithms aimed
at enhancing the spectrum of TS.

##  II Basic definition

To facilitate clarity in our exposition, we denote the binary field as
$GF(2)\equiv\mathbb{F}_{2}$. Formulas employ a zero-based numbering
convention. The cardinality of a finite set $M$ is denoted as $|M|$. In
expressions where addition is conducted within the field $\mathbb{F}_{2}$, the
symbol $\oplus$ is employed. The set of integers is denoted as $\mathbb{Z}$.
Our foundational notation is introduced following the conventions outlined in
[6].

######  Definition 1.

The circulant matrix $Q$, denoted as $\\{Q_{ij}\\}_{i,j=0}^{z-1}$ with $z>0$,
is defined as follows:

$Q_{ij}=\begin{cases}1,&\text{if }i+1\equiv j\pmod{z},\\\
0,&\text{otherwise},\end{cases}$

for $i,j=0,\ldots,z-1$.

Additionally, it is assumed that the inverse of $Q$, denoted as $Q^{-1}$, is
equivalent to the zero matrix $\mathbf{0}$ in $\mathbb{F}_{2}^{z\times z}$. We
assume $Q^{-1}\equiv 0\in\mathbb{F}_{2}^{z\times z}$.

######  Definition 2.

The quasi-cyclic parity-check matrix, denoted as $H$ and of size $mz\times nz$
with $m,n>0$ and circulant $z$, is expressed as:

$H=\left[\begin{array}[]{llll}Q^{a_{00}}&Q^{a_{01}}&\ldots&Q^{a_{0,n-1}}\\\
Q^{a_{10}}&Q^{a_{11}}&\ldots&Q^{a_{1,n-1}}\\\ \vdots&\vdots&\vdots&\vdots\\\
Q^{a_{m-1,0}}&Q^{a_{m-1,1}}&\ldots&Q^{a_{m-1,n-1}}\\\ \end{array}\right].$

######  Definition 3.

The exponential matrix $E(H)$, belonging to $\mathbb{Z}^{m\times n}$ and
defined for $H$ as follows:

$E(H)=\left[\begin{array}[]{llll}a_{00}&a_{01}&\ldots&a_{0,n-1}\\\
a_{10}&a_{11}&\ldots&a_{1,n-1}\\\ \vdots&\vdots&\vdots&\vdots\\\
a_{m-1,0}&a_{m-1,1}&\ldots&a_{m-1,n-1}\\\ \end{array}\right].$

######  Definition 4.

The mother matrix or base (protograph) matrix $M(H)$ is obtained from $E(H)$
by replacing -1 with 0, and all other values with 1.

######  Definition 5.

The linear code defined by a quasi-cyclic parity-check matrix $H$, denoted as
$C=C(H)$, is a subset of $\mathbb{F}_{2}^{nz}$ and is defined as:

$C(H)=\\{x\in\mathbb{F}_{2}^{nz}:\quad Hx^{T}=0\\}.$

##  III Cyclic Group Decomposition

Let’s assume that the circulant size $z$ is equal to the product of two
integers $l$ and $z_{\ast}$, where both $l$ and $z_{\ast}$ are greater than 1.
Notably, this property is found in various practical instances, including
length-adapted quasi-cyclic codes such as the enhanced mobile broadband (eMBB)
5G QC-LDPC codes, DVB-S2/X codes, Graph Neural Network and others.

######  Definition 6.

([6], 3.1), [7, 8]. The mapping $\mathbb{P}_{z\rightarrow z_{\ast}}$ from a
set of quasi-cyclic matrices $\mathbb{F}_{2}^{mz\times nz}$ with circulant
size $z$ to a set of quasi-cyclic matrices $\mathbb{F}_{2}^{mz_{\ast}\times
nz_{\ast}}$ with circulant size $z_{\ast}$ is determined by the mapping of
their exponential matrices, denoted as $E_{z}\rightarrow E_{z_{\ast}}$. Here,
$E_{z}$ and $E_{z_{\ast}}$ belong to $\mathbb{Z}^{m\times n}$ and follow a
modular lifting scheme:

$\\{E_{z_{\ast}}\\}_{ij}=\begin{cases}\\{E_{z}\\}_{ij}\,\mathrm{mod}\,z_{\ast},&\text{if
}\\{E_{z}\\}_{ij}\geqslant 0,\\\ -1,&\text{if
}\\{E_{z}\\}_{ij}=-1.\end{cases}$

It’s worth noting that the mapping $\mathbb{P}_{z\rightarrow z_{\ast}}$
preserves the structure of the mother matrix. Specifically, the Tanner graph
of a quasi-cyclic matrix $\tilde{H}$ with the exponential matrix
$E_{z}=E(\tilde{H})$, along with the natural projection, constitutes an
$l$-graph covering of the parity-check matrix $H$ with $E_{z_{\ast}}=E(H)$,
[9].

######  Definition 7.

Linear mapping $P_{z\rightarrow z_{\ast}}$ set of vectors
$\mathbb{F}_{2}^{nz}$ to a set of vectors $\mathbb{F}_{2}^{nz_{\ast}}$ we will
determine by the following procedure. For arbitrary $x\in\mathbb{F}_{2}^{nz}$
let’s denote $y=P_{z\rightarrow z_{\ast}}x\in\mathbb{F}_{2}^{nz_{\ast}}$.
Component $y_{j}$, ${0\leqslant j<nz_{\ast}-1}$, where $j=qz_{\ast}+r$,
$0\leqslant r<z_{\ast}$, is calculated as follows:

$y_{j}=x_{qz+r}\oplus x_{qz+r+z_{\ast}}\oplus\ldots\oplus
x_{qz+r+(l-1)z_{\ast}}.$ (1)

If we consider $x$ as the codeword of a quasi-cyclic parity-check matrix
$\tilde{H}$, then the vector $P_{z\rightarrow z_{\ast}}x$ becomes the image of
a pseudocode word (as defined in [9]) corresponding to $x$ under the
homomorphism $\mathbb{Z}\rightarrow\mathbb{Z}_{2}$. This $l$-covering is
determined by the mapping $\mathbb{P}_{z\rightarrow z_{\ast}}$. Graph covers,
accompanied by their corresponding lifting operations, can be seen as
enhancing the delay operator in convolutional codes. The tail-bited form of
convolutional codes evolves into Quasi-Cyclic codes with an expanding
circulant size, as elaborated in [12, 9, 10, 11]. As observed, both codewords
[13, 14, 15] and pseudo-codewords [16, 17, 18] consistently approach their
respective upper bounds.

######  Definition 8.

Projection index operator: The function $\pi_{z\rightarrow z_{\ast}}$ is
defined as:

$\pi_{z\rightarrow
z_{\ast}}:\\{0,1,2,\ldots\\}\longrightarrow\\{0,1,2,\ldots\\},$

and it operates as follows: for $j\geqslant 0$, $j=qz+r$, $0\leqslant r<z$,

$\pi_{z\rightarrow z_{\ast}}(j)=qz_{\ast}+(r\,\mathrm{mod}\,z_{\ast}).$

Using the definition of $\pi_{z\rightarrow z_{\ast}}$, $P_{z\rightarrow
z_{\ast}}$ can be expressed as:

$\forall x\in\mathbb{F}_{2}^{nz}\quad\\{P_{z\rightarrow
z_{\ast}}x\\}_{j}=\sum_{k\in\pi^{-1}(j)}x_{k},\,\,j=0,1,\ldots,nz_{\ast}-1,$

where the summation is performed in $\mathbb{F}_{2}$.

######  Definition 9.

[19][Definition 27] A $(w,v)$-TS pseudo-codeword is a vector
$x\in\mathbb{F}_{2}^{nz}$ satisfying the condition that the Hamming weights of
the vectors $x$ and $Hx^{T}$ are equal to $w$ and $v$ respectively, where
$w>0$ and $v\geqslant 0$.

We fix an arbitrary quasi-cyclic check matrix $H\in\mathbb{F}_{2}^{mz\times
nz}$ with a circulant size of $z$, where $z=lz_{\ast}$,
$l,z_{\ast}\in\mathbb{Z}$, and $l,z_{\ast}>1$.

######  Theorem 1.

For any pseudocode word $(w,v)$-pseudocode word $x\in\mathbb{F}_{2}^{nz}$
relative to the check matrix $H$ vector $x_{\ast}=P_{z\rightarrow
z_{\ast}}x\in\mathbb{F}_{2}^{nz_{\ast}}$ will $(w^{\prime},v^{\prime})$-TS
pseudo-code word relative to the parity check matrix
$H_{\ast}=\mathbb{P}_{z\rightarrow z_{\ast}}H$, and $w^{\prime}\leqslant
w,\;v^{\prime}\leqslant v,$

$\quad
v-v^{\prime}=2r^{\prime},\,w-w^{\prime}=2r^{\prime\prime},\,\,r^{\prime},r^{\prime\prime}\in\\{0,1,2,\ldots\\}.$

As a consequence, the linear transformation

$P_{z\rightarrow
z_{\ast}}:\mathbb{F}_{2}^{nz}\longrightarrow\mathbb{F}_{2}^{nz_{\ast}}$

maps the linear code $C(H)$ to some subset of code $C(H_{\ast})$.

######  Remark 1.

Case $w^{\prime}=0$ possible if $w$ – even number. In this case, the statement
of the theorem makes no sense.

######  Remark 2.

The corollary indicated at the end of the theorem is directly deduced from the
theorem 4.4 from [9].

###### Proof.

To simplify the proof, we will use the symbols $\mathbb{P}$, $P$, $\pi$
without index $z\rightarrow z_{\ast}$.

The first part of the theorem is that the number of non-zero components of the
vector $x_{\ast}=Px$ will be the same as $x$, or less by an even number. This
follows from the definition of the operation $P$ (1). To prove the second
part, we introduce a number of notations and simplifications.

From the definition of the Hamming weight it follows that it is sufficient to
prove the statement of the theorem for $m=1$, that is for parity-check matrix
${H\in\mathbb{F}_{2}^{z\times nz}}$ from one block (circulant) row.

For an arbitrary vector $y\in\mathbb{F}_{2}^{q}$ through $\mathrm{supp}\,y$ we
will denote the set of indices $j\in\\{0,1,\ldots,q-1\\}$ such that $y_{j}=1$.

$\sigma:\mathbb{Z}\longrightarrow\mathbb{Z}_{2}$ — homomorphism of additive
groups.

Let’s assume that the index $i$ defines some scalar linear equation. Will
write $\rho(i)=1$ if this equation does not hold for vector $x$ (clear from
the context) and $\rho(i)=0$ otherwise.

Let us denote by $V^{0}$ and $V^{0}_{\ast}$ subsets of vertex indices
$\\{i\\}_{i=0}^{nz-1}$ and $\\{i\\}_{i=0}^{nz_{\ast}-1}$ respectively,
corresponding to non-zero circulants of the matrices $\mathbb{F}_{2}^{z\times
nz}$ and $\mathbb{F}_{2}^{z_{\ast}\times nz_{\ast}}$.

Since any active parity-check — i.e. scalar equation of the system $Hu=0$
($H_{\ast}v=0$), containing non-zero vector component $x$ ($x_{\ast}$) —
depends only on $\mathrm{supp}\,x\cap V^{0}$ ($\mathrm{supp}\,x_{\ast}\cap
V^{0}_{\ast}$) and, in addition, for $\tilde{x}$,
$\mathrm{supp}\,\tilde{x}=\mathrm{supp}\,x\cap V^{0}$ equality is satisfied

$\mathrm{supp}\,(P\tilde{x})=\mathrm{supp}\,(Px)\cap V^{0}_{\ast},$

we can assume that $\mathrm{supp}\,x\subset V^{0}$,
$\mathrm{supp}\,x_{\ast}\subset V^{0}_{\ast}$. There are relations

$\pi(V^{0})=V^{0}_{\ast},\quad\mathrm{supp}\,x_{\ast}\subset\pi(\mathrm{supp}\,x)$

Quasi-cyclic matrix structure $H$ and $H_{\ast}$ uniquely defines mappings

$\displaystyle c(\cdot):$ $\displaystyle
V^{0}\longrightarrow\\{0,1,\ldots,z-1\\}$ $\displaystyle c_{\ast}(\cdot):$
$\displaystyle V^{0}_{\ast}\longrightarrow\\{0,1,\ldots,z_{\ast}-1\\}$

corresponding to the vertex index $j$ row index $i$ such that the element of
the corresponding check matrix in position $(i,j)$ is equal to 1. Let us prove
the equality

$c_{\ast}(\pi(j))=\pi(c(j)),\quad j\in V^{0}.$ (2)

Let’s fix an arbitrary index $j\in V^{0}$, $j=qz+r$, $0\leqslant q<n$,
$0\leqslant r<z$. Then $c(j)=(r-a_{q})\,\mathrm{mod}\,z$, where $a_{q}$ —
exponent (upper index) $q$-th circulant of the matrix $H$, and the operation
$a\,\mathrm{mod}\,z$ is defined so that the result lies in the interval
$[0,z-1]$ for any integer $a$. The chain of equalities is fair

$\pi(c(j))=((r-a_{q})\,\mathrm{mod}\,z)\,\mathrm{mod}\,z_{\ast}=\\\
=(r-a_{q})\,\mathrm{mod}\,z_{\ast}=(r\,\mathrm{mod}\,z_{\ast}-a_{q}\,\mathrm{mod}\,z_{\ast})\,\mathrm{mod}\,z_{\ast}=\\\
=c_{\ast}(qz_{\ast}+r\,\mathrm{mod}\,z_{\ast})=c_{\ast}(\pi(j)).$

Mapping

$\pi:\\{0,1,\ldots,nz-1\\}\longrightarrow\\{0,1,\ldots,nz_{\ast}-1\\}$

defines the decomposition of a set $V^{0}$ into disjoint subsets
$W_{j}:=\pi^{-1}(j)$, $j\in V^{0}_{\ast}$.

By definition of operation $P$ set of indexes $\mathrm{supp}\,x_{\ast}$
correspond one-to-one with these $W_{j}$, for which
$W_{j}\cap\mathrm{supp}\,x$ consists of an odd number of elements. We will
denote this fact $W_{j}\sim\mathrm{supp}\,x_{\ast}$.

######  Lemma 1.

Let’s $\mathcal{W}$ — arbitrary family of sets $W_{j}$, $j\in V_{\ast}^{0}$.

$\hat{\mathcal{W}}:=\\{W\in\mathcal{W}:\;W\sim\mathrm{supp}\,x_{\ast}\\}.$

Then the following parities coincide:

$\sigma(|\hat{\mathcal{W}}|)=\sigma\left(\left|\bigcup_{W\in\mathcal{W}}\\{W\cap\mathrm{supp}\,x\\}\right|\right)$
(3)

###### Proof.

Let us first assume the equality $\hat{\mathcal{W}}=\mathcal{W}$. Considering
that the sets in the union on the right side (3) do not intersect, we get:

$\left|\bigcup_{W\in\mathcal{W}}\\{W\cap\mathrm{supp}\,x\\}\right|=\sum_{W\in\mathcal{W}}|\\{W\cap\mathrm{supp}\,x\\}|=\\\
=\sum_{W\in\mathcal{W}}(1+2s_{W})=|\mathcal{W}|+2s,$

where $s_{W}$, $s$ — some integers. This proves the lemma in a special case.
If $\hat{\mathcal{W}}\neq\mathcal{W}$, then the number of indices
$\mathrm{supp}\,x$ in every set $\mathcal{W}\setminus\hat{\mathcal{W}}$ will
be either zero or a positive even number, and we can refer to an already
proven fact. ∎

Using the following notation $C^{a}$, $C^{a}_{\ast}$ let us denote the sets of
active parity-checks for $H$, $H_{\ast}$ relative to vectors $x$, $x_{\ast}$:

$C^{a}=c(\mathrm{supp}\,x),\quad
C^{a}_{\ast}=c_{\ast}(\mathrm{supp}\,x_{\ast})$

######  Lemma 2.

For any $s\in C^{a}_{\ast}$ there is a non-empty set of indices
${\\{i_{1}^{s},\ldots,i_{k(s)}^{s}\\}}$, $i_{l}^{s}\in C^{a}$,
$l=1,\ldots,k(s)$ such that

$\rho(s)=\rho(i_{1}^{s})\oplus\ldots\oplus\rho(i^{s}_{k(s)}),$

and for different $s^{\prime},s^{\prime\prime}$ the index sets do not
intersect.

###### Proof.

Let’s fix the $s\in C^{a}_{\ast}$ and consider the equation

$s=c_{\ast}(\pi(j)),\quad j\in\mathrm{supp}\,x.$ (4)

Set of solutions to the (4) denote by $R=R(s)$. From the equality we see (2)
follows it follows that the following sets are either fully contained in
$R(s)$, or do not intersect with it:

$\displaystyle\mathrm{supp}\,x\cap W_{j},$ $\displaystyle j\in V^{0}_{\ast}$
(5) $\displaystyle\mathrm{supp}\,x\cap c^{-1}(i),$ $\displaystyle
i=0,1,\ldots,z-1$ (6)

contained in $R(s)$ non-empty representatives (5), (6) form two partitions of
this set. Let’s define

$\mathcal{W}(s):=\\{W_{j}:\,\mathrm{supp}\,x\cap W_{j}\subset R(s),\,j\in
V_{\ast}^{0}\\}.$

As a set $\\{i_{l}^{s}\\}_{l=1}^{k(s)}$ let’s take different indices $i$,
${0\leqslant i<z-1}$, for which the sets (6) are non-empty and contained in
$R(s)$. Number of solutions to the equation $c_{\ast}(j_{\ast})=s$,
$j_{\ast}\in\mathrm{supp}\,x_{\ast}$ equal to the number of such
$W\in\mathcal{W}(s)$, that $W\sim\mathrm{supp}\,x_{\ast}$. Hence and from the
lemma (1) we get equalities:

$\rho(s)=\sigma\left(|\\{W\in\mathcal{W}(s):\,W\sim\mathrm{supp}\,x_{\ast}\\}|\right)=\sigma(|R(s)|)=\\\
=\sigma\left(\left|\bigcup_{l=1}^{k(s)}\\{\mathrm{supp}\,x\cap
c^{-1}(i_{l}^{s})\\}\right|\right)=\\\
=\sum_{l=1}^{k(s)}\sigma(|\\{\mathrm{supp}\,x\cap
c^{-1}(i_{l}^{s})\\}|)=\sum_{l=1}^{k(s)}\rho(i_{l}^{s}),$

where the summation is performed in $\mathbb{F}_{2}$.

If $s^{\prime}\in C^{a}_{\ast}$, $s^{\prime}\neq s$, that set of indexes
$\\{i_{l}^{s^{\prime}}\\}_{l=1}^{k(s^{\prime})}$ cannot intersect with set
$\\{i_{l}^{s}\\}_{l=1}^{k(s)}$ due to equality (2). ∎

######  Remark 3.

In certain scenarios, it is possible that there are no solutions $j$ to the
equation $y_{j}=1$, where $j$ is projected into $\text{supp }x_{\ast}$
according to the definition given in Equation (4). By repeating the reasoning
presented in the lemma, it becomes evident that in such cases, the number of
active checks unsatisfied, denoted as $\\{i_{l}^{s}\\}_{l=1}^{k(s)}$, will be
even.

The remaining part of the theorem can be derived from Lemma 2. For any
unsatisfied check $s\in C^{a}_{\ast}$, where $\rho(s)=1$, the number of
unsatisfied checks among $\\{i_{l}^{s}\\}_{l=1}^{k(s)}\subset C^{a}$ will
either be equal to 1 or exceed 1 by an even number. Additionally, considering
the remark, the checks from $C^{a}$ that are not related to $C^{a}_{\ast}$
will result in an even number. ∎

Numerical Example 1.

Consider a QC parity-check matrix, with circulant $z=128$ and exponential
matrix

$\displaystyle E(H)=[E_{1}|E_{2}],\,\text{where}$ (7)
$\displaystyle\begin{subarray}{c}E_{1}=\left[\begin{array}[]{rrrrrrrrrr}21&65&126&39&84&89&16&89&94&28\\\
12&29&27&105&0&0&0&2&108&78\\\ 47&26&97&40&66&0&81&1&33&97\\\
113&21&64&26&53&103&85&81&102&48\end{array}\right]\end{subarray}$ (8)
$\displaystyle\begin{subarray}{c}E_{2}=\left[\begin{array}[]{rrrrrrrrrr}31&12&101&9&122&99&90&65&41&-1\\\
126&98&27&1&41&118&49&17&12&11\\\ 89&37&52&42&2&120&38&-1&86&7\\\
113&98&71&70&121&66&95&40&-1&23\end{array}\right]\end{subarray}$ (9)

For $H$ a lifting operation, inverse to projection, has been performed. For
this purpose the binary matrix was used $B=\\{b_{ij}\\}$, $i=0,\ldots,3$ ,
$j=0,\ldots,19$, whose elements are drawn from a pseudo-random binary
distribution. The resulting $\tilde{H}\in\mathbb{F}_{2}^{1024\times 5120}$,
$\tilde{z}=2z=256$ defined by its exponential matrix $\tilde{E}=E(\tilde{H})$,

$\\{\tilde{E}\\}_{ij}=\left\\{\begin{array}[]{ll}\\{E\\}_{ij}+b_{ij}z,&\\{E\\}_{ij}\geqslant
0,\\\ -1,&\\{E\\}_{ij}=-1,\\\ \end{array}\right.$

where $E=E(H)$. It’s obvious that $H=\mathbb{P}_{256\rightarrow
128}(\tilde{H})$.

It has been determined using an approximate method that there are 874903
$(w,v)$-Trapping sets in the space $\mathbb{F}_{2}^{5120}$ under the
constraints $w\leqslant 30$ and $v\leqslant w$. Each of these words has
undergone projection using the operation $P_{256\rightarrow 128}$ (refer to
Definition 7). The resulting words have been classified into their respective
classes $(w^{\prime},v^{\prime})$. The distribution of differences
$(w-w^{\prime},v-v^{\prime})$ is presented in Table I. Note that two class
changes

$(w,v)\rightarrow(w,v),\quad(w,v)\rightarrow(w,v-2)$

make up for this matrix and its lifting 99.26% cases.

TABLE I: Distribution of differences $(w-w^{\prime},v-v^{\prime})$ $w-w^{\prime}$ | $v-v^{\prime}$ | frequency, %
---|---|---
0 | 0 | 93.071689
0 | 2 | 6.191543
0 | 4 | 0.191678
0 | 6 | 0.002743
2 | 0 | 0.360154
2 | 2 | 0.152474
2 | 4 | 0.016458
2 | 6 | 0.000571
4 | 0 | 0.006400
4 | 2 | 0.003543
4 | 4 | 0.001257
6 | 0 | 0.000685
6 | 2 | 0.000457
6 | 4 | 0.000228
8 | 4 | 0.000114

##  IV QC Codes TS Enumerating

We will assume that we are given a quasi-cyclic parity-check matrix
$H\in\mathbb{F}_{2}^{mz\times nz}$, $m,n,z>0$. Automorphism group ( [20][Ch.
8, § 5]) $Aut(C(H))$ linear code $C(H)$ contains a subgroup
$\mathcal{G}_{n,z}$ quasi-cyclic shifts. $\mathcal{G}_{n,z}$ — cyclic group of
order $z$ with generator $\pi_{0}$, which acts on indexes $j$, $0\leqslant
j<nz-1$, $j=qz+r$, $0\leqslant r<z$ in the following way:

$\pi_{0}(j)=qz+(r+1)\,\mathrm{mod}\,z.$

$k>0$ steps of the abstract decoder will be written in the form of a nonlinear
operator $D_{k}:\mathbb{R}^{nz}\rightarrow\mathbb{R}^{nz}$.

If $x\in\mathbb{F}_{2}^{nz}$ — some $(w,v)$-Trapping sets, $w>0$, and the
generator $\pi_{0}\in\mathcal{G}_{n,z}$ commutes with $D_{k}$, $k=1,2,\ldots$
then it’s easy to see the error limit [21][Step 2] will be the same for the
entire orbit $\\{\pi x:\,\pi\in\mathcal{G}_{n,z}\\}$. Moreover, automorphisms
$\mathcal{G}_{n,z}$ commute with projectors $P$ (def. 7) Trapping sets pseudo-
codewords, more precisely, the following statement holds.

######  Statement 1.

For any divisor $z_{\ast}$ numbers $z$ and any $s=0,1,\ldots,{z-1}$ the
following diagram is commutative:

${\mathbb{F}_{2}^{nz}}$${\mathbb{F}_{2}^{nz}}$${\mathbb{F}_{2}^{nz_{\ast}}}$${\mathbb{F}_{2}^{nz_{\ast}}}$$\scriptstyle{\pi_{0}^{s}}$$\scriptstyle{P_{z\rightarrow
z_{\ast}}}$$\scriptstyle{P_{z\rightarrow
z_{\ast}}}$$\scriptstyle{\pi_{0}^{s\,\mathrm{mod}\,z_{\ast}}}$

###### Proof.

Follows from the definitions $P_{z\rightarrow z_{\ast}}$ and
$\pi_{0}\in\mathcal{G}_{n,z}$. ∎

From previous discussions and statements (1) it is clear that it is sufficient
to leave a set of pseudo-codewords that are not pairwise equivalent to each
other.

Let’s choose some approximate algorithm solve, enumerating for the quasi-
cyclic check matrix $H\in\mathbb{F}_{2}^{mz\times nz}$ set $X$ pseudo-code
words that are not equivalent in pairs with respect to each other
$\mathcal{G}_{n,z}$. Of course, there are many such algorithms, optimized in
different ways, for example to:

  * •

Strategy I. get maximum number $x\in\mathbb{F}_{2}^{nz}$ with minimum distance
$d_{\epsilon}^{2}$ up to the error limit;

  * •

Strategy II. get maximum number $x\in\mathbb{F}_{2}^{nz}$ $x\sim(w,v)$ under
restrictions $w\leqslant w_{max}$, $v\leqslant v(w)$, where in the simplest
case $v(w)=w$.

Algorithm 1 Algorithm for QC Codes TS enumeration

1:$E(H)$, $N>0$ \- number of lifted matrix $E_{j}$.

2: Construct lifted matrices $E_{j}$ of the exponential matrix $E(H)$ using
$B_{j}$ (see numerical example 1) and the corresponding parity-check matrices
$H_{j}$, $j=0,\ldots,N-1$.

3: Calculate $X_{2z,j}:=\mathtt{solve}(H_{j})$.

4: Calculate $X_{z,j}:=P_{2z\rightarrow z}X_{2z,j}$.

5: Find the maximum subset of a set $\cup_{j=0}^{N-1}X_{z,j}$, consisting of
pairwise nonequivalent pseudo-codewords.

The Algorithm 1 computational complexity is solely determined by Step 3. The
validity of the method, as per Theorem (1), is specifically established for
words with class conversion $(w,v)\rightarrow(w^{\prime},v^{\prime})$, where
$w^{\prime}=w$. Notably, such cases constitute the predominant scenarios in
the problems under consideration.

Numeric Example 2:

Consider the QC parity-check matrix given in (7)-(9) and employ 32 matrices
($N=32$). Through 20 hours of computations utilizing four parallel threads on
an Intel Xeon E5-2696 v4 processor, a total of 28,623,960 distinct
$(w,v)$-Trapping Sets were founded, Strategy I. The distribution of these
words, categorized by the class $(w,v)$, is presented in tables II to IV. The
rows in the tables correspond to the number of variable nodes $w$, while the
columns represent the count of unsatisfied checks $v$.

TABLE II: Distribution of Trapping sets $(w,v)$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---
1 | 0 |  |  |  |  |  |  |  |  |
2 | 0 | 0 |  |  |  |  |  |  |  |
3 | 0 | 0 | 0 |  |  |  |  |  |  |
4 | 0 | 0 | 0 | 1 |  |  |  |  |  |
5 | 0 | 0 | 0 | 2 | 33 |  |  |  |  |
6 | 0 | 0 | 1 | 4 | 38 | 803 |  |  |  |
7 | 0 | 0 | 0 | 1 | 82 | 1079 | 11109 |  |  |
8 | 0 | 0 | 0 | 10 | 125 | 1886 | 13722 | 82004 |  |
9 | 0 | 0 | 1 | 11 | 184 | 2212 | 23952 | 74786 | 257967 |
10 | 0 | 0 | 0 | 20 | 210 | 3122 | 20028 | 150662 | 221759 | 537954
11 | 0 | 0 | 0 | 14 | 249 | 2548 | 23038 | 89105 | 523548 | 434372
12 | 0 | 0 | 1 | 26 | 249 | 2288 | 14748 | 87080 | 253567 | 1141220
13 | 0 | 0 | 0 | 10 | 168 | 1638 | 10379 | 49714 | 199393 | 485167
14 | 0 | 0 | 0 | 14 | 153 | 1217 | 7100 | 32254 | 113767 | 314533
15 | 0 | 0 | 0 | 11 | 105 | 781 | 4771 | 20972 | 70765 | 183229
16 | 0 | 0 | 2 | 9 | 97 | 578 | 3331 | 14007 | 46158 | 116059
17 | 0 | 0 | 0 | 5 | 51 | 414 | 2116 | 9305 | 30284 | 75122
18 | 0 | 0 | 0 | 3 | 54 | 258 | 1451 | 6401 | 20480 | 49946
19 | 0 | 0 | 0 | 0 | 28 | 168 | 1013 | 4129 | 13555 | 33001
20 | 0 | 0 | 1 | 1 | 21 | 116 | 658 | 2759 | 9017 | 22248
21 | 0 | 0 | 0 | 1 | 6 | 73 | 394 | 1808 | 6010 | 14602
22 | 0 | 0 | 0 | 1 | 8 | 50 | 247 | 1184 | 3860 | 9805
23 | 0 | 0 | 0 | 0 | 3 | 39 | 176 | 746 | 2511 | 6446
24 | 0 | 0 | 0 | 0 | 0 | 24 | 91 | 499 | 1665 | 4356
25 | 0 | 0 | 0 | 0 | 1 | 12 | 81 | 294 | 1023 | 2759
26 | 0 | 0 | 0 | 0 | 0 | 7 | 51 | 196 | 672 | 1893
27 | 0 | 0 | 0 | 0 | 1 | 6 | 26 | 144 | 416 | 1226
28 | 0 | 0 | 0 | 0 | 0 | 4 | 15 | 73 | 269 | 798
29 | 0 | 0 | 0 | 0 | 0 | 2 | 10 | 55 | 179 | 488
30 | 0 | 0 | 0 | 0 | 0 | 1 | 5 | 36 | 113 | 327
TABLE III: Distribution of Trapping sets $(w,v)$ | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---
11 | 679776 |  |  |  |  |  |  |  |
12 | 525023 | 461020 |  |  |  |  |  |  |
13 | 1554985 | 389114 | 258537 |  |  |  |  |  |
14 | 657114 | 1513059 | 256509 | 148743 |  |  |  |  |
15 | 388532 | 708806 | 1321139 | 151631 | 57480 |  |  |  |
16 | 229091 | 418952 | 672534 | 1008359 | 72773 | 31479 |  |  |
17 | 147227 | 250979 | 403669 | 568414 | 710717 | 38932 | 10705 |  |
18 | 96483 | 163431 | 244586 | 355260 | 445490 | 486945 | 16008 | 5903 |
19 | 64579 | 108837 | 161037 | 219709 | 296733 | 331568 | 310638 | 8197 | 2002
20 | 43578 | 72524 | 108737 | 146508 | 189905 | 231101 | 234722 | 201297 | 3294
21 | 29199 | 49859 | 73927 | 99409 | 127728 | 153153 | 176151 | 162620 | 123395
22 | 19921 | 33911 | 50844 | 68599 | 88005 | 104483 | 121419 | 127482 | 108790
23 | 13300 | 23202 | 35095 | 48044 | 60763 | 73618 | 84312 | 92364 | 91845
24 | 9024 | 15971 | 24386 | 33526 | 42439 | 51402 | 59559 | 65539 | 69455
25 | 5995 | 10959 | 17133 | 23651 | 30270 | 36385 | 42387 | 47275 | 51012
26 | 4229 | 7595 | 11775 | 16658 | 21354 | 25734 | 30061 | 34101 | 36835
27 | 2736 | 5223 | 8275 | 11831 | 15478 | 18698 | 21929 | 24431 | 27141
28 | 1832 | 3441 | 5762 | 8268 | 11245 | 13586 | 15902 | 18157 | 19773
29 | 1222 | 2310 | 3990 | 5878 | 7974 | 9774 | 11568 | 13128 | 14457
30 | 813 | 1537 | 2753 | 4178 | 5723 | 7115 | 8728 | 9757 | 10807
TABLE IV: Distribution of Trapping sets $(w,v)$ | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30
---|---|---|---|---|---|---|---|---|---|---|---
20 | 1199 |  |  |  |  |  |  |  |  |  |
21 | 1696 | 516 |  |  |  |  |  |  |  |  |
22 | 77348 | 748 | 311 |  |  |  |  |  |  |  |
23 | 71948 | 47293 | 429 | 194 |  |  |  |  |  |  |
24 | 63799 | 46955 | 28875 | 252 | 112 |  |  |  |  |  |
25 | 49967 | 44223 | 30251 | 17646 | 168 | 70 |  |  |  |  |
26 | 38506 | 36280 | 29742 | 19657 | 10920 | 106 | 52 |  |  |  |
27 | 28602 | 28679 | 25804 | 19810 | 12566 | 6552 | 72 | 35 |  |  |
28 | 21540 | 21716 | 21008 | 17841 | 13092 | 7953 | 4066 | 41 | 32 |  |
29 | 15185 | 16371 | 16191 | 14971 | 12051 | 8647 | 4949 | 2507 | 0 | 0 |
30 | 11685 | 12146 | 12662 | 12214 | 10673 | 8224 | 5699 | 3093 | 1485 | 0 | 0

##  V Quasi-Cyclic Codes Trapping Set Weighing

This section describes techniques to expedite the estimation of the error-
floor probability by leveraging the inherent characteristics of quasi-cyclic
codes. The strategy involves utilizing the tabular Importance Sampling method,
specifically in step 3, [21]. In this step, the estimation of the weight of
trapping sets pseudo-codewords is briefly proposed in ([22], §4.1).

As in previous sections, $H\in\mathbb{F}_{2}^{mz\times nz}$, $m,n,z>0$ —
parity-check matrix defining a linear code $C(H)$,
$D_{k}:\mathbb{R}^{nz}\rightarrow\mathbb{R}^{nz}$ — decoder $k>0$ iterations,
$\mathcal{G}_{n,z}$ — cyclic group of code automorphisms $C(H)$, acting from
the left on sets $\mathbb{F}_{2}^{nz}$, $\mathbb{R}^{nz}$ with generatrix
$\pi_{0}$, $N:=nz$.

Probability of error in decoding a codeword of size $N$ with a normally
distributed $N$-dimensional random noise $\xi\sim\mathcal{N}(\theta,\Sigma)$,
$\Sigma=\mathrm{diag}(\sigma^{2},\ldots,\sigma^{2})$ equal [21][eq. 5]:

$P_{f}=\int\limits_{\mathbb{R}^{N}}I_{e}(y)w(y)f^{\ast}(y)\,dy.$ (10)

where $I_{e}(\cdot)$ — characteristic function of non-codewords from
$\mathbb{R}^{N}$, $f^{\ast}(\cdot)$ — biased density distribution,

$\displaystyle f^{\ast}(y)$
$\displaystyle=1/|\mathcal{V}|\,\sum_{x\in\mathcal{V}}f(y,x),\quad\mathcal{V}\subset\mathbb{R}^{N},\,y\in\mathbb{R}^{N}$
$\displaystyle f(y,x)$
$\displaystyle=(2\pi\sigma^{2})^{-N/2}\exp(-1/2\sigma^{2}\,\|y-x\|^{2}_{\mathbb{R}^{N}}),\quad
x,y\in\mathbb{R}^{N}$ $\displaystyle w(y)$
$\displaystyle=f(y,c)/f^{\ast}(y),\quad y\in\mathbb{R}^{N}$

$f(\cdot,x)$ — density distribution $N$-dimensional normal random variable,
$f\sim\mathcal{N}(x,\Sigma)$. $c=(1,\ldots,1)\in\mathbb{R}^{N}$ — encoded zero
codeword. Defined $\|\cdot\|$ the Euclidean norm.

As noted in the previous section, $d_{\epsilon}^{2}(y)=d_{\epsilon}^{2}(\pi
y)$, $\pi\in\mathcal{G}_{n,z}$, $y\in\mathbb{F}_{2}^{N}$ given that
$D_{k}\pi=\pi D_{k}$, $k=1,2,\ldots$. It follows that it is reasonable to
choose a set $\mathcal{V}$ in the form of a set of disjoint complete
$\mathcal{G}_{n,z}$-orbits of elements. We will denote these elements
$\mathcal{V}_{0}=\\{y_{0}^{b},\ldots,y_{p-1}^{b}\\}$, $y_{i}^{b}\nsim
y_{j}^{b}$, $i\neq j$, $y_{j}^{b}\in\mathbb{R}^{N}$. Then

$\displaystyle\mathcal{V}=\mathcal{V}_{0}\sqcup\pi_{0}\mathcal{V}_{0}\sqcup\ldots\sqcup\pi_{0}^{z-1}\mathcal{V}_{0},\;|\mathcal{V}|=pz,$
$\displaystyle f^{\ast}(\cdot)=1/z\,\sum_{j=0}^{z-1}f^{\ast}_{j}(\cdot),\;$
$\displaystyle\text{where}\;f^{\ast}_{j}(\cdot)=1/p\,\sum_{x\in\pi_{0}^{j}\mathcal{V}_{0}}f(\cdot,x),\;j=0,\ldots,z-1.$

The encoding elements $0,1\in\mathbb{F}_{2}$ are represented by numbers
$1,-1\in\mathbb{R}$ respectively. Consequently, for Trapping Sets
$x\in\mathbb{F}_{2}^{N}$, the codeword can be expressed as $c-\mu
x\in\mathbb{R}^{N}$, where $\mu>0$ is a method parameter. To simplify
calculations, we utilize a natural embedding
$\mathbb{F}_{2}^{N}\subset\mathbb{R}^{N}$, translating elements
$\\{0,1\\}\in\mathbb{F}_{2}$ into numbers $\\{0,1\\}\in\mathbb{R}$. The
"basis" vectors from $\mathcal{V}_{0}$ can be represented in the form
$y_{j}^{b}=c-\mu x_{j}^{b}$, where $x_{j}^{b}\in\mathbb{R}^{N}$,
$j=0,\ldots,p-1$, $\\{x_{j}^{b}\\}_{i}\in\\{0,1\\}$, and $i=0,\ldots,N-1$.

The following statement simplifies the expression $P_{f}$ for such a choice of
set $\mathcal{V}$.

######  Statement 2.

Let’s pretend that $\pi D_{k}=D_{k}\pi$, for all $\pi\in\mathcal{G}_{n,z}$,
$k=1,2,\ldots$. Then

$P_{f}=\int\limits_{\mathbb{R}^{N}}I_{e}(y)w(y)f_{0}^{\ast}(y)\,dy$ (11)

###### Proof.

$P_{f}=1/z\,\sum_{j=0}^{z-1}\,\int\limits_{\mathbb{R}^{N}}I_{e}(y)w(y)f_{j}^{\ast}(y)\,dy=:1/z\,\sum_{j=0}^{z-1}A_{j}.$

Commutability $\pi$ and $D_{k}$ gives equality $I_{e}(\pi y)=I_{e}(y)$,
$y\in\mathbb{R}^{N}$. It is also easy to verify $f(\pi
y,x)=f(y,\pi^{-1}x),\;f^{\ast}(\pi y)=f^{\ast}(y),\;\;\forall
x,y\in\mathbb{R}^{N},\;\pi\in\mathcal{G}_{n,z}.$

Let’s make a variable change $y=\pi_{0}^{j}u$ in the term $A_{j}$:

$A_{j}=\int\limits_{\mathbb{R}^{N}}I_{e}(\pi_{0}^{j}u)\frac{f(\pi_{0}^{j}u,c)}{f^{\ast}(\pi_{0}^{j}u)}f^{\ast}_{j}(\pi_{0}^{j}u)\,du=$
$\int\limits_{\mathbb{R}^{N}}I_{e}(u)\frac{f(u,\pi_{0}^{-j}c)}{f^{\ast}(u)}f^{\ast}_{0}(u)\,du=A_{0},$

where used $\pi c=c$. This implies the statement. ∎

Approximation (11) can be obtained using the Monte Carlo method:

$P_{f}=1/L\,\sum_{l=0}^{L-1}I_{e}(y_{l})w(y_{l}),$ (12)

where $y_{l}$ taken from a density distribution $f^{\ast}_{0}(\cdot)$.
Calculation of value (12) can be simplified further.

$y_{l}=y^{b}_{l\,\mathrm{mod}\,p}+\xi_{l}=c-\mu
x_{l\,\mathrm{mod}\,p}^{b}+\xi_{l},\,\,l=0,1,\ldots,\,\,\xi_{l}\sim\mathcal{N}(\theta,\Sigma)$

Let’s transform the expression $w(y_{l})$:

$w(y_{l})=f(y_{l},c)/f^{\ast}(y_{l})=zp\,\frac{R(y_{l})}{S(y_{l})},\;\;l=1,2,\ldots.$
$R(y_{l})=\exp\left(-1/2\sigma^{2}\,\|y_{l}-c\|^{2}_{\mathbb{R}^{N}}+\delta\right)=\\\
=\exp\left(-1/2\sigma^{2}\,\|\mu
x^{b}_{l\,\mathrm{mod}\,p}-\xi_{l}\|^{2}_{\mathbb{R}^{N}}+\delta\right)$ (13)
$S(y_{l})=\sum_{j=0}^{z-1}\sum_{x\in\pi_{0}^{j}\mathcal{V}_{0}}\exp\left(-1/2\sigma^{2}\,\|y_{l}-x\|^{2}_{\mathbb{R}^{N}}+\delta\right)=\\\
=\sum_{j=0}^{z-1}\sum_{k=0}^{p-1}\exp\left(-1/2\sigma^{2}\|y_{l}-\pi_{0}^{j}y_{k}^{b}\|^{2}_{\mathbb{R}^{N}}+\delta\right)=\\\
=\sum_{j=0}^{z-1}\sum_{k=0}^{p-1}\exp\left(-1/2\sigma^{2}\|\mu(\pi_{0}^{j}x_{k}^{b}-x^{b}_{l\,\mathrm{mod}\,p})+\xi_{l}\|^{2}_{\mathbb{R}^{N}}+\delta\right),$
(14)

$l=0,1,\ldots$, and $\delta$ — a real number used in the calculation to
normalize the argument of the exponent. In the last expression (14) let’s swap
the summation signs and the sum of the exponents according to $j$ from $0$ to
$z-1$ let’s denote $S_{lk}$. Then $S(y_{l})=\sum_{k=0}^{p-1}S_{lk}$.

For any pair $l,k$, $k=0,\ldots,p-1$, $l\geqslant 0$ let’s select two subsets
of indices $j$ namely, we get:

$\displaystyle J^{1}_{lk}$ $\displaystyle=\\{j:\;0\leqslant
j<z-1,\,\pi_{0}^{j}(\mathrm{supp}\,x_{k}^{b})\cap\mathrm{supp}\,x_{l\,\mathrm{mod}\,p}^{b}\neq\varnothing\\}$
(15) $\displaystyle J^{2}_{lk}$ $\displaystyle=\\{j:\;0\leqslant
j<z-1,\,\pi_{0}^{j}(\mathrm{supp}\,x_{k}^{b})\cap\mathrm{supp}\,x_{l\,\mathrm{mod}\,p}^{b}=\varnothing\\}$
(16)

Let’s break the amount down $S_{lk}$ by two:

$S_{lk}=\sum_{j\in J^{1}_{lk}}\exp(\ldots)+\sum_{j\in
J^{2}_{lk}}\exp(\ldots)=:S^{1}_{lk}+S^{2}_{lk}.$

Calculation of quantities $S^{1}_{lk}$ and $S^{2}_{lk}$ can be simplified.

$S^{1}_{lk}=\exp\left(-1/2\sigma^{2}\,\|\xi_{l}\|^{2}_{\mathbb{R}^{N}}+\delta\right)\times\\\
\sum_{j\in
J^{1}_{lk}}\exp\bigg{[}-\mu^{2}/2\sigma^{2}\,|(\pi_{0}^{j}(\mathrm{supp}\,x_{k}^{b}))\Delta(\mathrm{supp}\,x^{b}_{l\,\mathrm{mod}\,p})|\\\
+\mu/\sigma^{2}\bigg{(}\sum_{i\in\mathrm{supp}\,x^{b}_{l\,\mathrm{mod}\,p}\setminus\pi_{0}^{j}(\mathrm{supp}\,x^{b}_{k})}\\{\xi_{l}\\}_{i}\quad\\\
-\sum_{i\in\pi_{0}^{j}(\mathrm{supp}\,x^{b}_{k})\setminus\mathrm{supp}\,x^{b}_{l\,\mathrm{mod}\,p}}\\{\xi_{l}\\}_{i}\bigg{)}\bigg{]},$
(17)

where $\Delta$ — symmetric difference of sets, and

$S^{2}_{lk}=\exp\Big{(}-1/2\sigma^{2}\,\|\xi_{l}\|_{\mathbb{R}^{N}}-\mu^{2}/2\sigma^{2}\,\big{(}|\mathrm{supp}\,x^{b}_{k}|\\\
+|\mathrm{supp}\,x^{b}_{l\,\mathrm{mod}\,p}|\big{)}+\mu/\sigma^{2}\times\sum_{i\in\mathrm{supp}\,x^{b}_{l\,\mathrm{mod}\,p}}\\{\xi_{l}\\}_{i}+\delta\Big{)}\\\
\times\sum_{j\in
J^{2}_{lk}}\exp\left(-\mu/\sigma^{2}\sum_{i\in\pi_{0}^{j}(\mathrm{supp}\,_{k}^{b})}\\{\xi_{l}\\}_{i}\right)$
(18)

Properties of equations (17), (18) is that the calculations are divided into
index-independent $j$ and the parts that depend on it. In order to simplify
direct calculations, it is enough for us to store two tables of sets:

$\displaystyle T^{1}_{klj}$
$\displaystyle=\pi_{0}^{j}(\mathrm{supp}\,x_{k}^{b})\setminus\mathrm{supp}\,x_{l}^{b}$
(19) $\displaystyle T^{2}_{klj}$
$\displaystyle=\mathrm{supp}\,x^{b}_{l}\setminus\pi_{0}^{j}(\mathrm{supp}\,x_{k}^{b}),$
(20)

$k,l=0,\ldots,p-1,\,j=0,\ldots,z-1$. Families of sets (19), (20) connected by
simple relations: $\pi_{0}^{z-j}T^{1}_{k,l,j}=T^{2}_{l,k,z-j}$,
$k,l=0,\ldots,p-1$, $j=0,\ldots,z-1$. In practice, most sets on the right
sides (19), (20) will not intersect.

##  VI CONCLUSION

This paper introduces an approach to enumerate and assess Trapping sets in
quasi-cyclic codes with a circulant size that is not a prime number. To
streamline the importance sampling step, specifically in estimating the weight
of Trapping sets pseudo-codewords, a tabular quasi-cyclic method is proposed
for the list of Trapping sets.

## References

  * [1] V. Usatyuk, D. Sapozhnikov, S. Egorov Spherical and Hyperbolic Toric Topology-Based Codes On Graph Embedding for Ising MRF Models: Classical and Quantum Topology Machine Learning, 2023, arXiv:2307.15778
  * [2] T. Misiakiewicz, A. Montanari Six Lectures on Linearized Neural Networks 2023 https://arxiv.org/abs/2308.13431v1
  * [3] M. Chavira, A. Darwiche, "Compiling Bayesian networks using variable elimination", 20th Int. Joint Conf. Artif. Intell., pp. 2443-2449, 2007.
  * [4] M. Vuffray, et al., "Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models." NIPS 2016, pp. 2595-2603
  * [5] Lazaro-Gredilla Miguel, D. Antoine, G. Dileep, Perturb-and-max-product: Sampling and learning in discrete energy-based models. NeurIPS 2021
  * [6] N. Polyanskii, V. Usatyuk, I. Vorobyev, Floor Scale Modulo Lifting for QC-LDPC codes. 2017, arXiv:1701.07521
  * [7] S. Myung, K. Yang,"Extension of quasi-cyclic LDPC codes by lifting," Proc. ISIT 2005., pp. 2305-2309.
  * [8] S. Myung, K. Yang, Y. Kim, Lifting methods for quasi-cyclic LDPC codes, IEEE Comm. Lett., 2006, 10(6), pp. 489-491.
  * [9] R. Koetter, W.-C. W. Li, P. O. Vontobel, J. L. Walker. Characterizations of pseudo-codewords of (low-density) parity-check codes, Advances in Mathematics, Vol. 213, Issue 1, 2007, pp. 205-229.
  * [10] A. E. Pusane, R. Smarandache, P. O. Vontobel and D. J. Costello, "On Deriving Good LDPC Convolutional Codes from QC LDPC Block Codes," IEEE Trans. on Information Theory, 2007, pp. 1221-1225
  * [11] A. E. Pusane, R. Smarandache, P. O. Vontobel and D. J. Costello, "Deriving Good LDPC Convolutional Codes from LDPC Block Codes," IEEE Trans. on Information Theory, vol. 57, no. 2, pp. 835-857, 2011
  * [12] R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, D. J. Costello, "LDPC block and convolutional codes based on circulant matrices," IEEE Transactions on Information Theory, vol. 50, no. 12, pp. 2966-2984, 2004
  * [13] D. J. MacKay and M. C. Davey, “Evaluation of Gallager codes for short block length and high rate applications,” Proc. of the IMA Workshop on Codes, System and Graphical Models. Springer-Verlag 2001, pp. 113–130
  * [14] R. Smarandache, P. O. Vontobel, “Quasi-cyclic LDPC codes: Influence of proto- and Tanner-graph structure on minimum Hamming distance upper bounds,” IEEE Trans. Inf. Theory, vol. 58(2) , pp. 585–607, 2012
  * [15] B. K. Butler, P. H. Siegel, "Bounds on the Minimum Distance of Punctured Quasi-Cyclic LDPC Codes," IEEE Transactions on Information Theory, vol. 59, no. 7, pp. 4584-4597, 2013
  * [16] R. Smarandache, "Pseudocodewords from Bethe permanents,"IEEE Intern. Symposium on Information Theory, 2013, pp. 2059-2063
  * [17] P. O. Vontobel, "Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function," in IEEE Transactions on Information Theory, vol. 59, no. 9, pp. 6018-6048, Sept. 2013
  * [18] A. Dehghan, A. H. Banihashemi, "On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles," in IEEE Transactions on Information Theory, vol. 64, no. 6, pp. 4438-4451,2018
  * [19] A. Price, J. Hall A Survey on Trapping Sets and Stopping Sets //2017, arXiv:1705.05996
  * [20] F. MacWilliams, and N. Sloane. The Theory of Error-Correcting Codes // North-holland Publishing Company, 1977, 778 p.
  * [21] C. A. Cole, S. G. Wilson, E. K. Hall, T. R. Giallorenzi A General Method for Finding Low Error Rates of LDPC Codes. 2006, arXiv:cs/0605051.
  * [22] T. Richardson Error floors of LDPC codes In Allerton, Oct. 2003