Массив Костаса
В математике массив Костаса (названный в честь Джона П. Костаса) можно рассматривать геометрически как набор из n точек, лежащих в клетках шахматной доски размерности n × n таким образом, чтобы каждая строка или столбец содержали только одну точку и все n(n − 1)/2 вектора смещений между каждой парой точек были различны. С помощью этого массива можно создать идеальную кнопкообразную функцию неопределённости (то есть функцию, которая бесконечна в точке (0,0) и принимает значение ноль в других точках), что делает применение массивов Костаса полезным для таких приложений, как гидро- и радиолокация.
Массив Костаса может быть представлен в цифровом виде как массив из n × n чисел, где каждой точке ставится в соответствие 1, а в случае отсутствия точки в массив записывается 0. Если интерпретировать их как двоичные матрицы, эти массивы чисел имеют свойство: каждая строка и столбец имеет только одну точку на нем, поэтому они также являются матрицами перестановок. Таким образом, массивы Костаса для любого n являются подмножеством матриц перестановок порядка n.
Массивы Костаса можно рассматривать как двумерные аналоги одномерных линеек Голомба. Они представляют математический интерес, применяются в разработках радиолокационной техники на фазированных решётках.
Все массивы Костаса вплоть до размера 27 × 27 известны . Существует два способа получения массивов Костаса, работающих с рядом простых чисел и степенью простых чисел. Они известны как методы Уэлча (Велча (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.
Известные массивы
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}
Полная база данных массивов для всех размерностей, которые были тщательно проверены, доступна здесь
Построение
Уэлч (Велч)
Массив Уэлча-Костаса, или просто массив Уэлча (Велча), является массивом Костаса, полученным с использованием метода, разработанного Ллойдом Р. Уэлчем (англ. 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.
- Golomb S. W., Taylor H. Construction and properties of Costas arrays (англ.) // Proceedings of the IEEE : journal. — 1984. — Vol. 72, no. 9. — P. 1143—1163.
- 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.
- Richard K. Guy. Sections C18, F9 // Unsolved Problems in Number Theory (неопр.). — 3rd ed. — Springer Verlag, 2004. — ISBN 0-387-20860-7.
- 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.
Ссылки
- Scott Rickard. www.costasarrays.org (4 октября 2011). Архивировано 6 февраля 2012 года.
- December 1999 Programmer's Challenge: Costas arrays. MacTech.
- On-Line Encyclopedia of Integer Sequences: