Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Advances in Mathematics of Communications

LDPC LCD codes from odd graphs

Dean Crnković, Nina Mostarac, Andrea Švob

Published Jun 18, 2025• 1 citation
Publisher

Abstract

In this paper, we study binary low-density parity-check, or LDPC codes, determined by the adjacency matrices of the odd graphs as their parity-check matrices. We show that for the odd graph $ O_n $, $ n\geq 3 $, the obtained code $ C_n $ is an $ (n, n) $-regular binary LDPC code of length $ {2n-1 \choose n-1} $, dimension $ {2n-2 \choose n-2} $ and minimum distance $ n+1 $. Further, we show that the girth of the corresponding Tanner graph determined by the adjacency matrix of an odd graph is equal to 6, and give the expression for the variance of the syndrome weight for $ C_n $. Moreover, we show that there are no absorbing sets of size smaller than 3 for these codes and that the absorbing sets of size 3 exist only for $ n = 3 $. Additionally, we give the structure of $ (a, b) $ absorbing sets with $ b \leq a\leq n $. Finally we prove that $ C_n $ is also a linear code with complementary dual, or LCD code, for $ n\geq3 $.

DOI
10.3934/amc.2025029

Related papers

Generalization of Tanner′s Minimum Distance Bounds for LDPC Codes

Shin Min Ho, Kim Joon Sung, Song Hong-Yeop

LDPC(Low Density Parity Check) codes are described by bipartite graphs with bit nodes and parity-check nodes. Tanner derived minimum distance bounds of the regular LDPC code in terms of the eigenvalues of the associated adjacency matrix. In this paper we generalize the Tanner's results. We derive minimum distance bounds applicable to both regular and blockwise-irregular LDPC codes. The first bound considers the relation between bit nodes in a minimum-weight codeword, and the second one considers the connectivity between parity nodes adjacent to a minimum-weight codeword. The derived bounds make it possible to describe the distance property of the code in terms of the eigenvalues of the associated matrix.

한국통신학회논문지•Jan 1, 2004•0 citations

Edge coloring of graphs with applications in coding theory

Ghaffar Raeisi, Mohammad Gholami

In this paper, a new type of edge coloring of graphs together with an algorithm for such an edge coloring is presented to construct some column-weight three low-density parity-check (LDPC) codes whose Tanner graphs are free of 4-cycles. This kind of edge coloring is applied on some well-known classes of graphs such as complete graphs and complete bipartite graphs to generate some column-weight 3 LDPC codes having flexibility in terms of code length and rate. Interestingly, the constructed (3, k)-regular codes with regularities k = 4, 5,..., 22 have lengths n = 12, 20, 26, 35, 48, 57, 70, 88, 104, 117, 140, 155, 176, 204, 228, 247, 280, 301, 330, having minimum block length compared to the best known similar codes in the literature. In addition to linear complexity of generating such parity-check matrices, they can be considered as the base matrices of some quasi-cyclic (QC) LDPC codes with maximum achievable girth 18, which inherit the low-complexity encoder implementations of QC-LDPC codes. Simulation results show that the QC-LDPC codes with large girth lifted from the constructed base matrices have good performances and outperform random codes, progressive edge growth LDPC codes, some finite fields and group rings based QC-LDPC codes and also have a close competition to the standard IEEE 802. 16e (WiMAX) code.

China Communications•Jan 1, 2021•7 citations

Extremal absorbing sets in low-density parity-check codes

Emily McMillon, Allison Beemer, Christine A. Kelley

Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of $ b $ for a given $ a $ for which an $ (a,b) $-absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.

Advances in Mathematics of Communications•Apr 7, 2021•3 citations

Polygon Semi Regular Low Density Parity Check Codes

khalil shah

I proposed a new algorithm for the allocation of g- values to the binary vectors. An infinite family of simple graphs in generated by placing copies of polygons in parallel such that degree of each vertex is three. We call them polygon graphs. Since polygon graphs are bipartite therefore they can be used as Tanner graphs to generate low density parity check codes. An incidence structure defined on these polygon graphs in named as polygon semi design. Rows of incidence matrix are reduced by deleting rows from the bottom one by one. These matrices serve as parity check matrices to define low density parity check codes for various dimensions. Size of the stopping sets in the associated Tanner graphs of LDPC codes determine the performance of codes over binary erasure channel. The generated polygon semi regular LDPC codes are simulated and their performance is presented by BER. plots. There exists polygon semi regular LDPC codes e.g. (25,4,17), (49,6,19) etc. The LDPC codes of girth 6 presented by Vera Pless has parameters (25,4,10), (49,6,14). This shows a significant improvement in terms of minimum distance.

•Jun 10, 2010•0 citations

Thresholds of Absorbing Sets in Low-Density Parity-Check Codes

Alessandro Tomasoni, S. Bellini, Marco Ferrari

The error floor phenomenon in many low-density parity-check (LDPC) codes is caused by combinatorial objects in their Tanner graph, known as absorbing sets. In this paper, we highlight a threshold behavior for the min-sum decoding algorithm in the graph of an absorbing set with fixed-point representation of messages. For an absorbing set of interest in a binary LDPC code we can compute the threshold, a novel real-valued parameter that is closely related to its harmfulness. We show that absorbing sets with negative thresholds cannot trap the decoder if the dynamic range of the extrinsic messages is large enough. We also prove that, in regular LDPC codes, absorbing sets with negative thresholds exist if the variable node degree is odd. The examples presented in this paper show that odd-column-weight LDPC codes can have many absorbing sets with negative thresholds, but that these absorbing sets do not trap a well-designed decoder. Simulations show a good agreement between the results of the analysis presented in this paper and the performance of practical decoders with fixed-point messages.

arXiv:1401.8168•IEEE Transactions on Communications•Jan 1, 2017•22 citations

Quasi-Cyclic Low Density Parity Check Codes

M.P.C. Fossorier

In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than , and a relatively mild necessary and sufficient condition for the code to have a girth of or is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.

•Jan 1, 2003•0 citations
In this paper, we study binary low-density parity-check, or LDPC codes, determined by the adjacency matrices of the odd graphs as their parity-check matrices. We show that for the odd graph OnO_nOn​, n≥3n\geq 3n≥3, the obtained code CnC_nCn​ is an (n,n)(n, n)(n,n)-regular binary LDPC code of length (2n−1n−1){2n-1 \choose n-1}(n−12n−1​), dimension (2n−2n−2){2n-2 \choose n-2}(n−22n−2​) and minimum distance n+1n+1n+1. Further, we show that the girth of the corresponding Tanner graph determined by the adjacency matrix of an odd graph is equal to 6, and give the expression for the variance of the syndrome weight for CnC_nCn​. Moreover, we show that there are no absorbing sets of size smaller than 3 for these codes and that the absorbing sets of size 3 exist only for n=3n = 3n=3. Additionally, we give the structure of (a,b)(a, b)(a,b) absorbing sets with b≤a≤nb \leq a\leq nb≤a≤n. Finally we prove that CnC_nCn​ is also a linear code with complementary dual, or LCD code, for n≥3n\geq3n≥3.
LDPC(Low Density Parity Check) codes are described by bipartite graphs with bit nodes and parity-check nodes. Tanner derived minimum distance bounds of the regular LDPC code in terms of the eigenvalues of the associated adjacency matrix. In this paper we generalize the Tanner's results. We derive minimum distance bounds applicable to both regular and blockwise-irregular LDPC codes. The first bound considers the relation between bit nodes in a minimum-weight codeword, and the second one considers the connectivity between parity nodes adjacent to a minimum-weight codeword. The derived bounds make it possible to describe the distance property of the code in terms of the eigenvalues of the associated matrix.
In this paper, a new type of edge coloring of graphs together with an algorithm for such an edge coloring is presented to construct some column-weight three low-density parity-check (LDPC) codes whose Tanner graphs are free of 4-cycles. This kind of edge coloring is applied on some well-known classes of graphs such as complete graphs and complete bipartite graphs to generate some column-weight 3 LDPC codes having flexibility in terms of code length and rate. Interestingly, the constructed (3, k)-regular codes with regularities k = 4, 5,..., 22 have lengths n = 12, 20, 26, 35, 48, 57, 70, 88, 104, 117, 140, 155, 176, 204, 228, 247, 280, 301, 330, having minimum block length compared to the best known similar codes in the literature. In addition to linear complexity of generating such parity-check matrices, they can be considered as the base matrices of some quasi-cyclic (QC) LDPC codes with maximum achievable girth 18, which inherit the low-complexity encoder implementations of QC-LDPC codes. Simulation results show that the QC-LDPC codes with large girth lifted from the constructed base matrices have good performances and outperform random codes, progressive edge growth LDPC codes, some finite fields and group rings based QC-LDPC codes and also have a close competition to the standard IEEE 802. 16e (WiMAX) code.
Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of $ b $ for a given $ a $ for which an $ (a,b) $-absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.
I proposed a new algorithm for the allocation of g- values to the binary vectors. An infinite family of simple graphs in generated by placing copies of polygons in parallel such that degree of each vertex is three. We call them polygon graphs. Since polygon graphs are bipartite therefore they can be used as Tanner graphs to generate low density parity check codes. An incidence structure defined on these polygon graphs in named as polygon semi design. Rows of incidence matrix are reduced by deleting rows from the bottom one by one. These matrices serve as parity check matrices to define low density parity check codes for various dimensions. Size of the stopping sets in the associated Tanner graphs of LDPC codes determine the performance of codes over binary erasure channel. The generated polygon semi regular LDPC codes are simulated and their performance is presented by BER. plots. There exists polygon semi regular LDPC codes e.g. (25,4,17), (49,6,19) etc. The LDPC codes of girth 6 presented by Vera Pless has parameters (25,4,10), (49,6,14). This shows a significant improvement in terms of minimum distance.
The error floor phenomenon in many low-density parity-check (LDPC) codes is caused by combinatorial objects in their Tanner graph, known as absorbing sets. In this paper, we highlight a threshold behavior for the min-sum decoding algorithm in the graph of an absorbing set with fixed-point representation of messages. For an absorbing set of interest in a binary LDPC code we can compute the threshold, a novel real-valued parameter that is closely related to its harmfulness. We show that absorbing sets with negative thresholds cannot trap the decoder if the dynamic range of the extrinsic messages is large enough. We also prove that, in regular LDPC codes, absorbing sets with negative thresholds exist if the variable node degree is odd. The examples presented in this paper show that odd-column-weight LDPC codes can have many absorbing sets with negative thresholds, but that these absorbing sets do not trap a well-designed decoder. Simulations show a good agreement between the results of the analysis presented in this paper and the performance of practical decoders with fixed-point messages.
In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than , and a relatively mild necessary and sufficient condition for the code to have a girth of or is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.