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 Communications

Enhancing Iterative Decoding of Cyclic LDPC Codes Using Their Automorphism Groups

Chao Chen, Baoming Bai, Xinquan Yang, Li Li, Yang Yang

Published Apr 4, 2013• 9 citations
Publisher

Abstract

For cyclic LDPC codes, we propose to use their automorphism groups to improve the iterative decoding performance. The basic idea is to construct nonequivalent parity-check matrices via column permutations. Three types of iterative decoders are devised to take advantage of the code's automorphism group. In this paper we focus on cyclic LDPC codes defined by a circulant parity-check matrix and consider two known subgroups of the automorphism group of a cyclic code. For the large class of idempotent-based cyclic LDPC codes in the literature, we show that the two subgroups only provide equivalent parity-check matrices and thus cannot be harnessed for iterative decoding. Towards exploiting the automorphism group of a code, we propose a new class of cyclic LDPC codes based on pseudo-cyclic MDS codes with two information symbols, for which nonequivalent parity-check matrices are obtained. Simulation results show that for our constructed codes of short lengths, the automorphism group can significantly enhance the iterative decoding performance.

DOI
10.1109/tcomm.2013.032713.120050

Related papers

Quasi-Cyclic LDPC Codes on Cyclic Subgroups of Finite Fields

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

A new class of quasi-cyclic LDPC codes whose parity-check matrices are arrays of circulant permutation matrices constructed based on cyclic subgroups of finite fields is presented. This class of codes contains several known classes of algebraic quasi-cyclic LDPC codes as subclasses. Experimental results show that the codes constructed perform very well over the AWGN channel when decoded with iterative decoding based on belief propagation. This class of new QC-LDPC codes contains a subclass of codes which have large minimum distances. Combinatorial expressions for the ranks of the parity-check matrices of a subclass of codes constructed based on fields of characteristic two are given.

IEEE Transactions on Communications•Jun 28, 2011•34 citations

Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes

Thorsten Hehn, Olgica Milenković, Stefan Laendner +1 more

We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the tradeoff between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovasz's local lemma (LLL) and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed properties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum-likelihood (ML) decoding.

arXiv:0708.0905•IEEE Transactions on Information Theory•Dec 1, 2008•33 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

Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes

Abstract — We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the trade-off between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovász’s Local Lemma and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed prop-erties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum likelihood decoding.

•Feb 28, 2015•0 citations

A Revolving Iterative Algorithm for Decoding Algebraic Cyclic and Quasi-Cyclic LDPC Codes

Keke Liu, Shu Lin, Khaled Abdel-Ghaffar

Cyclic and quasi-cyclic algebraic LDPC codes constructed based on finite fields, finite geometries, and combinatorial designs can achieve excellent performance in terms of error rate, error floor and rate of decoding convergence with iterative decoding. However, the relatively high density of the parity-check matrix of an algebraic cyclic or quasi-cyclic LDPC code makes the hardware implementation complexity of the decoder quite large, which may be a critical issue in practical applications. This paper presents an effective reduced-complexity algorithm for decoding algebraic cyclic and quasi-cyclic LDPC codes based on the block cyclic structure and cyclic grouping of the rows of their parity-check matrices. The decoding of a code is carried out based on a single small submatrix of the parity-check matrix of the code in a revolving manner. The proposed decoding algorithm significantly reduces the hardware implementation complexity and the size of memory required to store information.

IEEE Transactions on Communications•Sep 26, 2013•21 citations

Nonbinary Cyclic LDPC Codes Derived from Idempotents and Modular Golomb Rulers

Chao Chen, Baoming Bai, Zhuo Li +2 more

Based jointly on idempotents and modular Golomb rulers, we construct a class of nonbinary cyclic low-density parity-check (LDPC) codes. The defining parity-check matrix is a sparse circulant, on which we put two constraints: 1) the characteristic polynomial is an idempotent, 2) the nonzero elements of the first row are located on a modular Golomb ruler. We show that the second constraint forms a necessary and sufficient condition for the Tanner graph to have no cycles of length 4. The minimum distance of the code is proved equal to the column weight of the parity-check matrix plus one. A search algorithm is presented, with which we obtain some high rate codes with large minimum distances. The issue of code equivalence is also discussed. Simulation results show that the obtained codes perform well under iterative decoding.

IEEE Transactions on Communications•Feb 10, 2012•9 citations
For cyclic LDPC codes, we propose to use their automorphism groups to improve the iterative decoding performance. The basic idea is to construct nonequivalent parity-check matrices via column permutations. Three types of iterative decoders are devised to take advantage of the code's automorphism group. In this paper we focus on cyclic LDPC codes defined by a circulant parity-check matrix and consider two known subgroups of the automorphism group of a cyclic code. For the large class of idempotent-based cyclic LDPC codes in the literature, we show that the two subgroups only provide equivalent parity-check matrices and thus cannot be harnessed for iterative decoding. Towards exploiting the automorphism group of a code, we propose a new class of cyclic LDPC codes based on pseudo-cyclic MDS codes with two information symbols, for which nonequivalent parity-check matrices are obtained. Simulation results show that for our constructed codes of short lengths, the automorphism group can significantly enhance the iterative decoding performance.
A new class of quasi-cyclic LDPC codes whose parity-check matrices are arrays of circulant permutation matrices constructed based on cyclic subgroups of finite fields is presented. This class of codes contains several known classes of algebraic quasi-cyclic LDPC codes as subclasses. Experimental results show that the codes constructed perform very well over the AWGN channel when decoded with iterative decoding based on belief propagation. This class of new QC-LDPC codes contains a subclass of codes which have large minimum distances. Combinatorial expressions for the ranks of the parity-check matrices of a subclass of codes constructed based on fields of characteristic two are given.
We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the tradeoff between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovasz's local lemma (LLL) and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed properties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum-likelihood (ML) decoding.
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.
Abstract — We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the trade-off between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovász’s Local Lemma and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed prop-erties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum likelihood decoding.
Cyclic and quasi-cyclic algebraic LDPC codes constructed based on finite fields, finite geometries, and combinatorial designs can achieve excellent performance in terms of error rate, error floor and rate of decoding convergence with iterative decoding. However, the relatively high density of the parity-check matrix of an algebraic cyclic or quasi-cyclic LDPC code makes the hardware implementation complexity of the decoder quite large, which may be a critical issue in practical applications. This paper presents an effective reduced-complexity algorithm for decoding algebraic cyclic and quasi-cyclic LDPC codes based on the block cyclic structure and cyclic grouping of the rows of their parity-check matrices. The decoding of a code is carried out based on a single small submatrix of the parity-check matrix of the code in a revolving manner. The proposed decoding algorithm significantly reduces the hardware implementation complexity and the size of memory required to store information.
Based jointly on idempotents and modular Golomb rulers, we construct a class of nonbinary cyclic low-density parity-check (LDPC) codes. The defining parity-check matrix is a sparse circulant, on which we put two constraints: 1) the characteristic polynomial is an idempotent, 2) the nonzero elements of the first row are located on a modular Golomb ruler. We show that the second constraint forms a necessary and sufficient condition for the Tanner graph to have no cycles of length 4. The minimum distance of the code is proved equal to the column weight of the parity-check matrix plus one. A search algorithm is presented, with which we obtain some high rate codes with large minimum distances. The issue of code equivalence is also discussed. Simulation results show that the obtained codes perform well under iterative decoding.