In order to count the number of trapping sets (TS), we changed Cole's Importance Sampling (IS) approach, which led to a message-passing decoder problem. Several concepts have been combined to suggest improvements to Cole's IS: utilizing short cycles and simultaneous TS impulse tree decomposition, un-wrapping of message passing iterations Tanner Graph/Forney's Normal Graph symmetry's Graph Authomorphism is a complex yet simple concept. Superior Velasquez-Subramani and Karimi-Banihashemi TS enumerating techniques were supported. The proposed technique under PEG (1008, 504) Mackay code for single thread implementation is 43 times quicker than the original Cole's method and 5027 times (71463 times, multi-thread) faster than the Velasquez-Subramani LP method. For the TS enumerating problem at (2640, 1320), Margulis's code is 37958 times quicker than the suggested Velasquez-Subramani LP approach for single thread implementation, 82 times faster than Karimi-Banihashemi, and 134 times faster than Cole's original solution. On the basis of the creation of QC-LDPC codes, we demonstrate the effects of improved EMD spectrum and increased hamming distance on the TS spectrum and BER/FER error-floor level.
In order to count the number of trapping sets (TS), we changed Cole's Importance Sampling (IS) approach, which led to a message-passing decoder problem. Several concepts have been combined to suggest improvements to Cole's IS: utilizing short cycles and simultaneous TS impulse tree decomposition, un-wrapping of message passing iterations Tanner Graph/Forney's Normal Graph symmetry's Graph Authomorphism is a complex yet simple concept. Superior Velasquez-Subramani and Karimi-Banihashemi TS enumerating techniques were supported. The proposed technique under PEG (1008, 504) Mackay code for single thread implementation is 43 times quicker than the original Cole's method and 5027 times (71463 times, multi-thread) faster than the Velasquez-Subramani LP method. For the TS enumerating problem at (2640, 1320), Margulis's code is 37958 times quicker than the suggested Velasquez-Subramani LP approach for single thread implementation, 82 times faster than Karimi-Banihashemi, and 134 times faster than Cole's original solution. On the basis of the creation of QC-LDPC codes, we demonstrate the effects of improved EMD spectrum and increased hamming distance on the TS spectrum and BER/FER error-floor level.
We modified Cole's Importance Sampling (IS) method for enumerating of Trapping Sets (TS, asymmetric subgraphs) causing an error under message-passing decoder. Proposed Cole's IS modifications based on combination of several ideas: parallel TS impulse tree decomposition using unwrapping of message passing iterations, according short cycles dense and straightforward idea of Tanner Graph/ Forney's Normal Graph symmetry - Graph Authomorphism. Its allowed superior Velasquez-Subramani and Karimi-Banihashemi TS enumerating methods. Particularly proposed method under PEG (1008, 504) Mackay code for single thread implementation 5027-times (71463 times, multi-treads) faster compare to Velasquez-Subramani LP method and 43-times faster compare to original Cole's method. For TS enumerating problem under (2640, 1320) Margulis code compare to Velasquez-Subramani LP method proposed method for single thread implementation 37958 times faster, 82-times faster than Karimi-Banihashemi and 134-times faster than Cole's original method. NVIDIA Titan RTX GPU implementation of proposed method gives a further 2-30 times acceleration. FPGA device providing further acceleration from 1.25 to 44 times. We show on example of QC-LDPC codes construction how improvement of EMD spectrum, increase hamming(code) distance effect on TS spectrum and BER/FER error-floor level.
Purpose of researchis a modification of Cole's importance sampling method for finding trapping sets in an LDPC code to speed up their search.Methods.Cole proposed a method for searching for trapping sets in an LDPC code by using a Monte Carlo method that causes the decoding algorithm to fail at nodes potentially contained in trapping sets. His method makes it possible to accelerate the study of the efficiency of medium-length LDPC codes in the region of large SNRs. The modified method uses the properties of automorphisms of Tanner graphs, which make it possible to exclude a significant number of symbolic nodes from the enumeration. The modified method also provides for an ordered enumeration over subgraphs containing cycles.Results.The proposed method made it possible to speed up the search for trapping sets in Mackay's PEG(1008, 504) LDPC code by 5027 times compared to the Velasquez-Subramani method, and 43 times faster compared to the original Cole method. In the case of (2640, 1320) LDPC Margulis code, the proposed method is 28 times faster than the Velasquez-Subramani quasi-cyclic method and 134 times faster than the original Cole method.Conclusion.The result of experimental studies showed the possibility of using the developed method to improve the connectivity spectrum, increase the code distance of QC-LDPC codes. This made it possible to reduce the probability of a bit error at the decoder output by orders of magnitude at high signal-to-noise ratios in the AWGN channel.
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
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.
The error floor phenomenon observed with LDPC codes and their graph-based, iterative, message-passing (MP) decoders is commonly attributed to the existence of error-prone substructures - variously referred to as near-codewords, trapping sets, absorbing sets, or pseudocodewords - in a Tanner graph representation of the code. Many approaches have been proposed to lower the error floor by designing new LDPC codes with fewer such substructures or by modifying the decoding algorithm. Using a theoretical analysis of iterative MP decoding in an idealized trapping set scenario, we show that a contributor to the error floors observed in the literature may be the imprecise implementation of decoding algorithms and, in particular, the message quantization rules used. We then propose a new quantization method - (q+1)-bit quasi-uniform quantization - that efficiently increases the dynamic range of messages, thereby overcoming a limitation of conventional quantization schemes. Finally, we use the quasi-uniform quantizer to decode several LDPC codes that suffer from high error floors with traditional fixed-point decoder implementations. The performance simulation results provide evidence that the proposed quantization scheme can, for a wide variety of codes, significantly lower error floors with minimal increase in decoder complexity.
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. . . . . . . .