Loading [MathJax]/jax/output/HTML-CSS/jax.js

Proposed by Serdar Kadıoğlu, Özgür Akgün

A costas array is a pattern of n marks on an nn grid, one mark per row and one per column, in which the n(n1)/2 vectors between the marks are all-different.

Such patterns are important as they provide a template for generating radar and sonar signals with ideal ambiguity functions.

A model for Costas Array Problem (CAP) is to define an array of variables X1,,Xn which form a permutation. For each length l{1,,n1}, we add nl more variables Xl1 1,,Xln1, whereby each of these variables is assigned the difference of XiXi+l for i{1,,nl}. These additional variables form a difference triangle as shown in the figure below.

Each line of this difference triangle must not contain any value twice. That is, the CAP is simply a collection of all-different constraints on X1,,Xn and Xl1,Xlnl for all l{1,,n1}.

6x6 Costas Array 316254

Costas arrays can be constructed using the generation methods based on the theory of finite fields for infinitely many n. However, there is no construction method for all n and it is, e.g., unknown whether there exists a Costas Array of order 32.

The problem description was taken from [kadioglu2009dialectic] with small adaptations.

Here is a website which contains some more information on the problem: http://datagenetics.com/blog/february22013

Helmut Simonis has slides on Costas Arrays here: http://4c.ucc.ie/~hsimonis/ELearning/costas/slides.pdf