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

IEEE Transactions on Information Theory

On the Girth of Quasi-Cyclic Protograph LDPC Codes

M. Karimi, Amir H. Banihashemi

Published Mar 6, 2013• 89 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2013.2251395

Related papers

On the girth of quasi cyclic protograph LDPC codes

Mehdi 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, on one hand, and the lifting degree and the size and the structure of the base graph, on the other hand. As a result, for a given base graph and a given lifting degree, we derive an upper bound on the girth of the resulting lifted graphs (codes). The upper bounds derived here are generally tighter than the existing bounds. The results presented in this work can be used to select an appropriate lifting degree for a given base graph, in order to have a desired girth, or to provide some insight in designing good base graphs, or to properly select the base graph's edge permutations.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•6 citations

Analytical Lower Bound on the Lifting Degree of Multiple-Edge QC-LDPC Codes With Girth 6

Mohammad‐Reza Sadeghi, Farzane Amirzade

Multiple-edge protographs have some advantages over single-edge protographs, such as potentially having larger minimum Hamming distance. However, most of results in the literature are related to the construction of single-edge quasi-cyclic low-density parity-check codes (QC-LDPC) codes and little research has been done for the construction of multiple-edge QC-LDPC codes. In this letter, for the first time, necessary and sufficient conditions for the exponent matrices to have multiple-edge QC-LDPC codes with girth 6 are provided. As a consequence of this letter, a lower bound on the lifting degree of regular and irregular multiple-edge QC-LDPC codes with girth 6 is derived. We also present QC-LDPC codes whose lifting degrees meet our proposed lower bound. These codes have shorter lengths compared with single-edge QC-LDPC codes. Another contribution of this letter is presenting a technique to reduce the size of the search space to find these codes.

IEEE Communications Letters•May 29, 2018•24 citations

Efficient Search of Girth-Optimal QC-LDPC Codes

Alireza Tasdighi, Amir H. Banihashemi, Mohammad‐Reza Sadeghi

In this paper, we study the cycle structure of quasi-cyclic (QC) low-density parity-check (LDPC) codes with the goal of obtaining the shortest code with a given degree distribution and girth. We focus on QC-LDPC codes, whose Tanner graphs are cyclic liftings of fully connected base graphs of size 3 × n, n ≥ 4, and obtain minimal lifting degrees that result in girths 6 and 8. This is performed through an efficient exhaustive search, and as a result, we also find all the possible non-isomorphic codes with the same minimum block length, girth, and degree distribution. The exhaustive search, which is ordinarily a formidable task, is made possible by pruning the search space of many codes that are isomorphic to those previously examined in the search process. Many of the pruning techniques proposed in this paper are also applicable to QC-LDPC codes with base graphs other than the 3 × n fully connected ones discussed here, as well as to codes with a larger girth. To further demonstrate the effectiveness of the pruning techniques, we use them to search for QC-LDPC codes with girths 10 and 12, and find a number of such codes that have a shorter block length compared with the best known similar codes in the literature. In addition, motivated by the exhaustive search results, we tighten the lower bound on the block length of QC-LDPC codes of girth 6 constructed from fully connected 3 × n base graphs, and construct codes that achieve the lower bound for an arbitrary value of n ≥ 4.

IEEE Transactions on Information Theory•Feb 3, 2016•78 citations

On the girth of (3,L) quasi-cyclic LDPC codes based on complete protographs

Sudarsan V. S. Ranganathan, D. Divsalar, Richard D. Wesel

We consider the problem of constructing (3,L) quasi-cyclic low-density parity-check (LDPC) codes from complete protographs. A complete protograph is a small bipartite graph with two disjoint vertex sets such that every vertex in the variable-node set is connected to every vertex in the check-node set by a unique edge. This paper analyzes the required lifting factor for achieving girths of six or eight in the resulting quasi-cyclic codes with constraints on lifting. The required lifting factors provide lower bounds on the block-length of such codes.

arXiv:1504.04975•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•16 citations

Constructing Large Girth QC Protograph LDPC Codes Based on PSD-PEG Algorithm

Xueqin Jiang, Han Hai, Hui-Ming Wang +1 more

For a given base graph, the lifted graph can be obtained by a copy-and-permute procedure. If the permutation is cyclic, the lifted graph corresponds to a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code. The girth of the QC protograph LDPC code is determined by the girth of the base graph and the permutation shifts. In this paper, we first derive a lower bound on the lifting degree to achieve a large girth lifted graph. Then, motivated by the cycle searching and girth maximizing features of the progressive edge-growth (PEG) algorithm, we introduce the permutation shifts determining (PSD) PEG algorithm, which can construct large girth base graph and determine the optimal permutation shifts, simultaneously. It is shown that the computational complexity of PSD-PEG algorithm is much lower than that of the PEG algorithm and the PEG-QC algorithm for the same codeword length. Furthermore, we show that the PSD-PEG algorithm can also be used to construct nonbinary QC protograph LDPC codes without low weight codes. Simulation results show that the binary and nonbinary QC protograph LDPC codes constructed by the PSD-PEG algorithm have good bit error rate performance and frame error rate performance over the additive white Gaussian noise channel.

IEEE Access•Jan 1, 2017•23 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
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 paper, we study the relationships between the girth of the Tanner graph of a quasi cyclic (QC) protograph low-density parity-check (LDPC) code, on one hand, and the lifting degree and the size and the structure of the base graph, on the other hand. As a result, for a given base graph and a given lifting degree, we derive an upper bound on the girth of the resulting lifted graphs (codes). The upper bounds derived here are generally tighter than the existing bounds. The results presented in this work can be used to select an appropriate lifting degree for a given base graph, in order to have a desired girth, or to provide some insight in designing good base graphs, or to properly select the base graph's edge permutations.
Multiple-edge protographs have some advantages over single-edge protographs, such as potentially having larger minimum Hamming distance. However, most of results in the literature are related to the construction of single-edge quasi-cyclic low-density parity-check codes (QC-LDPC) codes and little research has been done for the construction of multiple-edge QC-LDPC codes. In this letter, for the first time, necessary and sufficient conditions for the exponent matrices to have multiple-edge QC-LDPC codes with girth 6 are provided. As a consequence of this letter, a lower bound on the lifting degree of regular and irregular multiple-edge QC-LDPC codes with girth 6 is derived. We also present QC-LDPC codes whose lifting degrees meet our proposed lower bound. These codes have shorter lengths compared with single-edge QC-LDPC codes. Another contribution of this letter is presenting a technique to reduce the size of the search space to find these codes.
In this paper, we study the cycle structure of quasi-cyclic (QC) low-density parity-check (LDPC) codes with the goal of obtaining the shortest code with a given degree distribution and girth. We focus on QC-LDPC codes, whose Tanner graphs are cyclic liftings of fully connected base graphs of size 3 × n, n ≥ 4, and obtain minimal lifting degrees that result in girths 6 and 8. This is performed through an efficient exhaustive search, and as a result, we also find all the possible non-isomorphic codes with the same minimum block length, girth, and degree distribution. The exhaustive search, which is ordinarily a formidable task, is made possible by pruning the search space of many codes that are isomorphic to those previously examined in the search process. Many of the pruning techniques proposed in this paper are also applicable to QC-LDPC codes with base graphs other than the 3 × n fully connected ones discussed here, as well as to codes with a larger girth. To further demonstrate the effectiveness of the pruning techniques, we use them to search for QC-LDPC codes with girths 10 and 12, and find a number of such codes that have a shorter block length compared with the best known similar codes in the literature. In addition, motivated by the exhaustive search results, we tighten the lower bound on the block length of QC-LDPC codes of girth 6 constructed from fully connected 3 × n base graphs, and construct codes that achieve the lower bound for an arbitrary value of n ≥ 4.
We consider the problem of constructing (3,L) quasi-cyclic low-density parity-check (LDPC) codes from complete protographs. A complete protograph is a small bipartite graph with two disjoint vertex sets such that every vertex in the variable-node set is connected to every vertex in the check-node set by a unique edge. This paper analyzes the required lifting factor for achieving girths of six or eight in the resulting quasi-cyclic codes with constraints on lifting. The required lifting factors provide lower bounds on the block-length of such codes.
For a given base graph, the lifted graph can be obtained by a copy-and-permute procedure. If the permutation is cyclic, the lifted graph corresponds to a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code. The girth of the QC protograph LDPC code is determined by the girth of the base graph and the permutation shifts. In this paper, we first derive a lower bound on the lifting degree to achieve a large girth lifted graph. Then, motivated by the cycle searching and girth maximizing features of the progressive edge-growth (PEG) algorithm, we introduce the permutation shifts determining (PSD) PEG algorithm, which can construct large girth base graph and determine the optimal permutation shifts, simultaneously. It is shown that the computational complexity of PSD-PEG algorithm is much lower than that of the PEG algorithm and the PEG-QC algorithm for the same codeword length. Furthermore, we show that the PSD-PEG algorithm can also be used to construct nonbinary QC protograph LDPC codes without low weight codes. Simulation results show that the binary and nonbinary QC protograph LDPC codes constructed by the PSD-PEG algorithm have good bit error rate performance and frame error rate performance over the additive white Gaussian noise channel.
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.