ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P2.03 / 217–229
https://doi.org/10.26493/1855-3974.2501.4c4
(Also available at http://amc-journal.eu)
LDPC codes from cubic semisymmetric graphs*
Dean Crnković , Sanja Rukavina , Marina Šimac †
Department of Mathematics, University of Rijeka,
Radmile Matejčić 2, 51000 Rijeka, Croatia
Received 10 December 2020, accepted 16 July 2021, published online 14 April 2022
Abstract
In this paper we study LDPC codes having cubic semisymmetric graphs as their Tanner
graphs. We discuss the structure of the smallest absorbing sets of these LDPC codes.
Further, we give the expression for the variance of the syndrome weight of the constructed
codes, and present computational and simulation results.
Keywords: LDPC code, cubic graph, semisymmetric graph.
Math. Subj. Class. (2020): 94B05, 05C99
1 Introduction and preliminaries
Throughout this paper we assume graphs to be finite, simple and connected. For the con-
cepts and notation related to the graph theory and coding theory, we refer the reader to [10]
and [15], respectively.
In this paper we use cubic semisymmetric graphs for the construction of LDPC codes.
A graph is called a 3-regular graph, i.e. a cubic graph, if every vertex of the graph has
the degree equal to three. A graph is edge-transitive (vertex-transitive) if its automorphism
group acts transitively on the set of edges (set of vertices). A regular graph is semisymmet-
ric if it is edge-transitive, but not vertex-transitive. It has been proved that every semisym-
metric graph is necessarily bipartite with two parts of equal size (see [14]).
Semisymmetric graphs were first studied by Folkman in 1967 (see [12]). He proposed
a construction of semisymmetric graphs and constructed the smallest semisymmetric graph
with 20 vertices and 40 edges (the Folkman graph). Furthermore, it has been proved that
there are no semisymmetric graphs with 2p or 2p2 vertices for a prime number p.
*This work has been fully supported by Croatian Science Foundation under the project 6732.
†Corresponding author.
E-mail addresses: deanc@math.uniri.hr (Dean Crnković), sanjar@math.uniri.hr (Sanja Rukavina),
msimac@math.uniri.hr (Marina Šimac)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
218 Ars Math. Contemp. 22 (2022) #P2.03 / 217–229
A cubic semisymmetric graph is a 3-regular graph which is semisymmetric. A con-
struction of cubic semisymmetric graphs and the (non)existence of graphs with a certain
number of vertices have been a subject of many studies. For example, in [20], the exis-
tence of the unique cubic semisymmetric graph with 2p3 vertices for a prime number p,
the Gray graph of order 54, was proved. In [11], the condition for the existence of cubic
semisymmetric graphs with 6p3 vertices was given, and a construction of such graphs was
described. The classification of cubic semisymmetric graphs with at most 768 vertices was
given in [4]. All of the listed graphs have girth at least eight.
The dual code C⊥ of an [n, k] linear code C is an [n, n− k] code defined by
C⊥ =
{
x ∈ Fnp | x · y = 0, ∀y ∈ C
}
,
where · is the standard inner product. A generator matrix of the code C⊥ is called a parity-
check matrix of C.
A binary low-density parity-check (LDPC) code is a binary linear code defined by a
sparse parity-check matrix H . That is to say, H contains a very small number of nonzero
entries. An LDPC code is (wc, wr)-regular if the weight of each column is equal to wc,
and the weight of each row is equal to wr.
LDPC codes can be presented using Tanner graphs, which were introduced by Tanner
in [26]. The Tanner graph of an LDPC code is a bipartite graph that consists of two sets
of vertices; bit nodes that correspond to codeword bits and check nodes that correspond to
parity-check equations. An edge connects a bit node to a check node if that bit is included
in the corresponding parity-check equation. If an LDPC code is (wc, wr)-regular, the cor-
responding Tanner graph is a biregular bipartite graph in which vertices are of degree wc
or wr.
The decoding performance of an LDPC code depends on the structure of the corre-
sponding Tanner graph; the existence of short cycles in the Tanner graph of a code es-
tablishes a correlation between iterations in the process of decoding, and therefore, has a
negative impact on the bit error rate (BER) performance of the code. The shorter the cy-
cles are, the more significant the effect is. Furthermore, the iterative decoding performance
of an LDPC code is related with the existence of certain undesirable substructures of the
corresponding Tanner graph. For an AWGN channel, substructures that are called trapping
sets, determine error floor performance of an LDPC code. It has been proved that absorbing
sets, as a special type of trapping sets, have an important role in the error floor (see [25]).
Various combinatorial structures, including graphs, were used for a construction of
LDPC codes without cycles of length four (see, e.g., [6, 16, 17, 23]). In [7], the authors in-
vestigated a family of LDPC codes constructed by taking bipartite cubic symmetric graphs
as the Tanner graphs. In this paper, we construct LDPC codes from cubic semisymmetric
graphs and study the smallest absorbing sets in the corresponding Tanner graphs.
The paper is organized as follows. In Section 2, the construction of the family of LDPC
codes using cubic semisymmetric graphs is presented, some properties of the obtained
codes are analyzed and the results regarding the code parameters are given. Furthermore,
the expression for the variance of the syndrome weight of the constructed LDPC codes is
presented. In Section 3, the structure of the smallest absorbing sets is studied. Sections 4
and 5 contain computational and simulation results.
D. Crnković et al.: LDPC codes from cubic semisymmetric graphs 219
2 LDPC codes constructed from cubic semisymmetric graphs
Let G be a connected cubic semisymmetric graph with 2n vertices, and denote by A its
adjacency matrix. Since every semisymmetric graph is bipartite with two parts of equal
size, its adjacency matrix can be written as follows
A =
[
0 H
HT 0
]
, (2.1)
where H is an n× n matrix.
Taking the matrix H as a parity-check matrix, one can construct a (3, 3)-regular LDPC
code CH(G) of length n. The dimension of that code is equal to n − rank2(H), where
rank2(H) =
1
2 rank2(A). Furthermore, the density of the parity-check matrix H is equal
to 3n . For the constructed code CH(G), the cubic semisymmetric graph G is its Tanner
graph.
From the fact that semisymmetric graphs are edge-transitive, but not vertex-transitive, it
follows that HT determines another LDPC code CHT (G). The code CHT (G) is a
(3, 3)-regular LDPC code of length n, and its dimension is equal to n − rank2(H) as
well.
Let H and HT be n × n parity-check matrices of the codes CH(G) and CHT (G), re-
spectively. For the code CH(G), the bit node graph Γb is defined in the following way:
vertices of the graph correspond to codeword bits, and two vertices are adjacent if and only
if the corresponding bits are included in the same parity-check equation. In other words,
two vertices of the graph Γb are adjacent if and only if the corresponding bit nodes of the
Tanner graph of the code CH(G) have a common neighbour. Similarly, the vertices of the
check node graph Γc correspond to parity-check equations of the code, and two vertices
are adjacent if and only if the corresponding parity-check equations have a bit in common.
That is to say, two vertices of the graph Γc are adjacent if and only if the corresponding
check nodes of the Tanner graph of the code CH(G) have a common neighbour. Note that
the check node graph Γc of the code CH(G) is the bit node graph of the code CHT (G).
Theorem 2.1. Let G be a connected cubic semisymmetric graph with girth at least six and
let H be the parity-check matrix of the code CH(G). Then the corresponding bit node graph
Γb and check node graph Γc are 6-regular.
Proof. Let v be a bit node of the Tanner graph G. The degree of the node v is equal to
three, and each of its neighbours is adjacent to another two bit nodes. Using the fact that G
does not have cycles of length four, it follows that v has a common neighbour with exactly
six other bit nodes. In other words, the degree of a vertex of the graph Γb is equal to six,
i.e., the graph Γb is 6-regular. In the same way it can be concluded that the graph Γc is also
6-regular.
Theorem 2.2. Let G be a connected cubic semisymmetric graph with 2n vertices and girth
at least six. Further, let H be the parity-check matrix of the code CH(G) and let Γb and Γc
be the corresponding bit node graph and check node graph, respectively. Matrices Tb and
Tc are square (0, 1)-matrices of order n satisfying Tb = HTH − 3I and Tc = HHT − 3I
if and only if Tb and Tc are the adjacency matrices of the graphs Γb and Γc, respectively.
220 Ars Math. Contemp. 22 (2022) #P2.03 / 217–229
Proof. Let us consider the n × n matrix HTH = [hi,j ]. The degree of a bit node of the
Tanner graph G of the code CH(G) is equal to three, hence hi,i = 3, i ∈ {1, . . . , n}. An
element hi,j , i ̸= j, of the matrix H is equal to one or zero depending on whether the
corresponding nodes of the graph Γb are adjacent or not. Accordingly, Tb = HTH − 3I ,
where Tb is the adjacency matrix of the graph Γb.
Conversely, let Tb = [ti,j ] be an n × n (0, 1)-matrix with the property that
Tb = H
TH − 3I . HTH is a symmetric matrix and, consequently, Tb is also a sym-
metric matrix such that ti,i = 0, i ∈ {1, . . . , n}. The girth of the Tanner graph G is greater
than four, so hi,j , i ̸= j, is equal to zero or one, and represents the number of common
neighbours of the corresponding bit nodes of the Tanner graph G of the code CH(G). It
follows that Tb is the adjacency matrix of the graph Γb.
An analog statement for the matrix Tc can be formed similarly by observing check
nodes of the Tanner graph of the code CH(G).
A clique of a graph G is a complete subgraph of the graph G. The clique number of the
graph G, denoted by ω(G), is the number of vertices in a clique of the largest size in G, i.e.
the order of a complete subgraph of G of maximum possible size for G. In the sequel, the
clique number of the bit node graph Γb and the check node graph Γc will be examined.
Lemma 2.3. Let G be a connected cubic semisymmetric graph. Further, let CH(G) be
the corresponding LDPC code and let Γb and Γc be its bit node and check node graph,
respectively. The clique numbers of the graphs Γb and Γc are at least three.
Proof. Each check node of the Tanner graph G is a common neighbour of every pair of
its three adjacent bit nodes. Thus, each check node determines the complete graph K3
as a subgraph of the bit node graph Γb. Similarly, each bit node of the Tanner graph
determines the complete graph K3 as a subgraph of the check node graph Γc. Hence,
ω(Γb), ω(Γc) ≥ 3.
Lemma 2.4. Let G be a connected cubic semisymmetric graph with girth greater than six.
Further, let CH(G) be the corresponding LDPC code and let Γb and Γc be its bit node and
check node graph, respectively. Then the complete graph K4 is not a subgraph of Γb or
Γc.
Proof. Suppose that K4 is a subgraph of the graph Γb. Let the bit nodes u1, u2, u3, u4 be
the vertices of K4. We have the following two possibilities:
(a) One of the check nodes (say v1) in the corresponding subgraph of the Tanner graph G
has degree three. Let u1, u2 and u3 be the bit nodes adjacent with v1. Furthermore,
let the check node v2 be a common neighbour of u1 and u4. Since u2 and u4 are
adjacent in Γb, they have a common neighbour v3 in G. Then u1v1u2v3u4v2u1 is a
cycle of length six, which is impossible since the girth of the graph G is greater than
six.
(b) The check nodes in the corresponding subgraph of the Tanner graph G have degrees
at most two. Let the check node vi be a common neighbour of the bit nodes u1 and
ui+1, i = 1, 2, 3. Since u2 and u4 are adjacent in Γb, they have a common neighbour
v4 in G. Then u1v1u2v4u4v3u1 is a cycle of length six, which contradicts the fact
that the girth of the graph G is greater than six.
D. Crnković et al.: LDPC codes from cubic semisymmetric graphs 221
Analog arguments yield that K4 is not a subgraph of Γc.
The following theorem is a direct consequence of Lemmas 2.3 and 2.4.
Theorem 2.5. Let G be a connected cubic semisymmetric graph with girth greater than
six. Further, let CH(G) be the corresponding LDPC code and let Γb and Γc be its bit node
and check node graph, respectively. Then ω(Γb) = ω(Γc) = 3.
In the sequel, we discuss the minimum distance of the codes CH(G) and CHT (G). The
following results from [24] will be used.
Theorem 2.6 ([24, Theorem 3.1]). Let C be a binary linear code with a parity-check matrix
H . Then there exists a codeword in C with weight w if and only if there are w columns in
H whose vector sum is a zero vector.
Theorem 2.7 ([24, Theorem 3.2]). Let C be a binary linear code with a parity-check matrix
H . Then the minimum distance of the code C is equal to the smallest number of columns in
H whose vector sum is a zero vector.
The column weight of parity check matrices H and HT of codes CH(G) and CHT (G) is
equal to three, and according to Theorem 2.6, the codes are even. Therefore, the minimum
distance of the codes is an even number.
Theorem 2.8. Let G be a connected cubic semisymmetric graph with girth greater than six.
Let d(CH(G)) and d(CTH(G)) be the minimum distances of the codes CH(G) and CHT (G),
respectively. Then d(CH(G)) ≥ 6 and d(CTH(G)) ≥ 6.
Proof. The column weight of the parity-check matrix H of the code CH(G) is equal to
three, and since the graph G does not have cycles of length four, it follows that the minimum
distance of the code is at least four (see [13]). Assume that the minimum distance of the
code is equal to four. As a consequence of Theorem 2.7, four columns of the parity-check
matrix whose sum equals zero exist. Therefore, a set S in the graph G, which consists of
four bit nodes such that each pair of the vertices has a different common neighbour in G,
exists. Moreover, the set S determines the complete graph K4 as a subgraph of the bit node
graph Γb. Using Theorem 2.5, we conclude that the minimum distance of the code is at
least six.
Observing check nodes of the Tanner graph of the code CH(G), and the check node
graph Γc, one can prove the statement for the minumum distance of the code CHT (G).
In [7, Theorem 1], the minimum distance of an LDPC code constructed from a bipartite
cubic symmetric graph is expressed using the second largest eigenvalue of the adjacency
matrix of that graph. In a similar way, using the result given in Theorem 2.8, one can prove
the following theorem.
Theorem 2.9. Let G be a connected cubic semisymmetric graph with 2n vertices and girth
greater than six. Let λ2 be the second largest eigenvalue of its adjacency matrix A. Let
d(CH(G)) and d(CTH(G)) be the minimum distances of the codes CH(G) and CHT (G), re-
spectively. Then the following inequalities hold
d ≥

2
5n, λ2 ≤ 2,
2
9n, 2 < λ2 ≤
√
6,
6,
√
6 < λ2 < 3,
222 Ars Math. Contemp. 22 (2022) #P2.03 / 217–229
where d ∈ {d(CH(G)), d(CTH(G))}.
Remark 2.10. The results given above refer to the LDPC codes constructed from con-
nected cubic semisymmetric graphs with girth greater than six. According to the classifi-
cation of cubic semisymmetric graphs with at most 768 vertices (see [4]), all such graphs
have girth at least eight. Consequently, all of the associated LDPC codes have properties
stated above.
Theorem 2.11. Let G be a connected cubic semisymmetric graph with 2n vertices. Then
the dimension of the codes CH(G) and CHT (G) is at most n− 2α(Γb) + 1, where α(Γb) is
the independence number of the bit node graph Γb.
Proof. The 2-rank of the parity-check matrix of a binary code determines its dimension.
The 2-rank of the matrix H is equal to the 2-rank of the matrix HT and, therefore, it is
sufficent to observe the matrix H and the corresponding code CH(G). A maximal indepen-
dent set of Γb determines α(Γb) linearly independent columns of the parity check matrix
H . These columns have the property that no two columns have an entry equal to one at
the same position. Due to the fact that Γb is a 6-regular graph, there are 6α(Γb) ones at
different positions within the columns. Therefore, adding any other α(Γb)− 1 columns of
the matrix, a set of 2α(Γb)− 1 linearly independent columns of the parity check matrix is
defined. Hence, 2-rank of the matrix H is at least 2α(Γb)− 1.
As a consequence, the dimension of the code is at most n − 2α(Γb) + 1, where n
is the length of the code, i.e. the number of vertices of the graph Γb, and α(Γb) is the
independence number of the graph Γ.
2.1 The variance of syndrome weight
To predict a decoding efficiency one can use a channel state information (CSI) (e.g. the
crossover probability, a signal-to-noise ratio), which has an important role for communi-
cation systems. The estimation (performed prior to decoding) of the crossover probability
based on the probability of syndrome weight was proposed in [18] and [27].
The expression for the variance of the syndrome weight of the LDPC codes constructed
from bipartite cubic symmetric graphs is given in [7]. In a similar way, one can obtain the
expression for the variance of the syndrome weight of the LDPC codes constructed from
cubic semisymmetric graphs which is given by
V ar(w) =
n
2
(7f6(ρ)− 6f4(ρ)) ,
where the function ft is defined by ft(ρ) =
1−(1−2ρ)t
2 (see [22]).
3 Absorbing sets
Let G = G(C) be the Tanner graph of an LDPC code C which is determined by an m× n
parity check matrix H . A (κ, τ) trapping set is a set T , that consists of κ bit nodes, having
the property that the induced subgraph G[T ] has exactly τ check nodes of odd degree. The
most harmful trapping sets are those with small sizes and small ratios τκ . If the Tanner
graph of an LDPC code does not have trapping sets with size smaller than the minimum
distance of the code, then the error floor of the code is dominated by the minimum distance
(see [9]). Let T be a trapping set. If every bit node in G[T ] is connected with fewer check
nodes of odd degree than check nodes of even degree, then T is called an absorbing set.
D. Crnković et al.: LDPC codes from cubic semisymmetric graphs 223
Let A be a (κ, τ)− trapping set in the Tanner graph of an (3, wr) LDPC code. Using
simple counting it can be seen that τ is an even number if κ is even, and an odd number if
κ is odd.
The results in the sequel refer to the LDPC codes for which the corresponding Tanner
graphs have girth at least six. We examine the existence of the smallest absorbing sets in
the Tanner graphs of the LDPC codes constructed from the cubic semisymmetric graphs.
Theorem 3.1. Let the Tanner graph of the LDPC code CH(G) be a connected cubic
semisymmetric graph G with girth at least six. Then there is no absorbing set of size
smaller than three in the graph G.
Proof. The proof follows directly from the definition of an absorbing set and the fact that
the Tanner graph of the code has no cycles of length four.
Theorem 3.2. Let G be a connected cubic semisymmetric graph with girth greater than
six, which is the Tanner graph of the LDPC codes CH(G) and CHT (G). The Tanner graph
G has no absorbing set of size three.
Proof. Let A be a (3, 3)-absorbing set, which is the only possible structure of an absorbing
set of size three in the Tanner graph of the codes (see Figure 1). The proof follows directly
from the fact that the absorbing set defines a cycle of length six in the Tanner graph.
Figure 1: The only possible structure of an absorbing set of size three in the Tanner graph
of the LDPC codes CH(G). and CHT (G).
Theorem 3.3. Let G be a connected cubic semisymmetric graph with girth greater than
six, which is the Tanner graph of the LDPC codes CH(G) and CHT (G). The only possible
structure for an absorbing set of size four is (4, 4)-absorbing set.
Proof. Since the size of an absorbing set is an even number, and according to the previous
observations, the possible structures for absorbing sets of size four in the Tanner graph of
the codes are (4, 0), (4, 2) and (4, 4) absorbing sets (see Figure 2(a), (b) and (c), respec-
tively). The proof follows directly from the fact that (4, 0) and (4, 2) absorbing sets define
the complete graph K4 as a subgraph of the graph Γb.
224 Ars Math. Contemp. 22 (2022) #P2.03 / 217–229
(a)
(b)
(c)
Figure 2: The possible structures of an absorbing set of size four in the Tanner graph of the
LDPC codes CH(G) and CHT (G).
4 Computational results
Within this section the parameters of the LDPC codes obtained from cubic semisymmetric
graphs are presented. For the construction of the cubic semisymmetric graphs we have
employed the method presented in [1]. The parameters of the constructed codes can be
seen in Table 1. The parameter v denotes the number of vertices of the corresponding
cubic semisymmetric graph.
v LDPC1 LDPC2
54 [27, 8, 6] [27, 8, 8]∗
112 [56, 12, 14] [56,12,16]
120 [60, 14, 8] [60,14,12]
144 [72, 16, 12]∗ [72, 16, 14]∗
216 [108, 16, 24] [108, 16, 32]
240 [120, 22, 16] [120, 22, 24]
294 [147, 26, 14] [147, 26, 26]
336 [168, 24, 14] [168, 24, 42]
378 [189, 11, 42] [189, 11, 56]
384 [192, 35, 16] [192, 35, 18]
400 [200,24,32] [200,24,60]
432 [216, 24, 48] [216, 24, 60]
v LDPC1 LDPC2
448 [224, 33, 32] [224,33,32]
486 [243, 2, 162]∗ [243, 2, 162]∗
546 [273, 5, 130] [273, 5, 130]
576 [288, 32, 48] [288, 32, 56]
672 [336, 47, 14] [336, 47, 42]
702 [351, 8, 78] [351, 8, 104]∗
720 [360,10,120] [360,10,120]
784 [392, 12, 98] [392,12,112]
798 [399, 5, 190] [399, 5, 190]
864 [432, 32, 96] [432, 32, 108]
882 [441, 44, 42] [441, 44, 78]
896 [448, 48, 84] [448,48,100]
Table 1: The parameters of LDPC codes constructed from cubic semisymmetric graphs
with less than 1000 vertices (using the method presented in [1]).
D. Crnković et al.: LDPC codes from cubic semisymmetric graphs 225
The Tanner graphs of the constructed codes have girth at least eight. The codes CH(G)
and CHT (G) are isomorphic in the case when the number of vertices of the cubic semisym-
metric graph G is 486, 546, 720 or 798.
Remark 4.1. Lately, much interest has been devoted to LCD codes, which have an impor-
tant application in cryptography, in protection against side-channel and fault attacks (see
[2]). Self-orthogonal codes can be used to construct quantum error-correcting codes, which
can protect quantum information in quantum computations and quantum communications
(see [3]).
The LDPC codes marked in bold are self-orthogonal codes, and those labeled with ∗ in
Table 1 are LCD codes.
Remark 4.2. Codes CH(G) and CHT (G) constructed from a cubic semisymmetric graph
(CSSG) have the same length and dimension, and, in general, different minimum distance.
Thus, the construction gives diversity in code parameters for the same graph, which is
not the case for LDPC codes which are constructed in [7] using cubic symmetric graphs
(CSGs).
According to the classification of CSSGs with at most 768 vertices (see [4]), all the
graphs have girth at least eight, while according to [5] many CSGs have girth equal to six.
Moreover, semisymmetric graphs form a wider family than symmetric graphs.
Furthermore, we have compared the parameters of the LDPC codes constructed from
CSSGs to the parameters of the LDPC codes constructed from CSGs. The results are shown
in Table 2. It can be concluded that, for the same code length, the LDPC codes from CSSGs
achieve higher code rate than those constructed using CSGs. When n = 27, the code rate
is four times greater.
n Rate (CSSG) Rate (CSG)
27 0.296 0.074
56 0.214 {0.107, 0.143}
60 0.233 {0.067, 0.083}
72 0.222 {0.083, 0.111}
Table 2: Rates od LDPC codes constructed from cubic symmetric and semisymmetric
graphs with the same length.
5 Simulation results
In this section, we present simulation results of the LDPC codes derived from the cubic
semisymmetric graphs, over the additive white gaussian noise (AWGN) channel. We have
compared the codes with randomly generated LDPC codes of the same length and dimen-
sion and a parity-check matrix with a column weight equal to three. For randomly gener-
ated codes we have used the software for LDPC codes available on [21], which employs the
construction from [8, 19]. The codes are decoded with the sum-product decoding algorithm
and the maximum number of iteration is set to 50. Figures 3 - 6 show the performance of
the codes.
226 Ars Math. Contemp. 22 (2022) #P2.03 / 217–229
Remark 5.1. The LDPC codes that we are aware of were not adequate for the comparison
with the LDPC codes obtained in this paper because of the different parameters of the
codes. Thus, we have used the best known random construction for LDPC codes. It has
been proved in [8] that the construction leads to LDPC codes with performance close to the
Shannon limit. Moreover, the best results were obtained in the case of the smallest possible
column weight.
Figure 3: BER performance of the [56, 12, 16] LDPC code derived from the Ljubljana
graph.
Figure 4: BER performance of the [147, 26, 26] LDPC code derived from the cubic
semisymmetric graph with 294 vertices.
D. Crnković et al.: LDPC codes from cubic semisymmetric graphs 227
Figure 5: BER performance of the [288, 32, 56] LDPC code derived from the cubic
semisymmetric graph with 576 vertices.
Figure 6: BER performance of the [448, 48, 100] LDPC code derived from the cubic
semisymmetric graph with 896 vertices.
The obtained simulation results indicate better BER performance of the codes con-
structed from the cubic semisymmetric graphs than randomly generated LDPC codes.
ORCID iDs
Dean Crnković https://orcid.org/0000-0002-3299-7859
Sanja Rukavina https://orcid.org/0000-0003-3365-7925
Marina Šimac https://orcid.org/0000-0001-9291-3365
228 Ars Math. Contemp. 22 (2022) #P2.03 / 217–229
References
[1] A. Bretto and L. Gillibert, G-graphs: An efficient tool for constructing symmetric and semisym-
metric graphs, Discrete Appl. Math. 156 (2008), 2719–2739, doi:10.1016/j.dam.2007.11.011.
[2] J. Bringer, C. Carlet, H. Chabanne, S. Guilley and H. Maghrebi, Orthogonal direct sum mask-
ing, in: Information Security Theory and Practice. Securing the Internet of Things. WISTP
2014. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, volume 8501, 2014
pp. 40–56, doi:10.1007/978-3-662-43826-8_4.
[3] A. R. Calderbank, E. M. Rains, P. W. Shor and N. J. A. Sloane, Quantum error correction and
orthogonal geometry, Phys. Rev. Lett. 78 (1997), 405–408, doi:10.1103/physrevlett.78.405.
[4] M. Conder, A. Malnič, D. Marušič and P. Potočnik, A census of semisymmetric cubic graphs
on up to 768 vertices, J. Algebr. Comb. 23 (2006), 255–294, doi:10.1007/s10801-006-7397-3.
[5] M. Conder and R. Nedela, A refined classification of symmetric cubic graphs, J. Algebra 322
(2009), 722–740, doi:10.1016/j.jalgebra.2009.03.011.
[6] D. Crnković, S. Rukavina and M. Šimac, LDPC codes from µ-geodetic graphs obtained from
block designs, Graphs Comb. 35 (2019), 451–469, doi:10.1007/s00373-019-02007-4.
[7] D. Crnković, S. Rukavina and M. Šimac, LDPC codes constructed from cubic symmetric
graphs, Appl. Algebra Eng. Commun. Comput. (2020), doi:10.1007/s00200-020-00468-2.
[8] R. M. N. D. J. C. MacKay, Near Shannon limit performance of low density parity check codes,
Electron. Lett. 32 (1996), 1645–1646, doi:10.1049/el:19961141.
[9] Q. Diao, Y. Y. Tai, S. Lin and K. Abdel-Ghaffar, Trapping set structure of finite geometry ldpc
codes, in: 2012 IEEE International Symposium on Information Theory Proceedings, 2012 pp.
3088–3092, doi:10.1109/isit.2012.6284130.
[10] R. Diestel, Graph Theory, Springer-Verlag, Berlin Heidelberg, 2017, doi:10.1007/
978-3-662-53622-3.
[11] Y.-Q. Feng, M. Ghasemi and C. Wang, Cubic semisymmetric graphs of order 6p3, Discrete
Math. 310 (2010), 2345–2355, doi:10.1016/j.disc.2010.05.018.
[12] J. Folkman, Regular line-symmetric graphs, J. Comb. Theory 3 (1967), 215–232, doi:10.1016/
S0021-9800(67)80069-3.
[13] M. Greferath, C. Rößing and L. Storme, Galois geometries and low-density parity-check codes,
in: Current Research Topics in Galois Geometry, Nova Science Publishers/Novinka, New York,
pp. 245–270, 2014.
[14] F. Harary, Graph Theory, Addison-Wesley Publishing Company, 1969, doi:10.1201/
9780429493768.
[15] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University
Press, Cambridge, 2003, doi:10.1017/cbo9780511807077.
[16] F. Ivanov and V. Zyablov, LDPC codes based on steiner quadruple systems and permutation
matrices, in: Fourteenth International Workshop on Algebraic and Combinatorial Coding The-
ory, Nova Science Publishers/Novinka, New York, pp. 175–180, 2014, http://www.moi.
math.bas.bg/acct2014/acct2014end.html.
[17] J.-L. Kim, U. N. Peled, I. Perepelitsa, V. Pless and S. Friedland, Explicit construction of fam-
ilies of LDPC codes with no 4-cycles., IEEE Trans. Inf. Theory 50 (2004), 2378–2388, doi:
10.1109/tit.2004.834760.
[18] G. Lechner and C. Pacher, Estimating channel parameters from the syndrome of a linear code,
IEEE Commun. Lett. 17 (2013), 2148–2151, doi:10.1109/lcomm.2013.091113.131646.
D. Crnković et al.: LDPC codes from cubic semisymmetric graphs 229
[19] D. J. C. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inf.
Theory 45 (1999), 399–431, doi:10.1109/18.748992.
[20] A. Malnič, D. Marušič and C. Wang, Cubic edge-transitive graphs of order 2p3, Discrete Math-
ematics 274 (2004), 187–198, doi:10.1016/S0012-365X(03)00088-8.
[21] R. M. Neal, Software for Low Density Parity Check (LDPC) codes, University of Toronto,
2012, {https://www.cs.toronto.edu/~radford/ldpc.software.html}.
[22] C. Pacher, P. Grabenweger and D. E. Simos, Weight distribution of the syndrome of linear
codes and connections to combinatorial designs, in: 2016 IEEE International Symposium on
Information Theory (ISIT), IEEE Press, 2016 pp. 3038–3042, doi:10.1109/isit.2016.7541857.
[23] J. Rosenthal and P. O. Vontobel, Constructions of LDPC codes using Ramanujan graphs
and ideas from Margulis, in: 38th Allerton Conference on Communication, Control
and Computing, 2000 pp. 248–257, https://www.math.uzh.ch/aa/index.php?
publication-show&key1=Coding%20Theory&key2=Joachim%20Rosenthal.
[24] W. E. Ryan and S. Lin, Channel codes. Classical and modern, Cambridge University Press,
2009, doi:10.1017/cbo9780511803253.
[25] C. Schlegel and S. Zhang, On the dynamics of the error floor behavior in (regular) LDPC codes,
IEEE Trans. Inf. Theory 56 (2010), 3248–3264, doi:10.1109/tit.2010.2048448.
[26] R. M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory 27
(1981), 533–547, doi:10.1109/tit.1981.1056404.
[27] V. Toto-Zarasoa, A. Roumy and C. Guillemot, Maximum likelihood BSC parameter estimation
for the Slepian-Wolf problem, IEEE Commun. Lett. 15 (2011), 232–234, doi:10.1109/lcomm.
2011.122810.102182.