%0 Journal Article
%T Multidimensional Costas Arrays and Their Enumeration Using GPUs and FPGAs
%A Rafael A. Arce-Nazario
%A Jos¨¦ Ortiz-Ubarri
%J International Journal of Reconfigurable Computing
%D 2012
%I Hindawi Publishing Corporation
%R 10.1155/2012/196761
%X The enumeration of two-dimensional Costas arrays is a problem with factorial time complexity and has been solved for sizes up to 29 using computer clusters. Costas arrays of higher dimensionality have recently been proposed and their properties are beginning to be understood. This paper presents, to the best of our knowledge, the first proposed implementations for enumerating these multidimensional arrays in GPUs and FPGAs, as well as the first discussion of techniques to prune the search space and reduce enumeration run time. Both GPU and FPGA implementations rely on Costas array symmetries to reduce the search space and perform concurrent explorations over the remaining candidate solutions. The fine grained parallelism utilized to evaluate and progress the exploration, coupled with the additional concurrency provided by the multiple instanced cores, allowed the FPGA (XC5VLX330-2) implementation to achieve speedups of up to 30¡Á over the GPU (GeForce GTX 580). 1. Introduction A two-dimensional Costas array (2DCA) of size is a permutation such that for every integer , , and , where and , , , implies that . Thus, informally, a size Costas array is defined as matrix containing exactly dots, where every row and column contain exactly one dot and the vectors joining each pair of dots are distinct. Figure 1 illustrates a Costas array of size , both as a matrix and a permutation. The figure also shows the array¡¯s difference triangle, which organizes the differences between the various permutation digits in rows where each row corresponds to a fixed . By definition, each row in the difference triangle of a Costas array must consist of unique numbers. Figure 1: The Costas array (1, 3, 2, 5, 6, and 4), its matrix and permutation representations. The difference triangle confirms that this is a Costas array since each row consists of unique numbers. Their definition implies that Costas arrays have perfect autocorrelation (autocorrelation = 1), which makes them useful in communications where signals must be recoverable even in the presence of considerable noise. Costas arrays are useful in many security and communication applications, such as remote object recognition and optical communications [1]. Furthermore, some special cases of Costas arrays can be used for digital watermarking [2]. Costas arrays with dimensions higher than two were introduced in 2008 by Drakakis [3]. These arrays maintain perfect autocorrelation, which broadens their applicability in optical communications, for example, 3D optical orthogonal codes [4]. Multidimensional periodic Costas arrays
%U http://www.hindawi.com/journals/ijrc/2012/196761/