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

Code-Independent Error Floor Estimation Techniques for Flooding and Layered Decoders of LDPC Codes

Ali Farsiabi

Published Jan 1, 2020• 5 citations
Publisher

Abstract

Finite-length low-density parity-check (LDPC) codes under iterative message passing algorithms suffer from error floor, i.e., as the channel quality improves, at some point, the error rate does not decrease as fast as its initial rate of decrease.The literature on the error floor analysis/estimation of LDPC codes can be, in general, partitioned into two main categories.The first category requires the full knowledge of the parity-check matrix or Tanner graph of the code to estimate the error floor.The second category, on the other hand, is code-independent, in that, rather than the full knowledge of the code's Tanner graph, these techniques only require the multiplicity and topology of harmful substructures of the Tanner graph, referred to as trapping sets (TSs), and possibly the degree distributions of the graph, to estimate the error floor.The proposed techniques in this thesis fit within the second category.The linear state-space model is a well-known code-independent method to estimate the contribution of a trapping set structure to the error floor of low-density paritycheck codes.In this thesis we first provide an in-depth analysis of this method by incorporating a more accurate model for the incoming messages to the TS structure that takes into account the randomness and the correlation among such messages.Based on this analysis, we demonstrate that both randomness and correlation result in the over-estimation of the failure probability of the TS.We then propose an alternate code-independent technique for the error floor estimation of iterative LDPC decoders that can accurately estimate the contribution of different TS structures in the error floor.Compared to the linear state-space model, the proposed method is not only more accurate, but also more general, in that, it is applicable to any saturating iterative message-passing decoder, symmetrically quantized or unquantized, over any memoryless binary-input output-symmetric channel.To the best of our knowledge, all the existing work on the theoretical analysis of error floor is limited to two-phase message passing algorithms, also known as flooding or parallel schedule.There are however a variety of message passing schedules which iii 4.5 The steps of constructing the digraph D l (S) of the (5, 3) LETS for a layered decoder from the flooding digraph D f (S).(The colors (edge types) red (dotted), blue (dashed) and purple (dash-dotted) represent L 1 , L 2 and L 3 , respectively.) . . . . . . . . . . . . . . . . . . . . . .69 4.6 QC-LDPC codes used for simulations.The entries of the matrices, that are not equal to -1, represent the right circular shift of the identity matrix to create the corresponding block of the parity-check matrix.The -1 entries represent zero blocks. . . . . . . . . . . . . . . . . . .80 4.7 Simulation and estimation results of C 1 for different saturation levels.The maximum number of iterations I max = 30. . . . . . . . . . . . .81 4.8 The (5, 5) LETS structure of C 1 in which the row layers for different CNs are shown. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81 4.9 The approximate estimate of the failure probability of the (5, 5) LETS of C 1 for various row layered schedules at E b /N 0 = 6 dB and saturation level 31.75.The schedules are sorted based on r. . . . . . . . . . . .83 4.10 The simulation and estimation results of C 1 for different row schedules.(The saturation level is 31.75, and the maximum number of iterations for layered schedules and the flooding schedule are set to 30 and 60, respectively.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83 4.11 The effect of various row layered schedules on the failure probability of different classes of LETSs in C 2 (E b /N 0 = 6 dB, saturation level 15.75).85 4.12 The effect of various row layered schedules on the total FER of C 2 (E b /N 0 = 6 dB, saturation level 15.75). . . . . . . . . . . . . . . . . .85 4.13 The error estimation of the ten (7, 1) LETS groups of C 2 for the two schedules (1, 2, 3, 4, 5, 6) and (4, 1, 5, 2, 3, 6) (saturation level 15.75). .86 4.14 Simulation and estimation results of C 2 for the two schedules (1, 2, 3, 4, 5, 6) and (4, 1, 5, 2, 3, 6) (saturation level 15.75,I max = 30). .87 5.1 A labelled (5,3) LETS of the Tanner (155, 64) code in which the flow of the state variables are shown.The VNs, mis-satisfied CNs and unsatisfied CNs are shown by black circles, white squares and gray squares, respectively.The directed edges related to the layers number 1, 2 and 3 are represented by red, blue and purple colors, respectively.93 xiii 5.2 The VNs v 1 and v 4 related to Fig. 5.1 with the mis-satisfied CN c j connecting them.Figures (a) and (b) are related to virtual VNs, v k and v k , that are used during the update of VNs from layers L 1 and L 3 , respectively.. . . . . . . . . . . . . . . . . . . . . . . . . . . . .99 5.3 Base graph of Example 16: The solid (red), dashed (green), dotted (blue) and dashed-dotted (purple) arrows, respectively, illustrate the updating order which the column layered decoder perform, accordingly.109 5.4 The error estimation related to (5, 5) LETS of C 1 for various column layered schedules at E b /N 0 = 6 dB.All the schedules result in the same dominant eigenvalue of the layered transition matrix, r = 16.9536.The saturation level is 15.75. . . . . . . . . . . . . . . . . . . . . . . . . .111 5.5 The simulation and estimation results related to code C 1 showing the effect of different schedules.The saturation level is 15.75 and the maximum number of iterations is 30. . . . . . . . . . . . . . . . . . .111 5.6 The simulation and estimation results related to code C 2 showing the effect of different schedules.The saturation level is 15.75.The maximum number of iterations is 30. . . . . . . . . . . . . . . . . . . . .113 6.1 The histogram of the conditional error indicator function of a (5, 5) ETS of (640, 192) QC-LDPC code [3] at different iterations. . . . . .128 6.2 Simulation and estimation results for C 1 decoded by SPA over the AWGN channel (I max = 200). . . . . . . . . . . . . . . . . . . . . . .134 6.3 Simulation and extrapolated estimation results for C 1 decoded by SPA over the AWGN channel (I max = 200).The extrapolated curves are obtained based on the results at E b /N 0 = 4.5 dB . . . . . . . . . . . .136 6.4 Simulation and estimation results for C 2 decoded by SPA over the AWGN channel (I max = 200, C th = 25).The extrapolation in DSLM E is based on the results at E b /N 0 = 2.75 dB. . . . . . . . . . . . . . . .136 6.5 Simulation and estimation results for C 3 decoded by SPA over the AWGN channel (I max = 200).The extrapolation in DSLM E is based on the results at E b /N 0 = 4.5 dB. . . . . . . .

DOI
10.22215/etd/2020-14343

Related papers

Error Floor Estimation of LDPC Decoders — A Code Independent Approach to Measuring the Harmfulness of Trapping Sets

Ali Farsiabi, Amir H. Banihashemi

The linear state-space model is a well-known code-independent method to estimate the contribution of a trapping set (TS) structure to the error floor of low-density parity-check (LDPC) codes. In this paper, we provide an in-depth analysis of this method by incorporating a more accurate model for the incoming messages to the TS structure that takes into account the randomness and the correlation among such messages. Based on this analysis, we demonstrate that both randomness and correlation result in the over-estimation of the failure probability of the TS. We then propose an alternate code-independent technique for the error floor estimation of iterative LDPC decoders that can accurately estimate the contribution of different TS structures in the error floor. Compared to the linear state-space model, the proposed method is not only more accurate, but also more general, in that, it is applicable to any saturating iterative message-passing decoder, symmetrically quantized or unquantized, over any memoryless binary-input output-symmetric channel. The proposed technique can be viewed as the local application of importance sampling (IS) to the message-passing algorithm over the subgraph induced by the TS in the code's Tanner graph. In the message-passing process, to account for the effect of the rest of the Tanner graph, density evolution along with a simple correlation model is used to generate the messages coming into the TS from the rest of the Tanner graph. Extensive simulations demonstrate that the proposed technique can accurately estimate the error floor of LDPC codes over both additive white Gaussian noise (AWGN) channel and binary symmetric channel (BSC), for a variety of iterative decoding algorithms and quantization schemes.

IEEE Transactions on Communications•Feb 20, 2020•15 citations

Error Floor Analysis of LDPC Column Layered Decoders

Ali Farsiabi, Amir H. Banihashemi

In this letter, we analyze the error floor of column layered decoders, also known as shuffled decoders, for low-density parity-check (LDPC) codes under saturating sum-product algorithm (SPA). To estimate the error floor, we evaluate the failure rate of different trapping sets (TSs) that contribute to the frame error rate in the error floor region. For each such TS, we model the dynamics of SPA in the vicinity of the TS by a linear state-space model that incorporates the information of the layered message-passing schedule. Consequently, the model parameters and the failure rate of the TS change as a result of the change in the order by which the messages of different layers are updated. This, in turn, causes the error floor of the code to change as a function of scheduling. Based on the proposed analysis, we then devise an efficient search algorithm to find a schedule that minimizes the error floor. Simulation results are presented to verify the accuracy of the proposed error floor estimation technique.

arXiv:2107.11479•IEEE Communications Letters•Dec 21, 2021•3 citations

High Speed Low Error Floor Hardware Implementation and Fast and Accurate Error Floor Estimation of LDPC Decoders

Sina Tolouei

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

•Jan 1, 2014•2 citations

Error Floor Analysis of LDPC Row Layered Decoders

Ali Farsiabi, Amir H. Banihashemi

In this paper, we analyze the error floor of quasi-cyclic (QC) low-density parity-check (LDPC) codes decoded by the sum-product algorithm (SPA) with row layered message-passing scheduling. For this, we develop a linear state-space model of trapping sets (TSs) which incorporates the layered nature of scheduling. We demonstrate that the contribution of each TS to the error floor is not only a function of the topology of the TS, but also depends on the row layers in which different check nodes of the TS are located. This information, referred to as TS layer profile (TSLP), plays an important role in the harmfulness of a TS. As a result, the harmfulness of a TS in particular, and the error floor of the code in general, can significantly change by changing the order in which the information of different layers, corresponding to different row blocks of the parity-check matrix, is updated. We also study the problem of finding a layer ordering that minimizes the error floor, and obtain row layered decoders with error floor significantly lower than that of their flooding counterparts. As part of our analysis, we make connections between the parameters of the state-space model for a row layered schedule and those of the flooding schedule. Simulation results are presented to show the accuracy of analytical error floor estimates.

arXiv:2104.06867•IEEE Transactions on Information Theory•Jul 21, 2021•11 citations

Improving the Error Floor Performance of LDCP Codes with Better Codes and Better Decoders

Dung Viet Nguyen

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.

•Jan 1, 2012•1 citation

Error Floors of LDPC Codes and Related Topics

Brian K. Butler

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.</

•Jan 1, 2013•1 citation
Finite-length low-density parity-check (LDPC) codes under iterative message passing algorithms suffer from error floor, i.e., as the channel quality improves, at some point, the error rate does not decrease as fast as its initial rate of decrease.The literature on the error floor analysis/estimation of LDPC codes can be, in general, partitioned into two main categories.The first category requires the full knowledge of the parity-check matrix or Tanner graph of the code to estimate the error floor.The second category, on the other hand, is code-independent, in that, rather than the full knowledge of the code's Tanner graph, these techniques only require the multiplicity and topology of harmful substructures of the Tanner graph, referred to as trapping sets (TSs), and possibly the degree distributions of the graph, to estimate the error floor.The proposed techniques in this thesis fit within the second category.The linear state-space model is a well-known code-independent method to estimate the contribution of a trapping set structure to the error floor of low-density paritycheck codes.In this thesis we first provide an in-depth analysis of this method by incorporating a more accurate model for the incoming messages to the TS structure that takes into account the randomness and the correlation among such messages.Based on this analysis, we demonstrate that both randomness and correlation result in the over-estimation of the failure probability of the TS.We then propose an alternate code-independent technique for the error floor estimation of iterative LDPC decoders that can accurately estimate the contribution of different TS structures in the error floor.Compared to the linear state-space model, the proposed method is not only more accurate, but also more general, in that, it is applicable to any saturating iterative message-passing decoder, symmetrically quantized or unquantized, over any memoryless binary-input output-symmetric channel.To the best of our knowledge, all the existing work on the theoretical analysis of error floor is limited to two-phase message passing algorithms, also known as flooding or parallel schedule.There are however a variety of message passing schedules which iii 4.5 The steps of constructing the digraph D l (S) of the (5, 3) LETS for a layered decoder from the flooding digraph D f (S).(The colors (edge types) red (dotted), blue (dashed) and purple (dash-dotted) represent L 1 , L 2 and L 3 , respectively.) . . . . . . . . . . . . . . . . . . . . . .69 4.6 QC-LDPC codes used for simulations.The entries of the matrices, that are not equal to -1, represent the right circular shift of the identity matrix to create the corresponding block of the parity-check matrix.The -1 entries represent zero blocks. . . . . . . . . . . . . . . . . . .80 4.7 Simulation and estimation results of C 1 for different saturation levels.The maximum number of iterations I max = 30. . . . . . . . . . . . .81 4.8 The (5, 5) LETS structure of C 1 in which the row layers for different CNs are shown. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81 4.9 The approximate estimate of the failure probability of the (5, 5) LETS of C 1 for various row layered schedules at E b /N 0 = 6 dB and saturation level 31.75.The schedules are sorted based on r. . . . . . . . . . . .83 4.10 The simulation and estimation results of C 1 for different row schedules.(The saturation level is 31.75, and the maximum number of iterations for layered schedules and the flooding schedule are set to 30 and 60, respectively.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83 4.11 The effect of various row layered schedules on the failure probability of different classes of LETSs in C 2 (E b /N 0 = 6 dB, saturation level 15.75).85 4.12 The effect of various row layered schedules on the total FER of C 2 (E b /N 0 = 6 dB, saturation level 15.75). . . . . . . . . . . . . . . . . .85 4.13 The error estimation of the ten (7, 1) LETS groups of C 2 for the two schedules (1, 2, 3, 4, 5, 6) and (4, 1, 5, 2, 3, 6) (saturation level 15.75). .86 4.14 Simulation and estimation results of C 2 for the two schedules (1, 2, 3, 4, 5, 6) and (4, 1, 5, 2, 3, 6) (saturation level 15.75,I max = 30). .87 5.1 A labelled (5,3) LETS of the Tanner (155, 64) code in which the flow of the state variables are shown.The VNs, mis-satisfied CNs and unsatisfied CNs are shown by black circles, white squares and gray squares, respectively.The directed edges related to the layers number 1, 2 and 3 are represented by red, blue and purple colors, respectively.93 xiii 5.2 The VNs v 1 and v 4 related to Fig. 5.1 with the mis-satisfied CN c j connecting them.Figures (a) and (b) are related to virtual VNs, v k and v k , that are used during the update of VNs from layers L 1 and L 3 , respectively.. . . . . . . . . . . . . . . . . . . . . . . . . . . . .99 5.3 Base graph of Example 16: The solid (red), dashed (green), dotted (blue) and dashed-dotted (purple) arrows, respectively, illustrate the updating order which the column layered decoder perform, accordingly.109 5.4 The error estimation related to (5, 5) LETS of C 1 for various column layered schedules at E b /N 0 = 6 dB.All the schedules result in the same dominant eigenvalue of the layered transition matrix, r = 16.9536.The saturation level is 15.75. . . . . . . . . . . . . . . . . . . . . . . . . .111 5.5 The simulation and estimation results related to code C 1 showing the effect of different schedules.The saturation level is 15.75 and the maximum number of iterations is 30. . . . . . . . . . . . . . . . . . .111 5.6 The simulation and estimation results related to code C 2 showing the effect of different schedules.The saturation level is 15.75.The maximum number of iterations is 30. . . . . . . . . . . . . . . . . . . . .113 6.1 The histogram of the conditional error indicator function of a (5, 5) ETS of (640, 192) QC-LDPC code [3] at different iterations. . . . . .128 6.2 Simulation and estimation results for C 1 decoded by SPA over the AWGN channel (I max = 200). . . . . . . . . . . . . . . . . . . . . . .134 6.3 Simulation and extrapolated estimation results for C 1 decoded by SPA over the AWGN channel (I max = 200).The extrapolated curves are obtained based on the results at E b /N 0 = 4.5 dB . . . . . . . . . . . .136 6.4 Simulation and estimation results for C 2 decoded by SPA over the AWGN channel (I max = 200, C th = 25).The extrapolation in DSLM E is based on the results at E b /N 0 = 2.75 dB. . . . . . . . . . . . . . . .136 6.5 Simulation and estimation results for C 3 decoded by SPA over the AWGN channel (I max = 200).The extrapolation in DSLM E is based on the results at E b /N 0 = 4.5 dB. . . . . . . .
The linear state-space model is a well-known code-independent method to estimate the contribution of a trapping set (TS) structure to the error floor of low-density parity-check (LDPC) codes. In this paper, we provide an in-depth analysis of this method by incorporating a more accurate model for the incoming messages to the TS structure that takes into account the randomness and the correlation among such messages. Based on this analysis, we demonstrate that both randomness and correlation result in the over-estimation of the failure probability of the TS. We then propose an alternate code-independent technique for the error floor estimation of iterative LDPC decoders that can accurately estimate the contribution of different TS structures in the error floor. Compared to the linear state-space model, the proposed method is not only more accurate, but also more general, in that, it is applicable to any saturating iterative message-passing decoder, symmetrically quantized or unquantized, over any memoryless binary-input output-symmetric channel. The proposed technique can be viewed as the local application of importance sampling (IS) to the message-passing algorithm over the subgraph induced by the TS in the code's Tanner graph. In the message-passing process, to account for the effect of the rest of the Tanner graph, density evolution along with a simple correlation model is used to generate the messages coming into the TS from the rest of the Tanner graph. Extensive simulations demonstrate that the proposed technique can accurately estimate the error floor of LDPC codes over both additive white Gaussian noise (AWGN) channel and binary symmetric channel (BSC), for a variety of iterative decoding algorithms and quantization schemes.
In this letter, we analyze the error floor of column layered decoders, also known as shuffled decoders, for low-density parity-check (LDPC) codes under saturating sum-product algorithm (SPA). To estimate the error floor, we evaluate the failure rate of different trapping sets (TSs) that contribute to the frame error rate in the error floor region. For each such TS, we model the dynamics of SPA in the vicinity of the TS by a linear state-space model that incorporates the information of the layered message-passing schedule. Consequently, the model parameters and the failure rate of the TS change as a result of the change in the order by which the messages of different layers are updated. This, in turn, causes the error floor of the code to change as a function of scheduling. Based on the proposed analysis, we then devise an efficient search algorithm to find a schedule that minimizes the error floor. Simulation results are presented to verify the accuracy of the proposed error floor estimation technique.
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 analyze the error floor of quasi-cyclic (QC) low-density parity-check (LDPC) codes decoded by the sum-product algorithm (SPA) with row layered message-passing scheduling. For this, we develop a linear state-space model of trapping sets (TSs) which incorporates the layered nature of scheduling. We demonstrate that the contribution of each TS to the error floor is not only a function of the topology of the TS, but also depends on the row layers in which different check nodes of the TS are located. This information, referred to as TS layer profile (TSLP), plays an important role in the harmfulness of a TS. As a result, the harmfulness of a TS in particular, and the error floor of the code in general, can significantly change by changing the order in which the information of different layers, corresponding to different row blocks of the parity-check matrix, is updated. We also study the problem of finding a layer ordering that minimizes the error floor, and obtain row layered decoders with error floor significantly lower than that of their flooding counterparts. As part of our analysis, we make connections between the parameters of the state-space model for a row layered schedule and those of the flooding schedule. Simulation results are presented to show the accuracy of analytical error floor estimates.
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.</