Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Costas array
Set of marks on a 2d square grid such that no two pairs of marks are the same distance apart

In mathematics, a Costas array can be regarded geometrically as a set of n points, each at the center of a square in an n×n square tiling such that each row or column contains only one point, and all of the n(n − 1)/2 displacement vectors between each pair of dots are distinct. This results in an ideal "thumbtack" auto-ambiguity function, making the arrays useful in applications such as sonar and radar. Costas arrays can be regarded as two-dimensional cousins of the one-dimensional Golomb ruler construction, and, as well as being of mathematical interest, have similar applications in experimental design and phased array radar engineering.

Costas arrays are named after John P. Costas, who first wrote about them in a 1965 technical report. Independently, Edgar Gilbert also wrote about them in the same year, publishing what is now known as the logarithmic Welch method of constructing Costas arrays. The general enumeration of Costas arrays is an open problem in computer science and finding an algorithm that can solve it in polynomial time is an open research question.

We don't have any images related to Costas array yet.
We don't have any YouTube videos related to Costas array yet.
We don't have any PDF documents related to Costas array yet.
We don't have any Books related to Costas array yet.
We don't have any archived web articles related to Costas array yet.

Numerical representation

A Costas array may be represented numerically as an n×n array of numbers, where each entry is either 1, for a point, or 0, for the absence of a point. When interpreted as binary matrices, these arrays of numbers have the property that, since each row and column has the constraint that it only has one point on it, they are therefore also permutation matrices. Thus, the Costas arrays for any given n are a subset of the permutation matrices of order n.

Arrays are usually described as a series of indices specifying the column for any row. Since it is given that any column has only one point, it is possible to represent an array one-dimensionally. For instance, the following is a valid Costas array of order N = 4:

0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 {\displaystyle {\begin{array}{|c|c|c|c|}\hline 0&0&0&1\\\hline 0&0&1&0\\\hline 1&0&0&0\\\hline 0&1&0&0\\\hline \end{array}}}     or simply     ∙ ∙ ∙ ∙ {\displaystyle {\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\\hline \end{array}}}

There are dots at coordinates: (1,2), (2,1), (3,3), (4,4)

Since the x-coordinate increases linearly, we can write this in shorthand as the set of all y-coordinates. The position in the set would then be the x-coordinate. Observe: {2,1,3,4} would describe the aforementioned array. This defines a permutation. This makes it easy to communicate the arrays for a given order of N.

Known arrays

Costas array counts are known for orders 1 through 292 (sequence A008404 in the OEIS):

OrderNumber
11
22
34
412
540
6116
7200
8444
9760
102160
114368
127852
1312828
1417252
1519612
1621104
1718276
1815096
1910240
206464
213536
222052
23872
24200
2588
2656
27204
28712
29164

Here are some known arrays: N = 1 {1}

N = 2 {1,2} {2,1}

N = 3 {1,3,2} {2,1,3} {2,3,1} {3,1,2}

N = 4 {1,2,4,3} {1,3,4,2} {1,4,2,3} {2,1,3,4} {2,3,1,4} {2,4,3,1} {3,1,2,4} {3,2,4,1} {3,4,2,1} {4,1,3,2} {4,2,1,3} {4,3,1,2}

N = 5 {1,3,4,2,5} {1,4,2,3,5} {1,4,3,5,2} {1,4,5,3,2} {1,5,3,2,4} {1,5,4,2,3} {2,1,4,5,3} {2,1,5,3,4} {2,3,1,5,4} {2,3,5,1,4} {2,3,5,4,1} {2,4,1,5,3} {2,4,3,1,5} {2,5,1,3,4} {2,5,3,4,1} {2,5,4,1,3} {3,1,2,5,4} {3,1,4,5,2} {3,1,5,2,4} {3,2,4,5,1} {3,4,2,1,5} {3,5,1,4,2} {3,5,2,1,4} {3,5,4,1,2} {4,1,2,5,3} {4,1,3,2,5} {4,1,5,3,2} {4,2,3,5,1} {4,2,5,1,3} {4,3,1,2,5} {4,3,1,5,2} {4,3,5,1,2} {4,5,1,3,2} {4,5,2,1,3} {5,1,2,4,3} {5,1,3,4,2} {5,2,1,3,4} {5,2,3,1,4} {5,2,4,3,1} {5,3,2,4,1}

N = 6 {1,2,5,4,6,3} {1,2,6,4,3,5} {1,3,2,5,6,4} {1,3,2,6,4,5} {1,3,6,4,5,2} {1,4,3,5,6,2} {1,4,5,3,2,6} {1,4,6,5,2,3} {1,5,3,4,6,2} {1,5,3,6,2,4} {1,5,4,2,3,6} {1,5,4,6,2,3} {1,5,6,2,4,3} {1,5,6,3,2,4} {1,6,2,4,5,3} {1,6,3,2,4,5} {1,6,3,4,2,5} {1,6,3,5,4,2} {1,6,4,3,5,2} {2,3,1,5,4,6} {2,3,5,4,1,6} {2,3,6,1,5,4} {2,4,1,6,5,3} {2,4,3,1,5,6} {2,4,3,6,1,5} {2,4,5,1,6,3} {2,4,5,3,6,1} {2,5,1,6,3,4} {2,5,1,6,4,3} {2,5,3,4,1,6} {2,5,3,4,6,1} {2,5,4,6,3,1} {2,6,1,4,3,5} {2,6,4,3,5,1} {2,6,4,5,1,3} {2,6,5,3,4,1} {3,1,2,5,4,6} {3,1,5,4,6,2} {3,1,5,6,2,4} {3,1,6,2,5,4} {3,1,6,5,2,4} {3,2,5,1,6,4} {3,2,5,6,4,1} {3,2,6,1,4,5} {3,2,6,4,5,1} {3,4,1,6,2,5} {3,4,2,6,5,1} {3,4,6,1,5,2} {3,5,1,2,6,4} {3,5,1,4,2,6} {3,5,2,1,6,4} {3,5,4,1,2,6} {3,5,4,2,6,1} {3,5,6,1,4,2} {3,5,6,2,1,4} {3,6,1,5,4,2} {3,6,4,5,2,1} {3,6,5,1,2,4} {4,1,2,6,5,3} {4,1,3,2,5,6} {4,1,6,2,3,5} {4,2,1,5,6,3} {4,2,1,6,3,5} {4,2,3,5,1,6} {4,2,3,6,5,1} {4,2,5,6,1,3} {4,2,6,3,5,1} {4,2,6,5,1,3} {4,3,1,6,2,5} {4,3,5,1,2,6} {4,3,6,1,5,2} {4,5,1,3,2,6} {4,5,1,6,3,2} {4,5,2,1,3,6} {4,5,2,6,1,3} {4,6,1,2,5,3} {4,6,1,5,2,3} {4,6,2,1,5,3} {4,6,2,3,1,5} {4,6,5,2,3,1} {5,1,2,4,3,6} {5,1,3,2,6,4} {5,1,3,4,2,6} {5,1,6,3,4,2} {5,2,3,1,4,6} {5,2,4,3,1,6} {5,2,4,3,6,1} {5,2,6,1,3,4} {5,2,6,1,4,3} {5,3,2,4,1,6} {5,3,2,6,1,4} {5,3,4,1,6,2} {5,3,4,6,2,1} {5,3,6,1,2,4} {5,4,1,6,2,3} {5,4,2,3,6,1} {5,4,6,2,3,1} {6,1,3,4,2,5} {6,1,4,2,3,5} {6,1,4,3,5,2} {6,1,4,5,3,2} {6,1,5,3,2,4} {6,2,1,4,5,3} {6,2,1,5,3,4} {6,2,3,1,5,4} {6,2,3,5,4,1} {6,2,4,1,5,3} {6,2,4,3,1,5} {6,3,1,2,5,4} {6,3,2,4,5,1} {6,3,4,2,1,5} {6,4,1,3,2,5} {6,4,5,1,3,2} {6,4,5,2,1,3} {6,5,1,3,4,2} {6,5,2,3,1,4}

Enumeration of known Costas arrays to order 200,3 order 5004 and to order 10305 are available. Although these lists and databases of these Costas arrays are likely near complete, other Costas arrays with orders above 29 that are not in these lists may exist. In general, the currently best known upper bound on the number C ( n ) {\displaystyle C(n)} of Costas Arrays of order n {\displaystyle n} is of asymptotic form C ( n ) / n ! ≤ e − Θ ( n ) {\displaystyle C(n)/n!\leq e^{-\Theta (n)}} .6

Constructions

Welch

A Welch–Costas array, or just Welch array, is a Costas array generated using the following method, first discovered by Edgar Gilbert in 1965 and rediscovered in 1982 by Lloyd R. Welch. The Welch–Costas array is constructed by taking a primitive root g of a prime number p and defining the array A by A i , j = 1 {\displaystyle A_{i,j}=1} if j ≡ g i mod p {\displaystyle j\equiv g^{i}{\bmod {p}}} , otherwise 0. The result is a Costas array of size p − 1.

Example:

3 is a primitive element modulo 5.

31 = 3 ≡ 3 (mod 5) 32 = 9 ≡ 4 (mod 5) 33 = 27 ≡ 2 (mod 5) 34 = 81 ≡ 1 (mod 5)

Therefore, [3 4 2 1] is a Costas permutation. More specifically, this is an exponential Welch array. The transposition of the array is a logarithmic Welch array.

The number of Welch–Costas arrays which exist for a given size depends on the totient function.

Lempel–Golomb

The Lempel–Golomb construction takes α and β to be primitive elements of the finite field GF(q) and similarly defines A i , j = 1 {\displaystyle A_{i,j}=1} if α i + β j = 1 {\displaystyle \alpha ^{i}+\beta ^{j}=1} , otherwise 0. The result is a Costas array of size q − 2. If α + β = 1 then the first row and column may be deleted to form another Costas array of size q − 3: such a pair of primitive elements exists for every prime power q>2.

Extensions by Taylor, Lempel, and Golomb

Generation of new Costas arrays by adding or subtracting a row/column or two with a 1 or a pair of 1's in a corner were published in a paper focused on generation methods7 and in Golomb and Taylor's landmark 1984 paper.8

More sophisticated methods of generating new Costas arrays by deleting rows and columns of existing Costas arrays that were generated by the Welch, Lempel or Golomb generators were published in 1992.9 There is no upper limit on the order for which these generators will produce Costas arrays.

Other methods

Two methods that found Costas arrays up to order 52 using more complicated methods of adding or deleting rows and columns were published in 200410 and 2007.11

Variants

Costas arrays on a hexagonal lattice are known as honeycomb arrays. It has been shown that there are only finitely many such arrays, which must have an odd number of elements, arranged in the shape of a hexagon. Currently, 12 such arrays (up to symmetry) are known, which has been conjectured to be the total number.12

See also

Notes

References

  1. Costas (1965); Gilbert (1965); An independent discovery of Costas arrays, Aaron Sterling, October 9, 2011. - Costas, J. P. (1965), Medium constraints on sonar design and performance, Class 1 Report R65EMH33, G.E. Corporation ↩

  2. Beard (2006); Drakakis et al. (2008); Drakakis, Iorio & Rickard (2011); Drakakis et al. (2011) - Beard, James (March 2006), "Generating Costas Arrays to Order 200", 2006 40th Annual Conference on Information Sciences and Systems, IEEE, doi:10.1109/ciss.2006.286635, S2CID 2241386 https://doi.org/10.1109%2Fciss.2006.286635 ↩

  3. Beard (2006). - Beard, James (March 2006), "Generating Costas Arrays to Order 200", 2006 40th Annual Conference on Information Sciences and Systems, IEEE, doi:10.1109/ciss.2006.286635, S2CID 2241386 https://doi.org/10.1109%2Fciss.2006.286635 ↩

  4. Beard (2008). - Beard, James K. (March 2008), "Costas array generator polynomials in finite fields", 2008 42nd Annual Conference on Information Sciences and Systems, IEEE, doi:10.1109/ciss.2008.4558709, S2CID 614347 https://doi.org/10.1109%2Fciss.2008.4558709 ↩

  5. Beard (2017); Beard, James K., Files for Download: Costas Arrays, retrieved 2020-04-20 - Beard, James K. (2017), Costas arrays and enumeration to order 1030, IEEE Dataport, doi:10.21227/H21P42 https://ieee-dataport.org/open-access/costas-arrays-and-enumeration-order-1030 ↩

  6. Warnke, Correll & Swanson (2023). - Warnke, Lutz; Correll, Bill; Swanson, Christopher (2023), "The density of Costas arrays decays exponentially", IEEE Transactions on Information Theory, 69 (1): 575–581, doi:10.1109/TIT.2022.3202507, MR 4544975 https://doi.org/10.1109%2FTIT.2022.3202507 ↩

  7. Golomb (1984). - Golomb, Solomon W. (1984), "Algebraic constructions for Costas arrays", Journal of Combinatorial Theory, Series A, 37 (1): 13–21, doi:10.1016/0097-3165(84)90015-3, MR 0749508 https://doi.org/10.1016%2F0097-3165%2884%2990015-3 ↩

  8. Golomb & Taylor (1984). - Golomb, S. W.; Taylor, H. (1984), "Construction and properties of Costas arrays" (PDF), Proceedings of the IEEE, 72 (9): 1143–1163, doi:10.1109/PROC.1984.12994, S2CID 39718506, archived from the original (PDF) on 2011-09-30, retrieved 2011-10-10 https://web.archive.org/web/20110930054835/http://www.costasarrays.org/costasrefs/golomb84constructions.pdf ↩

  9. Golomb (1992). - Golomb, Solomon W. (1992), "The T 4 {\displaystyle T_{4}} and G 4 {\displaystyle G_{4}} constructions for Costas arrays", IEEE Transactions on Information Theory, 38 (4): 1404–1406, doi:10.1109/18.144726, MR 1168761 https://doi.org/10.1109%2F18.144726 ↩

  10. Rickard (2004). - Rickard, Scott (2004), "Searching for Costas Arrays using Periodicity Properties", IMA International Conference on Mathematics in Signal Processing ↩

  11. Beard et al. (2007). - Beard, James; Russo, Jon; Erickson, Keith; Monteleone, Michael; Wright, Michael (April 2007), "Costas array generation and search methodology", IEEE Transactions on Aerospace and Electronic Systems, 43 (2): 522–538, doi:10.1109/taes.2007.4285351, S2CID 32271456 https://zenodo.org/record/893374 ↩

  12. Blackburn, Simon R.; Panoui, Anastasia; Paterson, Maura B.; Stinson, Douglas R. (2010-12-10), "Honeycomb Arrays", The Electronic Journal of Combinatorics, 17: R172, doi:10.37236/444, ISSN 1077-8926 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r172 ↩