# Cross-Correlation Properties of Costas Arrays and Their Images under Horizontal and Vertical Flips

Authors: Konstantinos Drakakis; Rod Gow; John Healy; Scott Rickard
Journal: Mathematical Problems in Engineering
 (2008)

---

## Abstract

We consider the cross-correlation of a Costas array with
its image under a horizontal and/or a vertical flip. We propose and prove several bounds on the maximal
cross-correlation and on its value at the origin, for both general
Costas arrays and for algebraically constructed ones.


---

## Body

## 1. Introduction

Costas arrays  were  introduced as  frequency hopping
patterns with ideal autoambiguity properties by Dr. Costas [1, 2], in an effort to improve
SONAR performance. Unable to find a general construction technique himself, he
approached Professor Solomon Golomb, who published [3] and proved [4] two generation techniques
for Costas arrays, both based on the theory of finite fields, known as the
Welch and the Golomb-Lempel methods, respectively. These
are still the only general construction methods for Costas arrays available
today.In multiuser and multiplexing systems it is desirable
that the signals used have low cross-correlation, in order to minimize
cross-talk. While Costas arrays are known for (and, indeed, defined by) their
ideal autocorrelation, they typically exhibit poor cross-correlation.
Subfamilies of Costas arrays with low cross-correlation are, therefore,
particularly suitable for such applications. In this paper, we examine the
cross-correlation of pairs of Costas arrays related by a horizontal and/or a
vertical flip, in order to identify array pairs with good cross-correlation
properties. Such a small family will be sufficient in some applications, for
example, when a small number of SONARs/RADARs (4 or less) operate in the same
geographical area (otherwise larger families will need to be considered, but
this study lies outside the scope of this paper).Regarding the layout of the paper, in Section2 we
give the definition of Costas arrays and describe the construction methods
available. In Section 3, we review the literature on cross-correlation
properties of Costas arrays. In Section 4, we prove the reflective symmetry
property of Welch Costas arrays. Section 5 states and proves bounds on the
cross-correlation of pairs of Costas arrays in the same
family.


## 2. Costas Arrays: Definition and Algebraic Constructions

Definition 2.1.
Let[n]:={1,…,n},n∈ℕ and consider a bijection f:[n]→[n];f is a Costas permutation if and only if
for all i,j,k such that 1≤i,j,i+k,j+k≤n,(2.1)f(i+k)−f(i)=f(j+k)−f(j)⇒i=jork=0.A
Costas array Af is the permutation  array corresponding to a
Costas permutation f.
This correspondence is a matter of convention: we choose here the convention
that the jth element of the permutation indexes the
position of the (unique) 1 in the jth column of the array, j∈[n],
counting from top to bottom in the usual array convention: f(i)=j⇔aj,if=1.
It is customary to refer to (and denote) the 1s of a permutation array as
“dots” and to 0s as “blanks.” Definition 2.1 is equivalent to the statement
that all distance vectors (f(i)−f(j),i−j),
where i>j,
between pairs of dots in a Costas array are distinct (note that we take the
second coordinate to be nonnegative).An example Costas array is shown in the
top left of Figure1. Note that the image of a Costas array under rotation by 90°,
horizontal or vertical flips, and transposition is still a Costas array: each
Costas array generates a family of eight members (or four, if the array is
symmetric) also shown in the figure. The notation used signifies the generation
of this family using two operators: R,
a 90°  rotation counterclockwise (CCW), and T,
a vertical flip. We also define for convenience S=R2T to be the horizontal flip, in which case we
also have that R2=ST=TS,
the double (horizontal and vertical) flip. The numbers under each array
correspond to the permutation indexing it.Labeling of
rotations and reflections of a Costas array.I,
the original array; R,
a   90° rotation CCW; ST=R2,
a  180° rotation; R3,
a 270° rotation CCW; RT,
a reflection about the main antidiagonal; S=R2T,
a horizontal flip; R3T,
a reflection about the main diagonal; and T,
a vertical flip.
(a)(b)Every Costas array of sizen≤27 has been found by exhaustive computer search
[5–7]: they add up to about 150
000 arrays in total.The two known construction methods for Costas arrays
are based on finite field techniques; each one has several submethods/variants
[3, 4, 8]. In the sequel we will work
exclusively with the main methods.Theorem 2.2  (Welch constructionW1(p,α,c)).
Letp be a prime, let α be a primitive root of the finite field 𝔽(p) of p elements, and let c∈[p−1]−1 be a constant; then, the function f:[p−1]→[p−1] where f(i)=αi−1+cmodp is a bijection with the Costas property.The reason for the presence of −1 in the exponent is that when c=0,
1 is a fixed point f(1)=1.
We refer to arrays generated with c≠0 as circular shifts of the array generated by c=0 for the same p and α.
Welch Costas arrays have antireflective symmetry (see below, and see
also [9]).Definition 2.3.
Letf:[2n]→[2n];f has  antireflective symmetry if
and only if
(2.2)f(n+i)+f(i)=2n+1,i∈[n],which means, in other words,
that  the right half of Af is the vertical flip of the left half.Theorem 2.4  (Golomb constructionG2(p,m,a,b)).
Letp be a prime, m∈ℕ,
and let α,β be primitive roots of the finite field 𝔽(pm) of q=pm elements; then, the function f:[q−2]→[q−2] where αi+βf(i)=1 is a bijection with the Costas property.Ifα=β,
the array is known as a Lempel Costas array, and is symmetric about the
main diagonal.


## 3. Cross-Correlations of Costas Arrays

Definition 3.1.
Letf,g:[n]→[n],n∈ℕ,
and let u,v∈ℤ;
the cross-correlation between f and g at (u,v) is defined as(3.1)Ψf,g(u,v)=|{(f(i)+u,i+v):i∈[n]}∩{(g(i),i):i∈[n]}|.In
other words, in order to find the cross-correlation of two Costas arrays Af and Ag of order n at (u,v),
we place the two arrays on top of each other, slide the first v columns horizontally and u rows vertically, and count the number of pairs
of dots that overlap. We will also use the notation ΨAf,Ag instead of Ψf,g.There are few previous works on cross-correlations of
Costas arrays in the literature. The closest to the subject of this paper is
O'Carroll et al. [10]
(further details about its relevance to the present work will be given in
Section 5). Titlebaum and
Maric  [11] proved that the maximal cross-correlation of two
Welch or Lempel Costas arrays generated from reciprocal primitive roots of an
odd prime is 2. They also proved that the upper   bound on the maximum of the
cross-correlation of two Welch Costas arrays of order n is n/2,
and established that primes of certain forms had good or bad cross-correlation
bounds, for example, they showed that the upper bound on the maximum of the
cross-correlation of a pair of Welch Costas arrays is realized for primes
equivalent to 1 modulo 4.Drumheller and Titlebaum [12] derived upper bounds on the maximal cross-correlation
of two Golomb or two Welch Costas arrays, both in terms of the relative powers
of the generating primitive elements.Rickard has previously proposed that the upper bound
on the maximal cross-correlation of a pair of Golomb arrays of ordern,
taken over all such possible pairs of different arrays, is at most (n−1)/2  [13]. He also proposed that (a) for primes p of the form 2r+1,r prime (known as safe or Germain primes), this
quantity exhibits local minima, and that (b) the upper bound on the maximal
cross-correlation of a pair of Golomb arrays of order p−2,
taken over all such possible pairs of different arrays, is one less than the
corresponding quantity for pairs of Welch arrays of order p−1,
taken over all pairs of different arrays that are not circular shifts of each
other, as long as p is not a safe prime.Finally, Etzion has demonstrated that the maximum of
the cross-correlation of any Costas array with its image under rotation by180∘ is exactly 2 [14].


## 4. A Symmetry Property of the Welch Arrays

Welch Costas arrays, as mentioned above, have
anti-reflective symmetry (see Definition2.3), also known as glide-reflection
symmetry (G-symmetry) [14]. For completeness, we present a proof of this
property.Theorem 4.1.
A Welch Costas array has
antireflective symmetry.Proof.
Consider
the  Welch Costas permutationf generated by α in 𝔽(p);
then, for all i∈[(p−1)/2],(4.1)f(i)+f(i+p−12)=α+i−1+c+α(p−1)/2+i−1+c=α+i−1+c+p−αi−1+c=p,in view of the  fact that α(p−1)/2≡−1modp.
This completes the proof.We will make use of this property later in the paper.
It should be noted that this symmetry does not characterize the Welch Costas
arrays, that is, there exist non-Welch arrays with this property. Some
conditions on the existence of arrays with antireflective symmetry were
established in [14].


## 5. Proof of Some Correlation Bounds

In this
section we present upper bounds on the cross-correlation values of Costas
arrays related by a flip. More specifically, we divide our results in two
groups: those dealing with the maximum of the cross-correlation and those
dealing with the cross-correlation at the origin.


### 5.1. Bounds on Cross-Correlation Maximum

Freedman and Levanon [15] proved that, for n>3,
the cross-correlation between any two arrays of the same size will have at
least 2 hits. We present a special case where the
cross-correlation between a pair of arrays is exactly 2: the cross-correlation
between any Costas array and its 180° rotation has a maximum value of 2.Theorem 5.1.
LetI be a Costas array of order n>1;
then max(u,v)ΨI,R2(u,v)=2.Proof.
The key observation is that a
rotation by180° generates a Costas array whose distance
vectors are the same as in the original array: letting two dots lie at A=(f(i),i),B=(f(j),j),
where i>j,
their images in the rotated array lie at A′=(n+1−f(i),n+1−i),B′=(n+1−f(j),n+1−j),n being the order of the array. The distance
vectors BA and A′B′ are equal: (f(i),i)−(f(j),j)=(f(i)−f(j),i−j) and (n+1−f(j),n+1−j)−(n+1−f(i),n+1−i)=(f(i)−f(j),i−j).
It follows that a shift will align these pairs, whence max(u,v)ΨI,R2(u,v)≥2 (but note that the shift aligns A with B′ and B with A′).
Assume now that, for this given shift, a third pair of
dots become aligned as well, sayC and K,
where C is a point in I and K a point in R2:
then K has a pre-image in I,
say a point k.
We claim that the points A,B,C,
and k form a parallelogram, violating the Costas
property: indeed, by the triple alignment we get A′K=BC and B′K=AC,
while, by the observation above, A′K=kA and B′K=kB.
It follows that BC=kA,AC=kB,
hence AkBC is a parallelogram and the proof is complete.As mentioned earlier, this result has also been
derived by Etzion ([14, Theorem 2]); we chose to present it here for
completeness, offering a more concise proof. O'Carroll et al. [10] sketched a proof that the
maximal cross-correlation of any two amongst a Golomb array and its S,T,
and ST flips is identically 2.We now prove two bounds for Welch Costas arrays of
ordern:
first, we show that the peak of the cross-correlation of a Welch Costas array
and its vertical flip T is n/2.
Then we consider the case of a Welch Costas array and its horizontal flip S which yields a rather better result.Theorem 5.2.
For any antireflective Costas
arrayI of (even) order n and its vertical flip T,(5.1)max(u,v)ΨI,T(u,v)=n2.In particular, the result holds
true for any Welch Costas array generated in 𝔽(p) (where n=p−1).Proof.
We prove
this property by considering the form of three distinct regions of the
cross-correlation. Letf be the permutation corresponding to i.
Then, we show that
(i)
for allu,ΨI,T(u,v)≤1 when v≠n/2,(ii)
ΨI,T(u,n/2)=0 when u≠0,(iii)
ΨI,T(0,n/2)=n/2. Fixing u and v,
we find the number of pairs (i,j) for which(5.2)(f(i),i)=(u,v)+(n+1−f(j),j)⇒f(v+j)=u+n+1−f(j)=u+f(j±n2),where “+” is chosen if j≤n/2,
and “−” otherwise.
Assumingv≠n/2,
this equation has at most one solution j because of the Costas property. Assuming v=n/2,
the equation becomes u=0,
which is satisfied for no j if we choose u≠0,
but is satisfied for all j∈[n/2],
that is n/2 values of j,
if we choose u=0.
This completes the proof.Theorem 5.3.
For any Welch Costas arrayI and its horizontal flip S,(5.3)max(u,v)ΨI,S(u,v)=2.Proof.
Letf be the Welch permutation generated in 𝔽(p) by the primitive root α and the parameter c.
For fixed values of u and v,
we need to find the number of pairs (i,j) for which(5.4)(αi−1+cmodp,i)=(u,v)+(αp−j−1+cmodp,j)whence we get the two
equations(5.5)αi−1+cmodp=u+αp−j−1+cmodp,i=v+j,namely(5.6)αv+j−1+cmodp=u+αp−j−1+cmodp.If this equation is true, it is
also true modp,
whence(5.7)αv+j−1+c≡u+αc−jmodp⟺αv−1+cα2j−ugj−αc≡0modp.Setting αj=x,
we obtain(5.8)αv−1+cx2−ux−αc≡0modp.This is an equation of the
second degree in a field, and therefore it has at most 2 solutions for x and thus for j.
Note, however, that not all solutions of this equation need actually also be
solutions of (5.6). Note also that, as both I and S are Costas arrays, Freedman and Levanon's
result [15] guarantees
that there are two solutions for at least one pair of values of u and v.Theorem 5.4.
For any Costas arrayI of order n>1,(5.9)max(u,v)ΨI,G(u,v)≤n2orn−12,depending on whether n is even or odd, respectively, where G is either S or T.Proof.
Assumen even, and assume there exists a shift for
which a subset A of (n/2)+1 dots of I can be aligned with a subset W of equally many dots of T.I also contains a subset B of (n/2)+1 dots, namely the pre-image of W:
the distance vectors in B are the vertical flips of the distance vectors
in A.
Observe now that, as no two dots of a Costas array lie
in the same row or column, each distance vector is different from its vertical
flip. AssumeA contains both a vector x and its vertical flip x′,
where, without loss of generality, the starting point of x lies to the left of the starting point of x′.
Then B contains both vectors as well, but now the
starting point of x lies to the right of the starting point of x′.
This implies that the two pairs of equal vectors cannot both be collocated,
hence I contains at least two equal vectors and is not
Costas, a contradiction.
It follows that distance vectors between points ofA are disjoint from distance vectors between
points of B.
But this is absurd, since, by the pigeonhole principle, A and B have at least 2 dots in common, hence they
necessarily share a common distance vector.
Assumingn odd, and considering a subset A of (n−1)/2+1 dots of I,
we end up, as before, with another subset B of (n−1)/2+1 dots in I,
so that each set contains the vertical flips of the distance vectors present in
the other. But now the pigeonhole principle only guarantees the two sets have
at least one dot in common, so it is necessary to count more carefully. Indeed,
if we assume that the shift aligning A and B has a nonzero vertical component, say u≠0,
it follows that |u|≥1 dots can belong to neither A nor B,
whence |A∩B|≥2,
that is,  they share a common distance vector, which is impossible.
This implies that the shift aligningA and B is purely horizontal, so that A and B are vertical flips of each other. The only dot
that could possibly lie in A∩B then is the (unique) dot of the central row,
and since at least one dot must exist in A∩B (or else I would have at least n+1 dots), we deduce that no shift is possible.
Hence, (n−1)/2+1=1⇔n=1 is the only possibility.
The argument forG=S is completely analogous. This completes the
proof.Note that, forn even, the upper bound is actually achieved for
a Welch Costas array, while, for n odd, the upper bound is again achieved for a
Costas array resulting from the removal of the corner dot from a Welch Costas
array generated with c=0,
in both cases due to the antireflective symmetry.


### 5.2. Bounds on Origin Value of Cross-Correlation

We now consider
some of the bounds regarding the values of the cross-correlation at the origin,
that is, the number of hits for perfect overlay of two arrays. The reason for
our particular interest in the value of the cross-correlation at the origin is,
on the one hand, practical, as it becomes the only relevant value in a
multiuser system where users' clocks are synchronized, and, on the other hand,
theoretical, as it is often much simpler to compute or estimate than a general
value, as we are about to see.First, we show that a Costas array of even order and
its vertical or horizontal flip (S and T,
resp.) do not overlap, while the corresponding result for odd orders is that
they overlap at one point only. Note that we already derived and used part of
this result in the proof of Theorem 5.4.Theorem 5.5.
For any Costas array of ordern,(5.10)ΨI,B(0,0)=nmod2,when array B is either S or T.Proof.
Since a Costas array contains one
dot per column and row,ΨI,T(0,0) will equal the number of dots a vertical flip
leaves fixed: if n is even there is no fixed dot, whereas if n is odd exactly one dot remains fixed, namely
the one lying on the central row. The horizontal flip is analogously treated.
This completes the proof.We now sketch a proof that a symmetric Costas array of
even order and its rotation by90° in either direction (R and R3) do not overlap, while the corresponding
result for odd order is that they overlap at one point only.Theorem 5.6.
For any symmetric Costas array of ordern,(5.11)ΨI,B(0,0)=nmod2when array B is one of R or R3.Proof.
We can show this by observing that a
symmetric array's rotation by±90∘ is equivalent to a horizontal or vertical flip
and then invoking Theorem 5.5.Next, we prove that if we overlay a Welch Costas array
with itsR2 rotation, the number of hits depends on the
array order.Theorem 5.7.
For any Welch Costas arrayI,(5.12)ΨI,R2(0,0)={0,forp≡1mod4,2,forp≡3mod4.Proof.
A Welch Costas array of sizen=p−1 contains dots at positions(5.13)(f(i),i),i∈[p−1]wheref(i)=αi−1+cmodpfor prime p and a primitive element α of 𝔽(p).
Its R2 rotation contains dots at positions (p−f(j),p−j),j∈[p−1].
The value at the origin of the cross-correlation is
equal to the largest possible number of solutions of the simultaneous
equations(5.14)f(i)=p−f(j),i=p−j.Substituting the latter into the
former and using (5.13), we get, after some manipulation,(5.15)⟺⟺αi−1+cmodp+αp−i−1+cmodp=p⟺αi−1+c+α−i+c≡0modp⟺αi−1+c≡α−i+(p−1)/2+cmodp⟺i−1≡−i+p−12mod(p−1)⟺eitheri−1=−i+32(p−1)⟺i=3p−14ori−1=−i+p−12⟺i=p+14.As i is an integer, these equations can be
satisfied if and only if p≡3mod4.
Therefore, when p is of this form, we have two solutions, but
when p≡1mod4,
there are no solutions.Theorem 5.8.
For a Golomb Costas arrayI of order n,(5.16)ΨI,R2(0,0)=nmod3.Proof.
A Golomb Costas array of ordern=q−2 has dots at positions (f(i),i),
where(5.17)αi+βf(i)=1,i∈[q−2]for q=pm,p prime, integer m,
and primitive elements α and β.
Its R2 rotation has dots at positions (q−1−f(j),q−1−j),j∈[p−2].
The value of the cross-correlation at the origin is
the number of solutions of the simultaneous equationsf(i)+f(j)=q−1 and i+j=q−1.
It follows that(5.18)αj+βf(j)=1,f(j)=q−1−f(i),j=q−1−i⇒αq−1−i+βq−1−f(i)=1⟺α−i+β−f(i)=1⟺1αi+1βf(i)=1⟺αi+βf(i)αiβf(i)=1⟺1αiβf(i)=1.We therefore end up with two
simultaneous equations:(5.19)αiβf(i)=1,αi+βf(i)=1⟺(αi)2−αi+1=0βf(i)=1−αi.Setting x=αi,
we obtain the quadratic(5.20)x2−x+1=0.Now we consider three
cases.
(i)
n≡1mod3⇔q≡0mod3: q is a power of 3, so (5.20)
becomes(5.21)x2+2x+1=0⟺(x+1)2=0⟺x=2.Since only solution exists, ΨI,R2(0,0)=1.(ii)
Otherwise,x solves x2−x+1=0 if and only if  −x solves x2+x+1=0⇔(x3−1)/(x−1)=0⇔x3=1,x≠1.
This has  solutions in 𝔽(q) if and only if  3∣q−1⇔n≡2mod3:(a)
n≡2mod3:
(5.20) has 2 roots in 𝔽(q).(b)
n≡0mod3:
(5.20) has 0 roots  𝔽(q).


## 5.1. Bounds on Cross-Correlation Maximum

Freedman and Levanon [15] proved that, for n>3,
the cross-correlation between any two arrays of the same size will have at
least 2 hits. We present a special case where the
cross-correlation between a pair of arrays is exactly 2: the cross-correlation
between any Costas array and its 180° rotation has a maximum value of 2.Theorem 5.1.
LetI be a Costas array of order n>1;
then max(u,v)ΨI,R2(u,v)=2.Proof.
The key observation is that a
rotation by180° generates a Costas array whose distance
vectors are the same as in the original array: letting two dots lie at A=(f(i),i),B=(f(j),j),
where i>j,
their images in the rotated array lie at A′=(n+1−f(i),n+1−i),B′=(n+1−f(j),n+1−j),n being the order of the array. The distance
vectors BA and A′B′ are equal: (f(i),i)−(f(j),j)=(f(i)−f(j),i−j) and (n+1−f(j),n+1−j)−(n+1−f(i),n+1−i)=(f(i)−f(j),i−j).
It follows that a shift will align these pairs, whence max(u,v)ΨI,R2(u,v)≥2 (but note that the shift aligns A with B′ and B with A′).
Assume now that, for this given shift, a third pair of
dots become aligned as well, sayC and K,
where C is a point in I and K a point in R2:
then K has a pre-image in I,
say a point k.
We claim that the points A,B,C,
and k form a parallelogram, violating the Costas
property: indeed, by the triple alignment we get A′K=BC and B′K=AC,
while, by the observation above, A′K=kA and B′K=kB.
It follows that BC=kA,AC=kB,
hence AkBC is a parallelogram and the proof is complete.As mentioned earlier, this result has also been
derived by Etzion ([14, Theorem 2]); we chose to present it here for
completeness, offering a more concise proof. O'Carroll et al. [10] sketched a proof that the
maximal cross-correlation of any two amongst a Golomb array and its S,T,
and ST flips is identically 2.We now prove two bounds for Welch Costas arrays of
ordern:
first, we show that the peak of the cross-correlation of a Welch Costas array
and its vertical flip T is n/2.
Then we consider the case of a Welch Costas array and its horizontal flip S which yields a rather better result.Theorem 5.2.
For any antireflective Costas
arrayI of (even) order n and its vertical flip T,(5.1)max(u,v)ΨI,T(u,v)=n2.In particular, the result holds
true for any Welch Costas array generated in 𝔽(p) (where n=p−1).Proof.
We prove
this property by considering the form of three distinct regions of the
cross-correlation. Letf be the permutation corresponding to i.
Then, we show that
(i)
for allu,ΨI,T(u,v)≤1 when v≠n/2,(ii)
ΨI,T(u,n/2)=0 when u≠0,(iii)
ΨI,T(0,n/2)=n/2. Fixing u and v,
we find the number of pairs (i,j) for which(5.2)(f(i),i)=(u,v)+(n+1−f(j),j)⇒f(v+j)=u+n+1−f(j)=u+f(j±n2),where “+” is chosen if j≤n/2,
and “−” otherwise.
Assumingv≠n/2,
this equation has at most one solution j because of the Costas property. Assuming v=n/2,
the equation becomes u=0,
which is satisfied for no j if we choose u≠0,
but is satisfied for all j∈[n/2],
that is n/2 values of j,
if we choose u=0.
This completes the proof.Theorem 5.3.
For any Welch Costas arrayI and its horizontal flip S,(5.3)max(u,v)ΨI,S(u,v)=2.Proof.
Letf be the Welch permutation generated in 𝔽(p) by the primitive root α and the parameter c.
For fixed values of u and v,
we need to find the number of pairs (i,j) for which(5.4)(αi−1+cmodp,i)=(u,v)+(αp−j−1+cmodp,j)whence we get the two
equations(5.5)αi−1+cmodp=u+αp−j−1+cmodp,i=v+j,namely(5.6)αv+j−1+cmodp=u+αp−j−1+cmodp.If this equation is true, it is
also true modp,
whence(5.7)αv+j−1+c≡u+αc−jmodp⟺αv−1+cα2j−ugj−αc≡0modp.Setting αj=x,
we obtain(5.8)αv−1+cx2−ux−αc≡0modp.This is an equation of the
second degree in a field, and therefore it has at most 2 solutions for x and thus for j.
Note, however, that not all solutions of this equation need actually also be
solutions of (5.6). Note also that, as both I and S are Costas arrays, Freedman and Levanon's
result [15] guarantees
that there are two solutions for at least one pair of values of u and v.Theorem 5.4.
For any Costas arrayI of order n>1,(5.9)max(u,v)ΨI,G(u,v)≤n2orn−12,depending on whether n is even or odd, respectively, where G is either S or T.Proof.
Assumen even, and assume there exists a shift for
which a subset A of (n/2)+1 dots of I can be aligned with a subset W of equally many dots of T.I also contains a subset B of (n/2)+1 dots, namely the pre-image of W:
the distance vectors in B are the vertical flips of the distance vectors
in A.
Observe now that, as no two dots of a Costas array lie
in the same row or column, each distance vector is different from its vertical
flip. AssumeA contains both a vector x and its vertical flip x′,
where, without loss of generality, the starting point of x lies to the left of the starting point of x′.
Then B contains both vectors as well, but now the
starting point of x lies to the right of the starting point of x′.
This implies that the two pairs of equal vectors cannot both be collocated,
hence I contains at least two equal vectors and is not
Costas, a contradiction.
It follows that distance vectors between points ofA are disjoint from distance vectors between
points of B.
But this is absurd, since, by the pigeonhole principle, A and B have at least 2 dots in common, hence they
necessarily share a common distance vector.
Assumingn odd, and considering a subset A of (n−1)/2+1 dots of I,
we end up, as before, with another subset B of (n−1)/2+1 dots in I,
so that each set contains the vertical flips of the distance vectors present in
the other. But now the pigeonhole principle only guarantees the two sets have
at least one dot in common, so it is necessary to count more carefully. Indeed,
if we assume that the shift aligning A and B has a nonzero vertical component, say u≠0,
it follows that |u|≥1 dots can belong to neither A nor B,
whence |A∩B|≥2,
that is,  they share a common distance vector, which is impossible.
This implies that the shift aligningA and B is purely horizontal, so that A and B are vertical flips of each other. The only dot
that could possibly lie in A∩B then is the (unique) dot of the central row,
and since at least one dot must exist in A∩B (or else I would have at least n+1 dots), we deduce that no shift is possible.
Hence, (n−1)/2+1=1⇔n=1 is the only possibility.
The argument forG=S is completely analogous. This completes the
proof.Note that, forn even, the upper bound is actually achieved for
a Welch Costas array, while, for n odd, the upper bound is again achieved for a
Costas array resulting from the removal of the corner dot from a Welch Costas
array generated with c=0,
in both cases due to the antireflective symmetry.


## 5.2. Bounds on Origin Value of Cross-Correlation

We now consider
some of the bounds regarding the values of the cross-correlation at the origin,
that is, the number of hits for perfect overlay of two arrays. The reason for
our particular interest in the value of the cross-correlation at the origin is,
on the one hand, practical, as it becomes the only relevant value in a
multiuser system where users' clocks are synchronized, and, on the other hand,
theoretical, as it is often much simpler to compute or estimate than a general
value, as we are about to see.First, we show that a Costas array of even order and
its vertical or horizontal flip (S and T,
resp.) do not overlap, while the corresponding result for odd orders is that
they overlap at one point only. Note that we already derived and used part of
this result in the proof of Theorem 5.4.Theorem 5.5.
For any Costas array of ordern,(5.10)ΨI,B(0,0)=nmod2,when array B is either S or T.Proof.
Since a Costas array contains one
dot per column and row,ΨI,T(0,0) will equal the number of dots a vertical flip
leaves fixed: if n is even there is no fixed dot, whereas if n is odd exactly one dot remains fixed, namely
the one lying on the central row. The horizontal flip is analogously treated.
This completes the proof.We now sketch a proof that a symmetric Costas array of
even order and its rotation by90° in either direction (R and R3) do not overlap, while the corresponding
result for odd order is that they overlap at one point only.Theorem 5.6.
For any symmetric Costas array of ordern,(5.11)ΨI,B(0,0)=nmod2when array B is one of R or R3.Proof.
We can show this by observing that a
symmetric array's rotation by±90∘ is equivalent to a horizontal or vertical flip
and then invoking Theorem 5.5.Next, we prove that if we overlay a Welch Costas array
with itsR2 rotation, the number of hits depends on the
array order.Theorem 5.7.
For any Welch Costas arrayI,(5.12)ΨI,R2(0,0)={0,forp≡1mod4,2,forp≡3mod4.Proof.
A Welch Costas array of sizen=p−1 contains dots at positions(5.13)(f(i),i),i∈[p−1]wheref(i)=αi−1+cmodpfor prime p and a primitive element α of 𝔽(p).
Its R2 rotation contains dots at positions (p−f(j),p−j),j∈[p−1].
The value at the origin of the cross-correlation is
equal to the largest possible number of solutions of the simultaneous
equations(5.14)f(i)=p−f(j),i=p−j.Substituting the latter into the
former and using (5.13), we get, after some manipulation,(5.15)⟺⟺αi−1+cmodp+αp−i−1+cmodp=p⟺αi−1+c+α−i+c≡0modp⟺αi−1+c≡α−i+(p−1)/2+cmodp⟺i−1≡−i+p−12mod(p−1)⟺eitheri−1=−i+32(p−1)⟺i=3p−14ori−1=−i+p−12⟺i=p+14.As i is an integer, these equations can be
satisfied if and only if p≡3mod4.
Therefore, when p is of this form, we have two solutions, but
when p≡1mod4,
there are no solutions.Theorem 5.8.
For a Golomb Costas arrayI of order n,(5.16)ΨI,R2(0,0)=nmod3.Proof.
A Golomb Costas array of ordern=q−2 has dots at positions (f(i),i),
where(5.17)αi+βf(i)=1,i∈[q−2]for q=pm,p prime, integer m,
and primitive elements α and β.
Its R2 rotation has dots at positions (q−1−f(j),q−1−j),j∈[p−2].
The value of the cross-correlation at the origin is
the number of solutions of the simultaneous equationsf(i)+f(j)=q−1 and i+j=q−1.
It follows that(5.18)αj+βf(j)=1,f(j)=q−1−f(i),j=q−1−i⇒αq−1−i+βq−1−f(i)=1⟺α−i+β−f(i)=1⟺1αi+1βf(i)=1⟺αi+βf(i)αiβf(i)=1⟺1αiβf(i)=1.We therefore end up with two
simultaneous equations:(5.19)αiβf(i)=1,αi+βf(i)=1⟺(αi)2−αi+1=0βf(i)=1−αi.Setting x=αi,
we obtain the quadratic(5.20)x2−x+1=0.Now we consider three
cases.
(i)
n≡1mod3⇔q≡0mod3: q is a power of 3, so (5.20)
becomes(5.21)x2+2x+1=0⟺(x+1)2=0⟺x=2.Since only solution exists, ΨI,R2(0,0)=1.(ii)
Otherwise,x solves x2−x+1=0 if and only if  −x solves x2+x+1=0⇔(x3−1)/(x−1)=0⇔x3=1,x≠1.
This has  solutions in 𝔽(q) if and only if  3∣q−1⇔n≡2mod3:(a)
n≡2mod3:
(5.20) has 2 roots in 𝔽(q).(b)
n≡0mod3:
(5.20) has 0 roots  𝔽(q).


## 6. Conclusion

Families of
Costas arrays with low cross-correlation are useful in a multiuser setting,
where the necessity for ideal autoambiguity for optimal RADAR/SONAR performance
is combined with the need to minimize cross-interference between different users.
We focused on the special case of the cross-correlation of two Costas arrays
related by a horizontal and/or a vertical flip and considered both general
Costas arrays and more specific algebraically constructed subfamilies.On many occasions the cross-correlation was found to
be low (2 or less), implying that for a small number of users it is possible to
use flipped variants of the same array without significant interference. Our
options increase further if we tie all users to a common clock, in which case
the only cross-correlation value that becomes relevant is that at the origin.For a larger number of users, larger families of
Costas arrays need to be considered; we relegate this for future work. We have
also collected empirical results regarding the cross-correlation of a Costas
array with its image under rotation by±90°,
or under transposition (and flips and/or rotations thereof), but so far we have
been unable to find provable formulas for these results.



---

*Source: 369321-2009-02-03.xml*