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:1012.3201

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

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

Published Dec 15, 2010• 12 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1012.3201

Related papers

Cyclic and Quasi-Cyclic LDPC Codes on 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 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.

IEEE Transactions on Information Theory•Jan 31, 2012•108 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

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

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

Circulant Arrays on Cyclic Subgroups of Finite Fields: Rank Analysis and Construction of Quasi-Cyclic LDPC Codes

Li Guo Zhang, Shu Lin, Khaled Abdel-Ghaffar +2 more

This paper consists of three parts. The first part presents a large class of new binary quasi-cyclic (QC)-LDPC codes with girth of at least 6 whose parity-check matrices are constructed based on cyclic subgroups of finite fields. Experimental results show that the codes constructed perform well over the binary-input AWGN channel with iterative decoding using the sum-product algorithm (SPA). The second part analyzes the ranks of the parity-check matrices of codes constructed based on finite fields with characteristic of 2 and gives combinatorial expressions for these ranks. The third part identifies a subclass of constructed QC-LDPC codes that have large minimum distances. Decoding of codes in this subclass with the SPA converges very fast.

arXiv:1004.1184•Apr 7, 2010•0 citations
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 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 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.
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 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.
This paper consists of three parts. The first part presents a large class of new binary quasi-cyclic (QC)-LDPC codes with girth of at least 6 whose parity-check matrices are constructed based on cyclic subgroups of finite fields. Experimental results show that the codes constructed perform well over the binary-input AWGN channel with iterative decoding using the sum-product algorithm (SPA). The second part analyzes the ranks of the parity-check matrices of codes constructed based on finite fields with characteristic of 2 and gives combinatorial expressions for these ranks. The third part identifies a subclass of constructed QC-LDPC codes that have large minimum distances. Decoding of codes in this subclass with the SPA converges very fast.