Integer linear programming techniques for constant dimension codes and related structures

Titelangaben

Heinlein, Daniel:
Integer linear programming techniques for constant dimension codes and related structures.
Bayreuth , 2018 . - 256 S.
( Dissertation, 2018 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Angaben zu Projekten

Abstract

The lattice of subspaces of a finite dimensional vector space over a finite field is combined with the so-called subspace distance or the injection distance a metric space.
A subset of this metric space is called subspace code.
If a subspace code contains solely elements, so-called codewords, with equal dimension, it is called constant dimension code, which is abbreviated as CDC.
The minimum distance is the smallest pairwise distance of elements of a subspace code.
In the case of a CDC, the minimum distance is equivalent to an upper bound on the dimension of the pairwise intersection of any two codewords.

Subspace codes play a vital role in the context of random linear network coding, in which data is transmitted from a sender to multiple receivers such that participants of the communication forward random linear combinations of the data.

The two main problems of subspace coding are the determination of the cardinality of largest subspace codes and the classification of subspace codes.

Using integer linear programming techniques and symmetry, this thesis answers partially the questions above while focusing on CDCs.

With the coset construction and the improved linkage construction, we state two general constructions, which improve on the best known lower bound of the cardinality in many cases.

A well-structured CDC which is often used as building block for elaborate CDCs is the lifted maximum rank distance code, abbreviated as LMRD.
We generalize known upper bounds for CDCs which contain an LMRD, the so-called LMRD bounds.
This also provides a new method to extend an LMRD with additional codewords.
This technique yields in sporadic cases best lower bounds on the cardinalities of largest CDCs.
The improved linkage construction is used to construct an infinite series of CDCs whose cardinalities exceed the LMRD bound.

Another construction which contains an LMRD together with an asymptotic analysis in this thesis restricts the ratio between best known lower bound and best known upper bound to at least 61.6% for all parameters.

Furthermore, we compare known upper bounds and show new relations between them.

This thesis describes also a computer-aided classification of largest binary CDCs in dimension eight, codeword dimension four, and minimum distance six.
This is, for non-trivial parameters which in addition do not parametrize the special case of partial spreads, the third set of parameters of which the maximum cardinality is determined and the second set of parameters with a classification of all maximum codes.

Provable, some symmetry groups cannot be automorphism groups of large CDCs.
Additionally, we provide an algorithm which examines the set of all subgroups of a finite group for a given, with restrictions selectable, property.
In the context of CDCs, this algorithm provides on the one hand a list of subgroups, which are eligible for automorphism groups of large codes and on the other hand codes having many symmetries which are found by this method can be enlarged in a postprocessing step.
This yields a new largest code in the smallest open case, namely the situation of the binary analogue of the Fano plane.

Abstract in weiterer Sprache

Der Verband der Untervektorräume eines endlichdimensionalen Vektorraumes über einem endlichen Körper ist versehen mit der so genannten subspace distance oder der injection distance ein metrischer Raum.
Eine Teilmenge dieses metrischen Raumes heißt subspace code.
Falls ein subspace code ausschließlich Elemente, so genannte Codeworte, derselben Dimension beinhaltet, nennt man ihn constant dimension code, abgekürzt CDC.
Die Minimaldistanz ist der kleinste paarweise Abstand von Elementen eines subspace codes.
Im Falle von CDCs ist die Minimaldistanz äquivalent zu einer oberen Schranke an die Dimension des Durchschnitts von je zwei Codewörtern.

Subspace codes spielen eine entscheidende Rolle im Kontext von random linear network coding, bei dem Daten zwischen einem Sender und mehreren Empfängern übertragen werden, so dass Teilnehmer der Kommunikation zufällige Linearkombinationen der Daten weitersenden.

Zwei wichtige Probleme des subspace coding sind die Bestimmung der Kardinalität größter subspace codes und der Klassifikation von subspace codes.

Diese Arbeit gibt unter Zuhilfenahme von Techniken der ganzzahligen linearen Optimierung und Symmetrie teilweise Antworten auf obige Fragen mit dem Fokus auf CDCs.

Mit der coset construction und der improved linkage construction geben wir zwei allgemeine Konstruktionen an, die die beste bekannte untere Schranke an die Kardinalität in vielen Fällen verbessern.

Ein als Baustein für aufwändige CDCs oft genutzter und sehr strukturierter CDC ist der lifted maximum rank distance code, abgekürzt LMRD.
Wir verallgemeinern obere Schranken für CDCs die einen LMRD beinhalten, so genannte LMRD bounds.
Dies liefert eine neue Methode um einen LMRD mit weiteren Codewörtern zu erweitern.
In sporadischen Fällen liefert diese Technik neue beste untere Schranken an die Kardinalität von größten CDCs.
Die improved linkage construction wird genutzt, um eine unendliche Serie von CDCs deren Kardinalität die LMRD bound übertrifft, zu konstruieren.

Eine weitere Konstruktion, die einen LMRD beinhaltet, gepaart mit einer asymptotischen Analyse in dieser Arbeit, beschränkt das Verhältnis zwischen bester bekannter unterer Schranke und bester bekannter oberer Schranke auf mindestens 61,6% für alle Parameter.

Des Weiteren vergleichen wir bekannte obere Schranken und zeigen neue Beziehungen zwischen ihnen auf.

Diese Arbeit beschreibt zudem eine computergestützte Klassifikation von größten binären CDCs in Dimension acht, Codewortdimension vier und Minimaldistanz sechs.
Dies ist, für nichttriviale Parameter, die zusätzlich nicht den Spezialfall von partial spreads parametrisieren, der dritte Parametersatz, bei dem die maximale Kardinalität festgestellt wurde und der zweite Parametersatz, bei dem eine Klassifikation aller größten Codes vorliegt.

Einige Symmetriegruppen können beweisbar nicht Automorphismengruppen von großen CDCs sein.
Wir geben zusätzlich einen Algorithmus an, der alle Untergruppen einer endlichen Gruppe nach einer vorgegebenen, mit Einschränkungen wählbaren, Eigenschaft durchsucht.
Im Kontext von CDCs liefert dieser Algorithmus zum einen eine Liste von Untergruppen, die als Kandidaten von Automorphismengruppen von großen Codes infrage kommen und zum anderen können hierdurch gefundene Codes mit viel Symmetrie weiterverarbeitet und vergrößert werden.
Dies liefert einen neuen größten Code in dem kleinsten offenen Fall, nämlich in der Situation des binären Analogons der Fano Ebene.