Costas Massif

I matematik kan Costas-arrayen (uppkallad efter John P. Costas) geometriskt ses som en uppsättning av n punkter som ligger på kvadraterna på ett n × n schackbräde så att varje rad eller kolumn bara innehåller en punkt och alla n ( n − 1 )/2 vektorer av förskjutningar mellan varje par av punkter var olika. Denna array kan användas för att skapa en idealisk osäkerhetsknappfunktion (det vill säga en funktion som är oändlig vid (0,0) och noll vid andra punkter), vilket gör Costas arrayer användbara för applikationer som hydro- och radar.

Costas-matrisen kan representeras digitalt som en matris av n × n tal, där varje punkt tilldelas en 1:a, och i frånvaro av en punkt skrivs en 0 till matrisen. Om de tolkas som binära matriser, är dessa matriser med tal har egenskapen: varje rad och en kolumn har bara en punkt på sig, så de är också permutationsmatriser. Costas-matriser för vilket n som helst är alltså en delmängd av permutationsmatriser av ordningen n .

Costas-arrayer kan ses som tvådimensionella analoger av endimensionella Golomb-linjaler . De är av matematiskt intresse, de används i utvecklingen av radarteknik på fasade arrayer .

Alla Costas-arrayer upp till storleken 27 × 27 är kända [1] . Det finns två sätt att få Costas-arrayer, att arbeta med ett antal primtal och primtalspotenser. De är kända som Welch (Lloyd R. Welch) och Lempel-Golomb metoder och har sitt ursprung i matematiken från finita fältteori .

Hittills är alla Costas-arrayer för alla storlekar okända. För närvarande är de minsta storlekarna för vilka arrayer är okända 32×32 och 33×33.

Definiera arrayer

Matriser beskrivs vanligtvis som en serie index som anger kolumnerna för varje rad. Med tanke på att det bara finns en punkt i en kolumn kan matrisen representeras som endimensionell. Till exempel, en Costas-matris av ordning N = 4:

0	ett	0	0
ett	0	0	0
0	0	ett	0
0	0	0	ett

Det finns punkter med koordinater: (1,2), (2,1), (3,3), (4,4)

X -koordinaten ökar linjärt, vi kan kort skriva detta som en sekvens av y - koordinater. Då blir positionen i uppsättningen x - koordinaten. Ovanstående array kan kodas med sekvensen {2,1,3,4}. Detta gör det enkelt att hantera arrays av order N .

Kända arrayer

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}

En komplett databas med arrayer för alla dimensioner, som har kontrollerats noggrant, finns här [2]

Byggnad

Welch (Welch)

Welch-Costas array, eller helt enkelt Welch (Welch ) array, är en Costas array erhållen med en metod utvecklad av Lloyd R. Welch . En Welch-Costas-matris konstrueras genom att ta den primitiva roten g av ett primtal p och definiera en matris A , där if , annars 0. Resultatet är en Costas-matris med storleken p − 1. $A_{i,j}=1$ $i\equiv g^{j}{\bmod {p))$

Exempel

3 är en primitiv rotmodulo 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}}

Därför är [3 4 2 1] en Costas-permutation. Detta är en Welch (Welch) diskret exponentiell array. Den transponerade arrayen är en Welch diskret logaritmisk array.

Antalet Welch-Costas-arrayer som finns för en given storlek beror på Euler-funktionen .

Lempel-Golomb

Lempel-Golomb-metoden använder de primitiva elementen α och β från det finita fältet GF( q ) och bestämmer på liknande sätt om , annars 0. Resultatet är en Costas-matris med storleken q − 2. Om α + β = 1, då den första rad och kolumn tas bort för att bilda en annan Costas-array med storleken q − 3: det är inte känt om det finns sådana par av primitiva element för varje potens av q . $A_{i,j}=1$ $\alpha ^{i}+\beta ^{j}=1$

Se även

Litteratur

Costas, JP En studie av en klass av detektionsvågformer som har nästan idealiska egenskaper för avstånds-Doppler-tvetydighet // Proceedings of the IEEE : journal. - 1984. - Vol. 72 , nr. 8 . - P. 996-1009 .
Golomb SW , Taylor H. Konstruktion och egenskaper hos Costas arrayer // Proceedings of the IEEE : journal. - 1984. - Vol. 72 , nr. 9 . - P. 1143-1163 .
Beard J., Russo J., Erickson K., Monteleone M., Wright M. Combinatoric Collaboration on Costas Arrays and Radar Applications (engelska) // In IEEE Radar Conference : journal. - 2004. - S. 260-265 .
Richard K Guy . Avsnitt C18, F9 // Olösta problem i talteori (neopr.) . — 3:e uppl. - Springer Verlag , 2004. - ISBN 0-387-20860-7 .
Oscar Moreno. Undersökning av resultat på signalmönster för att lokalisera ett eller flera mål // Difference Sets, Sequences and Their Correlation Properties (engelska) / Alexander Pott, P. Vijay Kumar, Tor Helleseth, Dieter Jungnickel (red). — Kluwer. — ISBN 0792359585 .

Länkar

Scott Richard. www.costasarrays.org (4 oktober 2011). Arkiverad från originalet den 6 februari 2012. (obestämd)
December 1999 Programmerarens utmaning: Costas arrayer . Mactech. (obestämd)
On-Line Encyclopedia of Integer Sequences :
- A008404 : Antal Costas-arrayer av ordning n , med hänsyn till rotationer och vändningar.
- A001441 : Antal olikvärdiga Costas-arrayer av ordning n under dihedrisk grupp.