В математике массив Костаса (названный в честь Джона П. Костаса) можно рассматривать геометрически как набор из n точек, лежащих в клетках шахматной доски размерности n × n таким образом, чтобы каждая строка или столбец содержали только одну точку и все n(n − 1)/2 вектора смещений между каждой парой точек были различны. С помощью этого массива можно создать идеальную кнопкообразную функцию неопределённости (то есть функцию, которая бесконечна в точке (0,0) и принимает значение ноль в других точках), что делает применение массивов Костаса полезным для таких приложений, как гидро- и радиолокация.
Массив Костаса может быть представлен в цифровом виде как массив из n × n чисел, где каждой точке ставится в соответствие 1, а в случае отсутствия точки в массив записывается 0. Если интерпретировать их как двоичные матрицы, эти массивы чисел имеют свойство: каждая строка и столбец имеет только одну точку на нем, поэтому они также являются матрицами перестановок. Таким образом, массивы Костаса для любого n являются подмножеством матриц перестановок порядка n.
Массивы Костаса можно рассматривать как двумерные аналоги одномерных линеек Голомба. Они представляют математический интерес, применяются в разработках радиолокационной техники на фазированных решётках.
Все массивы Костаса вплоть до размера 27 × 27 известны [1]. Существует два способа получения массивов Костаса, работающих с рядом простых чисел и степенью простых чисел. Они известны как методы Уэлча (Велча (Lloyd R. Welch)) и Лемпеля-Голомба, и возникли в математике из теории конечных полей.
Пока неизвестны все массивы Костаса для всех размеров. В настоящее время самые маленькие размеры, для которых массивы неизвестны — 32 × 32 и 33 × 33.
Массивы, как правило, описываются как ряд индексов, указывающих столбцы для каждой строки. С учетом того, что в любом столбце имеется только одна точка, массив можно представить как одномерный. Например, массив Костаса порядка N = 4:
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
1
Существуют точки с координатами: (1,2), (2,1), (3,3), (4,4)
x-координата увеличивается линейно, мы можем записать это кратко как последовательность y-координат. Тогда позиция в наборе будет x-координатой. Вышеописанный массив может быть закодирован последовательностью {2,1,3,4}. Это позволяет легко обращаться с массивами порядка N.
Полная база данных массивов для всех размерностей, которые были тщательно проверены, доступна здесь [2]
Построение
Уэлч (Велч)
Массив Уэлча-Костаса, или просто массив Уэлча (Велча), является массивом Костаса, полученным с использованием метода, разработанного Ллойдом Р. Уэлчем (англ.Lloyd R. Welch).
Массив Уэлча-Костаса строится путём взятия первообразного корняgпростого числаp и определением массива A, где , если , в противном случае 0. Результатом является массив Костаса размера p − 1.
Пример
3 является первообразным корнем по модулю 5.
Поэтому [3 4 2 1] является перестановкой Костаса. Это дискретно экспоненциальный массив Уэлча (Велча). Транспонированный массив является дискретно логарифмическим массивом Уэлча.
Число массивов Уэлча-Костаса, которые существуют для данного размера, зависит от функции Эйлера.
Лемпель-Голомб
Метод Лемпеля-Голомба использует примитивные элементы α и β из конечного поля GF(q) и аналогично определяется , если , иначе 0. Результатом является массив Костаса размера q − 2. Если α + β = 1, то первая строка и столбец удаляются для формирования другого массива Костаса размера q − 3: неизвестно, есть ли такие пары примитивных элементов для каждой степени q.
Costas, J. P. A study of a class of detection waveforms having nearly ideal range-Doppler ambiguity properties (англ.) // Proceedings of the IEEE[англ.] : journal. — 1984. — Vol. 72, no. 8. — P. 996—1009.
Beard J., Russo J., Erickson K., Monteleone M., Wright M. Combinatoric Collaboration on Costas Arrays and Radar Applications (англ.) // In IEEE Radar Conference : journal. — 2004. — P. 260—265.
Oscar Moreno.Survey of results on signal patterns for locating one or multiple targets // Difference Sets, Sequences and Their Correlation Properties (англ.) / Alexander Pott, P. Vijay Kumar, Tor Helleseth, Dieter Jungnickel (eds). — Kluwer[англ.]. — ISBN 0792359585.
