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

Cyclic and Quasi-Cyclic LDPC Codes on Constrained Parity-Check Matrices and Their Trapping Sets

Qin Huang, Qiuju Diao, Shu Lin, Khaled Abdel-Ghaffar

Published Jan 31, 2012• 108 citations
Publisher

Abstract

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.

DOI
10.1109/tit.2011.2179842

Related papers

Cyclic and Quasi-Cyclic LDPC Codes on Row and Column Constrained Parity-Check Matrices and Their Trapping Sets

Qin Huang, Qiuju Diao, Shu Lin +1 more

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly LDPC codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterizations of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite geometry LDPC codes using the results developed in first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping sets of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite geometry and finite field cyclic and quasi-cyclic LDPC codes with large minimum weights are shown to have no harmful trapping sets with size smaller than their minimum weights. Consequently, their performance error-floors are dominated by their minimum weights.

arXiv:1012.3201•Dec 15, 2010•12 citations

Circulant decomposition: Cyclic, quasi-cyclic and LDPC codes

Qin Huang, Qiuju Diao, Shu Lin

This paper shows that a cyclic code can be put into quasi-cyclic form by decomposing a circular parity-check matrix through column and row permutations. Such a decomposition of a circular parity-check matrix of a cyclic code produces a group of shorter cyclic or quasi-cyclic codes and leads to a new method for constructing long cyclic codes from short cyclic codes. Also in this paper, new classes of cyclic and quasi-cyclic LDPC codes are derived from cyclic Euclidean geometry LDPC codes by decomposing their circular parity-check matrices. These new LDPC codes perform well and enlarge the repertoire of cyclic and quasi-cyclic LDPC codes.

International Symposium on Information Theory and its Applications•Oct 1, 2010•5 citations

Cyclic and quasi-cyclic LDPC codes: New developments

Qin Huang, Qiuju Diao, Shu Lin +1 more

This paper presents a technique to decompose a cyclic code given by a parity-check matrix in circulant form into descendant cyclic and quasi-cyclic codes of various length and rates. Based on this technique, cyclic finite geometry (FG) LDPC codes are decomposed into a large class of cyclic FG-LDPC codes and a large class of quasi-cyclic FG-LDPC codes.

Information Theory and Applications Workshop (ITA)•Feb 1, 2011•11 citations

Structural Analysis of Nonbinary Cyclic and Quasi-Cyclic LDPC Codes with α-Multiplied Parity-Check Matrices

Haiyang Liu, Hao Zhang, Lianrong Ma +1 more

In this letter, the structural analysis of nonbinary cyclic and quasi-cyclic (QC) low-density parity-check (LDPC) codes with α-multiplied parity-check matrices (PCMs) is concerned. Using analytical methods, several structural parameters of nonbinary cyclic and QC LDPC codes with α-multiplied PCMs are determined. In particular, some classes of nonbinary LDPC codes constructed from finite fields and finite geometries are shown to have good minimum and stopping distances properties, which may explain to some extent their wonderful decoding performances.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•May 11, 2020•0 citations

A transform approach for analyzing and constructing quasi-cyclic low-density parity-check codes

Qiuju Diao, Qin Huang, Shu Hwa Lin +1 more

An approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is presented. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is used to characterize certain structural properties of low-density parity-check (LDPC) codes such as the girths of their Tanner graphs. Many constructions of quasi-cyclic LDPC codes can be unified under the proposed approach.

Information Theory and Applications Workshop (ITA)•Feb 1, 2011•14 citations

A construction of the high-rate regular quasi-cyclic LDPC codes

Meng Qi, Jia Xiang Zhao, Wei Min Xu +1 more

In this paper, a scheme to construct the high-rate regular quasi-cyclic low-density parity-check (QC-LDPC) codes is developed based on the finite geometry low-density parity-check (LDPC) codes. To achieve this, we first decompose the EG-LDPC code into a set of the block submatrices with each of them being cyclic. Utilizing the decomposed structure, we then construct an auxiliary matrix to facilitate us for identifying and eliminating 6-cycles of the block submatrices. In the simulation, seven regular QC-LDPC codes with code rates being 4/5, 7/8, 10/11, 11/12, and 12/13 of moderate code lengths are constructed with this scheme. The performances of these codes demonstrate the effectiveness of the proposed scheme.

EURASIP Journal on Wireless Communications and Networking•Jan 17, 2019•3 citations
This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.
This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly LDPC codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterizations of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite geometry LDPC codes using the results developed in first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping sets of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite geometry and finite field cyclic and quasi-cyclic LDPC codes with large minimum weights are shown to have no harmful trapping sets with size smaller than their minimum weights. Consequently, their performance error-floors are dominated by their minimum weights.
This paper shows that a cyclic code can be put into quasi-cyclic form by decomposing a circular parity-check matrix through column and row permutations. Such a decomposition of a circular parity-check matrix of a cyclic code produces a group of shorter cyclic or quasi-cyclic codes and leads to a new method for constructing long cyclic codes from short cyclic codes. Also in this paper, new classes of cyclic and quasi-cyclic LDPC codes are derived from cyclic Euclidean geometry LDPC codes by decomposing their circular parity-check matrices. These new LDPC codes perform well and enlarge the repertoire of cyclic and quasi-cyclic LDPC codes.
In this letter, the structural analysis of nonbinary cyclic and quasi-cyclic (QC) low-density parity-check (LDPC) codes with α-multiplied parity-check matrices (PCMs) is concerned. Using analytical methods, several structural parameters of nonbinary cyclic and QC LDPC codes with α-multiplied PCMs are determined. In particular, some classes of nonbinary LDPC codes constructed from finite fields and finite geometries are shown to have good minimum and stopping distances properties, which may explain to some extent their wonderful decoding performances.
An approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is presented. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is used to characterize certain structural properties of low-density parity-check (LDPC) codes such as the girths of their Tanner graphs. Many constructions of quasi-cyclic LDPC codes can be unified under the proposed approach.
In this paper, a scheme to construct the high-rate regular quasi-cyclic low-density parity-check (QC-LDPC) codes is developed based on the finite geometry low-density parity-check (LDPC) codes. To achieve this, we first decompose the EG-LDPC code into a set of the block submatrices with each of them being cyclic. Utilizing the decomposed structure, we then construct an auxiliary matrix to facilitate us for identifying and eliminating 6-cycles of the block submatrices. In the simulation, seven regular QC-LDPC codes with code rates being 4/5, 7/8, 10/11, 11/12, and 12/13 of moderate code lengths are constructed with this scheme. The performances of these codes demonstrate the effectiveness of the proposed scheme.