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
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
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,
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 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.
Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four-cycles. A new class of bit flipping algorithms for LDPC codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.
Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</
Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</