Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Proceedings of Southwest State University

Trapping Sets Search Using the Method of Mixed Integer Linear Programming with a Priori List of Variable Nodes

Vasiliy S. Usatyuk, Егоров Сергей Иванович

Published Mar 1, 2024• 1 citation
Publisher

Abstract

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.

DOI
10.21869/2223-1560-2023-27-4-79-97

Related papers

Mixed Integer Linear Programming Method for Energy-Based Model Trapping Sets Enumerating

Vasiliy S. Usatyuk, Егоров Сергей Иванович

The paper introduces an efficient method for identifying trapping sets in codes on the graphs, employing a mixed linear programming approach. The method guarantees a comprehensive search, essential for nonlinear channels in communication systems, energy-based models, natural language processing DNN, metric learning and other intricate dynamic systems. An in-depth analysis of symmetry and asymmetry properties of dynamic systems, represented by trapping sets TS(a, 0)-codewords and TS(a, b)-pseudocodewords respectively, offers a thorough understanding of their dynamics. Implemented in Python, the proposed method is publicly available on GitHub and supports both the Community Edition version, with restrictions on the number of conditions, and the Commercial Edition CPLEX. The technique involves solving a mixed integer linear programming problem using a predefined list of variable nodes participating in the shortest (short) cycles with small Extrinsic Message Degree values within the code graph. These cycles, akin to topological invariants, represent multidimensional voids formed by code and pseudo-code words. Consequently, the method can be viewed as an approach for constructing topological complexes and calculating topological invariants. The method was applied to search for trapping sets in LDPC codes, utilizing the mathematical linear programming package IBM CPLEX Optimization Studio version 22.1.0.0 The computations ran on a 16-core AMD Ryzen 3950X processor with 128GB KF3200 DDR4 RAM, utilizing 32 threads. In the Margulis code (2640, 1320), the proposed method identified the trapping set TS(6,6) in just 0.29 seconds. Notably, compared to the Velasquez-Subramani method, the proposed method achieved a speedup of 15082 times. Leveraging its high speed and thorough search capabilities, the method successfully identified trapping sets TS(62,16) and TS(52,14) for the first time in the Margulis code (4896, 2474). Finally, employing the proposed method with CPLEX Community Edition version 22.1.1.0, we discovered trapping sets, specifically$TS(102,2)$and$TS(108,4)$, within the Mackay LDPC code (408,204). These findings necessitated a brute-force trapping set search, demanding more than 10101operations.

International Conference on Digital Signal Processing and its Applications (DSPA)•Mar 27, 2024•6 citations

Construction of LDPC Codes Using Cole's Modified Importance Sampling Method

Vasiliy S. Usatyuk, Егоров Сергей Иванович

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.

Proceedings of Southwest State University•Apr 14, 2023•5 citations

Search and weighting for trapping sets in quasi-cyclic codes by multigraph lift and projection method

Vasiliy S. Usatyuk, Yu. O. Kuznetsov, Егоров Сергей Иванович

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.

Proceedings of Southwest State University•Apr 7, 2025•2 citations

Low Error Floor QC-LDPC Codes Construction Using Modified Cole's Trapping Sets Enumerating

Vasiliy S. Usatyuk

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.

International Conference on Digital Signal Processing and its Applications (DSPA)•Mar 29, 2023•4 citations

An Modified Cole's Importance Sampling Method For Low Error Floor QC-LDPC Codes Construction

Vasiliy S. Usatyuk

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.

arXiv:2208.05795•Aug 11, 2022•0 citations

Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming

Wojciech Sułek

An approach to design protograph-based low-density parity-check (LDPC) codes utilizing mixed integer linear programming (MILP) optimization is presented in this paper. The protograph (base graph) cyclic lifting for a class of quasi-cyclic LDPC codes is considered. In general, the short cycles elimination is the primary optimization goal, possibly weighted by a metric of cycles connectivity. A notion of closed walks in the base graph is shown to be a convenient way for representing sources of cycles in the lifted graph. We express the condition for non-existence of a cycle in the lifted graph corresponding to a closed walk in the base graph in the form of a set of linear inequalities. Such inequalities, collected for all closed walks shorter than a desired limit corresponding to girth, form a set of linear constraints. Meanwhile, the longer closed walks can be reflected in a linear objective function of the optimization. The proposed combination of constraints and objective function forms an input to a MILP solver. As a result, a globally optimized code graph can be obtained. The method can be utilized for binary as well as nonbinary LDPC codes. The numerical results show that the constructed codes can outperform similar codes deigned with reference heuristic search methods.

IEEE Access•Dec 12, 2018•10 citations
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.
The paper introduces an efficient method for identifying trapping sets in codes on the graphs, employing a mixed linear programming approach. The method guarantees a comprehensive search, essential for nonlinear channels in communication systems, energy-based models, natural language processing DNN, metric learning and other intricate dynamic systems. An in-depth analysis of symmetry and asymmetry properties of dynamic systems, represented by trapping sets TS(a, 0)-codewords and TS(a, b)-pseudocodewords respectively, offers a thorough understanding of their dynamics. Implemented in Python, the proposed method is publicly available on GitHub and supports both the Community Edition version, with restrictions on the number of conditions, and the Commercial Edition CPLEX. The technique involves solving a mixed integer linear programming problem using a predefined list of variable nodes participating in the shortest (short) cycles with small Extrinsic Message Degree values within the code graph. These cycles, akin to topological invariants, represent multidimensional voids formed by code and pseudo-code words. Consequently, the method can be viewed as an approach for constructing topological complexes and calculating topological invariants. The method was applied to search for trapping sets in LDPC codes, utilizing the mathematical linear programming package IBM CPLEX Optimization Studio version 22.1.0.0 The computations ran on a 16-core AMD Ryzen 3950X processor with 128GB KF3200 DDR4 RAM, utilizing 32 threads. In the Margulis code (2640, 1320), the proposed method identified the trapping set TS(6,6) in just 0.29 seconds. Notably, compared to the Velasquez-Subramani method, the proposed method achieved a speedup of 15082 times. Leveraging its high speed and thorough search capabilities, the method successfully identified trapping sets TS(62,16) and TS(52,14) for the first time in the Margulis code (4896, 2474). Finally, employing the proposed method with CPLEX Community Edition version 22.1.1.0, we discovered trapping sets, specificallyTS(102,2)TS(102,2)TS(102,2)andTS(108,4)TS(108,4)TS(108,4), within the Mackay LDPC code (408,204). These findings necessitated a brute-force trapping set search, demanding more than 10101operations.
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 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.
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.
An approach to design protograph-based low-density parity-check (LDPC) codes utilizing mixed integer linear programming (MILP) optimization is presented in this paper. The protograph (base graph) cyclic lifting for a class of quasi-cyclic LDPC codes is considered. In general, the short cycles elimination is the primary optimization goal, possibly weighted by a metric of cycles connectivity. A notion of closed walks in the base graph is shown to be a convenient way for representing sources of cycles in the lifted graph. We express the condition for non-existence of a cycle in the lifted graph corresponding to a closed walk in the base graph in the form of a set of linear inequalities. Such inequalities, collected for all closed walks shorter than a desired limit corresponding to girth, form a set of linear constraints. Meanwhile, the longer closed walks can be reflected in a linear objective function of the optimization. The proposed combination of constraints and objective function forms an input to a MILP solver. As a result, a globally optimized code graph can be obtained. The method can be utilized for binary as well as nonbinary LDPC codes. The numerical results show that the constructed codes can outperform similar codes deigned with reference heuristic search methods.