Costas array

of order An permutation matrix in which the line segments connecting pairs of ones in the matrix are distinct as vectors, i.e., no two agree in both magnitude and slope. Thus, if and in the matrix, with , , and at least three of these four ordered pairs are distinct, and if equals , then All known (1996) general constructions for Costas arrays (see [a3], [a4], [a5]) involve primitive roots in finite fields (cf. Field). The Welch construction, for every prime , gives a Costas array of order by setting when , where is a primitive root modulo . Removing row and column from this construction leaves a Costas array of order . When is used as the primitive root modulo , the array can be further reduced to order .

In Golomb's construction, if and are any two primitive elements in , for , a Costas array of order is obtained by setting whenever . (The case had been discovered by A. Lempel.) If , then , so that by removing the first row and first column, a Costas array or order is obtained. As shown in [a6], for every one can find primitive roots and (not necessarily distinct) with .

For , or any prime , and for no other finite fields, there is a primitive root with . Thus, in the Lempel construction, , so that if the first two rows and first two columns are removed, a (symmetric) Costas array or order results. For , or any prime , there are primitive roots and with and . In this case, , and . By successive removal of rows and columns Costas arrays of orders , , , and are obtained for these values of .

In some cases a Costas array of order can be obtained from one of order by adjoining a in an exterior corner, i.e., in one of the positions , , , or . Several prime-order examples were obtained in this way from a Welch example of order .

The total number of Costas arrays of order is known (1996) for (see the table), with a local maximum at .'
<tbody> </tbody>    2 2 13 12828 3 4 14 17252 4 12 15 19612 5 40 16 21104 6 116 17 18276 7 200 18 15096 8 444 19 10240 9 760 20 6464 10 2160 21 3536 11 4368 22 2052 12 7852 23 872

For a prime number there are primitive roots, each of which leads to a different Costas array of order . Since can be arbitrarily large, . It has been conjectured, but not proved, that . This would require infinitely often. No case of is yet known, but no examples of Costas arrays of orders , , or have yet been found. (Many larger orders also lack examples.)

J.P. Costas [a1] first proposed these arrays for an application to frequency hopping sonar signals. Let the rows represent equally spaced frequencies, and the columns equal duration time intervals. Then the Costas array specifies a permuted order for the frequencies to be transmitted in consecutive time intervals. As a sonar (or radar) signal this design has an ideal "thumb-tack" ambiguity function (the two-dimensional auto-correlation function in time and frequency). The horizontal (time) shift measures range (the distance to the target) and the vertical (frequency) shift measures the Doppler (the velocity of the target relative to the observer). For any non-zero shift parallel to the coordinate axes a Costas array has at most one "hit" (coincidence of a with a ), and thus gives the least ambiguous reading of the correct range and Doppler in the presence of noise.