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

International Conference on Communications

Partially Quasi-Cyclic Protograph-Based LDPC Codes

Roxana Smarandache, David G. M. Mitchell, Danniel J. Costello

Published Jun 1, 2011• 10 citations
Publisher

Abstract

A significant amount of the analysis of protograph-based low-density parity-check (LDPC) codes has been devoted to the subclass of quasi-cyclic (QC) LDPC codes. Despite their implementation advantages and algebraic properties that make them easy to analyze, protograph-based QC-LDPC codes have undesirable fixed upper limits on important code parameters. This implies that picking a QC code from an asymptotically good or capacity approaching ensemble is suboptimal, since long QC codes will not perform close to the ensemble asymptotic limits. Indeed, these limits can only be achieved by codes that are not QC. In this paper we present an overview together with some new results on partially-QC protograph-based LDPC codes, i.e., LDPC codes whose parity-check matrix is partially composed of circulant submatrices. We perform both a minimum Hamming distance and girth analysis of these codes. Moreover, we present explicit partially-QC LDPC code constructions with parameters that exceed the restricted QC upper bounds.

DOI
10.1109/icc.2011.5963333

Related papers

Quasi-Cyclic LDPC Codes Based on Pre-Lifted Protographs

David G. M. Mitchell, Roxana Smarandache, Daniel J. Costello

Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case, we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared with one-step circulant-based liftings. The expected performance improvement is verified by simulation results.

arXiv:1407.5364•IEEE Transactions on Information Theory•Jul 24, 2014•58 citations

Quasi-cyclic LDPC codes based on pre-lifted protographs

David G. M. Mitchell, Roxana Smarandache, Daniel J. Costello

Quasi-cyclic Low-Density Parity-Check (QC-LDPC) codes based on protographs are of great interest to code designers because of their implementation advantages and algebraic properties that make them easy to analyze. However, the protograph structure imposes undesirable fixed upper limits on important code parameters. In this paper, we show that the upper bound on the minimum Hamming distance of protograph-based QC codes can be improved by the careful application of a two-step lifting procedure applied to the protograph. The promised improvement is validated by constructing codes with minimum distance exceeding the upper bound for QC codes based on a particular protograph.

IEEE Information Theory Workshop (ITW)•Oct 1, 2011•11 citations

Quasi-cyclic asymptotically regular LDPC codes

David G. M. Mitchell, Roxana Smarandache, Michael Lentmaier +1 more

Families of asymptotically regular LDPC block code ensembles can be formed by terminating (J, K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates, minimum distance that grows linearly with block length, and capacity approaching iterative decoding thresholds, despite the fact that the terminated ensembles are almost regular. In this paper, we investigate the properties of the quasi-cyclic (QC) members of such an ensemble. We show that an upper bound on the minimum Hamming distance of members of the QC sub-ensemble can be improved by careful choice of the component protographs used in the code construction. Further, we show that the upper bound on the minimum distance can be improved by using arrays of circulants in a graph cover of the protograph.

arXiv:1007.0404•IEEE Information Theory Workshop (ITW)•Aug 1, 2010•7 citations

Hierarchical and High-Girth QC LDPC Codes

Yige Wang, Stark Christiaan Draper, Jonathan S. Yedidia

We present an approach to designing capacity-approaching high-girth low-density parity-check (LDPC) codes that are friendly to hardware implementation, and compatible with some desired input code structure defined using a protograph. The approach is based on a mapping of any class of codes defined using a protograph into a family of hierarchical quasi-cyclic (HQC) LDPC codes. Whereas the parity check matrices of standard quasi-cyclic (QC) LDPC codes are composed of circulant submatrices, those of HQC LDPC codes are composed of a hierarchy of circulant submatrices that are, in turn, constructed from circulant submatrices, and so on, through some number of levels. Next, we present a girth-maximizing algorithm that optimizes the degrees of freedom within the family of codes to yield a high-girth HQC LDPC code, subject to bounds imposed by the fact that HQC codes are still quasi-cyclic. Finally, we discuss how certain characteristics of a code protograph will lead to inevitable short cycles and show that these short cycles can be eliminated using a “squashing” procedure that results in a high-girth QC LDPC code, although not a hierarchical one. We illustrate our approach with three design examples of QC LDPC codes-two girth-10 codes of rates 1/3 and 0.45 and one girth-8 code of rate 0.7-all of which are obtained from protographs of one-sided spatially coupled codes.

arXiv:1111.0711•IEEE Transactions on Information Theory•Mar 20, 2013•53 citations

Constructing good QC-LDPC codes by pre-lifting protographs

David G. M. Mitchell, Roxana Smarandache, Daniel J. Costello

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are of great interest to code designers because of their implementation advantages and algebraic properties that facilitate their analysis. In this paper, we present some new results on QC-LDPC codes that are constructed using a two-step lifting procedure based on a protograph, and, by implementing this method instead of the usual one-step procedure, we are able to show improved minimum distance and girth properties. We also present two design rules to construct QC-LDPC codes: one uses only circulant permutation matrices at the first (pre-lifting) stage and the other uses a selection of non-commuting permutation matrices. For both techniques, we obtain a demonstrable increase in the minimum distance compared to a one-step circulant-based lifting. The expected performance improvement is verified by simulation results.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•4 citations

Quasi-Cyclic LDPC Codes: Influence of Proto- and Tanner-Graph Structure on Minimum Hamming Distance Upper Bounds

Roxana Smarandache, Pascal O. Vontobel

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close to) the respective minimum Hamming distance upper bounds. Because of the tight algebraic connection between QC codes and convolutional codes, we can state similar results for the free Hamming distance of convolutional codes. In fact, some QC code statements are established by first proving the corresponding convolutional code statements and then using a result by Tanner that says that the minimum Hamming distance of a QC code is upper bounded by the free Hamming distance of the convolutional code that is obtained by “unwrapping” the QC code.

arXiv:0901.4129•IEEE Transactions on Information Theory•Feb 1, 2012•136 citations
A significant amount of the analysis of protograph-based low-density parity-check (LDPC) codes has been devoted to the subclass of quasi-cyclic (QC) LDPC codes. Despite their implementation advantages and algebraic properties that make them easy to analyze, protograph-based QC-LDPC codes have undesirable fixed upper limits on important code parameters. This implies that picking a QC code from an asymptotically good or capacity approaching ensemble is suboptimal, since long QC codes will not perform close to the ensemble asymptotic limits. Indeed, these limits can only be achieved by codes that are not QC. In this paper we present an overview together with some new results on partially-QC protograph-based LDPC codes, i.e., LDPC codes whose parity-check matrix is partially composed of circulant submatrices. We perform both a minimum Hamming distance and girth analysis of these codes. Moreover, we present explicit partially-QC LDPC code constructions with parameters that exceed the restricted QC upper bounds.
Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case, we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared with one-step circulant-based liftings. The expected performance improvement is verified by simulation results.
Quasi-cyclic Low-Density Parity-Check (QC-LDPC) codes based on protographs are of great interest to code designers because of their implementation advantages and algebraic properties that make them easy to analyze. However, the protograph structure imposes undesirable fixed upper limits on important code parameters. In this paper, we show that the upper bound on the minimum Hamming distance of protograph-based QC codes can be improved by the careful application of a two-step lifting procedure applied to the protograph. The promised improvement is validated by constructing codes with minimum distance exceeding the upper bound for QC codes based on a particular protograph.
Families of asymptotically regular LDPC block code ensembles can be formed by terminating (J, K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates, minimum distance that grows linearly with block length, and capacity approaching iterative decoding thresholds, despite the fact that the terminated ensembles are almost regular. In this paper, we investigate the properties of the quasi-cyclic (QC) members of such an ensemble. We show that an upper bound on the minimum Hamming distance of members of the QC sub-ensemble can be improved by careful choice of the component protographs used in the code construction. Further, we show that the upper bound on the minimum distance can be improved by using arrays of circulants in a graph cover of the protograph.
We present an approach to designing capacity-approaching high-girth low-density parity-check (LDPC) codes that are friendly to hardware implementation, and compatible with some desired input code structure defined using a protograph. The approach is based on a mapping of any class of codes defined using a protograph into a family of hierarchical quasi-cyclic (HQC) LDPC codes. Whereas the parity check matrices of standard quasi-cyclic (QC) LDPC codes are composed of circulant submatrices, those of HQC LDPC codes are composed of a hierarchy of circulant submatrices that are, in turn, constructed from circulant submatrices, and so on, through some number of levels. Next, we present a girth-maximizing algorithm that optimizes the degrees of freedom within the family of codes to yield a high-girth HQC LDPC code, subject to bounds imposed by the fact that HQC codes are still quasi-cyclic. Finally, we discuss how certain characteristics of a code protograph will lead to inevitable short cycles and show that these short cycles can be eliminated using a “squashing” procedure that results in a high-girth QC LDPC code, although not a hierarchical one. We illustrate our approach with three design examples of QC LDPC codes-two girth-10 codes of rates 1/3 and 0.45 and one girth-8 code of rate 0.7-all of which are obtained from protographs of one-sided spatially coupled codes.
Quasi-cyclic (QC) low-density parity-check (LDPC) codes are of great interest to code designers because of their implementation advantages and algebraic properties that facilitate their analysis. In this paper, we present some new results on QC-LDPC codes that are constructed using a two-step lifting procedure based on a protograph, and, by implementing this method instead of the usual one-step procedure, we are able to show improved minimum distance and girth properties. We also present two design rules to construct QC-LDPC codes: one uses only circulant permutation matrices at the first (pre-lifting) stage and the other uses a selection of non-commuting permutation matrices. For both techniques, we obtain a demonstrable increase in the minimum distance compared to a one-step circulant-based lifting. The expected performance improvement is verified by simulation results.
Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close to) the respective minimum Hamming distance upper bounds. Because of the tight algebraic connection between QC codes and convolutional codes, we can state similar results for the free Hamming distance of convolutional codes. In fact, some QC code statements are established by first proving the corresponding convolutional code statements and then using a result by Tanner that says that the minimum Hamming distance of a QC code is upper bounded by the free Hamming distance of the convolutional code that is obtained by “unwrapping” the QC code.