Costas Massif

Matematiikassa Costas-taulukko (nimetty John P. Costasin mukaan) voidaan ajatella geometrisesti n pisteen joukkona, joka sijaitsee n × n -shakkilaudan neliöillä siten, että jokainen rivi tai sarake sisältää vain yhden pisteen ja kaikki n ( n ) − 1 )/2 siirtymävektoria kunkin pisteparin välillä olivat erilaisia. Tätä ryhmää voidaan käyttää luomaan ihanteellinen epävarmuuspainiketoiminto (eli funktio, joka on ääretön kohdassa (0,0) ja nolla muissa kohdissa), mikä tekee Costas-taulukoista hyödyllisiä sovelluksissa, kuten vesi- ja tutka.

Costas-taulukko voidaan esittää digitaalisesti n × n luvun taulukkona, jossa jokaiselle pisteelle annetaan 1 ja jos pistettä ei ole, taulukkoon kirjoitetaan 0. Jos tulkitaan binäärimatriiseiksi, nämä numerotaulukot on ominaisuus: jokaisella rivillä ja sarakkeella on vain yksi piste, joten ne ovat myös permutaatiomatriiseja. Siten minkä tahansa n :n Costas-taulukot ovat kertaluvun n permutaatiomatriisien osajoukko .

Costas-taulukoita voidaan pitää yksiulotteisten Golomb -viivojen kaksiulotteisina analogeina . Ne ovat matemaattisesti kiinnostavia, niitä käytetään vaiheistettujen ryhmien tutkateknologian kehittämisessä .

Kaikki Costas-taulukot kokoon 27 × 27 asti tunnetaan [1] . On kaksi tapaa saada Costas-taulukoita, jotka toimivat useiden alkulukujen ja alkulukujen potenssien kanssa. Ne tunnetaan Welchin (Lloyd R. Welch) ja Lempel-Glombin menetelminä, ja ne ovat peräisin matematiikasta äärellisen kentän teoriasta .

Toistaiseksi kaikki Costas-taulukot kaikenkokoisille ovat tuntemattomia. Tällä hetkellä pienimmät koot, joille taulukoita ei tunneta, ovat 32×32 ja 33×33.

Taulukkomäärittely

Taulukot kuvataan tyypillisesti sarjana indeksejä, jotka osoittavat kunkin rivin sarakkeet. Koska missä tahansa sarakkeessa on vain yksi piste, taulukko voidaan esittää yksiulotteisena. Esimerkiksi Costas-taulukko, jonka järjestys on N = 4:

0	yksi	0	0
yksi	0	0	0
0	0	yksi	0
0	0	0	yksi

On pisteitä, joilla on koordinaatit: (1,2), (2,1), (3,3), (4,4)

X -koordinaatti kasvaa lineaarisesti, tämä voidaan kirjoittaa lyhyesti y - koordinaattien sarjana . Tällöin paikka joukossa on x - koordinaatti. Yllä oleva taulukko voidaan koodata sekvenssillä {2,1,3,4}. Tämä tekee N kertaluvun taulukoiden käsittelystä helppoa .

Tunnetut taulukot

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}

Täydellinen tietokanta taulukoista kaikille ulottuvuuksille, jotka on huolellisesti tarkastettu, on saatavilla täältä [2]

Rakennus

Welch (Welch)

Welch-Costas -taulukko tai yksinkertaisesti Welch (Welch ) -taulukko on Costas-taulukko, joka on saatu käyttämällä Lloyd R. Welchin kehittämää menetelmää . Welch-Costas-taulukko muodostetaan ottamalla alkuluvun p primitiivinen juuri g ja määrittämällä taulukko A , jossa jos , muuten 0. Tuloksena on Costas-taulukko, jonka koko on p − 1. $A_{i,j}=1$ $i\equiv g^{j}{\bmod {p))$

Esimerkki

3 on primitiivinen juuri modulo 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}}

Siksi [3 4 2 1] on Costas-permutaatio. Tämä on Welchin (Welch) diskreetti eksponentiaalinen ryhmä. Transponoitu matriisi on Welchin diskreetti logaritminen matriisi.

Tietylle koolle olemassa olevien Welch-Costas-taulukoiden määrä riippuu Euler-funktiosta .

Lempel-Golomb

Lempel-Golomb-menetelmä käyttää primitiivisiä alkioita α ja β äärellisestä kentästä GF( q ) ja määrittää samalla tavalla jos , muuten 0. Tuloksena on Costas-taulukko, jonka koko on q − 2. Jos α + β = 1, niin ensimmäinen rivi ja sarake poistetaan muodostamaan toinen Costas-taulukko, jonka koko on q − 3: ei tiedetä, onko sellaisia primitiivialkioiden pareja jokaiselle q :n potenssille . $A_{i,j}=1$ $\alpha ^{i}+\beta ^{j}=1$

Katso myös

Kirjallisuus

Costas, JP Tutkimus ilmaisuaaltomuotojen luokasta, jolla on lähes ihanteelliset etäisyys-Doppler-epäselvyydet // Proceedings of the IEEE : päiväkirja. - 1984. - Voi. 72 , no. 8 . - s. 996-1009 .
Golomb SW , Taylor H. Costas -taulukoiden rakenne ja ominaisuudet // Proceedings of the IEEE : päiväkirja. - 1984. - Voi. 72 , no. 9 . - s. 1143-1163 .
Beard J., Russo J., Erickson K., Monteleone M., Wright M. Combinatoric Collaboration on Costas Arrays and Radar Applications (englanniksi) // In IEEE Radar Conference : Journal. - 2004. - S. 260-265 .
Richard K Guy . Luvut C18, F9 // Ratkaisemattomat ongelmat lukuteoriassa (uuspr.) . – 3. painos - Springer Verlag , 2004. - ISBN 0-387-20860-7 .
Oscar Moreno. Survey of results on signal patterns for locating one tai use target // Difference Sets, Sequences and Their Correlation Properties (englanti) / Alexander Pott, P. Vijay Kumar, Tor Helleseth, Dieter Jungnickel (toim.). — Kluwer. — ISBN 0792359585 .

Linkit

Scott Richard. www.costasarrays.org (4. lokakuuta 2011). Arkistoitu alkuperäisestä 6. helmikuuta 2012. (määrätön)
Joulukuu 1999 Ohjelmoijan haaste: Costas-taulukot . Mactech. (määrätön)
On-line Encyclopedia of Integer Sequences :
- A008404 : Costas-taulukoiden määrä luokkaa n , lasketaan kierrokset ja käännökset erillisinä.
- A001441 : Eriarvoisten Costas-taulukoiden määrä luokkaa n dihedraaliryhmän alla.