Массив Костаса - Costas array

В математике Массив Костаса можно рассматривать геометрически как набор п точки, каждая в центре квадрат в п×п квадратная черепица так что каждая строка или столбец содержит только одну точку, и все п(п − 1)/2 смещение векторов между каждой парой точек различны. В результате получается идеальная "канцелярская кнопка".функция неоднозначности, что делает массивы полезными в таких приложениях, как сонар и радар. Массивы Костаса можно рассматривать как двумерные кузены одномерного Правитель голомба конструкции, и, помимо математического интереса, имеют аналогичные приложения в экспериментальная конструкция и фазированная решетка радиолокационная техника.

Массивы Костаса названы в честь Джон П. Костас, который впервые написал о них в техническом отчете за 1965 год. Независимо, Эдгар Гилберт также писал о них в том же году, публикуя то, что теперь известно как логарифмический метод Велча построения массивов Костаса.[1]

Числовое представление

Массив Костаса может быть представлен численно как п×п массив чисел, где каждая запись либо 1, если точка, либо 0, если точка отсутствует. При интерпретации как двоичные матрицы, эти массивы чисел обладают тем свойством, что, поскольку каждая строка и столбец имеют ограничение, состоящее только в одной точке, они также являются матрицы перестановок. Таким образом, массивы Костаса для любого заданного п являются подмножеством матриц перестановок порядка п.

Массивы обычно описываются как серия индексов, определяющих столбец для любой строки. Поскольку задано, что любой столбец имеет только одну точку, можно представить массив одномерно. Например, ниже приведен действительный массив порядка Костаса. N = 4:

0001
0010
1000
0100

В координатах: (1,2), (2,1), (3,3), (4,4) есть точки.

Поскольку Икс-координата увеличивается линейно, мы можем записать это сокращенно как множество всех у-координаты. Тогда позиция в наборе будет Икс-координат. Заметьте: {2,1,3,4} описал бы вышеупомянутый массив. Это упрощает передачу массивов для заданного порядка N.

Известные массивы

Счетчики массива Костаса известны для заказов с 1 по 29.[2] (последовательность A008404 в OEIS ):

порядокЧисло
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

Перечисление известных массивов Костаса порядка 200,[3] порядка 500[4] и на заказ 1030[5] доступны. Хотя эти списки и базы данных этих массивов Костаса, вероятно, почти завершены, могут существовать другие массивы Костаса с порядками выше 29, которых нет в этих списках.

Конструкции

Welch

А Массив Велча – Костаса, или просто массив Велча, представляет собой массив Костаса, сгенерированный с использованием следующего метода, впервые обнаруженный Эдгар Гилберт в 1965 году и заново открыт в 1982 году Ллойд Р. Велч.Массив Велча – Костаса строится следующим образом: первобытный корень грамм из простое число п и определение массива А к если , иначе 0. Результатом является массив Костаса размером п − 1.

Пример:

3 - примитивный элемент по модулю 5.

31 = 3 ≡ 3 (мод. 5)
32 = 9 ≡ 4 (мод. 5)
33 = 27 ≡ 2 (мод. 5)
34 = 81 ≡ 1 (мод. 5)

Следовательно, [3 4 2 1] - перестановка Костаса. В частности, это экспоненциальный массив Велча. Транспонирование массива представляет собой логарифмический массив Велча.

Количество массивов Велча – Костаса, существующих для данного размера, зависит от общая функция.

Лемпель – Голомб

Конструкция Лемпеля – Голомба принимает α и β как примитивные элементы из конечное поле GF (q) и аналогично определяет если , иначе 0. Результатом является массив Костаса размером q - 2. Если α + β = 1, то первая строка и столбец могут быть удалены, чтобы сформировать другой массив Костаса размером q - 3: такая пара примитивных элементов существует для каждой степени простого числа q> 2.

Расширения Тейлора, Лемпеля и Голомба

Генерация новых массивов Костаса путем добавления или вычитания строки / столбца или двух с единицей или парой единиц в углу были опубликованы в статье, посвященной методам генерации.[6] и в знаменательной статье Голомба и Тейлора 1984 года.[7]

Более сложные методы создания новых массивов Костаса путем удаления строк и столбцов существующих массивов Костаса, которые были сгенерированы генераторами Велча, Лемпеля или Голомба, были опубликованы в 1992 году.[8] Нет верхнего предела для порядка, для которого эти генераторы будут производить массивы Костаса.

Другие методы

В 2004 году были опубликованы два метода, которые находили массивы Костаса до 52 порядка с использованием более сложных методов добавления или удаления строк и столбцов.[9] и 2007.[10]

Варианты

Массивы Костаса на шестиугольная решетка известны как сотовые массивы. Было показано, что существует только конечное число таких массивов, которые должны иметь нечетное количество элементов, расположенных в форме шестиугольника. В настоящее время известно 12 таких массивов (с точностью до симметрии), и предполагалось, что это общее количество.[11]

Смотрите также

Примечания

  1. ^ Костас (1965); Гилберт (1965); Независимое открытие массивов Костаса, Аарон Стерлинг, 9 октября 2011 г.
  2. ^ Борода (2006); Drakakis et al. (2008); Дракакис, Иорио и Рикард (2011); Drakakis et al. (2011)
  3. ^ Борода (2006).
  4. ^ Борода (2008).
  5. ^ Борода (2017); Борода, Джеймс К., Файлы для загрузки: Costas Arrays, получено 2020-04-20
  6. ^ Голомб (1984).
  7. ^ Голомб и Тейлор (1984).
  8. ^ Голомб (1992).
  9. ^ Рикард (2004).
  10. ^ Beard et al. (2007).
  11. ^ Блэкберн, Саймон Р .; Пануи, Анастасия; Патерсон, Маура Б .; Стинсон, Дуглас Р. (10 декабря 2010 г.). «Сотовые массивы». Электронный журнал комбинаторики: R172 – R172. Дои:10.37236/444. ISSN  1077-8926.

Рекомендации

внешняя ссылка