En matemáticas, una matriz de Costas se puede considerar 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 vectores de desplazamiento entre cada par de puntos son distintos. Esto da como resultado una función de ambigüedad automática de "chincheta" ideal , lo que hace que las matrices sean útiles en aplicaciones como sonar y radar . Las matrices de Costas se pueden considerar como primos bidimensionales de lo unidimensional. La construcción de la regla Golomb y, además de ser de interés matemático, tiene aplicaciones similares en el diseño experimental y la ingeniería de radar de matriz en fase .
Las matrices Costas llevan el nombre de John P. Costas , quien escribió por primera vez sobre ellas en un informe técnico de 1965. Independientemente, Edgar Gilbert también escribió sobre ellos en el mismo año, publicando lo que ahora se conoce como el método logarítmico de Welch para construir matrices Costas. [1]
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 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 para cualquier fila. Dado que cualquier columna tiene un solo punto, es posible representar una matriz de forma unidimensional. Por ejemplo, lo siguiente es una matriz de Costas válida de orden N = 4:
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
1 | 0 | 0 | 0 |
0 | 1 | 0 | 0 |
Hay puntos en las coordenadas: (1,2), (2,1), (3,3), (4,4)
Dado que la coordenada x aumenta linealmente, podemos escribir esto en 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 hace que sea fácil de comunicar los arreglos para un fin determinado de N .
Matrices conocidas
Los recuentos de matrices de Costas se conocen para los pedidos 1 a 29 [2] (secuencia A008404 en la OEIS ):
Pedido | Número |
---|---|
1 | 1 |
2 | 2 |
3 | 4 |
4 | 12 |
5 | 40 |
6 | 116 |
7 | 200 |
8 | 444 |
9 | 760 |
10 | 2160 |
11 | 4368 |
12 | 7852 |
13 | 12828 |
14 | 17252 |
15 | 19612 |
dieciséis | 21104 |
17 | 18276 |
18 | 15096 |
19 | 10240 |
20 | 6464 |
21 | 3536 |
22 | 2052 |
23 | 872 |
24 | 200 |
25 | 88 |
26 | 56 |
27 | 204 |
28 | 712 |
29 | 164 |
Están disponibles la enumeración de matrices Costas conocidas para el pedido 200, [3] el pedido 500 [4] y el pedido 1030 [5] . Aunque estas listas y bases de datos de estas matrices Costas probablemente estén casi completas, es posible que existan otras matrices Costas con órdenes superiores a 29 que no estén en estas listas.
Construcciones
Welch
Una matriz de Welch-Costas , o simplemente una matriz de Welch, es una matriz de Costas generada mediante el siguiente método, descubierto por primera vez por Edgar Gilbert en 1965 y redescubierto en 1982 por Lloyd R. Welch . La matriz de Welch-Costas se construye tomando una raíz primitiva g de un número primo py definiendo la matriz A por Si , de lo contrario 0. El resultado es una matriz Costas de tamaño p - 1.
Ejemplo:
3 es un elemento primitivo módulo 5.
- 3 1 = 3 ≡ 3 (mod 5)
- 3 2 = 9 ≡ 4 (mod 5)
- 3 3 = 27 ≡ 2 (mod 5)
- 3 4 = 81 ≡ 1 (mod 5)
Por lo tanto, [3 4 2 1] es una permutación de Costas. Más específicamente, esta es una matriz de Welch exponencial. La transposición de la matriz es una matriz de Welch logarítmica.
El número de matrices de Welch-Costas que existen para un tamaño dado 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 , de lo contrario 0. El resultado es una matriz Costas de tamaño q - 2. Si α + β = 1, entonces la primera fila y columna se pueden eliminar para formar otra matriz Costas de tamaño q - 3: tal par de elementos primitivos existe para cada potencia principal q> 2 .
Extensiones de Taylor, Lempel y Golomb
La generación de nuevas matrices de Costas sumando o restando una fila / columna o dos 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 artículo histórico de Golomb y Taylor de 1984. [7]
En 1992 se publicaron métodos más sofisticados para generar nuevas matrices Costas mediante la eliminación de filas y columnas de matrices Costas existentes que fueron generadas por los generadores Welch, Lempel o Golomb. [8] No existe un límite superior en el orden para el que estos generadores producirán Matrices de Costas.
Otros metodos
En 2004 [9] y 2007 se publicaron dos métodos que encontraron matrices Costas hasta el orden 52 utilizando métodos más complicados de agregar o eliminar filas y columnas . [10]
Variantes
Las matrices de Costas en una celosía hexagonal se conocen como matrices de panal . Se ha demostrado que solo hay un número finito de tales matrices, que deben tener un número impar de elementos, dispuestos en forma de hexágono. Actualmente, se conocen 12 de tales matrices (hasta la simetría), que se ha conjeturado que es el número total. [11]
Ver también
Notas
- ^ Costas (1965) ; Gilbert (1965) ; Un descubrimiento independiente de matrices Costas , Aaron Sterling, 9 de octubre de 2011.
- ^ Barba (2006) ; Drakakis y col. (2008) ; Drakakis, Iorio y Rickard (2011) ; Drakakis y col. (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) .
- ^ Beard y col. (2007) .
- ^ Blackburn, Simon R .; Panoui, Anastasia; Paterson, Maura B .; Stinson, Douglas R. (10 de diciembre de 2010). "Matrices de panal" . La Revista Electrónica de Combinatoria : R172 – 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) , Proceedings of the IEEE , 97 (3): 586–593, doi : 10.1109 / JPROC.2008.2011947 , archivado desde el original (PDF) el 2012-04-25 , consultado el 2011-10-10.
- Beard, James (marzo de 2006), "Generating Costas Arrays to Order 200", 40ª Conferencia Anual sobre Ciencias y Sistemas de la Información de 2006 , IEEE, doi : 10.1109 / ciss.2006.286635.
- Beard, James K. (marzo de 2008), "Polinomios del generador de matrices de Costas en campos finitos", 42ª Conferencia Anual de Ciencias de la Información y Sistemas de 2008 , IEEE, doi : 10.1109 / ciss.2008.4558709.
- Beard, James K. (2017), matrices Costas y enumeración a pedido 1030 , puerto de datos IEEE, doi : 10.21227 / H21P42.
- Beard, J .; Russo, J .; Erickson, K .; Monteleone, M .; Wright, M. (2004), "Colaboración combinatoria en matrices Costas y aplicaciones de radar", IEEE Radar Conference, Filadelfia, Pensilvania (PDF) , págs. 260–265, doi : 10.1109 / NRC.2004.1316432 , archivado desde el original (PDF ) el 2012-04-25 , consultado el 2011-10-10.
- Beard, James; Russo, Jon; Erickson, Keith; Monteleone, Michael; Wright, Michael (abril de 2007), "Metodología de búsqueda y generación de matrices de Costas", IEEE Transactions on Aerospace and Electronic Systems , 43 (2): 522–538, doi : 10.1109 / taes.2007.4285351.
- Costas, JP (1965), Restricciones medias en el diseño y el rendimiento de la sonda, Informe de 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) , Proceedings of the IEEE , 72 (8): 996–1009, doi : 10.1109 / PROC.1984.12967 , archivado desde el original (PDF) el 30 de septiembre de 2011 , consultado el 10 de octubre de 2011.
- Drakakis, Konstantinos; Rickard, Scott; Beard, James K .; Caballero, Rodrigo; Iorio, Francesco; O'Brien, Gareth; Walsh, John (octubre de 2008), "Results of the Enumeration of Costas Arrays of Order 27", IEEE Transactions on Information Theory , 54 (10): 4684-4687, doi : 10.1109 / tit.2008.928979 , hdl : 2262/59260.
- Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott (2011), "La enumeración de matrices de Costas de orden 28 y sus consecuencias", Advances in Mathematics of Communications
- Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott; Walsh, John (agosto de 2011), "Results of the enumeration of Costas arrays of order 29", Advances in Mathematics of Communications , 5 (3): 547–553, doi : 10.3934 / amc.2011.5.547.
- Gilbert, EN (1965), "Cuadrados latinos que no contienen digramas repetidos", SIAM Review , 7 : 189-198, doi : 10.1137 / 1007035 , MR 0179095.
- Golomb, Solomon W. (1984), "Construcciones algebraicas para matrices 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), "El y construcciones para matrices Costas ", IEEE Transactions on Information Theory , 38 (4): 1404–1406, doi : 10.1109 / 18.144726 , MR 1168761
- Golomb, SW ; Taylor, H. (1984), "Construcción y propiedades de matrices Costas" (PDF) , Proceedings of the IEEE , 72 (9): 1143-1163, doi : 10.1109 / PROC.1984.12994 , archivado desde el original (PDF) en 2011-09-30 , consultado 2011-10-10.
- 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), "Levantamiento 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 NATO Advanced Science Institutes, 542 , Kluwer, p. 353, ISBN 0-7923-5958-5.
- Rickard, Scott (2004), "Búsqueda de matrices Costas utilizando propiedades de periodicidad", Conferencia Internacional IMA sobre Matemáticas en el procesamiento de señales.
enlaces externos
- El desafío del programador de MacTech 1999: matrices Costas
- Enciclopedia en línea de secuencias enteras :
- A008404: Número de matrices de Costas de orden n , contando rotaciones y giros como distintos.
- A001441: Número de matrices Costas no equivalentes de orden n bajo un grupo diedro.
- "Matriz de Costas" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]