Массив Костаса

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В математике массив Костаса (названный в честь Джона П. Костаса) можно рассматривать геометрически как набор из 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.

Известные массивы[править | править вики-текст]

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}

Полная база данных массивов для всех размерностей, которые были тщательно проверены, доступна здесь [2]

Построение[править | править вики-текст]

Уэлч (Велч)[править | править вики-текст]

Массив Уэлча-Костаса, или просто массив Уэлча (Велча), является массивом Костаса, полученным с использованием метода, разработанного Ллойдом Р. Уэлчем (англ. Lloyd R. Welch). Массив Уэлча-Костаса строится путем взятия первообразного корня g простого числа p и определением массива A, где A_{i,j} = 1, если i \equiv g^j \bmod p, в противном случае 0. Результатом является массив Костаса размера p − 1.


Пример

3 является первообразным корнем по модулю 5.

3^1 = 3
3^2 = 9 \equiv 4 \pmod{5}
3^3 = 27 \equiv 2 \pmod{5}
3^4 = 81 \equiv 1 \pmod{5}

Поэтому [3 4 2 1] является перестановкой Костаса. Это дискретно экспоненциальный массив Уэлча (Велча). Транспонированный массив является дискретно логарифмическим массивом Уэлча.

Число массивов Уэлча-Костаса, которые существуют для данного размера, зависит от функции Эйлера.

Лемпель-Голомб[править | править вики-текст]

Метод Лемпеля-Голомба использует примитивные элементы α и β из конечного поля GF(q) и аналогично определяется A_{i,j} = 1, если \alpha^i + \beta^j = 1, иначе 0. Результатом является массив Костаса размера q − 2. Если α + β = 1, то первая строка и столбец удаляются для формирования другого массива Костаса размера q − 3: неизвестно, есть ли такие пары примитивных элементов для каждой степени q.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Costas, J. P. (1984). «A study of a class of detection waveforms having nearly ideal range-Doppler ambiguity properties». Proceedings of the IEEE 72 (8): 996—1009.
  • Golomb S. W., Taylor H. (1984). «Construction and properties of Costas arrays». Proceedings of the IEEE 72 (9): 1143—1163.
  • Beard J., Russo J., Erickson K., Monteleone M., Wright M. (2004). «Combinatoric Collaboration on Costas Arrays and Radar Applications». In IEEE Radar Conference: 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.

Ссылки[править | править вики-текст]