Dissertation/Thesis Abstract

Integer Linear Programming Techniques for Constant Dimension Codes and Related Structures
by Heinlein, Daniel, Dr.Nat., Universitaet Bayreuth (Germany), 2018, 257; 13817237
Abstract (Summary)

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.

Indexing (document details)
Advisor:
Commitee:
School: Universitaet Bayreuth (Germany)
School Location: Germany
Source: DAI-C 81/1(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Computer science
Keywords: Subspace coding
Publication Number: 13817237
ISBN: 9781088398258
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest