Costasovo pole - Costas array

V matematice, a Costasovo pole lze považovat geometricky jako soubor n body, každý ve středu a náměstí v n×n čtvercové obklady takže každý řádek nebo sloupec obsahuje pouze jeden bod a všechny n(n − 1)/2 přemístění vektory mezi každou dvojicí teček jsou odlišné. Výsledkem je ideální „připínáček“funkce nejednoznačnosti, díky čemuž jsou pole užitečná v aplikacích, jako je sonar a radar. Costasova pole lze považovat za dvojrozměrné sestřenice jednorozměrných Golombův vládce konstrukce, a stejně jako matematické zajímavosti, mají podobné aplikace v experimentální design a fázované pole radarové inženýrství.

Pole Costas jsou pojmenována po John P. Costas, který o nich poprvé napsal v technické zprávě z roku 1965. Nezávisle, Edgar Gilbert také o nich napsal ve stejném roce a publikoval to, co je nyní známé jako logaritmická Welchova metoda konstrukce Costasových polí.^[1]

Numerická reprezentace

Pole Costas může být numericky reprezentováno jako n×n pole čísel, kde každá položka je buď 1, pro bod, nebo 0, pro absenci bodu. Při interpretaci jako binární matice, tato pole čísel mají vlastnost, že protože každý řádek a sloupec má omezení, že má na sobě pouze jeden bod, jsou tedy také permutační matice. To znamená, že Costasovy pole pro všechny dané n jsou podmnožinou permutačních matic řádu n.

Pole jsou obvykle popsána jako řada indexů specifikujících sloupec pro libovolný řádek. Vzhledem k tomu, že jakýkoli sloupec má pouze jeden bod, je možné pole jednorozměrně reprezentovat. Například následující je platné pole Costasovy objednávky N = 4:

Na souřadnicích jsou tečky: (1,2), (2,1), (3,3), (4,4)

Protože X- souřadnice se zvyšuje lineárně, můžeme to napsat ve zkratce jako množinu všech y-souřadnice. Pozice v sadě by pak byla X-koordinovat. Všimněte si: {2,1,3,4} by popsal výše uvedené pole. To usnadňuje komunikaci polí pro dané pořadí N.

Známá pole

Počty polí Costas jsou známé pro objednávky 1 až 29^[2] (sekvence A008404 v OEIS ):

Výčet známých Costasových polí na objednávku 200,^[3] objednat 500^[4] a objednat 1030^[5] jsou dostupné. Ačkoli jsou tyto seznamy a databáze těchto polí Costas pravděpodobně téměř kompletní, mohou existovat další pole Costas s objednávkami nad 29, která nejsou v těchto seznamech.

Stavby

Welch

A Pole Welch – Costas, nebo jen Welchovo pole, je Costasovo pole generované pomocí následující metody, poprvé objevené uživatelem Edgar Gilbert v roce 1965 a znovuobjeven v roce 1982 Lloyd R. Welch Pole Welch – Costas je konstruováno převzetím a primitivní kořen G a prvočíslo str a definování pole A podle ${ displaystyle A_ {i, j} = 1}$ -li ${ displaystyle j equiv g ^ {i} { bmod {p}}}$, jinak 0. Výsledkem je Costasovo pole velikosti str − 1.

Příklad:

3 je primitivní prvek modulo 5.

3¹ = 3 ≡ 3 (mod 5)

3² = 9 ≡ 4 (mod 5)

3³ = 27 ≡ 2 (mod 5)

3⁴ = 81 ≡ 1 (mod 5)

[3 4 2 1] je tedy Costasova obměna. Přesněji řečeno, jedná se o exponenciální Welchovo pole. Transpozice pole je logaritmické Welchovo pole.

Počet polí Welch – Costas, která existují pro danou velikost, závisí na totient funkce.

Lempel – Golomb

Konstrukce Lempel – Golomb trvá α a β primitivní prvky z konečné pole GF (q) a podobně definuje ${ displaystyle A_ {i, j} = 1}$ -li ${ displaystyle alpha ^ {i} + beta ^ {j} = 1}$, jinak 0. Výsledkem je Costasovo pole velikosti q - 2. Pokud α + β = 1, pak první řádek a sloupec mohou být odstraněny, aby vytvořily další Costasovo pole velikosti q - 3: taková dvojice primitivních prvků existuje pro každou hlavní sílu q> 2.

Rozšíření Taylor, Lempel a Golomb

Generování nových Costasových polí přidáním nebo odečtením řádku / sloupce nebo dvou s 1 nebo dvojicí 1 v rohu byly publikovány v příspěvku zaměřeném na metody generování^[6] a v dokumentu Golomb a Taylorův orientační bod 1984.^[7]

Sofistikovanější metody generování nových polí Costas odstraněním řádků a sloupců ze stávajících polí Costas, které byly generovány generátory Welch, Lempel nebo Golomb, byly publikovány v roce 1992.^[8] Neexistuje žádná horní hranice pro pořadí, pro které budou tyto generátory produkovat pole Costas.

Jiné metody

V roce 2004 byly publikovány dvě metody, které zjistily, že Costasova pole jsou až 52 s použitím složitějších metod přidávání nebo mazání řádků a sloupců^[9] a 2007.^[10]

Varianty

Costas pole na a šestihranná mříž jsou známé jako voštinové pole. Ukázalo se, že takových polí, která musí mít lichý počet prvků, uspořádaných do tvaru šestiúhelníku, je jen konečně mnoho. V současné době je známo 12 takových polí (až do symetrie), o kterých se předpokládá, že jsou celkovým počtem.^[11]

Viz také

• Permutace
• Vzepětí skupina
• Kombinatorický design

Poznámky

Reference

• Barker, L .; Drakakis, K .; Rickard, S. (2009), „Ke složitosti ověření majetku Costas“ (PDF), Sborník IEEE, 97 (3): 586–593, doi:10.1109 / JPROC.2008.2011947, archivovány z originál (PDF) dne 2012-04-25, vyvoláno 2011-10-10.
• Beard, James (březen 2006), „Generování Costasových polí na objednávku 200“, 40. výroční konference 2006 o informačních vědách a systémech, IEEE, doi:10.1109 / ciss.2006.286635.
• Beard, James K. (březen 2008), „Polynomy generátoru pole Costasova pole v konečných polích“, 42. výroční konference 2008 o informačních vědách a systémech, IEEE, doi:10.1109 / ciss.2008.4558709.
• Beard, James K. (2017), Pole Costas a výčet na objednávku 1030, IEEE Dataport, doi:10,21227 / H21P42.
• Beard, J .; Russo, J .; Erickson, K .; Monteleone, M .; Wright, M. (2004), „Kombinatorická spolupráce na Costasových polích a radarových aplikacích“, Radarová konference IEEE, Philadelphia, Pensylvánie (PDF), str. 260–265, doi:10.1109 / NRC.2004.1316432, archivovány z originál (PDF) dne 2012-04-25, vyvoláno 2011-10-10.
• Beard, James; Russo, Jon; Erickson, Keith; Monteleone, Michael; Wright, Michael (duben 2007), „Generování pole Costas a metodika vyhledávání“, Transakce IEEE na letectví a elektronických systémech, 43 (2): 522–538, doi:10.1109 / taes.2007.4285351.
• Costas, J. P. (1965), Střední omezení designu a výkonu sonaru, Zpráva třídy 1 R65EMH33, G.E. Korporace
• Costas, J. P. (1984), „Studie třídy detekčních křivek s téměř ideálními vlastnostmi Dopplerovy nejednoznačnosti“ (PDF), Sborník IEEE, 72 (8): 996–1009, doi:10.1109 / PROC.1984.12967, archivovány z originál (PDF) dne 30. 9. 2011, vyvoláno 2011-10-10.
• Drakakis, Konstantinos; Rickard, Scott; Beard, James K .; Caballero, Rodrigo; Iorio, Francesco; O'Brien, Gareth; Walsh, John (říjen 2008), „Výsledky výčtu Costasových polí řádu 27“, Transakce IEEE na teorii informací, 54 (10): 4684–4687, doi:10.1109 / tit.2008.928979.
• Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott (2011), „Výčet Costasových polí řádu 28 a jeho důsledky“, Pokroky v matematice komunikací
• Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott; Walsh, John (srpen 2011), „Výsledky výčtu Costasových polí řádu 29“, Pokroky v matematice komunikací, 5 (3): 547–553, doi:10.3934 / amc.2011.5.547.
• Gilbert, E. N. (1965), „Latinské čtverce, které neobsahují žádné opakované digramy“, Recenze SIAM, 7: 189–198, doi:10.1137/1007035, PAN  0179095.
• Golomb, Solomon W. (1984), „Algebraické konstrukce pro Costasova pole“, Journal of Combinatorial Theory, Řada A, 37 (1): 13–21, doi:10.1016/0097-3165(84)90015-3, PAN  0749508.
• Golomb, Solomon W. (1992), „The ${ displaystyle T_ {4}}$ a ${ displaystyle G_ {4}}$ stavby pro pole Costas ", Transakce IEEE na teorii informací, 38 (4): 1404–1406, doi:10.1109/18.144726, PAN  1168761
• Golomb, S. W.; Taylor, H. (1984), "Konstrukce a vlastnosti Costasových polí" (PDF), Sborník IEEE, 72 (9): 1143–1163, doi:10.1109 / PROC.1984.12994, archivovány z originál (PDF) dne 30. 9. 2011, vyvoláno 2011-10-10.
• Guy, Richard K. (2004), „Sekce C18 a F9“, Nevyřešené problémy v teorii čísel (3. vyd.), Springer Verlag, ISBN  0-387-20860-7.
• Moreno, Oscar (1999), „Průzkum výsledků o signálních vzorcích pro lokalizaci jednoho nebo více cílů“, Pott, Alexander; Kumar, P. Vijay; Helleseth, Tor; et al. (eds.), Sady rozdílů, sekvence a jejich korelační vlastnosti, Series Advanced Science Institutes Series NATO, 542, Kluwer, s. 353, ISBN  0-7923-5958-5.
• Rickard, Scott (2004), „Hledání Costasových polí pomocí vlastností periodicity“, Mezinárodní konference IMA o matematice ve zpracování signálu.

externí odkazy

• MacTech Výzva programátora 1999: Costasova pole
• On-line encyklopedie celočíselných sekvencí:
  • A008404: Počet polí Costas objednávky n, počítá rotace a převrácení jako odlišné.
  • A001441: Počet nerovných Costasových polí objednávky n pod vzepětí.
• "Costasovo pole", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]