In mathematics, a Costas array can be regarded geometrically as a set of n points lying on the squares of a n×n checkerboard, such that each row or column contains only one point, and that all of the n(n − 1)/2 displacement vectors between each pair of dots are distinct. This results in an ideal 'thumbtack' auto-ambiguity function, making the arrays useful in applications such as sonar and radar. Costas arrays can be regarded as two-dimensional cousins of the one-dimensional Golomb ruler construction, and, as well as being of mathematical interest, have similar applications in experimental design and phased array radar engineering.
Contents
Costas arrays are named after John P. Costas, who first wrote about them in a 1965 technical report. Independently, Edgar Gilbert also wrote about them in the same year, publishing what is now known as the logarithmic Welch method of constructing Costas arrays.
Numerical representation
A Costas array may be represented numerically as an n×n array of numbers, where each entry is either 1, for a point, or 0, for the absence of a point. When interpreted as binary matrices, these arrays of numbers have the property that, since each row and column has the constraint that it only has one point on it, they are therefore also permutation matrices. Thus, the Costas arrays for any given n are a subset of the permutation matrices of order n.
Arrays are usually described as a series of indices specifying the column for any row. Since it is given that any column has only one point, it is possible to represent an array one-dimensionally. For instance, the following is a valid Costas array of order N = 4:
There are dots at coordinates: (1,2), (2,1), (3,3), (4,4)
Since the x-coordinate increases linearly, we can write this in shorthand as the set of all y-coordinates. The position in the set would then be the x-coordinate. Observe: {2,1,3,4} would describe the aforementioned array. This makes it easy to communicate the arrays for a given order of N.
Known Arrays
Welch
A Welch–Costas array, or just Welch array, is a Costas array generated using the following method, first discovered by Edgar Gilbert in 1965 and rediscovered in 1982 by Lloyd R. Welch. The Welch–Costas array is constructed by taking a primitive root g of a prime number p and defining the array A by
Example:
3 is a primitive element modulo 5.
31 = 3 32 = 9 = 4 (mod 5) 33 = 27 = 2 (mod 5) 34 = 81 = 1 (mod 5)Therefore, [3 4 2 1] is a Costas permutation. More specifically, this is an exponential Welch array. The transposition of the array is a logarithmic Welch array.
The number of Welch–Costas arrays which exist for a given size depends on the totient function.
Lempel–Golomb
The Lempel–Golomb construction takes α and β to be primitive elements of the finite field GF(q) and similarly defines