What is a Costas array?

A Costas array is an permutation matrix () such that vectors connecting two of the matrix are all distinct as vectors. Equivalently a Costas sequence of length is a permutation with the distinct different property.

• A function has the distinct difference property if for all integers and , with and , implies .

Costas Example

f(i + h) - f(i) = f(j + h) - f(j)

A Costas array 2 4 3 1 2 -1 -2 1 -3 Array 2 4 3 1 h=1 2 -1 -2 h=2 1 -3

Not a Costas array 2 1 4 3 -1 3 -1 2 2 Array 2 1 4 3 h=1 -1 3 -1 h=2 2 2

Another Example

5 7 4 3 1 6 2

2 -3 -1 -2 5 -4

-1 -4 -3 3 1

-2 -6 2 -1

-4 -1 -2

1 -5

Costas Array applications

• Digital Watermarking
• Optical Communications
• Multiple target recognition

2D representation

A Costas array can be conveniently represented as a 2D permutation matrix.

Example: 4 2 1 3 5 6

How to generate Costas arrays

• By hand, JP Costas had his students do it for n=12 in the 80's

• Algebraically with finite fields.
  • Refer to Welch Construction
  • Refer to Lempel-Golomb Costruction
• Exhaustive computing
  • Costas arrays enumerated up to n=29, by Drakakis et al.
  • used hundreds of CPUs and took months

Simple algorithm

• Write an algorithm to generate all the n! permutations for Costas lenght n.
• Write an algorithm to determine if an arrays meets the Costas property.

Backtracking

Instead of using an algorithm to generate all the n! permutations. We will use backtracking to eliminate branches of computations and speed things a little bit more.

The backtracking algorithm work as follows:

1. Start with an array of length n with 1 in position 0
2. Add a number to the next position that is not in the array
3. If the sub array meets the Costas property move forward using step 2.
4. Otherwise
   • If there is a number available to try in the same position try it and goto step 3
   • Otherwise move one position back.

Costas Backtracking Example: Solution space n=5

Python implementation of the backtracking algorithm

        costas_list = []

        while current >= start:
                costas[current] += 1
                while costas[current] in costas[:current] and costas[current] <= n:
                        costas[current]+=1
        
                if costas[current] > n:
                        costas[current] = 0
                        current-=1

                elif isCostas(costas[:current+1], n):
                        if current < n-1:
                                current+=1
                        else:
                                costas_list.append(costas[:])

Python simple implementation of a function to check the Costas property

def isCostas(array, n):
        a_size = len(array)
        for c in range(1, a_size):
                hash = [0] * (2 * n)
                for i in range(a_size - c):
                       dif = array[i+c] - array[i]
                       if hash[dif] == 1:
                               return 0
                       else:
                               hash[dif] = 1
        return 1

How to parallelize?

We can start by computing the set of sub Costas of size less than N.

• Divide set in equal parts among the processes and have them complete the search.

• Have one process, the master, send one sub Costas to the other processes, the slaves. Once the slaves finish their computation, send back the results and wait for another sub Costas.

A parallel aproach using the Master/Worker method

The Master:

    # The master computes the sub Costas and have the set in 
    # the List scostas_list
    
        for i in range(1, num_procs):
                sub_costas = scostas_list.pop(0)
                comm.send(sub_costas, dest=i, tag=TAG_WORK)

        while len(scostas_list) > 0:

                sub_costas = scostas_list.pop(0)
                costas_list += comm.recv(source=MPI.ANY_SOURCE, tag=MPI.ANY_TAG, status=stat)
                comm.send(sub_costas, dest=stat.Get_source(), tag=TAG_WORK)

        for i in range(1, num_procs):
                costas_list += comm.recv(source=MPI.ANY_SOURCE, tag=MPI.ANY_TAG, status=stat)
                comm.send(sub_costas, dest=stat.Get_source(), tag=TAG_END)
                

A parallel aproach using the Master/Worker method

The Slave:

        sub_costas = comm.recv(source=0, tag=MPI.ANY_TAG, status=stat)
        
        while stat.Get_tag() == TAG_WORK:
                costas_list = findCostas(sub_costas, n, sub_n, sub_n)
                comm.send(costas_list, dest=0)
                sub_costas = comm.recv(source=0, tag=MPI.ANY_TAG, status=stat)

References:

R. Arce, J. Ortiz, "Enumeration of Costas Arrays in FPGAs and GPUs". International Conference on ReConFigurable Computing and FPGAs, Cancun, Mexico, 2011.

K. Drakakis, F. Iorio, S. Rickard, and J. Walsh, “Results of the enumeration of Costas arrays of order 29,” Advances in Mathematics of Communications, vol. 5, no. 3, pp. 547–553, 2011.

MPI4py, http://mpi4py.scipy.org/

Python, www.python.org