Costas Arrays
Publications
- Circular Costas maps: a multidimensional analog of circular Costas sequences . (2022). Ivelisse Rubio, & Jaziel Torres.
Abstract: A unifying theoretical framework is presented, in which the connections among Costas sequences, circular Costas sequences, Costas polynomials, the shifting property, and Welch sequences are extended to the multidimensional context. Several conjectures on multidimensional periodic Costas arrays by J. Ortiz-Ubarri et al. are proved. Furthermore, a conjecture on Costas polynomials over extension fields presented by Muratović-Ribić et al. is showed to be a multidimensional extension of a conjecture by Golomb and Moreno on circular Costas sequences. A weaker version of said conjecture is proved by considering a multidimensional extension of the shifting Costas property defined by O. Moreno.
Published in https://doi.org/10.48550/arXiv.2210.16661.
- Multidimensional Costas Arrays and Their Periodicity . (2022). Ivelisse Rubio, & Jaziel Torres.
Abstract: A novel higher-dimensional definition for Costas arrays is introduced. This defini- tion works for arbitrary dimensions and avoids some limitations of previous definitions. Some non-existence results are presented for multidimensional Costas arrays preserv- ing the Costas condition when the array is extended periodically throughout the whole space. In particular, it is shown that three-dimensional arrays with this property must have the least possible order; extending an analogous two-dimensional result by H. Taylor. Said result is conjectured to extend for Costas arrays of arbitrary dimensions.Published in https://doi.org/10.48550/arXiv.2208.02378.
Student Projects
Master Students
- Circular Costas maps: a multidimensional analog of circular Costas sequences . (2022). Ivelisse Rubio, & Jaziel Torres.
Abstract: A unifying theoretical framework is presented, in which the connections among Costas sequences, circular Costas sequences, Costas polynomials, the shifting property, and Welch sequences are extended to the multidimensional context. Several conjectures on multidimensional periodic Costas arrays by J. Ortiz-Ubarri et al. are proved. Furthermore, a conjecture on Costas polynomials over extension fields presented by Muratović-Ribić et al. is showed to be a multidimensional extension of a conjecture by Golomb and Moreno on circular Costas sequences. A weaker version of said conjecture is proved by considering a multidimensional extension of the shifting Costas property defined by O. Moreno.
Published in https://doi.org/10.48550/arXiv.2210.16661.
- Multidimensional Costas Arrays and Their Periodicity . (2022). Ivelisse Rubio, & Jaziel Torres.
Abstract: A novel higher-dimensional definition for Costas arrays is introduced. This defini- tion works for arbitrary dimensions and avoids some limitations of previous definitions. Some non-existence results are presented for multidimensional Costas arrays preserv- ing the Costas condition when the array is extended periodically throughout the whole space. In particular, it is shown that three-dimensional arrays with this property must have the least possible order; extending an analogous two-dimensional result by H. Taylor. Said result is conjectured to extend for Costas arrays of arbitrary dimensions.Published in https://doi.org/10.48550/arXiv.2208.02378.
- Multidimensional Costas Arrays and Periodic Properties. Thesis. (2022). Jaziel Torres.
Abstract: Costas arrays were first introduced for SONAR detection applications, but later became an interesting object of mathematical research. Several generalizations of Costas arrays to multiple dimensions have been proposed. In this thesis, we lay the ground for the study of multidimensional Costas arrays by proposing concepts and showing results that extend into the higher-dimensional realm most of what is known about the periodicity of two-dimensional Costas arrays. Among the most important results is, for large classes of arrays, the non-existence of multidimensional Costas arrays that preserve the Costas property in every commensurate window when extended periodically in all directions. We also extend to higher-dimensions the Golomb-Moreno Conjecture that asserts all circular Costas maps are those from the Welch construction, which had been proved in the two-dimensional case. We prove a weaker version of this conjecture in the higher-dimensional context.
Multidimensional Linear Complexity
Publications
- Analysis and Computation of Multidimensional Linear Complexity of Periodic Arrays. (2022). Rafael Arce, Carlos Hernández, José Ortiz, Ivelisse Rubio, & Jaziel Torres.
Abstract: Linear complexity is an important parameter for arrays that are used in applications related to information security. In this work we present new results on the multidimensional linear complexity of periodic arrays obtained using the definition and method proposed in [2,6,11]. The results include a generalization of a bound for the linear complexity, a comparison with the measure of complexity for multisequences, and computations of the complexity of arrays with periods that are not relatively prime for which the “unfolding method” does not work. We also present conjectures for exact formulas and the asymptotic behavior of the complexity of some array constructions.Published in https://doi.org/10.48550/arXiv.2207.14398.
- Linear complexity analysis of multidimensional periodic arrays. (2019). Rafael Arce-Nazario, Francis Castro, Domingo Gómez-Pérez, Oscar Moreno, José Ortiz-Ubarri, Ivelisse Rubio, & Andrew Tirkel.
Abstract: The linear complexity of a sequence is an important parameter for many applications, especially those related to information security, and hardware implementation. It is desirable to develop a corresponding measure and theory for multidimensional arrays that are consistent with those of sequences. In this paper we use Gröbner bases to develop a theory for analyzing the multidimensional linear complexity of general periodic arrays. We also analyze arrays constructed using the method of composition and establish tight bounds for their multidimensional linear complexity.
Final version published in Applicable Algebra in Engineering, Communication and Computing, 1-21, doi: 10.1007/s00200-019-00393-z, 2019.
- Finding a Gröbner basis for the ideal of recurrence relations on $m$-dimensional periodic arrays. (2016). Chris Heegard, Ivelisse Rubio, & Moss Sweedler.
Abstract: Recent developments in applications of multidimensional periodic arrays [9] have drawn new attention to the computation of Gröbner bases for the ideal of linear recurrence relations on the arrays. An m-dimensional infinite array can be represented by a multivariate power series sitting within the ring of multivariate Laurent series. We reinterpret the problem of finding linear recurrence relations on m-dimensional periodic arrays as finding the kernel of a module map involving quotients of Laurent series and present an algorithm to compute a Gröbner basis for this kernel. The algorithm does not assume the knowledge of a generating set for the kernel of this ideal and it is based on linear algebra computations. Finding a generating set is one application of the algorithm
Final version published in Contemporary Developments in Finite Fields and Applications (pp.296-320). Worls Scientific, June, 2016.
- Linear Complexity for Multidimensional Arrays – a Numerical Invariant. (2015). Tom Høholdt, Domingo Gómez-Pérez, Oscar Moreno, & Ivelisse Rubio.
Abstract: Linear complexity is a measure of how complex a one dimensional sequence can be. In this paper we extend the concept of linear complexity to multiple dimensions and present a definition that is invariant under well-orderings of the arrays. As a result we find that our new definition for the process introduced in the patent titled “Digital Watermarking” produces arrays with good asymptotic properties.
Final version published in Proceedings of the IEEE International Symposium on Information Theory (ISIT 2015). IEEE, 2015. p. 2697-2701.
Student Projects
Undergraduate Students
- Analysis and Computation of Multidimensional Linear Complexity of Periodic Arrays. Presentation. (2019). Luis Quiñones & Jaziel Torres.
Abstract: Sequences and multidimensional periodic arrays with entries in finite fields have important applications in coding theory and cryptography. The correlations and the linear complexity of the sequences and multidimensional arrays are important parameters for many applications, especially those related to information security, and hardware implementation. The general goal of this research is to study different constructions of sequences and multidimensional periodic arrays and their correlation and complexity parameters. We give a proof for the exact value of the complexity of an array constructed using the composition method that was previously conjectured.
- Complejidad de arreglos periódicos multidimensionales. Bachelor Thesis. (2016). Jeffry Matos.
Abstract: Para obtener arreglos que puedan tener aplicaciones en sistemas que utilizan marcas de agua digitales, criptografía o señales de radar multi-blanco, los mismos deben poseer buenas propiedades de correlación y complejidad [5]. Por esto es imperativo el poder tener una medida de la complejidad de un arreglo multidimensional que no presente limitaciones. Las bases de Gröbner [3] son conjuntos de polinomios que poseen propiedades algorítmicas muy ricas. Al utilizarlas, es posible generalizar la definición de la medida de la complejidad lineal de una sucesión a un arreglo. Si calculamos alguna base de Gröebner que genere los polinomios asociados al arreglo periódico multidimensional, entonces podremos examinar la complejidad del arreglo porque esto permite obtener un conjunto $\Delta_{Val(A)}$ cuyo tamaño define la complejidad lineal del arreglo. En este trabajo se estudian algunas propiedades de arreglos construidos utilizando un método propuesto por Moreno y Tirkel [7]. Se utilizó el algoritmo de Rubio-Sweedler [9] para computar las bases de Gröbner del arreglo y con las mismas examinar la complejidad de arreglos periódicos multidimensionales obtenidos con construcciones en [7], comparar con la complejidad de los arreglos vistos como multisucesiones [8], formular conjeturas y obtener resultados.
- Algoritmo para computar la complejidad linear de arreglos periodicos multidimensionales. Technical Report. (2016). Lillian González.
Abstract: Moreno y Terkel presentaron una construcción de arreglos periódicos multidimensionales con propiedades de buena correlación y complejidad. Para
analizar la complejidad de estos arreglos se “desenvolvían” utilizando el Teorema del Residuo Chino y luego se analizaban con el algoritmo Berlekamp-Massey. Pero este método presentaba una restricción en las dimensiones del arreglo pues tenían que ser coprimos. En [4, 5] fue propuesto una teoría nueva para analizar la
complejidad linear de arreglos multidimensionales que no tiene esta restricción; provee una definición de complejidad linear de arreglos multidimensionales que es consistente con la definición de complejidad linear en una dimensión. En esta investigación se implementa el algoritmo desarrollado en [3] sobre la teoría presentada en [4, 5].