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 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,
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.
In this article, we design finite-length irregular protograph-based quasi-cyclic (QC) low-density parity-check (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) £ in the Tanner graph of the code. 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 £ 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 number of times. Simulation results are provided to demonstrate the superior performance of designed codes compared to similar state-of-the-art irregular QC-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 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.
Forward error-correcting (FEC) codes play an important role in transmitting data with extremely high reliability through modern communication systems.Many applications such as optical communication channels require a very low error rate when transmitting data.In this thesis, we study the design and analysis of low-density parity-check (LDPC) codes in general and spatially coupled (SC) LDPC codes in particular.At first, we analyze the error floor performance of finite-length protographbased spatially coupled LDPC codes in terms of their design parameters.We conduct a comprehensive analysis to show that the parameter syndrome former memory (m) plays the main role in the average number of cycles and trapping sets in the Tanner graph of finite-length SC-LDPC codes.This, in fact, gives an insight into the error floor performance of protograph-based SC-LDPC codes, and demonstrates the superiority of these codes in the error floor region, compared to their block code counterparts.To complement the theoretical analysis conducted in the first stage of this research, we develop efficient design techniques for the construction of high-performance quasi-cyclic (QC)-LDPC and SC-LDPC codes, as the second part of the research.Our design approach is basically aimed at improving the performance of finite-length (SC) LDPC codes while maintaining the decoder complexity and latency small.The improvement in error floor is achieved by minimizing (elimination of) the most harmful trapping set (TS)s.In this regard, we present two design approaches: i) imposing simple conditions on the small cycles to result in the elimination of specific classes of trapping sets, ii) developing a search-based design technique such that specific trapping sets are targeted for minimization/elimination through the algorithm.Our constructed QC-LDPC and time-invariant SC-LDPC codes are superior to the stateof-the-art both in terms of their error floor performance and their low decoding latency and complexity.Finally, we look into the design of finite-length time-invariant QC SC-LDPC codes iii I would like to take this opportunity to express my sincere gratitude to my supervisor, Prof. Amir H. Banihashemi, for his invaluable guidance, continuous support and excellent mentorship during the course of my PhD studies.His immense knowledge and supervision always steered me to the right direction during this journey.Besides my supervisor, I would like to thank my committee members for their helpful comments and feedback on this thesis, and for their generosity in contributing their time to serve on my dissertation defense.I would like to mention the government of Ontario in acknowledgment of the Ontario Trillium Scholarship which pledged an ample
This thesis explores hardware implementation of low error floor and high speed low-density parity-check (LDPC) decoders.At first, a novel partially-parallel implementation of a protograph-based quasi-cyclic (QC) LDPC decoder, using a new column-layered message-passing schedule is presented.A new design for serial-input check nodes and switch networks, results in lower hardware complexity while having a higher throughput and comparable latency in comparison with all existing partiallyparallel architectures.Thereafter, we introduce a multi-step scheme for the input quantization of message-passing decoders for LDPC codes.The scheme is based on successive requantization and re-decoding of the input blocks that cause the decoder to be trapped in a trapping set, until the decoding is successful or a maximum number of requantization/re-decodings is reached.The proposed scheme, which is applicable to both regular and irregular codes, lowers the error floor significantly at the cost of small increase in complexity, memory and latency.Furthermore, to facilitate the process of code design and performance evaluation in the error floor region, we design a fast and accurate technique to estimate the error floor of variable-regular LDPC codes under quantized iterative decoding algorithms.This technique, which is based on enumerating the dominant elementary trapping sets of the code, provides significant improvement over existing methods in terms of speed and accuracy.Finally, we examine the harmfulness of trapping sets of variable-regular LDPC codes for soft-decision iterative decoding algorithms.We show that, other than the size of a trapping set, the number of unsatisfied check nodes and the trapping set's topological properties, the position of its subgraph in the Tanner graph of the code can also have an effect on its harmfulness.We also examine dominant trapping sets iii of the quantized min-sum (MS) decoding algorithm and two of its variants (offset-MS and MS with successive relaxation (SR)), for both regular and irregular LDPC codes.We show that the distribution of dominant trapping sets of these algorithms is similar for regular codes and different for irregular codes.Based on these results, we evaluate the error floor performance of a decoder, consisting of MS, offset-MS and SR-MS decoding algorithms working in parallel.First, I would like to thank my supervisor, Professor Amir H. Banihashemi for leading and encouraging me during my research.When I started as his M.A.Sc.student nine years ago, my dream was to acquire a set of skills.Amir helped me to achieve them with invaluable advice and excellent guidance.I would also like to thank M. Samy Hosny, the CEO of SiloconPro Inc. for supporting my research and providing me with his professional experience.I can not express my appreciation to my wonderful wife
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.