In this paper, both the high-complexity near-ML list decoding and the low-complexity belief propagation decoding are tested for some well-known regular and irregular LDPC codes. The complexity and performance trade-of...In this paper, both the high-complexity near-ML list decoding and the low-complexity belief propagation decoding are tested for some well-known regular and irregular LDPC codes. The complexity and performance trade-off is shown clearly and demonstrated with the paradigm of hybrid decoding. For regular LDPC code, the SNR-threshold performance and error-floor performance could be improved to the optimal level of ML decoding if the decoding complexity is progressively increased, usually corresponding to the near-ML decoding with progressively increased size of list. For irregular LDPC code, the SNR-threshold performance and error-floor performance could only be improved to a bottle-neck even with unlimited decoding complexity. However, with the technique of CRC-aided hybrid decoding, the ML performance could be greatly improved and approached with reasonable complexity thanks to the improved code-weight distribution from the concatenation of CRC and irregular LDPC code. Finally, CRC-aided 5GNR-LDPC code is evaluated and the capacity-approaching capability is shown.展开更多
A new favorable iterative algorithm named as PBiCGSTAB （preconditioned bi-conjugate gradient stabilized） algorithm is presented for solving large sparse complex systems. Based on the orthogonal list, the special tec...A new favorable iterative algorithm named as PBiCGSTAB （preconditioned bi-conjugate gradient stabilized） algorithm is presented for solving large sparse complex systems. Based on the orthogonal list, the special technique of only storing non-zero elements is carried out. The incomplete LU factorization without fill-ins is adopted to reduce the condition number of the coefficient matrix. The BiCGSTAB algorithm is extended from the real system to the complex system and it is used to solve the preconditioned complex linear equations. The locked-rotor state of a single-sided linear induction machine is simulated by the software programmed with the finite element method and the PBiCGSTAB algorithm. Then the results are compared with those from the commercial software ANSYS, showing the validation of the proposed software. The iterative steps required for the proposed algorithm are reduced to about one-third, when compared to the BiCG method, therefore the algorithm is fast.展开更多
Dijkstra algorithm is a theoretical basis to solve transportation network problems of the shortest path, which has a wide range of application in path optimization. Through analyzing traditional Dijkstra algorithm,on ...Dijkstra algorithm is a theoretical basis to solve transportation network problems of the shortest path, which has a wide range of application in path optimization. Through analyzing traditional Dijkstra algorithm,on account of the insufficiency of this algorithm in path optimization,this paper uses adjacency list and circular linked list with combination to store date,and through the improved quick sorting algorithm for weight sorting, accomplish a quick search to the adjacent node,and so an improved Dijkstra algorithm is got.Then apply it to the optimal path search,and make simulation analysis for this algorithm through the example,also verify the effectiveness of the proposed algorithm.展开更多
As part of the digital mine system, a real time emergency route generating algorithm for a large scale metal mine is studied. The tunnel is abstracted and mathematically described by the center line model. A series of...As part of the digital mine system, a real time emergency route generating algorithm for a large scale metal mine is studied. The tunnel is abstracted and mathematically described by the center line model. A series of definitions are made and the center lines are regularized. In order to improve the quality of the final routes, a center line dataset preprocessing is done according to the factors including the slope threshold and the tunnel closed state information, etc. While in preprocessing, the mineshaft and shaft with the steep slope are excluded implicitly. The interface is preserved for point-like objects (e.g. blowers), directions (e.g. wind direction of blowers) and so on. The final path finding algorithm is optimized by the filter operation that the calculation is only performed at the endpoints and hub points, which can further reduce computing data amount. In our experiment, 3 368 nodes out of 22 401 nodes are selected as key nodes, therefore, the data processing amount of the algorithm is reduced to 1/7 and the routes can be found in real time. The algorithm is implemented and integrated into the final digital mine system.展开更多
In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log ...In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.展开更多
How to keep cloud data intact and available to users is a problem to be solved. Authenticated skip list is an important data structure used in cloud data integrity verification. How to get the membership proof of the ...How to keep cloud data intact and available to users is a problem to be solved. Authenticated skip list is an important data structure used in cloud data integrity verification. How to get the membership proof of the element in authenticated skip list efficiently is an important part of authentication. Kaouthar Blibech and Alban Gabillon proposed a head proof and a tail proof algorithms for the membership proof of elements in the authenticated skip list. However, the proposed algorithms are uncorrelated each other and need plateau function. We propose a new algorithm for computing the membership proof for elements in the authenticated skip list by using two stacks, one is for storing traversal chain of leaf node, the other is for storing authentication path for the leaf. The proposed algorithm is simple and effective without needing plateau function. It can also be applicable for other similar binary hash trees.展开更多
Floorplanning is a prominent area in the Very Large-Scale Integrated (VLSI) circuit design automation, because it influences the performance, size, yield and reliability of the VLSI chips. It is the process of estimat...Floorplanning is a prominent area in the Very Large-Scale Integrated (VLSI) circuit design automation, because it influences the performance, size, yield and reliability of the VLSI chips. It is the process of estimating the positions and shapes of the modules. A high packing density, small feature size and high clock frequency make the Integrated Circuit (IC) to dissipate large amount of heat. So, in this paper, a methodology is presented to distribute the temperature of the module on the layout while simultaneously optimizing the total area and wirelength by using a hybrid Particle Swarm Optimization-Harmony Search (HPSOHS) algorithm. This hybrid algorithm employs diversification technique (PSO) to obtain global optima and intensification strategy (HS) to achieve the best solution at the local level and Modified Corner List algorithm (MCL) for floorplan representation. A thermal modelling tool called hotspot tool is integrated with the proposed algorithm to obtain the temperature at the block level. The proposed algorithm is illustrated using Microelectronics Centre of North Carolina (MCNC) benchmark circuits. The results obtained are compared with the solutions derived from other stochastic algorithms and the proposed algorithm provides better solution.展开更多
文摘In this paper, both the high-complexity near-ML list decoding and the low-complexity belief propagation decoding are tested for some well-known regular and irregular LDPC codes. The complexity and performance trade-off is shown clearly and demonstrated with the paradigm of hybrid decoding. For regular LDPC code, the SNR-threshold performance and error-floor performance could be improved to the optimal level of ML decoding if the decoding complexity is progressively increased, usually corresponding to the near-ML decoding with progressively increased size of list. For irregular LDPC code, the SNR-threshold performance and error-floor performance could only be improved to a bottle-neck even with unlimited decoding complexity. However, with the technique of CRC-aided hybrid decoding, the ML performance could be greatly improved and approached with reasonable complexity thanks to the improved code-weight distribution from the concatenation of CRC and irregular LDPC code. Finally, CRC-aided 5GNR-LDPC code is evaluated and the capacity-approaching capability is shown.
文摘A new favorable iterative algorithm named as PBiCGSTAB （preconditioned bi-conjugate gradient stabilized） algorithm is presented for solving large sparse complex systems. Based on the orthogonal list, the special technique of only storing non-zero elements is carried out. The incomplete LU factorization without fill-ins is adopted to reduce the condition number of the coefficient matrix. The BiCGSTAB algorithm is extended from the real system to the complex system and it is used to solve the preconditioned complex linear equations. The locked-rotor state of a single-sided linear induction machine is simulated by the software programmed with the finite element method and the PBiCGSTAB algorithm. Then the results are compared with those from the commercial software ANSYS, showing the validation of the proposed software. The iterative steps required for the proposed algorithm are reduced to about one-third, when compared to the BiCG method, therefore the algorithm is fast.
基金supported by the "Taishan Scholarship" Construction Engineering and Shandong Province Graduate Innovative Project(SDYC08011).
文摘Dijkstra algorithm is a theoretical basis to solve transportation network problems of the shortest path, which has a wide range of application in path optimization. Through analyzing traditional Dijkstra algorithm,on account of the insufficiency of this algorithm in path optimization,this paper uses adjacency list and circular linked list with combination to store date,and through the improved quick sorting algorithm for weight sorting, accomplish a quick search to the adjacent node,and so an improved Dijkstra algorithm is got.Then apply it to the optimal path search,and make simulation analysis for this algorithm through the example,also verify the effectiveness of the proposed algorithm.
基金Project(41161071)supported by the National Natural Science Foundation of China
文摘As part of the digital mine system, a real time emergency route generating algorithm for a large scale metal mine is studied. The tunnel is abstracted and mathematically described by the center line model. A series of definitions are made and the center lines are regularized. In order to improve the quality of the final routes, a center line dataset preprocessing is done according to the factors including the slope threshold and the tunnel closed state information, etc. While in preprocessing, the mineshaft and shaft with the steep slope are excluded implicitly. The interface is preserved for point-like objects (e.g. blowers), directions (e.g. wind direction of blowers) and so on. The final path finding algorithm is optimized by the filter operation that the calculation is only performed at the endpoints and hub points, which can further reduce computing data amount. In our experiment, 3 368 nodes out of 22 401 nodes are selected as key nodes, therefore, the data processing amount of the algorithm is reduced to 1/7 and the routes can be found in real time. The algorithm is implemented and integrated into the final digital mine system.
基金This paper was supported by Ph. D. Foundation of State Education Commission of China.
文摘In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.
基金partially supported by the Fundamental Research Funds for the Central Universities of China under Grant No.2015JBM034the China Scholarship Council Funds under File No.201407095023
文摘How to keep cloud data intact and available to users is a problem to be solved. Authenticated skip list is an important data structure used in cloud data integrity verification. How to get the membership proof of the element in authenticated skip list efficiently is an important part of authentication. Kaouthar Blibech and Alban Gabillon proposed a head proof and a tail proof algorithms for the membership proof of elements in the authenticated skip list. However, the proposed algorithms are uncorrelated each other and need plateau function. We propose a new algorithm for computing the membership proof for elements in the authenticated skip list by using two stacks, one is for storing traversal chain of leaf node, the other is for storing authentication path for the leaf. The proposed algorithm is simple and effective without needing plateau function. It can also be applicable for other similar binary hash trees.
文摘Floorplanning is a prominent area in the Very Large-Scale Integrated (VLSI) circuit design automation, because it influences the performance, size, yield and reliability of the VLSI chips. It is the process of estimating the positions and shapes of the modules. A high packing density, small feature size and high clock frequency make the Integrated Circuit (IC) to dissipate large amount of heat. So, in this paper, a methodology is presented to distribute the temperature of the module on the layout while simultaneously optimizing the total area and wirelength by using a hybrid Particle Swarm Optimization-Harmony Search (HPSOHS) algorithm. This hybrid algorithm employs diversification technique (PSO) to obtain global optima and intensification strategy (HS) to achieve the best solution at the local level and Modified Corner List algorithm (MCL) for floorplan representation. A thermal modelling tool called hotspot tool is integrated with the proposed algorithm to obtain the temperature at the block level. The proposed algorithm is illustrated using Microelectronics Centre of North Carolina (MCNC) benchmark circuits. The results obtained are compared with the solutions derived from other stochastic algorithms and the proposed algorithm provides better solution.
