Research On Costas Arrays Exhaustive Search Algorithms

Costas arrays have been widely used in wireless communications,radar and telemetry due to ideal auto-correlation property.Based on a brief introduction to the origin of the Costas arrays and the understanding of the structure of arrays,the paper discusses two methods to obtain Costas arrays,namely the finite field construction method and exhaustive search method.The paper discusses the advantages and disadvantages of these two methods,and focuses on how to search for Costas arrays by exhaustive method.The first research point of the paper is the Costas arrays search algorithm based on vectors.Aiming at the shortcomings of the exhaustive search algorithm based on difference matrix,this paper proposes a Costas arrays search algorithm based on vectors.Firstly,judging whether the permutation matrix conforms to the Costas arrays judgment criterion while judging the permutation matrix,which overcomes the shortcomings of backtracking the permutation matrix and then calculating the difference matrix,removes unnecessary calculations,and reduces redundancy.Secondly,using the characteristics of Costas arrays,a new vector-based Costas arrays criterion is proposed to determine whether a permutation matrix is a Costas arrays.That is,there are no two identical vectors in any one Costas arrays.The algorithm proposed in this paper simplifies the search process,reduces the time complexity,and the search speed is greatly improved.The second research point of the paper is the optimization of the Costas arrays search algorithm based on vectors.By studying the structural characteristics of the double circular linked list and the Costas arrays,the use of the double circular linked list can conveniently solve the problem of generating a permutation matrix and judging whether it is conflicted with the previous rows.All column values and the order value are combined into a double circular linked list.The column value that can be placed in each row can only be obtained from the double circular linked list.Once the value is obtained,it is removed from the double circular linked list,so that the following rows can only be obtained values from the remaining column values,avoiding the comparison with previous rows each time,which is beneficial to the improvement of the program search speed.Secondly,the symmetry of the Costas arrays is used to further simplify the search process and speed up the search process.The third research point of the paper is the parallel search of the Costas arrays.In a multi-core processor,threads are queued up and then fed to the multiple cores on the CPU to be processed in parallel.The thread pool technology can be used to implement the parallel search algorithm of Costas arrays,and atomic operations are used to solve the competition problem between threads.The parallel search algorithm further accelerates the search process of the arrays,making it possible to search for higher order Costas arrays.