CUDA Based Search Algorithm For Combinatorial Design And Almost Difference Set Pairs Construction Method

Ideal sequences and sequence pairs are widely used in the field of communication due to their excellent characteristics.Therefore,in the field of coding,the design of ideal sequences and sequence pairs has always been of great concern.However,the difficulty of directly constructing these sequences is significant,so scholars will choose to use methods such as difference set,almost difference set,difference set pairs,and almost difference set pairs to help study sequences and sequence pairs.This thesis mainly uses computer search and mathematical tools such as cyclotmic classes to optimize the combinatorial design search algorithm.By using the algorithm to search for well structured almost difference set pairs,new binary sequence pairs with ideal autocorrelation function values can be obtained using these almost difference set pairs.Firstly,two different combination design search algorithms are proposed,namely the exhaustive search algorithm based on full combination and the search algorithm based on parameters.Analyze the two algorithms separately.The former has simple code writing,simple process,and is not prone to errors.It has a speed advantage when used in situations where the order of the group is small;The latter process is complex and not conducive to parallelization,but the algorithm takes up less space during operation and is flexible to use,making it convenient to optimize using mathematical tools.Secondly,this thesis focuses on parallelization of computationally intensive modules in the algorithm based on CUDA,including parallelization for obtaining combinations and parallelization result judgment modules.For the result judgment module,this thesis proposes a more efficient decision algorithm based on bitwise operation,which is more in line with the characteristics of GPUs.For the results generated by the algorithm,this thesis also designed an algorithm module to remove equivalent results.For the optimization effect of the algorithm,not only are the optimization strategies evaluated from a theoretical perspective,but experiments are also used to compare the running speed of the algorithm.The comparative experiment includes comparing the speed of the algorithm before and after parallelization,as well as comparing the speed of the algorithm after adopting different optimization strategies.Finally,the improved parallelized search algorithm is used to search for almost difference set pairs,and the data obtained from the search is filtered,summarized,and summarized.Some construction methods for almost difference set pairs with a period length of 11 p based on generalized cyclotmic classes of order 2-5 are proposed,expanding the existence range of almost difference set pairs.