Contributions to the theory of Costas arrays

Abstract

This thesis aims to study Costas arrays from different points of view. A Costas array of size n is an n × n binary matrix such that no two of the (n/2) line segments connecting 1s have the same length and slope. Costas arrays are attractive, highly combinatorial objects with applications in radar engineering and signal processing that motivates us to study them carefully. Firstly, we investigated equivalent definitions and the methods, based on finite fields, that allow us to construct Costas arrays for infinitely many sizes, but not all sizes. There are three main approaches currently being considered to study Costas arrays; algebraic constructions based on finite fields by which we can construct Costas arrays of sizes equal to or a bit less than prime powers (systematically constructed). The other method is computer search, and the third is heuristic techniques. The enumeration of all Costas arrays up to size 29 has been completed via exhaustive search methods, revealing that more than 90% of these arrays are of completely unknown origin, called sporadic Costas arrays. So far, there is a general lack of research on the properties of sporadic Costas arrays, indicating an unclear relationship between sporadic Costas arrays and systematically constructed ones. One possible approach to make a link between systematically constructed Costas arrays and sporadic ones could be defining transformations that transform systematically generated Costas arrays to sporadic ones and vice versa. Our primary concern is to examine how it is possible to transform a given Costas array to obtain another Costas array or create another array close to being a Costas array and then examine the violation causes to the Costas property. Then, we can investigate the possible ways to eliminate or reduce these violation causes. We introduce a new transformation with the property that we can obtain another Costas array by transforming a given one for some Costas arrays. Surprisingly, some of the systematically constructed Costas arrays produce sporadic Costas arrays after applying the transformation. Costas arrays have perfect aperiodic properties, a solid property to ask, namely permutation matrices with aperiodic autocorrelation of at most one. By applying our new transformation on a given Costas array, we obtain a new array with the property that the values of its aperiodic autocorrelation function for all possible non-zero shifts are at most two. These arrays are called almost Costas arrays. We will also examine Costas arrays from permutation points of view and prove that we could not construct a Costas array for a specific class of permutation, namely odd permutation. The distinctness of all line segments formed by joining pairs of ones in a given Costas array implies that a permutation matrix fails to be a Costas array if and only if it includes ones that form a (possibly degenerate) parallelogram. We refer to these parallelograms as forbidden configurations. Therefore, a Costas array has no forbidden configurations. Consequently, a permutation matrix is close to being a Costas array if and only if it contains as few as possible forbidden configurations. With this in mind, we investigate the number of forbidden configurations in some classes of permutation matrices and introduce a transformation by which we can reduce the total number of forbidden configurations for these classes. We discover a close relationship between the class of odd permutations and exponential Welch Costas arrays. Exponential Welch Costas arrays have G-symmetric properties. We will show how G-symmetric arrays can be constructed using transforming odd permutations. Moreover, we realized that this transformation significantly reduces the number of forbidden configurations in a given odd permutation array. This perspective also helped us to construct a class of permutation polynomials over finite fields that is differentially at most 6-uniform, meaning the permutation matrices associated with this permutation polynomials have the property that for all possible non-zero shifts, the periodic autocorrelation function values are at most 6. These differentially 6-uniform mappings can be constructed by transforming an inverse function over a finite field. We also observe that constructing G-symmetric permutation matrices from odd permutations leads to much fewer forbidden configurations, meaning the permutation matrices associated with these transformed odd permutations are closer to Costas arrays. Moreover, we will see that all G-symmetric Costas arrays of even sizes can be found by applying this transformation on odd permutations. This attitude allows us to search for G-symmetric Costas arrays by checking the Costas property of (2 n/2 x (n/2)!) permutation matrices instead of n!, which results in a notable reduction in the search space. In the last chapter, we discuss a surprising link between exponential Welch Costas arrays and power mappings constructed over a finite field with p elements, where p is a prime. We determine the maximal aperiodic crosscorrelation of pairs of power mappings using an exhaustive search. In some exceptional cases, we will provide theoretical proof for the maximal crosscorrelation of the family of power mappings. We will discuss how the maximal crosscorrelation of the family of power mappings is almost the same as the maximal crosscorrelation of the family of exponential Welch. This observation motivates us to extend the family of Welch Costas arrays with the family of power mappings and then investigate the maximal crosscorrelation of this extended family. We determine the maximal crosscorrelation of this extended family by exhaustive search. Surprisingly, the maximal crosscorrelation of this extended family is equal to the maximal crosscorrelation of the family of exponential Welch, constructed over a finite field with p elements, where p is not a safe prime. In the case where p is a safe prime also, there is a close relationship that we will discuss. Moreover, we will discuss why providing theoretical proof for our observed results regarding the maximal crosscorrelation of this extended family can be tremendously complex. Families of arrays with low crosscorrelation properties are desirable for application in multiuser and multiplexing systems. Therefore, families of Costas arrays with low crosscorrelation are beneficial for such applications. With this in mind, we will introduce a subfamily of Lempel-Golomb Costas arrays that indicate lower crosscorrelation than the family of all Lempel- Golomb Costas arrays.

In dieser Dissertation sollen Costas-Matrizen aus verschiedenen Blickwinkeln untersucht werden. Eine Costas-Matrix der Größe n ist eine n × n 0-1-Matrix, bei der keine zwei der (n2 ) Liniensegmente, die Einsen verbinden, die gleiche Länge und Steigung haben. Costas-Matrizen sind Interessant, kombinatorische Objekte mit Anwendungen in der Radartechnik und der Signalverarbeitung, die uns dazu motivieren, sie sorgfältig zu untersuchen. Zunächst untersuchten wir die äquivalenten Definitionen und die auf endlichen Körpern basierenden Methoden, die es uns erlauben, Costas-Matrizen für unendlich viele Größen, aber nicht für alle Größen, zu konstruieren. Derzeit werden drei Hauptansätze zur Untersuchung von Costas-Matrizen erwogen: algebraische Konstruktionen auf der Grundlage der Theorie endlicher Körper, mit denen wir Costas-Matrizen mit Größen gleich oder etwas kleiner als Primzahlen konstruieren können (systematisch konstruiert). Die zweite Methode ist die Computersuche, und die dritte sind heuristische Techniken. Die Aufzählung aller Costas-Matrizen bis zur Größe 29 wurde mit Hilfe erschöpfender Suchmethoden abgeschlossen, wobei sich herausstellte, dass mehr als 90% dieser Matrizen völlig unbekannten Ursprungs sind, nämlich die so genannten sporadischen Costas-Matrizen. Bislang ist die Beziehung zwischen sporadischen Costas-Matrizen und systematisch konstruierten Matrizen unklar. Ein möglicher Ansatz, eine Verbindung zwischen systematisch konstruierten Costas-Matrizen und sporadischen Matrizen herzustellen, könnte darin bestehen, Transformationen zu definieren, die systematisch generierte Costas-Matrizen in sporadische umwandeln und umgekehrt. unser Hauptziel ist es, zu untersuchen, wie es möglich ist, eine gegebene Costas-Matrix umzuwandeln, um eine andere Costas-Matrix zu erhalten oder eine andere Matrix zu erstellen, die einer Costas-Matrix nahe kommt, und dann die Ursachen der Verletzung der Costas-Eigenschaft zu untersuchen. Anschließend können wir untersuchen, wie sich die Ursachen für diese Verstöße beseitigen oder verringern lassen. Wir führen eine neue Transformation ein, die einige Costas-Matrizen in andere Costas- Matrix transformiert. Überraschenderweise ergeben einige der systematisch konstruierten Costas-Matrizen nach Anwendung der Transformation sporadische Costas-Matrizen. Costas-Matrizen haben perfekte aperiodische Eigenschaften, was bedeutet, dass diese Permutationsmatrizen eine aperiodische Autokorrelation von höchstens eins haben. Durch Anwendung unserer neuen Transformation auf eine gegebene Costas-Matrix erhalten wir eine neue Matrix mit der Eigenschaft, dass die Werte ihrer aperiodischen Autokorrelationsfunktion für alle möglichen Verschiebungen ungleich Null höchstens zwei sind. Diese Matrizen werden als Fast-Costas-Matrizen bezeichnet. Wir werden Costas-Matrizen auch unter Permutationsgesichtspunkten untersuchen und beweisen, dass wir für eine bestimmte Klasse von Permutationen, nämlich ungerade Permutationen, keine Costas-Matrizen konstruieren können. Die Unterscheidbarkeit aller Liniensegmente, die durch das Verbinden von Paaren von Einsen in einer gegebenen Costas- Matrize gebildet werden, impliziert, dass eine Permutationsmatrix dann und nur dann keine Costas-Matrix ist, wenn sie Einsen enthält, die ein (möglicherweise entartetes) Parallelogramm bilden. Wir bezeichnen diese Parallelogramme als verbotene Konfigurationen. Eine Costas- Matrix hat also keine verbotenen Konfigurationen. Folglich kommt eine Permutationsmatrix einer Costas-Matrize nur dann nahe, wenn sie so wenige verbotene Konfigurationen wie möglich enthält. Vor diesem Hintergrund untersuchen wir die Anzahl der verbotenen Konfigurationen in einigen Klassen von Permutationsmatrizen und führen eine Transformation ein, mit der wir die Gesamtzahl der verbotenen Konfigurationen für diese Klassen reduzieren können. Wir entdecken eine enge Beziehung zwischen der Klasse der ungeraden Permutationen und exponentiellen Costas-Matrizen. Exponentielle Costas-Matrizen haben G-symmetrische Eigenschaften. Wir werden zeigen, wie G-symmetrische Matrizen durch Transformation ungerader Permutationen konstruiert werden können. Außerdem haben wir festgestellt, dass diese Transformation die Anzahl der verbotenen Konfigurationen in einer gegebenen Matrize mit ungeraden Permutationen erheblich reduziert. Diese Perspektive hat uns auch geholfen, eine Klasse von Permutationspolynomen über endlichen Körpern zu konstruieren, die differentiell höchstens 6-uniform ist, was bedeutet, dass die Permutationsmatrizen, die mit diesen Permutationspolynomen verbunden sind, die Eigenschaft haben, dass für alle möglichen Nicht- Null-Verschiebungen die periodischen Autokorrelationsfunktionswerte höchstens 6 sind. Diese differentiell 6-uniformen Abbildungen können durch Transformation einer Umkehrfunktion über einen endlichen Körper konstruiert werden. Wir beobachten auch, dass die Konstruktion von G-symmetrischen Permutationsmatrizen aus ungeraden Permutationen zu viel weniger verbotenen Konfigurationen führt, was bedeutet, dass die mit diesen transformierten ungeraden Permutationen verbundenen Permutationsmatrizen näher an Costas-Matrizen sind. Außerdem werden wir sehen, dass alle G-symmetrischen Costas-Matrizen gerader Größe durch Anwendung dieser Transformation auf ungerade Permutationen gefunden werden können. Diese Sichtweise ermöglicht es uns, nach G-symmetrischen Costas-Matrizen zu suchen, indem wir die Costas- Eigenschaft von (2 n/2 x (n/2)!) statt n! Permutationsmatrizen überprüfen, was zu einer beträchtlichen Reduzierung des Suchraums führt. Im letzten Kapitel diskutieren wir eine überraschende Verbindung zwischen exponentiellen Costas-Matrizen und Potenzabbildungen, die über einem endlichen Körper mit p Elementen konstruiert sind, wobei p eine Primzahl ist. Wir bestimmen die maximale aperiodische Kreuzkorrelation von Paaren von Potenzabbildungen mit Hilfe einer erschöpfenden Suche. In einigen Ausnahmefällen werden wir einen theoretischen Beweis für die maximale Kreuzkorrelation der Familie der Potenzabbildungen liefern. Wir werden erörtern, dass die maximale Kreuzkorrelation der Familie der Potenzabbildungen fast die gleiche ist wie die maximale Kreuzkorrelation der Familie der exponentiellen Welch. Diese Beobachtung motiviert uns, die Familie der Costas-Matrizen um die Familie der Potenzabbildungen zu erweitern und dann die maximale Kreuzkorrelation dieser erweiterten Familie zu untersuchen. Wir bestimmen die maximale Kreuzkorrelation dieser erweiterten Familie durch erschöpfende Suche. Überraschenderweise ist die maximale Kreuzkorrelation dieser erweiterten Familie gleich der maximalen Kreuzkorrelation der Familie der exponentiellen Welch, die über einem endlichen Körper mit p Elementen konstruiert wurde, wobei p keine sichere Primzahl ist. Auch für den Fall, dass p eine sichere Primzahl ist, gibt es eine enge Beziehung, die wir diskutieren werden. Außerdem werden wir erörtern, warum ein theoretischer Beweis für die von uns beobachteten Ergebnisse bezüglich der maximalen Kreuzkorrelation dieser erweiterten Familie äußerst komplex sein kann. Familien von Matrizen mit geringer Kreuzkorrelation sind für Anwendungen in Multiuser- und Multiplexing-systemen wünschenswert. Daher sind Familien von Costas-Matrizen mit geringer Kreuzkorrelation für solche Anwendungen von Vorteil. In diesem Sinne werden wir eine Unterfamilie von Costas-Matrizen einführen, die eine geringere Kreuzkorrelation aufweisen als die Familie aller Costas-Matrizen.