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

У математиці маси́в Костаса (названий на честь Джона П. Костаса) можна розглядати геометрично як набір з n точок, що лежать у клітинках шахової дошки розміру n × n так, щоб кожен рядок або стовпець містили лише одну точку і всі n(n − 1)/2 вектори зсувів між кожною парою точок були різні. За допомогою цього масиву можна створити ідеальну кнопкоподібну функцію невизначеності (тобто функцію, яка нескінченна в точці (0,0) і набуває значення нуль в інших точках), що робить масиви Костаса корисними для застосування в гідро- та радіолокації.

Масив Костаса можна подати в цифровому вигляді як масив з n × n чисел, де кожній точці ставиться у відповідність 1, а в разі відсутності точки в масив записується 0. Якщо інтерпретувати їх як двійкові матриці, ці масиви чисел мають властивість: на кожному рядку чи стовпці є лише одна точка, тому вони також є матрицями перестановок. Отже, масиви Костаса для будь-якого n є підмножиною матриць перестановок порядку n.

Масиви Костаса можна розглядати як двовимірні аналоги одновимірних лінійок Голомба. Вони становлять математичний інтерес, застосовуються в розробках радіолокаційної техніки на фазованих решітках.

Усі масиви Костаса аж до розміру 27×27 відомі[1]. Існує два способи отримання масивів Костаса, що працюють з рядом простих чисел та степенем простих чисел. Вони відомі як методи Велча і Лемпеля — Ґоломба, і виникли в математиці з теорії скінченних полів.

Поки що невідомі всі масиви Костаса для всіх розмірів. Нині найменші розміри, для яких масиви невідомі — 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 = 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}

Побудова

Велч

Масив Велча — Костаса, чи навіть масив Велча — масивом Костаса, отриманий за допомогою методу, який розробив Ллойд Р. Велч. Масив Велча — Костаса будується шляхом взяття первісного кореня 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. 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 (2 June). — P. 996—1009.
• Golomb S. W., Taylor H. Construction and properties of Costas arrays // Proceedings of the IEEE : журнал. — 1984. — Vol. 72, no. 9 (2 June). — 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. — 2 June. — 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 (4 жовтня 2011). www.costasarrays.org. Архів оригіналу за 6 лютого 2012.
• December 1999 Programmer's Challenge: Costas arrays. MacTech.
• В Енциклопедії послідовностей цілих чисел:
  • послідовність A008404 з Онлайн енциклопедії послідовностей цілих чисел, OEIS — кількість масивів Костаса порядку n, враховуючи обертання та перевороти як різні;
  • послідовність A001441 з Онлайн енциклопедії послідовностей цілих чисел, OEIS — кількість нееквівалентних масивів Костаса порядку n під діедральною групою.