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

Canadian Workshop on Information Theory (CWIT)

Classes of LDPC codes constructed from elements of finite fields and cyclotomic cosets

Salah A. Aly, Hussein H. Maza'ar

Published May 1, 2009• 1 citation
Publisher

Abstract

In this paper, we derive two algebraic methods for constructing regular low density parity check (LDPC) codes - one based on elements of finite fields and the other directly based on cyclotomic cosets. We show that the constructed codes have high rates and are free of cycles of length four; consequently, they can be decoded using standard iterative decoding algorithms. In addition we compute the exact dimension and establish bounds on the minimum and stopping distances of the constructed codes.

DOI
10.1109/cwit.2009.5069527

Related papers

Families of LDPC Codes Derived from Nonprimitive BCH Codes and Cyclotomic Cosets

Salah A. Aly

Low-density parity check (LDPC) codes are an important class of codes with many applications. Two algebraic methods for constructing regular LDPC codes are derived -- one based on nonprimitive narrow-sense BCH codes and the other directly based on cyclotomic cosets. The constructed codes have high rates and are free of cycles of length four; consequently, they can be decoded using standard iterative decoding algorithms. The exact dimension and bounds for the minimum distance and stopping distance are derived. These constructed codes can be used to derive quantum error-correcting codes.

arXiv:0802.4079•Feb 27, 2008•9 citations

Construction of LDPC Codes Based on Narrow-Sense-Primitive BCH Codes

Yi Yu, Liu Shaobo, Huang Dawei

In this paper, we present an algebraic method for constructing regular low-density parity-check (LDPC) codes based on narrow-sense-primitive BCH codes. The construction method results in a class of high rate LDPC codes in Gallager's original form. Codes in this class are free of cycles of length 4 in their Tanner graph and have good minimum distances. They can perform well with the iterative decoding. Also, proposed algebra LDPC codes can be designed for a new class of irregular codes based on a semi-algebraic structure for various code rates. It is shown that, with the proposed construction algorithms, fast construction time and reduced memory without the performance degradation can be achieved.

IEEE Vehicular Technology Conference•Dec 10, 2005•5 citations

On Algebraic Construction of Gallager and Circulant Low-Density Parity-Check Codes

H. Tang, Jun Xu, Y. Kou +2 more

This correspondence presents three algebraic methods for constructing low-density parity-check (LDPC) codes. These methods are based on the structural properties of finite geometries. The first method gives a class of Gallager codes and a class of complementary Gallager codes. The second method results in two classes of circulant-LDPC codes, one in cyclic form and the other in quasi-cyclic form. The third method is a two-step hybrid method. Codes in these classes have a wide range of rates and minimum distances, and they perform well with iterative decoding.

IEEE Transactions on Information Theory•Jun 1, 2004•108 citations

Approach to the construction of regular low-density parity-check codes from group permutation matrices

R. Sobhani

In this study, a new method for constructing low-density parity-check (LDPC) codes is presented. This construction is based on permutation matrices which come from a finite abstract group and hence the codes constructed in this manner are called group permutation low-density parity-check (GP-LDPC) codes. A necessary and sufficient condition under which a GP-LDPC code has a cycle is given and some properties of these codes are investigated. A class of flexible-rate GP-LDPC codes without cycles of length four is also introduced. Simulation results show that GP-LDPC codes perform very well with the iterative decoding and can outperform their random-like counterparts.

IET Communications•Aug 14, 2012•4 citations

Structured quasi‐cyclic low‐density parity‐check codes based on cyclotomic cosets

Morteza Esmaeili, Mehrab Najafian, Aaron Gulliver

This study considers the construction of four‐cycle free quasi‐cyclic low‐density parity‐check (QC‐LDPC) codes. These codes are based on the cyclotomic cosets of q modulo n where q is a prime power, n is a prime and ( n , q ) = 1. If s is the order of q modulo n , then n − 1 = sl for some integer l . Then there are l distinct cyclotomic cosets , 1 ≤ i ≤ l . Concatenation of the l circulant matrices formed using these sets gives an s × sl matrix M co ( n , q ). In addition, the Kronecker product of the transpose of ∪ i with itself modulo n gives an sl × sl matrix M kr ( n , q ). Replacing the entries of these matrices with their associated dispersed binary n × n matrices provides binary QC‐LDPC codes with girth at least six. Furthermore, for any prime power q ′ such that q ′ = n + 1 or q ′ ≥ 2 n , these two matrices can be used to construct q ′‐ary QC‐LDPC codes with girth at least six. These constructions produce large classes of four‐cycle free binary and non‐binary QC‐LDPC codes. Among the structured LDPC codes, the introduced technique, from code‐construction‐complexity perspective, which is an engineering factor, is at least among the best ones if not the best. Performance results are presented which show that the codes obtained perform well over additive white Gaussian noise channel with the iterative sum‐product decoding algorithm.

IET Communications•Jan 30, 2015•6 citations

Low-density parity-check codes based on finite geometries: a rediscovery and new results

Y. Kou, Shu Lin, M.P.C. Fossorier

This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.

IEEE Transactions on Information Theory•Jan 1, 2001•1,281 citations
In this paper, we derive two algebraic methods for constructing regular low density parity check (LDPC) codes - one based on elements of finite fields and the other directly based on cyclotomic cosets. We show that the constructed codes have high rates and are free of cycles of length four; consequently, they can be decoded using standard iterative decoding algorithms. In addition we compute the exact dimension and establish bounds on the minimum and stopping distances of the constructed codes.
Low-density parity check (LDPC) codes are an important class of codes with many applications. Two algebraic methods for constructing regular LDPC codes are derived -- one based on nonprimitive narrow-sense BCH codes and the other directly based on cyclotomic cosets. The constructed codes have high rates and are free of cycles of length four; consequently, they can be decoded using standard iterative decoding algorithms. The exact dimension and bounds for the minimum distance and stopping distance are derived. These constructed codes can be used to derive quantum error-correcting codes.
In this paper, we present an algebraic method for constructing regular low-density parity-check (LDPC) codes based on narrow-sense-primitive BCH codes. The construction method results in a class of high rate LDPC codes in Gallager's original form. Codes in this class are free of cycles of length 4 in their Tanner graph and have good minimum distances. They can perform well with the iterative decoding. Also, proposed algebra LDPC codes can be designed for a new class of irregular codes based on a semi-algebraic structure for various code rates. It is shown that, with the proposed construction algorithms, fast construction time and reduced memory without the performance degradation can be achieved.
This correspondence presents three algebraic methods for constructing low-density parity-check (LDPC) codes. These methods are based on the structural properties of finite geometries. The first method gives a class of Gallager codes and a class of complementary Gallager codes. The second method results in two classes of circulant-LDPC codes, one in cyclic form and the other in quasi-cyclic form. The third method is a two-step hybrid method. Codes in these classes have a wide range of rates and minimum distances, and they perform well with iterative decoding.
In this study, a new method for constructing low-density parity-check (LDPC) codes is presented. This construction is based on permutation matrices which come from a finite abstract group and hence the codes constructed in this manner are called group permutation low-density parity-check (GP-LDPC) codes. A necessary and sufficient condition under which a GP-LDPC code has a cycle is given and some properties of these codes are investigated. A class of flexible-rate GP-LDPC codes without cycles of length four is also introduced. Simulation results show that GP-LDPC codes perform very well with the iterative decoding and can outperform their random-like counterparts.
This study considers the construction of four‐cycle free quasi‐cyclic low‐density parity‐check (QC‐LDPC) codes. These codes are based on the cyclotomic cosets of q modulo n where q is a prime power, n is a prime and ( n , q ) = 1. If s is the order of q modulo n , then n − 1 = sl for some integer l . Then there are l distinct cyclotomic cosets , 1 ≤ i ≤ l . Concatenation of the l circulant matrices formed using these sets gives an s × sl matrix M co ( n , q ). In addition, the Kronecker product of the transpose of ∪ i with itself modulo n gives an sl × sl matrix M kr ( n , q ). Replacing the entries of these matrices with their associated dispersed binary n × n matrices provides binary QC‐LDPC codes with girth at least six. Furthermore, for any prime power q ′ such that q ′ = n + 1 or q ′ ≥ 2 n , these two matrices can be used to construct q ′‐ary QC‐LDPC codes with girth at least six. These constructions produce large classes of four‐cycle free binary and non‐binary QC‐LDPC codes. Among the structured LDPC codes, the introduced technique, from code‐construction‐complexity perspective, which is an engineering factor, is at least among the best ones if not the best. Performance results are presented which show that the codes obtained perform well over additive white Gaussian noise channel with the iterative sum‐product decoding algorithm.
This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.