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

arXiv:2507.00591

Construction of LDPC convolutional codes with large girth from Latin squares

Elisa Junghans, Julia Lieb

Published Jul 1, 2025• 0 citations
arXivHTMLPDF

Abstract

Due to their capacity approaching performance low-density parity-check (LDPC) codes gained a lot of attention in the last years. The parity-check matrix of the codes can be associated with a bipartite graph, called Tanner graph. To decrease the probability of decoding failure it is desirable to have LDPC codes with large girth of the associated Tanner graph. Moreover, to store such codes efficiently, it is desirable to have compact constructions for them. In this paper, we present constructions of LDPC convolutional codes with girth up to $12$ using a special class of Latin squares and several lifting steps, which enables a compact representation of these codes. With these techniques, we can provide constructions for well-performing and efficiently storable time-varying and time-invariant LDPC convolutional codes as well as for LDPC block codes.

DOI
10.48550/arxiv.2507.00591

Related papers

A Unifying Framework to Construct QC-LDPC Tanner Graphs of Desired Girth

Roxana Smarandache, David G. M. Mitchell

This paper presents a unifying framework to construct low-density parity-check (LDPC) codes with associated Tanner graphs of desired girth. Towards this goal, we highlight the role that a certain square matrix that appears in the product of the parity-check matrix with its transpose has in the construction of codes with graphs of desired girth and further explore it in order to generate the set of necessary and sufficient conditions for a Tanner graph to have a given girth between 6 and 12. For each such girth, we present algorithms to construct codes of the desired girth and we show how to use them to compute the minimum necessary value of the lifting factor. For girth larger than 12, we show how to use multi-step graph lifting methods to deterministically modify codes in order to increase their girth. We also give a new perspective on LDPC protograph-based parity-check matrices by viewing them as rows of a parity-check matrix equal to the sum of certain permutation matrices and obtain an important connection between all protographs and those with variable nodes of degree 2. We also show that the results and methodology that we develop for the all-one protograph can be used and adapted to analyze the girth of the Tanner graph of any parity-check matrix and demonstrate how this can be done using a well-known irregular, multi-edge protograph specified by the NASA Consultative Committee for Space Data Systems (CCSDS). Throughout the paper, we exemplify our theoretical results with constructions of LDPC codes with Tanner graphs of any girth between 6 and 14 and give sufficient conditions for a multi-step lifted parity-check matrix to have girth between 14 and 22.

arXiv:2108.01637•IEEE Transactions on Information Theory•Apr 25, 2022•17 citations

Node-splitting constructions for large girth irregular and protograph LDPC codes

Srinivas Subramanian, Asit Kumar Pradhan, Andrew Thangaraj

Low Density Parity Check (LDPC) codes have capacity-approaching performance over several channels of interest. In practice, for good block-error rate performance, the girth of the Tanner graph of an LDPC code needs to be as high as possible. In theory, to show that block-error rate approaches zero for increasing block-lengths, the girth of the Tanner graph sequence needs to tend to infinity with block-length. To meet these requirements, we construct sequences of large-girth irregular LDPC codes for a given degree-distribution pair (DDP) by applying a general node splitting algorithm on large girth graphs. The obtained Tanner graph meets the required DDP up to a suitable approximation. By optimizing the node-splitting method and using suitable large-girth graphs, we show code constructions with smaller block length for the same girth, when compared to previous constructions. Similar gains in block length are observed in the construction of sequences of large-girth protograph LDPC codes. Simulations, over a binary erasure channel, confirm the gains in block-error rate obtained by the large girth construction.

National Conference on Communications•Feb 1, 2014•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

A Class of Low-Density Parity-Check Convolutional Codes Based on Difference Families

Yucheng He, Christian Cardinal, David Haccoun

An algebraic construction for a class of low-density parity-check (LDPC) convolutional codes is presented on the basis of difference families associated with the code generator matrix. It can be shown that these codes have girth of at least 10 on the Tanner graph which is independent of either the size of the code generator matrix or the minimum Hamming distance of the codes. The code construction guarantees the independence of the messages exchanged in the belief propagation decoding process during two successive decoding iterations. Computer simulations show that over the additive white Gaussian noise channel, the best error performance of these codes at moderate signal-to- noise ratio values is practically obtained using only three to five iterations.

International Conference on Communications•Jan 1, 2008•2 citations

Searching for Voltage Graph-Based LDPC Tailbiting Codes With Large Girth

Irina E. Bocharova, Florian Hug, Rolf Johannesson +2 more

The relation between parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Using the principle of tailbiting, compact representations of bipartite graphs based on convolutional codes can be found. Bounds on the girth and the minimum distance of LDPC block codes constructed in such a way are discussed. Algorithms for searching iteratively for LDPC block codes with large girth and for determining their minimum distance are presented. Constructions based on all-one matrices, Steiner Triple Systems, and QC block codes are introduced. Finally, new QC regular LDPC block codes with girth up to 24 are given.

arXiv:1108.0840•IEEE Transactions on Information Theory•Nov 18, 2011•80 citations

ANALYSIS OF METHODS OF CONSTRUCTION AND ENCODING LOW-DENSITY PARITY CHECK CODES

Alexey Stanyslavovych Volkov, Stanislav Sergeevich Zhuchenko

The article analyzes the famous methods of construction and representations of the check matrix block and convolutional codes with low-density parity-check. The analysis the famous methods of coding block and convolutional codes with low-density parity-check. Showed advantages and disadvantages of the known methods and allowed to identify and formulate a scientific and technical challenge. Shows the method of representation of the check matrix block codes with low-density parity-check using the Tanner graph, which like the check matrix is fully defines the parameters of the code. Check matrix of convolutional codes with low-density parity-check can also be described by Tanner graph, however, because the check matrix is infinite, then the Tanner graph is infinite. The analysis method of constructing the parity check matrix of block codes with low-density parity-check, which is based on a shortened Reed-Solomon code. Codes constructed in this method have a Tanner graph girth at least 6, which allows them to effectively use iterative decoding methods.

Collected scientific works of Ukrainian State University of Railway Transport•Dec 22, 2014•0 citations
Due to their capacity approaching performance low-density parity-check (LDPC) codes gained a lot of attention in the last years. The parity-check matrix of the codes can be associated with a bipartite graph, called Tanner graph. To decrease the probability of decoding failure it is desirable to have LDPC codes with large girth of the associated Tanner graph. Moreover, to store such codes efficiently, it is desirable to have compact constructions for them. In this paper, we present constructions of LDPC convolutional codes with girth up to 121212 using a special class of Latin squares and several lifting steps, which enables a compact representation of these codes. With these techniques, we can provide constructions for well-performing and efficiently storable time-varying and time-invariant LDPC convolutional codes as well as for LDPC block codes.
This paper presents a unifying framework to construct low-density parity-check (LDPC) codes with associated Tanner graphs of desired girth. Towards this goal, we highlight the role that a certain square matrix that appears in the product of the parity-check matrix with its transpose has in the construction of codes with graphs of desired girth and further explore it in order to generate the set of necessary and sufficient conditions for a Tanner graph to have a given girth between 6 and 12. For each such girth, we present algorithms to construct codes of the desired girth and we show how to use them to compute the minimum necessary value of the lifting factor. For girth larger than 12, we show how to use multi-step graph lifting methods to deterministically modify codes in order to increase their girth. We also give a new perspective on LDPC protograph-based parity-check matrices by viewing them as rows of a parity-check matrix equal to the sum of certain permutation matrices and obtain an important connection between all protographs and those with variable nodes of degree 2. We also show that the results and methodology that we develop for the all-one protograph can be used and adapted to analyze the girth of the Tanner graph of any parity-check matrix and demonstrate how this can be done using a well-known irregular, multi-edge protograph specified by the NASA Consultative Committee for Space Data Systems (CCSDS). Throughout the paper, we exemplify our theoretical results with constructions of LDPC codes with Tanner graphs of any girth between 6 and 14 and give sufficient conditions for a multi-step lifted parity-check matrix to have girth between 14 and 22.
Low Density Parity Check (LDPC) codes have capacity-approaching performance over several channels of interest. In practice, for good block-error rate performance, the girth of the Tanner graph of an LDPC code needs to be as high as possible. In theory, to show that block-error rate approaches zero for increasing block-lengths, the girth of the Tanner graph sequence needs to tend to infinity with block-length. To meet these requirements, we construct sequences of large-girth irregular LDPC codes for a given degree-distribution pair (DDP) by applying a general node splitting algorithm on large girth graphs. The obtained Tanner graph meets the required DDP up to a suitable approximation. By optimizing the node-splitting method and using suitable large-girth graphs, we show code constructions with smaller block length for the same girth, when compared to previous constructions. Similar gains in block length are observed in the construction of sequences of large-girth protograph LDPC codes. Simulations, over a binary erasure channel, confirm the gains in block-error rate obtained by the large girth construction.
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.
An algebraic construction for a class of low-density parity-check (LDPC) convolutional codes is presented on the basis of difference families associated with the code generator matrix. It can be shown that these codes have girth of at least 10 on the Tanner graph which is independent of either the size of the code generator matrix or the minimum Hamming distance of the codes. The code construction guarantees the independence of the messages exchanged in the belief propagation decoding process during two successive decoding iterations. Computer simulations show that over the additive white Gaussian noise channel, the best error performance of these codes at moderate signal-to- noise ratio values is practically obtained using only three to five iterations.
The relation between parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Using the principle of tailbiting, compact representations of bipartite graphs based on convolutional codes can be found. Bounds on the girth and the minimum distance of LDPC block codes constructed in such a way are discussed. Algorithms for searching iteratively for LDPC block codes with large girth and for determining their minimum distance are presented. Constructions based on all-one matrices, Steiner Triple Systems, and QC block codes are introduced. Finally, new QC regular LDPC block codes with girth up to 24 are given.
The article analyzes the famous methods of construction and representations of the check matrix block and convolutional codes with low-density parity-check. The analysis the famous methods of coding block and convolutional codes with low-density parity-check. Showed advantages and disadvantages of the known methods and allowed to identify and formulate a scientific and technical challenge. Shows the method of representation of the check matrix block codes with low-density parity-check using the Tanner graph, which like the check matrix is fully defines the parameters of the code. Check matrix of convolutional codes with low-density parity-check can also be described by Tanner graph, however, because the check matrix is infinite, then the Tanner graph is infinite. The analysis method of constructing the parity check matrix of block codes with low-density parity-check, which is based on a shortened Reed-Solomon code. Codes constructed in this method have a Tanner graph girth at least 6, which allows them to effectively use iterative decoding methods.