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

Information Theory and Applications Workshop (ITA)

An efficient exhaustive low-weight codeword search for structured LDPC codes

Seyed Mehrdad Khatami, Ludovic Danjean, Danny Nguyen, Bane V. Vasic

Published Feb 1, 2013• 8 citations
Publisher

Abstract

In this paper, we present an algorithm to find all low-weight codewords in a given quasi-cyclic (QC) low-density parity-check (LDPC) code with a fixed column-weight and girth. The main idea is to view a low-weight codeword as an (a, 0) trapping sets, and then show that each topologically different (a, 0) trapping set can be dissected into smaller trapping sets. The proposed search method relies on the knowledge of possible topologies of such smaller trapping sets present in a code ensemble, which enables an efficient search. Combined with the high-rate QC LDPC code construction which successively adds blocks of permutation matrices, the algorithm ensures that in the code construction procedure all codewords up to a certain weight are avoided, which leads to a code with the desired minimum distance. The algorithm can be also used to determine the multiplicity of the low-weight codewords with different trapping set structure.

DOI
10.1109/ita.2013.6502981

Related papers

On the Construction of Multitype Quasi-Cyclic Low-Density Parity-Check Codes With Different Girth and Length

Farzaneh Abedi, Mohammad Gholami

Multitype quasi-cyclic (QC) low-density parity-check (LDPC) codes are a class of protograph LDPC codes lifted cyclically from protographs with multiple edges, represented by two weight and slope matrices. For a given weight-matrix, an approach is proposed to find the maximum-achievable girth$g_{\max }$of the corresponding multitype QC-LDPC codes by some inevitable chains having less complexity than the existing methods. This advantage leads to some new patterns of the weight matrices such that the corresponding codes have some improvements in terms of the maximum-achievable girths or the minimum-distance upper-bounds. In continue, for a given weight-matrix with maximum-achievable girth$g_{\max }$, some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girth$g$,$g\le g_{\max }$, have smaller lengths, higher rates, or larger minimum-distances than the state-of-the-art achievements. Simulation results show that the constructed codes have some error-rate advantages than PEG, random-like, CCSDS, and 802.11n/ac IEEE standard LDPC codes.

IEEE Access•Jan 1, 2021•2 citations

Construction of QC LDPC Codes With Low Error Floor by Efficient Systematic Search and Elimination of Trapping Sets

Bashirreza Karimi, Amir H. Banihashemi

We propose a systematic design of protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor. We first characterize the trapping sets of such codes and demonstrate, using edge coloring techniques, that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure. Based on this characterization, our design aims at eliminating a targeted collection of trapping sets. Considering the parent/child relationship between the trapping sets in the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection. An efficient layered algorithm is designed for the search of these targeted trapping sets. Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets while having a smaller block length, or a larger collection of trapping sets while having the same block length. In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.

IEEE Transactions on Communications•Nov 14, 2019•22 citations

Construction of QC-LDPC Codes with Low Error Floor by Efficient Systematic Search and Elimination of Trapping Sets

Bashirreza Karimi, Amir H. Banihashemi

We propose a systematic design of protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor. We first characterize the trapping sets of such codes and demonstrate that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure. Using this characterization, our design aims at eliminating a targeted collection of trapping sets. Considering the parent/child relationship between the trapping sets in the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection. An efficient layered algorithm is designed for the search of these targeted trapping sets. Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets with a smaller block length, or a larger collection of trapping sets with the same block length. In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.

arXiv:1902.07332•Feb 19, 2019•0 citations

Quasi-cyclic LDPC codes for fast encoding

Seho Myung, Kyeongcheol Yang, Jaeyoel Kim

In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.

IEEE Transactions on Information Theory•Jul 19, 2005•278 citations

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

Construction of QC-LDPC Codes with Low Error Floor by Efficient Systematic Search and Elimination of Trapping Sets

Bashirreza Karimi

In this thesis, we propose a systematic design of binary protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor.We first characterize the trapping sets of such codes and demonstrate, using edge coloring techniques, that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure.Based on this characterization, our design aims at eliminating a targeted collection of trapping sets.Considering the parent/child relationship between the structures of the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection.An efficient layered algorithm is designed for the search of these targeted trapping sets.Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets while having a smaller block length, or a larger collection of trapping sets while having the same block length.In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.Moreover, we design finite-length binary irregular protograph-based QC-LDPC codes with good waterfall performance and low error floor.To achieve a low error floor, we eliminate a targeted set of dominant elementary trapping sets (ETS) L in the Tanner graph of the code.This is a more challenging task since the variety of problematic structures is much larger than that of regular codes.For a given rate and girth, the codes are designed to be free of the largest set of problematic ETSs for a given block length, or to have the shortest block length while a given set of ETSs is avoided.The design is based on a search algorithm that identifies whether any instance of any structure within L exists in the Tanner graph of the constructed code or not.The search algorithm performs this task with minimal complexity, making it feasible to construct practical codes by running the search algorithm a large numberiiiFirst, I would like to thank my supervisor, Professor Amir H. Banihashemi for leading and encouraging me during my research.His guidance helped me in all the time of research and writing of this thesis.Thanks must also go to my committee members for their helpful suggestions and discussions.I can not express my appreciation to my wonderful wife, Arefeh who devoted her never ending love to me and was my partner towards success.I also appreciate the love and support of my family,

•Jan 1, 2021•2 citations
In this paper, we present an algorithm to find all low-weight codewords in a given quasi-cyclic (QC) low-density parity-check (LDPC) code with a fixed column-weight and girth. The main idea is to view a low-weight codeword as an (a, 0) trapping sets, and then show that each topologically different (a, 0) trapping set can be dissected into smaller trapping sets. The proposed search method relies on the knowledge of possible topologies of such smaller trapping sets present in a code ensemble, which enables an efficient search. Combined with the high-rate QC LDPC code construction which successively adds blocks of permutation matrices, the algorithm ensures that in the code construction procedure all codewords up to a certain weight are avoided, which leads to a code with the desired minimum distance. The algorithm can be also used to determine the multiplicity of the low-weight codewords with different trapping set structure.
Multitype quasi-cyclic (QC) low-density parity-check (LDPC) codes are a class of protograph LDPC codes lifted cyclically from protographs with multiple edges, represented by two weight and slope matrices. For a given weight-matrix, an approach is proposed to find the maximum-achievable girthgmax⁡g_{\max }gmax​of the corresponding multitype QC-LDPC codes by some inevitable chains having less complexity than the existing methods. This advantage leads to some new patterns of the weight matrices such that the corresponding codes have some improvements in terms of the maximum-achievable girths or the minimum-distance upper-bounds. In continue, for a given weight-matrix with maximum-achievable girthgmax⁡g_{\max }gmax​, some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girthggg,g≤gmax⁡g\le g_{\max }g≤gmax​, have smaller lengths, higher rates, or larger minimum-distances than the state-of-the-art achievements. Simulation results show that the constructed codes have some error-rate advantages than PEG, random-like, CCSDS, and 802.11n/ac IEEE standard LDPC codes.
We propose a systematic design of protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor. We first characterize the trapping sets of such codes and demonstrate, using edge coloring techniques, that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure. Based on this characterization, our design aims at eliminating a targeted collection of trapping sets. Considering the parent/child relationship between the trapping sets in the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection. An efficient layered algorithm is designed for the search of these targeted trapping sets. Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets while having a smaller block length, or a larger collection of trapping sets while having the same block length. In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.
We propose a systematic design of protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor. We first characterize the trapping sets of such codes and demonstrate that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure. Using this characterization, our design aims at eliminating a targeted collection of trapping sets. Considering the parent/child relationship between the trapping sets in the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection. An efficient layered algorithm is designed for the search of these targeted trapping sets. Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets with a smaller block length, or a larger collection of trapping sets with the same block length. In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.
In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.
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.
In this thesis, we propose a systematic design of binary protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor.We first characterize the trapping sets of such codes and demonstrate, using edge coloring techniques, that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure.Based on this characterization, our design aims at eliminating a targeted collection of trapping sets.Considering the parent/child relationship between the structures of the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection.An efficient layered algorithm is designed for the search of these targeted trapping sets.Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets while having a smaller block length, or a larger collection of trapping sets while having the same block length.In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.Moreover, we design finite-length binary irregular protograph-based QC-LDPC codes with good waterfall performance and low error floor.To achieve a low error floor, we eliminate a targeted set of dominant elementary trapping sets (ETS) L in the Tanner graph of the code.This is a more challenging task since the variety of problematic structures is much larger than that of regular codes.For a given rate and girth, the codes are designed to be free of the largest set of problematic ETSs for a given block length, or to have the shortest block length while a given set of ETSs is avoided.The design is based on a search algorithm that identifies whether any instance of any structure within L exists in the Tanner graph of the constructed code or not.The search algorithm performs this task with minimal complexity, making it feasible to construct practical codes by running the search algorithm a large numberiiiFirst, I would like to thank my supervisor, Professor Amir H. Banihashemi for leading and encouraging me during my research.His guidance helped me in all the time of research and writing of this thesis.Thanks must also go to my committee members for their helpful suggestions and discussions.I can not express my appreciation to my wonderful wife, Arefeh who devoted her never ending love to me and was my partner towards success.I also appreciate the love and support of my family,