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

Problems of Information Transmission

LDPC Codes from Deza Graphs

Dean Crnković, Sanja Rukavina, Marina Šimac

Published Dec 1, 2025• 1 citation
Publisher

Abstract

We give a construction of LDPC codes from Deza graphs with parameters $(v,k,1,0)$ . The Tanner graphs of these LDPC codes do not contain cycles of length 4. Special attention is given to the construction of LDPC codes from the Moore graphs with diameter 2. We identify and enumerate the smallest absorbing sets in the Tanner graphs of the obtained LDPC codes and analyze their structures. Furthermore, we describe a construction, based on the protograph operation, of an infinite family of LDPC codes, whose Tanner graphs have girth at least 6, obtained from each $(v,k,1,0)$ Deza graph. We give an expression for the variance of a syndrome weight of the constructed LDPC codes, and also present simulation results.

DOI
10.1134/s0032946025030019

Related papers

LDPC codes from cubic semisymmetric graphs

Dean Crnković, Sanja Rukavina, Marina Šimac

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 an expression for the variance of the syndrome weight of the constructed codes, and present computational and simulation results.

Ars Mathematica Contemporanea•Jul 21, 2021•3 citations

LDPC kodovi konstruirani iz nekih kombinatoričkih struktura

Marina Šimac

The main subjects of the thesis are LDPC codes constructed from combinatorial structures. Combinatorial structures that have been used for the construction are: \(\mu\)-geodetic graphs obtained from block designs, strongly regular graphs with parameters \((v, k, 0, 1)\), and block designs with parameters \((45, 5, 1)\). In the thesis we have constructed a family of LDPC codes using \(\mu\)-geodetic graphs obtained from block \((v, k, \lambda)\) designs. We have shown that the Tanner graphs of LDPC codes constructed from \(\mu\)-geodetic graphs obtained from block designs with \(k=3\) are free of cycles of length four, and we have analyzed properties of the constructed codes. We have examined a connection between the parameters of the constructed codes and the parameters of the initial design. The existence and the structures of absorbing sets in the Tanner graphs of the constructed codes have been analyzed. Analysis of structures of the absorbing sets enabled us to determine the exact number of the absorbing sets of certain size using parameters of the initial design. For construction of LDPC codes we have used strongly regular graphs with parameters \((v, k, 0, 1)\) since the Tanner graph of the corresponding LDPC code is free of cycles of length four. We have examined the existence and the structures of absorbing sets in the Tanner graphs of the constructed codes. LDPC codes from some block designs with parameters \((45, 5, 1)\) have been constructed. Simulation results for the constructed LDPC codes have been presented.

•Mar 23, 2017•0 citations

LDPC LCD codes from odd graphs

Dean Crnković, Nina Mostarac, Andrea Švob

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 $.

Advances in Mathematics of Communications•Jun 18, 2025•1 citation

LDPC Codes on Balanced Incomplete Block Designs: Construction, Girth, and Cycle Structure Analysis

Hengzhou Xu, Xiaodong Zhang, Mengmeng Xu +2 more

In this paper, we investigate the cycle structure inherent in the Tanner graphs of low-density parity-check (LDPC) codes constructed from balanced incomplete block designs (BIBDs). We begin by delineating the incidence structure of BIBDs and propose a methodology for constructing LDPC codes based on these designs. By analyzing the incidence relations between points and blocks within a BIBD, we prove that the resulting LDPC codes possess a girth of 6. Subsequently, we provide a detailed analysis of the cycle structure of the constructed LDPC codes and introduce a systematic approach for enumerating their short cycles. Using this method, we determine the exact numbers of cycles of lengths 6 and 8. Simulation results demonstrate that the constructed LDPC codes exhibit excellent performance.

Entropy•Apr 27, 2025•0 citations

The Design of Structured Low-Density Parity-Check Codes With Large Girth

Jing Long

This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.

Chinese Journal of Computers•Jan 1, 2007•1 citation

Recursive construction of LDPC codes

Shunliang Mei

To reduce the cycles in the Tanner graph which may affect the code performance,a recursive method to construct low-density parity-check(LDPC) codes was proposed.The method used a parity-check matrix of a short LDPC code as its mother matrix upon which a long code was constructed with circulant permutation matrices.By choosing the circulant permutation matrix parameters properly,the number of cycles having a given length in the Tanner graph of the constructed long codes were equal to or less than that of the short code.Either regular or irregular LDPC codes were constructed.Simulation results show that the LDPC codes constructed by this method have very low error-floor and almost no performance degradation due to their special structure as compared with random LDPC codes.

Journal of Tsinghua University(Science and Technology)•Jan 1, 2007•0 citations
We give a construction of LDPC codes from Deza graphs with parameters (v,k,1,0)(v,k,1,0)(v,k,1,0) . The Tanner graphs of these LDPC codes do not contain cycles of length 4. Special attention is given to the construction of LDPC codes from the Moore graphs with diameter 2. We identify and enumerate the smallest absorbing sets in the Tanner graphs of the obtained LDPC codes and analyze their structures. Furthermore, we describe a construction, based on the protograph operation, of an infinite family of LDPC codes, whose Tanner graphs have girth at least 6, obtained from each (v,k,1,0)(v,k,1,0)(v,k,1,0) Deza graph. We give an expression for the variance of a syndrome weight of the constructed LDPC codes, and also present simulation results.
The main subjects of the thesis are LDPC codes constructed from combinatorial structures. Combinatorial structures that have been used for the construction are: μ\muμ-geodetic graphs obtained from block designs, strongly regular graphs with parameters (v,k,0,1)(v, k, 0, 1)(v,k,0,1), and block designs with parameters (45,5,1)(45, 5, 1)(45,5,1). In the thesis we have constructed a family of LDPC codes using μ\muμ-geodetic graphs obtained from block (v,k,λ)(v, k, \lambda)(v,k,λ) designs. We have shown that the Tanner graphs of LDPC codes constructed from μ\muμ-geodetic graphs obtained from block designs with k=3k=3k=3 are free of cycles of length four, and we have analyzed properties of the constructed codes. We have examined a connection between the parameters of the constructed codes and the parameters of the initial design. The existence and the structures of absorbing sets in the Tanner graphs of the constructed codes have been analyzed. Analysis of structures of the absorbing sets enabled us to determine the exact number of the absorbing sets of certain size using parameters of the initial design. For construction of LDPC codes we have used strongly regular graphs with parameters (v,k,0,1)(v, k, 0, 1)(v,k,0,1) since the Tanner graph of the corresponding LDPC code is free of cycles of length four. We have examined the existence and the structures of absorbing sets in the Tanner graphs of the constructed codes. LDPC codes from some block designs with parameters (45,5,1)(45, 5, 1)(45,5,1) have been constructed. Simulation results for the constructed LDPC codes have been presented.
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 $.
In this paper, we investigate the cycle structure inherent in the Tanner graphs of low-density parity-check (LDPC) codes constructed from balanced incomplete block designs (BIBDs). We begin by delineating the incidence structure of BIBDs and propose a methodology for constructing LDPC codes based on these designs. By analyzing the incidence relations between points and blocks within a BIBD, we prove that the resulting LDPC codes possess a girth of 6. Subsequently, we provide a detailed analysis of the cycle structure of the constructed LDPC codes and introduce a systematic approach for enumerating their short cycles. Using this method, we determine the exact numbers of cycles of lengths 6 and 8. Simulation results demonstrate that the constructed LDPC codes exhibit excellent performance.
This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.
To reduce the cycles in the Tanner graph which may affect the code performance,a recursive method to construct low-density parity-check(LDPC) codes was proposed.The method used a parity-check matrix of a short LDPC code as its mother matrix upon which a long code was constructed with circulant permutation matrices.By choosing the circulant permutation matrix parameters properly,the number of cycles having a given length in the Tanner graph of the constructed long codes were equal to or less than that of the short code.Either regular or irregular LDPC codes were constructed.Simulation results show that the LDPC codes constructed by this method have very low error-floor and almost no performance degradation due to their special structure as compared with random LDPC codes.