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>
|
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.
References
| [a1] | J.P. Costas, "Project medior. A medium-oriented approach to sonar signal processing" , HMED Tech. Publ. R66EMH12 , General Electric (1966) |
| [a2] | S.W. Golomb, H. Taylor, "Two-dimensional synchronization patterns with minimum ambiguity" IEEE Trans. Inform. Theory , 28 (1982) pp. 600–604 |
| [a3] | S.W. Golomb, H. Taylor, "Constructions and properties of Costas arrays" Proc. IEEE , 72 (1984) pp. 1143–1163 |
| [a4] | S.W. Golomb, "Algebraic constructions for Costas arrays" J. Combin. Th. A , 37 (1984) pp. 13–21 |
| [a5] | S.W. Golomb, "The  and  constructions for Costas arrays" IEEE Trans. Inform. Th. , 38 (1992) pp. 1404–1406 |
| [a6] | O. Moreno, J. Sotero, "Computational approach to conjecture A of Golomb" Congressus Numerantium , 70 (1990) pp. 7–16 |
| [a7] | J.P. Costas, "A study of a class of detection waveforms having nearly ideal range-doppler ambiguity properties" Proc. IEEE , 72 (1984) pp. 996–1009 |
Costas array. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Costas_array&oldid=46534