Masiv Costas

V matematice lze Costasovo pole (pojmenované po Johnu P. Costasovi) geometricky považovat za množinu n bodů ležících na čtvercích n × n šachovnice tak, že každý řádek nebo sloupec obsahuje pouze jeden bod a všech n ( n − 1 )/2 vektory posunů mezi každou dvojicí bodů byly různé. Toto pole lze použít k vytvoření ideální funkce tlačítka nejistoty (tj. funkce, která je nekonečná v (0,0) a nula v ostatních bodech), díky čemuž jsou pole Costas užitečná pro aplikace, jako jsou hydro- a radary.

Pole Costas může být reprezentováno digitálně jako pole n × n čísel, kde každému bodu je přiřazena 1, a pokud bod neexistuje, zapíše se do pole 0. Pokud jsou interpretovány jako binární matice, tato pole čísel mají vlastnost: každý řádek a sloupec má na sobě pouze jeden bod, takže jsou to také permutační matice. Costasova pole pro libovolné n jsou tedy podmnožinou permutačních matic řádu n .

Costas pole lze považovat za dvourozměrné analogy jednorozměrných Golombových pravítek . Jsou matematicky zajímavé, používají se při vývoji radarové technologie na fázových polích .

Všechna pole Costas do velikosti 27 × 27 jsou známá [1] . Existují dva způsoby, jak získat pole Costas, pracovat s řadou prvočísel a mocnin prvočísel. Jsou známé jako Welchovy (Lloyd R. Welch) a Lempel-Golombovy metody a vznikly v matematice z teorie konečných polí .

Dosud nejsou známa všechna pole Costas pro všechny velikosti. V současné době jsou nejmenší velikosti, u kterých pole nejsou známa, 32×32 a 33×33.

Definování polí

Pole jsou obvykle popsány jako série indexů označujících sloupce pro každý řádek. Vzhledem k tomu, že v libovolném sloupci je pouze jeden bod, lze pole reprezentovat jako jednorozměrné. Například Costasovo pole řádu N = 4:

0	jeden	0	0
jeden	0	0	0
0	0	jeden	0
0	0	0	jeden

Existují body se souřadnicemi: (1,2), (2,1), (3,3), (4,4)

Souřadnice x lineárně narůstá, můžeme to krátce zapsat jako posloupnost souřadnic y . Potom bude pozice v množině x - souřadnice. Výše uvedené pole může být kódováno sekvencí {2,1,3,4}. To usnadňuje manipulaci s poli řádu N .

Známá pole

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}

Kompletní databáze polí pro všechny rozměry, které byly pečlivě zkontrolovány, je k dispozici zde [2]

Konstrukce

Welch (Welch)

Pole Welch-Costas , nebo jednoduše Welch (Welch ) pole, je pole Costas získané pomocí metody vyvinuté Lloydem R. Welchem . Welch-Costasovo pole je konstruováno tak, že vezmeme primitivní kořen g prvočísla p a definujeme pole A , kde if , jinak 0. Výsledkem je Costasovo pole o velikosti p − 1. $A_{i,j}=1$ $i\equiv g^{j}{\bmod {p))$

Příklad

3 je primitivní kořenový modul 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}}

Proto [3 4 2 1] je Costasova permutace. Toto je Welchovo (Welchovo) diskrétní exponenciální pole. Transponované pole je Welchovo diskrétní logaritmické pole.

Počet Welch-Costasových polí, která existují pro danou velikost, závisí na Eulerově funkci .

Lempel-Golomb

Lempel-Golombova metoda využívá primitivní prvky α a β z konečného tělesa GF( q ) a podobně určuje if , jinak 0. Výsledkem je Costasovo pole o velikosti q − 2. Jestliže α + β = 1, pak první řádek a sloupec jsou odstraněny, aby vytvořily další Costasovo pole velikosti q − 3: není známo, zda existují takové dvojice primitivních prvků pro každou mocninu q . $A_{i,j}=1$ $\alpha ^{i}+\beta ^{j}=1$

Viz také

Literatura

Costas, JP Studie třídy detekčních křivek, které mají téměř ideální rozsah-dopplerovské nejednoznačné vlastnosti // Proceedings of the IEEE : deník. - 1984. - Sv. 72 , č. 8 . - S. 996-1009 .
Golomb SW , Taylor H. Konstrukce a vlastnosti polí Costas // Proceedings of the IEEE : deník. - 1984. - Sv. 72 , č. 9 . - S. 1143-1163 .
Beard J., Russo J., Erickson K., Monteleone M., Wright M. Combinatoric Collaboration on Costas Arrays and Radar Applications (anglicky) // In IEEE Radar Conference: journal. - 2004. - S. 260-265 .
Richard K Guy . Sekce C18, F9 // Nevyřešené problémy v teorii čísel (neopr.) . — 3. vyd. - Springer Verlag , 2004. - ISBN 0-387-20860-7 .
Oscar Moreno. Přehled výsledků o vzorech signálů pro lokalizaci jednoho nebo více cílů // Soubory rozdílů, sekvence a jejich korelační vlastnosti (anglicky) / Alexander Pott, P. Vijay Kumar, Tor Helleseth, Dieter Jungnickel (eds). — Kluwer. — ISBN 0792359585 .

Odkazy

Scott Richard. www.costasarrays.org (4. října 2011). Archivováno z originálu 6. února 2012. (neurčitý)
Prosinec 1999 Programátorská výzva: Costas pole . Mactech. (neurčitý)
On-line encyklopedie celočíselných sekvencí :
- A008404 : Počet Costasových polí řádu n , počítání rotací a převrácení jako odlišné.
- A001441 : Počet neekvivalentních Costasových polí řádu n pod dihedrální skupinou.