What is a Costas array?

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 $t_1,\mathrm{\dots },t_n$ signals are sent from the observer to the moving object and that the $i$th signal takes time ${\delta }_i$ to hit the object. At times $t_1,\mathrm{\dots },t_n$ let the corresponding distances of the object be $d_1,\mathrm{\dots },d_n$. We note that $d_i=d_1+(t_i-t_1)v$. Suppose that the signal speed is $c$. The first signal hits the object when ${\delta }_{1}c-d_1={\delta }_{1}v$, hence when

$${\delta }_1=\frac{d_1}{c-v}=\frac{d_1}{c}\frac{1}{1-\frac{v}{c}}=\frac{d_1}{c}+O(c^{-2}).$$

The $i$th signal hits the object when ${\delta }_{i}c-d_i={\delta }_{i}v$, hence when

$${\delta }_i=\frac{d_i}{c-v}=\frac{d_i}{c}\frac{1}{1-\frac{c}{v}}=\frac{d_i}{c}+O(c^{-2})=\frac{d_1}{c}+\frac{(t_i-t_1)v}{c}+O(c^{-2}).$$

Supposing that $(t_i-t_1)v$ is negligible compared to $d_1$, we can say that approximately ${\delta }_1=\mathrm{\cdots }={\delta }_n$; write $\delta ={\delta }_1=\mathrm{\cdots }={\delta }_n$.

If the emitted signals have frequencies $e_1,\mathrm{\dots },e_n$ and the reflected signals have frequencies $r_1,\mathrm{\dots },r_n$, by the Doppler shift we have $r_i=e_i\cdot \frac{1-v/c}{1+v/c}$ [2, p. 4]. Thus the frequency shift for each signal is

$$r_i-e_i=-2v\frac{e_i}{c+v}=-\frac{2v{e}_i}{c}+O(c^{-2}).$$

We assume that the set of frequencies is narrowband, so that approximately $e_1=\mathrm{\cdots }=e_n$. Hence the frequency shifts are approximately equal; write $\xi =-\frac{2v{e}_1}{c}=\mathrm{\cdots }=-\frac{2v{e}_n}{c}$.

Then the frequency of the signal received at time $t_i+\delta$ will be equal to the sum of $\xi$ and the frequency of the signal emitted at time $t_i$. 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(t_i+\delta )=e(t_i)+\xi$ for each $i=1,\mathrm{\dots },n$.

Let’s use units such that the times $t_1,\mathrm{\dots },t_n$ are integers. We define the cross-correlation of the signals $e$ and $r$ by

$$C_{e,r}(v,h)=\sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}{\delta }_{e(i),r(i+v)-h},$$

where ${\delta }_{i,j}$ here is the Kronecker delta. For $t$ other than $t_1,\mathrm{\dots },t_n$ and $t$ other than $t_1+\delta ,\mathrm{\dots },t_n+\delta$, 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

$C_{e,r}(v,h)$ $=$ ${\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}{\delta }_{e(i),r(i+v)-h}$

$=$ ${\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}{\delta }_{e(i+\delta -v),r(i+\delta )-h}$

$=$ ${\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}{\delta }_{e(i+\delta -v),e(i)+\xi -h}$

$=$ ${\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}{\delta }_{e(i),e(i-\delta +v)+\xi -h}$

$=$ $C_{e,e}(v-\delta ,h-\xi ).$

Certainly $C_{e,e}(v,h)\le C_{e,e}(0,0)=n$ for all $v,h$. Thus $C_{e,r}(v,h)\le C_{e,r}(\delta ,\xi )=n$ for all $v,h$.

We wish to find

$$\underset{(v,h)\ne (0,0)}{\max }{C}_{e,e}(v,h).$$

For any , let $v=t_k-t_j$ and $h=e(t_k)-e(t_j)$.

$C_{e,e}(v,h)$ $=$ $C_{e,e}(t_k-t_j,e(t_k)-e(t_j))$

$=$ ${\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}{\delta }_{e(i),e(i+t_k-t_j)-e(t_k)+e(t_j)}$

$\ge$ ${\delta }_{e(t_j),e(t_j+t_k-t_j)-e(t_k)+e(t_j)}$

$=$ $1,$

so ${\max }_{(v,h)\ne (0,0)}{C}_{e,e}(v,h)\ge 1$.

We want to figure out $\delta$ and $\xi$ by knowing $C_{e,r}(v,h)$ for all $v,h$. If we have that ${\max }_{(v,h)\ne (0,0)}{C}_{e,e}(v,h)=1$, then either $(v,h)=(\delta ,\xi )$ and $C_{e,r}(v,h)=n$, or $(v,h)\ne (\delta ,\xi )$ and $C_{e,r}(v,h)\le 1$, that is, the autocorrelation at the pair $(\delta ,\xi )$ 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

$$f(i)=|\{1\le j\le n:e(t_j)\le e(t_i)\}|,1\le i\le n.$$

The sequence $f$ is a normalization of the sequence $e$. One quickly checks that ${\max }_{(v,h)\ne (0,0)}{C}_{e,e}(v,h)=1$ is equivalent to ${\max }_{(v,h)\ne (0,0)}{C}_{f,f}(v,h)=1$.

Let $T=\{(i,f(i)):i=1,\mathrm{\dots },n\}\subset {\mathbb{Z}}^2$. The condition ${\max }_{(v,h)\ne (0,0)}{C}_{f,f}(v,h)=1$ holds if and only if $|T\cap (T+(v,h))|\le 1$ for all $(v,h)\ne (0,0)$.

Definition.

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

This can also be said in the following way. For $1\le i_1\le i_2\le n$ and $1\le i_3\le i_4\le n$, if $(i_1-i_2,f(i_1)-f(i_2))=(i_3-i_4,f(i_3)-f(i_4))$ then $i_1=i_3$ and $i_2=i_4$.

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,\mathrm{\dots },n\}\subset \mathbb{Z}$. A Costas sequence $f$ of length $n$ is a bijection $f:[n]\to [n]$ that satisfies the condition on overlapping translates.

Moran [3]