In this letter, we supplement a known technique to design quasi-cyclic low-density parity-check (QC-LDPC) codes with girth 8 and variable node degrees 4. Using the technique of combining cycles of length 4 in the code's Tanner graph small trapping sets are avoided. The simulation results are presented to demonstrate the superiority of the developed codes in comparison with similar codes in the literature by the criterion of minimum length with a slight loss in energy efficiency
In this letter, we supplement a known technique to design quasi-cyclic low-density parity-check (QC-LDPC) codes with girth 8 and variable node degrees 4. Using the technique of combining cycles of length 4 in the code's Tanner graph small trapping sets are avoided. The simulation results are presented to demonstrate the superiority of the developed codes in comparison with similar codes in the literature by the criterion of minimum length with a slight loss in energy efficiency
In this letter, we propose a new technique to design quasi-cyclic low-density parity-check (QC-LDPC) codes with girth 8 and variable node degrees 3 and 4. Small trapping sets are avoided in the designed codes by imposing simple constraints on the cycles of length 8 in the code's Tanner graph. We also derive lower bounds on the block length of the codes that can satisfy such constraints. Simulation results are provided to demonstrate the superiority of the designed codes in comparison with similar codes in the literature.
Low-density parity-check (LDPC) codes exhibit excellent error correcting capability. However, small trapping sets in the Tanner graph are harmful to the iterative decoding algorithm. In this letter, we present a method of constructing (3, n) girth-eight quasi-cyclic LDPC codes with low error floor by removing the small trapping sets from the Tanner graph. To address this issue, we analyze the relationship between eight-cycles and small trapping sets of Tanner graphs based on fully connected base graphs without parallel edges. We find that if some eight-cycles are not found in the Tanner graphs, any elementary trapping set in the range of a ≤ 8 and b ≤ 3 is removed naturally. We also derive a lower bound on the permutation size for the construction of such codes. The experimental simulation shows a favorable error rate performance with lower error floor over additive white Gaussian noise channels.
Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.
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,
In this paper, we study the cycle structure of quasi-cyclic (QC) low-density parity-check (LDPC) codes with the goal of obtaining the shortest code with a given degree distribution and girth. We focus on QC-LDPC codes, whose Tanner graphs are cyclic liftings of fully connected base graphs of size 3 × n, n ≥ 4, and obtain minimal lifting degrees that result in girths 6 and 8. This is performed through an efficient exhaustive search, and as a result, we also find all the possible non-isomorphic codes with the same minimum block length, girth, and degree distribution. The exhaustive search, which is ordinarily a formidable task, is made possible by pruning the search space of many codes that are isomorphic to those previously examined in the search process. Many of the pruning techniques proposed in this paper are also applicable to QC-LDPC codes with base graphs other than the 3 × n fully connected ones discussed here, as well as to codes with a larger girth. To further demonstrate the effectiveness of the pruning techniques, we use them to search for QC-LDPC codes with girths 10 and 12, and find a number of such codes that have a shorter block length compared with the best known similar codes in the literature. In addition, motivated by the exhaustive search results, we tighten the lower bound on the block length of QC-LDPC codes of girth 6 constructed from fully connected 3 × n base graphs, and construct codes that achieve the lower bound for an arbitrary value of n ≥ 4.
One of the phenomena that influences significantly the performance of low-density parity-check codes is known as trapping sets. An (a,b) elementary trapping set, or simply an ETS where a is the size and b is the number of degree-one check nodes and ab<1, causes high decoding failure rate and exert a strong influence on the error floor. In this paper, we provide sufficient conditions for exponent matrices to have fully connected (3,n)-regular QC-LDPC codes with girths 6 and 8 whose Tanner graphs are free of small ETSs. Applying sufficient conditions on the exponent matrix to remove some 8-cycles results in removing all 4-cycles, 6-cycles as well as some small elementary trapping sets. For each girth we obtain a lower bound on the lifting degree and present exponent matrices with column weight three whose corresponding Tanner graph is free of certain ETSs.