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.
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.
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 to develop a new high-speed method for searching trappin sets in graph codes, ensuring the completeness of the search. Methods. There are two approaches to finding trappin sets. The first, based on the Monte Carlo method with a biased probability estimation using Importance Sampling, involves the use of a decoder. The advantage of this approach is its high performance. The disadvantages are the dependence on decoder parameters and channel characteristics and the finite probability of missing trappin sets. The second approach is based on the use of linear programming methods. The advantage of this approach is the completeness of the resulting list of trappin sets, due to its independence from the decoder parameters and channel characteristics. The disadvantage of this approach is its high computational complexity. In the article, within the framework of the second approach, a new method for searching trappin sets with less computational complexity is proposed. The method involves solving a mixed integer linear programming problem using an a priori list of code vertices participating in the shortest cycles in the code graph. Results.Using the proposed method, a search for trappin sets was performed for several low-density codes. For this purpose, the mathematical linear programming package IBM CPLEX version 12.8 was used, which was run on 32 threads of a 16-core AMD Ryzen 3950X processor with 32GB of RAM (DDR4). In the Margulis code (2640, 1320), using the proposed method, the trappin set TS(6,6) was found in a time of 0.53 s. The speedup provided by the method proposed in the paper compared to the Velazquez-Subramani method is 8252.415 times. Thanks to the high speed and completeness of the search, trappin sets were found for the first time TS(62,16) and TS(52,14) in the Margulis code (4896, 2474 ). Conclusion.The paper proposes a new method for searching trapping sets by solving a mixed integer linear programming problem with an a priori list of code. The method is fast and provides completeness of the search.
Purpose of research is to develop a new high-speed method for searching for trapping sets, and a new method for estimating the probability of errors caused by these trapping sets for quasi-cyclic codes with a circulant size that is not a prime number. Methods. The proposed method for searching for trapping sets uses the algebraic properties of quasi-cyclic codes on graphs. Using the graph lifting and projection operations, the problem of searching for trapping sets is transferred to a higher-dimensional space, where trapping sets are more distinguishable. The proposed method for estimating the probability of errors based on selection by importance, in comparison with the previously proposed Cole method, allows parallelization of calculations without the need to duplicate tables. This approach reduces the amount of required memory many times and allows calculations to be performed using separated indices. Results. The proposed method of searching for trapping sets is convenient for hardware implementation, in particular, on accelerator boards using FPGAs. For its implementation, less than half of the SLR (super logic regions) chiplet of the BittWare XUP-P3R accelerator (in a configuration with 128 GB of DDR4 RAM) or the AMD Alveo U200/VCU1525 accelerator (64 GB of DDR4 RAM) is sufficient. This, combined with reduced requirements for RAM volume, allows placing 5 execution units on the AMD Virtex UltraScale+ XCVU9P FPGA [51] crystal instead of 2x, required for the modified Cole method. At the same time, the search acceleration for a matrix with a circulant size of 128 will be 2.5 times. The application of the proposed method for estimating the probability of errors caused by trapping sets provides a 5.3-fold acceleration compared to the Cole method for a quasi-cyclic code with a circulant size of 2048. The proposed method allows one to estimate the noise immunity of the code over the entire range of the signal-to-noise ratio. Conclusion. The proposed method of searching for trapping sets has high performance and ensures completeness of the search. The proposed method of estimating the probability of errors caused by these trapping sets also has high performance.
We discuss error floor asympotics and present a method for improving the performance of low-density parity check (LDPC) codes in the high SNR (error floor) region. The method is based on Tanner graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. The proposed method can be modified to construct convolutional LDPC codes also. The method is illustrated by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm. Decoding results on AWGN channel are also presented to illustrate that optimizing codes for one channel/decoding algorithm can lead to performance improvement on other channels.
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.