IEEE Transactions on Communications

A Sub-Graph Expansion-Contraction Method for Error Floor Computation

Nithin Raveendran, David Declercq, Bane V. Vasic

Published Apr 21, 2020• 17 citations

Abstract

In this paper, we present a computationally efficient method for estimating error floors of low-density parity-check (LDPC) codes over the binary symmetric channel (BSC) without any prior knowledge of its trapping sets (TSs). Given the Tanner graph G of a code, and the decoding algorithm V, the method starts from a list of short cycles in G, and expands each cycle by including its sufficiently large neighborhood in G. Variable nodes of the expanded sub-graphs EXP are then corrupted exhaustively by all possible error patterns, and decoded by V operating on EXP. Union of support of the error patterns for which V fails on each EXP defines a subset of variable nodes that is a TS. The knowledge of the minimal error patterns and their strengths in each TSs is used to compute an estimation of the frame error rate. This estimation represents the contribution of error events localized on TSs, and therefore serves as an accurate estimation of the error floor performance of V at low BSC cross-over probabilities. We also discuss trade-offs between accuracy and computational complexity. Our analysis shows that in some cases the proposed method provides a million-fold improvement in computational complexity over standard Monte-Carlo simulation.

DOI: 10.1109/tcomm.2020.2988676

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 CommunicationsFeb 20, 202015 citations

Analysis of failures of decoders for LDPC codes

Shashi Kiran Chilappagari

Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.

Jan 1, 20080 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, 20121 citation

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

Ali Farsiabi

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

Jan 1, 20205 citations

Estimation of Bit and Frame Error Rates of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels

Hua Xiao, Amir H. Banihashemi

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSCs) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.

IEEE Transactions on CommunicationsDec 1, 200752 citations

Estimation of Bit and Frame Error Rates of Low-Density Parity-Check Codes on Binary Symmetric Channels

Hua Xiao, Amir H. Banihashemi

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSC) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.

arXiv:cs/0612011Canadian Workshop on Information Theory (CWIT)Jun 1, 200712 citations