conjunto de costas

En matemáticas, una matriz de Costas puede considerarse geométricamente como un conjunto de n puntos, cada uno en el centro de un cuadrado en un mosaico cuadrado de n × n , de modo que cada fila o columna contiene solo un punto, y todos los n ( n − 1)/2 los vectores de desplazamiento entre cada par de puntos son distintos. Esto da como resultado una función de ambigüedad automática ideal , lo que hace que los conjuntos sean útiles en aplicaciones como sonar y radar . Los conjuntos de Costas pueden considerarse primos bidimensionales de la construcción unidimensional de la regla Golomb y, además de ser de interés matemático, tienen aplicaciones similares en el diseño experimental y la ingeniería de radares en fase .

Los conjuntos Costas llevan el nombre de John P. Costas , quien escribió por primera vez sobre ellos en un informe técnico de 1965. De forma independiente, Edgar Gilbert también escribió sobre ellos ese mismo año, publicando lo que ahora se conoce como el método logarítmico de Welch para construir matrices de Costas. ^[1] La enumeración general de matrices de Costas es un problema abierto en informática y encontrar un algoritmo que pueda resolverlo en tiempo polinomial es una cuestión de investigación abierta.

Representación numérica

Una matriz de Costas se puede representar numéricamente como una matriz de números n × n , donde cada entrada es 1, para un punto, o 0, para la ausencia de un punto. Cuando se interpretan como matrices binarias , estas matrices de números tienen la propiedad de que, dado que cada fila y columna tiene la restricción de que solo tiene un punto, también son matrices de permutación . Por lo tanto, las matrices de Costas para cualquier n dado son un subconjunto de las matrices de permutación de orden n .

Las matrices generalmente se describen como una serie de índices que especifican la columna de cualquier fila. Dado que cualquier columna tiene un solo punto, es posible representar una matriz unidimensionalmente. Por ejemplo, la siguiente es una matriz de Costas válida de orden N = 4:

{\begin{array}{|c|c|c|c|}\hline 0&0&0&1\\\hline 0&0&1&0\\\hline 1&0&0&0\\\hline 0&1&0&0\\\hline \end{array}}

o simplemente

{\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\ \hline\end{matriz}}

Hay puntos en las coordenadas: (1,2), (2,1), (3,3), (4,4)

Dado que la coordenada x aumenta linealmente, podemos escribir esto de forma abreviada como el conjunto de todas las coordenadas y . La posición en el conjunto sería entonces la coordenada x . Observe: {2,1,3,4} describiría la matriz antes mencionada. Esto define una permutación. Esto facilita la comunicación de las matrices para un orden determinado de N.

matrices conocidas

Los recuentos de matrices de Costas se conocen para los pedidos del 1 al 29 ^[2] (secuencia A008404 en OEIS ):

A continuación se muestran algunas matrices conocidas: N = 1 {1}

norte = 2 {1,2} {2,1}

norte = 3 {1,3,2} {2,1,3} {2,3,1} {3,1,2}

norte = 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}

norte = 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}

norte = 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}

Está disponible la enumeración de matrices de Costas conocidas para ordenar 200, ^[3] ordenar 500 ^[4] y ordenar 1030 ^[5] . Aunque es probable que estas listas y bases de datos de estos conjuntos de Costas estén casi completas, es posible que existan otros conjuntos de Costas con órdenes superiores a 29 que no estén en estas listas.

Construcciones

galés

Una matriz Welch-Costas , o simplemente una matriz Welch, es una matriz Costas generada utilizando el siguiente método, descubierta por primera vez por Edgar Gilbert en 1965 y redescubierta en 1982 por Lloyd R. Welch . La matriz de Welch-Costas se construye tomando una raíz primitiva g de un número primo p y definiendo la matriz A por if , en caso contrario 0. El resultado es una matriz de Costas de tamaño p − 1. $A_{i,j}=1$ $j\equiv g^{i}{\bmod {p}}$

Ejemplo:

3 es un elemento primitivo módulo 5.

3 ¹ = 3 ≡ 3 (mod 5)

3 ² = 9 ≡ 4 (mod 5)

3 ³ = 27 ≡ 2 (mod 5)

3 ⁴ = 81 ≡ 1 (mod 5)

Por tanto, [3 4 2 1] es una permutación de Costas. Más específicamente, se trata de una matriz Welch exponencial. La transposición de la matriz es una matriz de Welch logarítmica.

El número de matrices Welch-Costas que existen para un tamaño determinado depende de la función totient .

Lempel–Golomb

La construcción de Lempel-Golomb toma α y β como elementos primitivos del campo finito GF( q ) y define de manera similar si , en caso contrario 0. El resultado es una matriz de Costas de tamaño q − 2. Si α + β = 1, entonces el primero la fila y la columna se pueden eliminar para formar otra matriz de Costas de tamaño q − 3: tal par de elementos primitivos existe para cada potencia prima q>2 . $A_{i,j}=1$ $\alpha ^{i}+\beta ^{j}=1$

Extensiones de Taylor, Lempel y Golomb

La generación de nuevos arreglos de Costas sumando o restando una o dos filas/columnas con un 1 o un par de unos en una esquina se publicó en un artículo centrado en los métodos de generación ^[6] y en el histórico artículo de Golomb y Taylor de 1984. ^[7]

En 1992 se publicaron métodos más sofisticados para generar nuevos conjuntos Costas eliminando filas y columnas de los conjuntos Costas existentes que fueron generados por los generadores Welch, Lempel o Golomb. ^[8] No existe un límite superior en el orden en el que estos generadores producirán Conjuntos de costas.

Otros metodos

^{En 2004 [9]} y 2007 se publicaron dos métodos que encontraron matrices de Costas hasta el orden 52 utilizando métodos más complicados para agregar o eliminar filas y columnas ^.

Variantes

Los conjuntos de costas en una red hexagonal se conocen como conjuntos de panal . Se ha demostrado que existen un número finito de conjuntos de este tipo, que deben tener un número impar de elementos dispuestos en forma de hexágono. Actualmente se conocen 12 de estos conjuntos (hasta la simetría), lo que se supone que es el número total. ^[11]

Ver también

Notas

^ Costas (1965); Gilbert (1965); Un descubrimiento independiente de los conjuntos de Costas, Aaron Sterling, 9 de octubre de 2011.
^ Barba (2006); Drakakis et al. (2008); Drakakis, Iorio y Rickard (2011); Drakakis et al. (2011)
^ Barba (2006).
^ Barba (2008).
^ Barba (2017); Beard, James K., Archivos para descargar: Costas Arrays , consultado el 20 de abril de 2020
^ Golomb (1984).
^ Golomb y Taylor (1984).
^ Golomb (1992).
^ Rickard (2004).
^ Barba y col. (2007).
^ Blackburn, Simón R.; Panoui, Anastasia; Paterson, Maura B.; Stinson, Douglas R. (10 de diciembre de 2010). "Matrices de panal". La Revista Electrónica de Combinatoria . 17 : R172. doi : 10.37236/444 . ISSN 1077-8926.

Referencias

Barker, L.; Drakakis, K.; Rickard, S. (2009), "Sobre la complejidad de la verificación de la propiedad Costas" (PDF) , Actas del IEEE , 97 (3): 586–593, doi :10.1109/JPROC.2008.2011947, S2CID 29776660, archivado del original (PDF) el 25 de abril de 2012 , consultado el 10 de octubre de 2011.
Beard, James (marzo de 2006), "Generating Costas Arrays to Order 200", 2006 40ª Conferencia Anual sobre Ciencias y Sistemas de la Información , IEEE, doi :10.1109/ciss.2006.286635, S2CID 2241386.
Beard, James K. (marzo de 2008), "Polinomios generadores de matrices de Costas en campos finitos", 2008, 42ª Conferencia Anual sobre Ciencias y Sistemas de la Información , IEEE, doi :10.1109/ciss.2008.4558709, S2CID 614347.
Beard, James K. (2017), Matrices de Costas y enumeración para ordenar 1030, IEEE Dataport, doi :10.21227/H21P42.
Barba, J.; Ruso, J.; Erickson, K.; Monteleone, M.; Wright, M. (2004), "Colaboración combinatoria en conjuntos Costas y aplicaciones de radar", IEEE Radar Conference, Filadelfia, Pensilvania (PDF) , págs. 260–265, doi :10.1109/NRC.2004.1316432, S2CID 7733481, archivado desde original (PDF) el 25 de abril de 2012 , consultado el 10 de octubre de 2011.
Barba, James; Ruso, Jon; Erickson, Keith; Monteleone, Michael; Wright, Michael (abril de 2007), "Metodología de búsqueda y generación de matrices Costas", IEEE Transactions on Aerospace and Electronic Systems , 43 (2): 522–538, doi :10.1109/taes.2007.4285351, S2CID 32271456.
Costas, JP (1965), Restricciones medias en el diseño y rendimiento del sonar , Informe Clase 1 R65EMH33, GE Corporation
Costas, JP (1984), "Un estudio de una clase de formas de onda de detección que tienen propiedades de ambigüedad Doppler de rango casi ideal" (PDF) , Actas del IEEE , 72 (8): 996–1009, doi :10.1109/PROC.1984.12967 , S2CID 2742217, archivado desde el original (PDF) el 30 de septiembre de 2011 , consultado el 10 de octubre de 2011.
Drakakis, Konstantinos; Rickard, Scott; Barba, James K.; Caballero, Rodrigo; Iorio, Francisco; O'Brien, Gareth; Walsh, John (octubre de 2008), "Resultados de la enumeración de matrices Costas de orden 27", IEEE Transactions on Information Theory , 54 (10): 4684–4687, doi :10.1109/tit.2008.928979, hdl : 2262/59260.
Drakakis, Konstantinos; Iorio, Francisco; Rickard, Scott (2011), "La enumeración de matrices de Costas de orden 28 y sus consecuencias", Avances en Matemáticas de las Comunicaciones
Drakakis, Konstantinos; Iorio, Francisco; Rickard, Scott; Walsh, John (agosto de 2011), "Resultados de la enumeración de matrices de Costas de orden 29", Avances en Matemáticas de las Comunicaciones , 5 (3): 547–553, doi : 10.3934/amc.2011.5.547 , hdl : 2262/ 59260.
Gilbert, EN (1965), "Cuadrados latinos que no contienen diagramas repetidos", SIAM Review , 7 (2): 189–198, doi :10.1137/1007035, MR 0179095.
Golomb, Solomon W. (1984), "Construcciones algebraicas para matrices de Costas", Journal of Combinatorial Theory , Serie A, 37 (1): 13–21, doi :10.1016/0097-3165(84)90015-3, MR 0749508.
Golomb, Solomon W. (1992), "Las construcciones y para matrices Costas", IEEE Transactions on Information Theory , 38 (4): 1404–1406, doi :10.1109/18.144726, MR 1168761 $T_{4}$ ${\ Displaystyle G_ {4}}$
Golomb, suroeste ; Taylor, H. (1984), "Construcción y propiedades de los arreglos Costas" (PDF) , Actas del IEEE , 72 (9): 1143–1163, doi :10.1109/PROC.1984.12994, S2CID 39718506, archivado desde el original ( PDF) el 30 de septiembre de 2011 , consultado el 10 de octubre de 2011.
Guy, Richard K. (2004), "Secciones C18 y F9", Problemas no resueltos en teoría de números (3.ª ed.), Springer Verlag , ISBN 0-387-20860-7.
Moreno, Oscar (1999), “Encuesta de resultados sobre patrones de señales para localizar uno o múltiples objetivos”, en Pott, Alexander; Kumar, P. Vijay; Helleseth, Tor; et al. (eds.), Conjuntos de diferencias, secuencias y sus propiedades de correlación , Serie de Institutos de Ciencias Avanzadas de la OTAN, vol. 542, Kluwer, pág. 353, ISBN 0-7923-5958-5.
Rickard, Scott (2004), "Búsqueda de matrices de Costas utilizando propiedades de periodicidad", Conferencia internacional IMA sobre matemáticas en procesamiento de señales.

enlaces externos

MacTech 1999 El desafío del programador: matrices Costas
Enciclopedia en línea de secuencias enteras :
- A008404: Número de matrices de Costas de orden n, contando rotaciones y volteos como distintos.
- A001441: Número de conjuntos de Costas no equivalentes de orden n bajo el grupo diédrico.
"Matriz de Costas", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]