Code-Independent Error Floor Estimation Techniques for Flooding and Layered Decoders of LDPC Codes
Ali Farsiabi · 2020
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. . . . . . . .