What is a Costas array?

Jordan Bell
April 3, 2014

1 Introduction

To find the speed and distance of a moving object relative to an observer, a signal with a known frequency is sent from the observer towards the object. It reflects off the object, and the reflected signal has a new frequency, due to the Doppler effect. Knowing the frequencies of the emitted and reflected signals, the speed of the moving object relative to the observer can be determined. Knowing the time between emitting the signal and receiving the reflected signal, the distance of the moving object to the object can be determined. See [2, p. 74].

Let’s say we have a stationary observer, and an object is moving radially away from the observer with a constant speed. One wants to find the speed v of the moving object and its distance d from the observer.

Suppose that at times t1,,tn signals are sent from the observer to the moving object and that the ith signal takes time δi to hit the object. At times t1,,tn let the corresponding distances of the object be d1,,dn. We note that di=d1+(ti-t1)v. Suppose that the signal speed is c. The first signal hits the object when δ1c-d1=δ1v, hence when


The ith signal hits the object when δic-di=δiv, hence when


Supposing that (ti-t1)v is negligible compared to d1, we can say that approximately δ1==δn; write δ=δ1==δn.

If the emitted signals have frequencies e1,,en and the reflected signals have frequencies r1,,rn, by the Doppler shift we have ri=ei1-v/c1+v/c [2, p. 4]. Thus the frequency shift for each signal is


We assume that the set of frequencies is narrowband, so that approximately e1==en. Hence the frequency shifts are approximately equal; write ξ=-2ve1c==-2venc.

Then the frequency of the signal received at time ti+δ will be equal to the sum of ξ and the frequency of the signal emitted at time ti. Let e(t) be the frequency of the signal emitted at time t, and let r(t) be the frequency of the reflected signal received at time t. So r(ti+δ)=e(ti)+ξ for each i=1,,n.

Let’s use units such that the times t1,,tn are integers. We define the cross-correlation of the signals e and r by


where δi,j here is the Kronecker delta. For t other than t1,,tn and t other than t1+δ,,tn+δ, it is convenient to take respectively e(t) and r(t) to be undefined rather than equal to 0. When either e(t) or r(t) is undefined the Kronecker delta will then be 0. Then

Ce,r(v,h) = i=-δe(i),r(i+v)-h
= i=-δe(i+δ-v),r(i+δ)-h
= i=-δe(i+δ-v),e(i)+ξ-h
= i=-δe(i),e(i-δ+v)+ξ-h
= Ce,e(v-δ,h-ξ).

Certainly Ce,e(v,h)Ce,e(0,0)=n for all v,h. Thus Ce,r(v,h)Ce,r(δ,ξ)=n for all v,h.

We wish to find


For any 1j<kn, let v=tk-tj and h=e(tk)-e(tj).

Ce,e(v,h) = Ce,e(tk-tj,e(tk)-e(tj))
= i=-δe(i),e(i+tk-tj)-e(tk)+e(tj)
= 1,

so max(v,h)(0,0)Ce,e(v,h)1.

We want to figure out δ and ξ by knowing Ce,r(v,h) for all v,h. If we have that max(v,h)(0,0)Ce,e(v,h)=1, then either (v,h)=(δ,ξ) and Ce,r(v,h)=n, or (v,h)(δ,ξ) and Ce,r(v,h)1, that is, the autocorrelation at the pair (δ,ξ) that we wish to find is as sharply distinguished as possible from the autocorrelation at the other time-frequency pairs (v,h).

2 Mathematics

Define a new sequence f by


The sequence f is a normalization of the sequence e. One quickly checks that max(v,h)(0,0)Ce,e(v,h)=1 is equivalent to max(v,h)(0,0)Cf,f(v,h)=1.

Let T={(i,f(i)):i=1,,n}2. The condition max(v,h)(0,0)Cf,f(v,h)=1 holds if and only if |T(T+(v,h))|1 for all (v,h)(0,0).


A Costas sequence of length n is a sequence f(1),,f(n) of length n such that if T={(i,f(i)):i=1,,n}, then |T(T+(v,h))|1 for all (v,h)(0,0). We call the set T a Costas array.

This can also be said in the following way. For 1i1i2n and 1i3i4n, if (i1-i2,f(i1)-f(i2))=(i3-i4,f(i3)-f(i4)) then i1=i3 and i2=i4.

Drakakis [1] gives a survey of Costas arrays.

3 Generalizations

Now that we have detached Costas sequences from the time-frequency setting in which they originate, we can investigate them as mathematical objects, and also investigate modifications of Costas sequences.

Let [n]={1,,n}. A Costas sequence f of length n is a bijection f:[n][n] that satisfies the condition on overlapping translates.

Moran [3]


  • [1] K. Drakakis (2006) A review of Costas arrays. J. Appl. Math. 2006, pp. 1–32. Note: Article ID 26385 Cited by: §2.
  • [2] N. Levanon and E. Mozeson (2004) Radar signals. John Wiley & Sons. Cited by: §1, §1.
  • [3] B. Moran (2001) Mathematics of radar. In Twentieth Century Harmonic Analysis - A Celebration, J. S. Byrnes (Ed.), pp. 295–328. Note: NATO Science Series, II. Mathematics, Physics and Chemistry - Vol. 33 Cited by: §3.