Structural properties of Costas arrays

Jonathan Jedwab; Jane Wodlinger

doi:10.3934/amc.2014.8.241

Article Contents

2014, Volume 8, Issue 3: 241-256. Doi: 10.3934/amc.2014.8.241

This issue Previous Article Next Article Higher genus universally decodable matrices (UDMG)

Structural properties of Costas arrays

Jonathan Jedwab^1, and
Jane Wodlinger^2,

1.
Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, Canada V5A 1S6
2.
Department of Mathematics and Statistics, University of Victoria, 3800 Finnerty Road, Victoria BC V8P 5C2

Received: August 2012

Revised: March 2014

Published: August 2014

Abstract / Introduction Related Papers Cited by

Abstract

We apply combinatorial arguments to establish structural constraints on Costas arrays. We prove restrictions on when a Costas array can contain a large corner region whose entries are all 0. In particular, we prove a 2010 conjecture due to Russo, Erickson and Beard. We then constrain the vectors joining pairs of 1s in a Costas array by establishing a series of results on its number of "mirror pairs," namely pairs of these vectors having the same length but opposite slopes.

Keywords:

Mathematics Subject Classification: Primary: 05B20.

Citation:

Related Papers

Cited by

References

[1]	J. K. Beard, Orders three through 100, Database of Costas arrays, available from: http://jameskbeard.com/jameskbeard/Files.html#CostasArrays
[2]	S. R. Blackburn, T. Etzion, K. M. Martin and M. B. Paterson, Two-dimensional patterns with distinct differences - constructions, bounds, and maximal anticodes, IEEE Trans. Inform. Theory, 56 (2010), 1216-1229.doi: 10.1109/TIT.2009.2039046.
[3]	C. P. Brown, M. Cenkl, R. A. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays, in Proc. IEEE Int. Symp. Inform. Theory, Kobe, Japan, 1993.doi: 10.1109/ISIT.1993.748721.
[4]	J. P. Costas, A study of a class of detection waveforms having nearly ideal range-Doppler ambiguity properties, Proc. IEEE, 72 (1984), 996-1009.
[5]	K. Drakakis, A review of Costas arrays, J. Appl. Math., (2006).doi: 10.1155/JAM/2006/26385.
[6]	K. Drakakis, Open problems in Costas arrays, preprint, arXiv:1102.5727
[7]	K. Drakakis, R. Gow, J. Healy and S. Rickard, Cross-correlation properties of Costas arrays and their images under horizontal and vertical flips, Math. Problems Engin., (2008).doi: 10.1155/2008/369321.
[8]	K. Drakakis, R. Gow and S. Rickard, Interlaced Costas arrays do not exist, Math. Problems Engin., (2008).doi: 10.1155/2008/456034.
[9]	K. Drakakis, R. Gow and S. Rickard, Common distance vectors between Costas arrays, Adv. Math. Commun., 3 (2009), 35-52.doi: 10.3934/amc.2009.3.35.
[10]	K. Drakakis, F. Iorio and S. Rickard, The enumeration of Costas arrays of order 28 and its consequences, Adv. Math. Commun., 5 (2011), 69-86.doi: 10.3934/amc.2011.5.69.
[11]	P. Erdős, R. Graham, I. Z. Ruzsa and H. Taylor, Bounds for arrays of dots with distinct slopes or lengths, Combinatorica, 12 (1992), 39-44.doi: 10.1007/BF01191203.
[12]	P. Erdős and P. Turán, On a problem of Sidon in additive number theory and on some related problems, J. London Math. Soc., 16 (1941), 212-215.
[13]	T. Etzion, Combinatorial designs derived from Costas arrays, in Sequences: Combinatorics, Compression, Security, and Transmission (ed. R.M. Capocelli), Springer-Verlag, 1990, 208-227.
[14]	T. Etzion, Sequence folding, lattice tiling, and multidimensional coding, IEEE Trans. Inform. Theory, 57 (2011), 4383-4400.doi: 10.1109/TIT.2011.2146010.
[15]	A. Freedman and N. Levanon, Any two $N \times N$ Costas arrays must have at least one common ambiguity sidelobe if $N>3$ - a proof, Proc. IEEE, 73 (1985), 1530-1531.
[16]	E. N. Gilbert, Latin squares which contain no repeated digrams, SIAM Review, 7 (1965), 189-198.doi: 10.1137/1007035.
[17]	S. Golomb, Algebraic constructions for Costas arrays, J. Combin. Theory Ser. A, 37 (1984), 13-21.doi: 10.1016/0097-3165(84)90015-3.
[18]	S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays, Proc. IEEE, 72 (1984), 1143-1163.doi: 10.1109/PROC.1984.12994.
[19]	S. Rickard, Database of Costas arrays, accessed 2012.
[20]	S. Rickard, Searching for Costas arrays using periodicity properties, in Proc. 2004 IMA Int. Conf. Math. Signal Proc., Cirencester, UK, 2004.
[21]	J. C. Russo, K. G. Erickson and J. K. Beard, Costas array search technique that maximizes backtrack and symmetry exploitation, in 44th Annual Conf. Inform. Sci. Systems, Princeton, USA, 2010.doi: 10.1109/CISS.2010.5464772.
[22]	H. Taylor, Non-attacking rooks with distinct differences, Technical Report CSI-84-03-02, Communication Sciences Institute, University of Southern California, 1984.
[23]	K. Taylor, S. Rickard and K. Drakakis, On Costas arrays with various types of symmetry, in 16th Int. Conf. Digital Signal Proc., IEEE, 2009.doi: 10.1109/ICDSP.2009.5201135.
[24]	J. L. Wodlinger, Costas Arrays, Golomb Rulers and Wavelength Isolation Sequence Pairs, Master's thesis, Department of Mathematics, Simon Fraser University, 2012. Available from: https://theses.lib.sfu.ca/thesis/etd7112