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:2105.03462 · IEEE International Symposium on Information Theory (ISIT)

Necessary and Sufficient Girth Conditions for Tanner Graphs of Quasi-Cyclic LDPC Codes

Roxana Smarandache, David G. M. Mitchell

Published Jul 12, 2021• 4 citations
arXivHTMLPDF

Abstract

This paper revisits the connection between the girth of a protograph-based LDPC code given by a parity-check matrix and the properties of powers of the product between the matrix and its transpose in order to obtain the necessary and sufficient conditions for a code to have given girth between 6 and 12, and to show how these conditions can be incorporated into simple algorithms to construct codes of that girth. To this end, we highlight the role that certain submatrices that appear in these products have in the construction of codes of desired girth. In particular, we show that imposing girth conditions on a parity-check matrix is equivalent to imposing conditions on a square submatrix obtained from it and we show how this equivalence is particularly strong for a protograph based parity-check matrix of variable node degree 2, where the cycles in its Tanner graph correspond one-to-one to the cycles in the Tanner graph of a square submatrix obtained by adding the permutation matrices (or products of these) in the composition of the parity-check matrix. We end the paper with exemplary constructions of codes with various girths and computer simulations. Although, we mostly assume the case of fully connected protographs of variable node degree 2 and 3, the results can be used for any parity-check matrix/protograph-based Tanner graph.

DOI
10.1109/isit45174.2021.9518241

Related papers

Necessary and Sufficient Girth Conditions for LDPC Tanner Graphs with Denser Protographs

Anthony Gómez-Fonseca, Roxana Smarandache, David G. M. Mitchell

This paper gives necessary and sufficient conditions for the Tanner graph of a quasi-cyclic (QC) low-density parity-check (LDPC) code based on the all-one protograph to have girth 6, 8, 10, and 12, respectively, in the case of parity-check matrices with column weight 4. These results are a natural extension of the girth results of the already-studied cases of column weight 2 and 3, and it is based on the connection between the girth of a Tanner graph given by a parity-check matrix and the properties of powers of the product between the matrix and its transpose. The girth conditions can be easily incorporated into fast algorithms that construct codes of desired girth between 6 and 12; our own algorithms are presented for each girth, together with constructions obtained from them and corresponding computer simulations. More importantly, this paper emphasizes how the girth conditions of the Tanner graph corresponding to a parity-check matrix composed of circulants relate to the matrix obtained by adding (over the integers) the circulant columns of the parity-check matrix. In particular, we show that imposing girth conditions on a parity-check matrix is equivalent to imposing conditions on a square circulant submatrix obtained from it.

arXiv:2106.00861•International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•2 citations

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

On the Girth of Quasi-Cyclic Protograph LDPC Codes

M. Karimi, Amir H. Banihashemi

In this paper, we study the relationships between the girth of the Tanner graph of a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code, the lifting degree, and the size and the structure of the base graph. As a result, for a given base graph, we derive a lower bound on the lifting degree as a necessary condition for the lifted graph to have a certain girth. This also provides an upper bound on the girth of the family of graphs lifted from a given base graph with a given lifting degree. The upper bounds derived here, which are applicable to both regular and irregular base graphs with no parallel edges, are in some cases more general and in some other cases tighter than the existing bounds. The results presented in this work can be used to design cyclic liftings with relatively small degree and relatively large girth. As an example, we present new QC protograph LDPC code constructions with girth 8 using fully connected base graphs. These constructions provide upper bounds on the lifting degree required for achieving girth 8 using fully connected base graphs.

IEEE Transactions on Information Theory•Mar 6, 2013•89 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

Necessary conditions for quasi-cyclic LDPC codes to have a given girth

Kyung-Joong Kim, Jin-Ho Chung, Kyeongcheol Yang

Short cycles in the Tanner graph of a low-density parity-check (LDPC) code may cause a severe performance degradation. In this paper, we investigate the cycle properties of quasi-cyclic LDPC (QC-LDPC) codes. We first analyze a necessary and sufficient condition for a cycle of a given length to exist, by using the sequence representation of a parity-check matrix for a QC-LDPC code. We then derive bounds which are necessary conditions for a QC-LDPC code to have a given girth in terms of its parameters. Our necessary conditions are applicable to any regular or irregular QC-LDPC codes as well as they improve the existing bounds for many classes of regular QC-LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•0 citations

Quasi-Cyclic Low-Density Parity-Check Codes From Circulant Permutation Matrices

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 12, and a relatively mild necessary and sufficient condition for the code to have a girth of 6, 8,10, or 12 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.

IEEE Transactions on Information Theory•Jul 27, 2004•1,220 citations
This paper revisits the connection between the girth of a protograph-based LDPC code given by a parity-check matrix and the properties of powers of the product between the matrix and its transpose in order to obtain the necessary and sufficient conditions for a code to have given girth between 6 and 12, and to show how these conditions can be incorporated into simple algorithms to construct codes of that girth. To this end, we highlight the role that certain submatrices that appear in these products have in the construction of codes of desired girth. In particular, we show that imposing girth conditions on a parity-check matrix is equivalent to imposing conditions on a square submatrix obtained from it and we show how this equivalence is particularly strong for a protograph based parity-check matrix of variable node degree 2, where the cycles in its Tanner graph correspond one-to-one to the cycles in the Tanner graph of a square submatrix obtained by adding the permutation matrices (or products of these) in the composition of the parity-check matrix. We end the paper with exemplary constructions of codes with various girths and computer simulations. Although, we mostly assume the case of fully connected protographs of variable node degree 2 and 3, the results can be used for any parity-check matrix/protograph-based Tanner graph.
This paper gives necessary and sufficient conditions for the Tanner graph of a quasi-cyclic (QC) low-density parity-check (LDPC) code based on the all-one protograph to have girth 6, 8, 10, and 12, respectively, in the case of parity-check matrices with column weight 4. These results are a natural extension of the girth results of the already-studied cases of column weight 2 and 3, and it is based on the connection between the girth of a Tanner graph given by a parity-check matrix and the properties of powers of the product between the matrix and its transpose. The girth conditions can be easily incorporated into fast algorithms that construct codes of desired girth between 6 and 12; our own algorithms are presented for each girth, together with constructions obtained from them and corresponding computer simulations. More importantly, this paper emphasizes how the girth conditions of the Tanner graph corresponding to a parity-check matrix composed of circulants relate to the matrix obtained by adding (over the integers) the circulant columns of the parity-check matrix. In particular, we show that imposing girth conditions on a parity-check matrix is equivalent to imposing conditions on a square circulant submatrix obtained from it.
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.
In this paper, we study the relationships between the girth of the Tanner graph of a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code, the lifting degree, and the size and the structure of the base graph. As a result, for a given base graph, we derive a lower bound on the lifting degree as a necessary condition for the lifted graph to have a certain girth. This also provides an upper bound on the girth of the family of graphs lifted from a given base graph with a given lifting degree. The upper bounds derived here, which are applicable to both regular and irregular base graphs with no parallel edges, are in some cases more general and in some other cases tighter than the existing bounds. The results presented in this work can be used to design cyclic liftings with relatively small degree and relatively large girth. As an example, we present new QC protograph LDPC code constructions with girth 8 using fully connected base graphs. These constructions provide upper bounds on the lifting degree required for achieving girth 8 using fully connected base graphs.
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.
Short cycles in the Tanner graph of a low-density parity-check (LDPC) code may cause a severe performance degradation. In this paper, we investigate the cycle properties of quasi-cyclic LDPC (QC-LDPC) codes. We first analyze a necessary and sufficient condition for a cycle of a given length to exist, by using the sequence representation of a parity-check matrix for a QC-LDPC code. We then derive bounds which are necessary conditions for a QC-LDPC code to have a given girth in terms of its parameters. Our necessary conditions are applicable to any regular or irregular QC-LDPC codes as well as they improve the existing bounds for many classes of regular QC-LDPC codes.
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 12, and a relatively mild necessary and sufficient condition for the code to have a girth of 6, 8,10, or 12 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.