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.
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.
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.
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.
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.
This study shows a new design method of a simulation probability density function (PDF) for a fast frame error rate (FER) evaluation of low-density parity-check (LDPC) codes. It is difficult to evaluate a very low FER of LDPC codes by Monte Carlo simulation methods since it has excellent performance under iterative decoding. Cole et al. proposed a three-step estimation method of the low FER of LDPC codes of moderate block length. By applying the importance sampling method, which is one of the fast simulation methods, the simulation time of the error performance of LDPC codes can be reduced. Another simulation PDF, which can treat more dominant trapping sets (TS) than Cole et al.'s method, is proposed. The selection of the dominant TS as proportional to its probability reduces the number of simulation runs without deteriorating the accuracy of the estimator. Unbiased estimator is given as well as that that of the Cole et al.'s method. Some numerical examples are shown to demonstrate the effectiveness of the proposed method. The simulation time for an LDPC code of length 504 is reduced to 1/10 when we evaluate FER of around 10-14.
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 propose an estimation method of a very low bit error rate (HER) of low-density parity-check (LDPC) codes. No analytical tool is available to evaluate performance of LDPC codes, and traditional Monte Carlo simulation methods can not estimate low HER of LDPC codes due to the limitation of time. Cole et al, show a fast frame error rate simulation method of LDPC codes by applying importance sampling (IS). At first, we extend Cole et aI.'s method to the HER estimation of LDPC codes. Since the simulation time of the HER evaluation version of the Cole et aI.'s method is proportional to the number of total dominant trapping sets used in the simulation, we should appropriately choose the dominant trapping sets to reduce the simulation time. To avoid the difficulty, we propose another simulation method, which selects a dominant trapping set as proportional to its upper bound. Additionally, we show some numerical examples to demonstrate the effectiveness of the proposed method. When we evaluate HER of 10−16, the simulation time of the proposed method is reduced to 1/6.6 of that of the HER evaluation version of the Cole et al.'s method under the condition of the same accuracy of the estimator.