Constructions, decoding and automorphisms of subspace codes

Abstract

Subspace codes are a family of codes used for (among others) random network coding, which is a model for multicast communication. These codes are defined as sets of vector spaces over a finite field. The main research problems arising in this area are the construction of codes with large cardinality for a given length and minimum distance and the development of fast and efficient decoding algorithms for these codes. In this thesis we address both of these problems and improve the known results from different aspects. We mainly focus on constant dimension codes, which is a subclass of subspace codes where each codeword has the same fixed dimension. First, we give new code constructions which improve the lower bounds on the size of constant dimension codes. To do so we introduce the concept of pending dots and pending blocks and use these to modify the lifted Ferrers diagram rank metric code construction. With our new constructions we can construct larger codes than known so far for certain parameter sets. Then we introduce orbit codes and show that these codes can be seen as the analogs of linear codes in classical block coding theory. We study the subclass of cyclic orbit codes in more detail and show what type of codes can be constructed as cyclic orbit codes. Moreover, we develop several decoding algorithms that are more efficient than other known algorithms for certain code parameters. The first two algorithms are minimum distance decoders while the last one is a more general list decoder. First we use the structure of the family of Desarguesian spread codes to decode these codes in some extension field of the underlying finite field. For the second algorithm we use the structure of orbit codes to come up with a syndrome type decoding algorithm (in analogy to syndrome decoding of linear block codes). Then we use the Plücker embedding to describe the balls of a given radius in the set of all vector spaces of a given dimension, which we can use to describe a list decoding algorithm in this embedding. Together with the fact that the family of lifted Gabidulin codes can be described by equations in the Plücker embedding, we come up with a list decoder for lifted Gabidulin codes that works by solving a system of equations in the Plücker embedding. Furthermore, we study the isometry classes and automorphism groups of subspace codes, both of which are of great interest from a theoretical point of view. We show what type of isometries for general subspace codes exist and then investigate the isometry classes and automorphism groups of some known constant dimension code constructions.

Sogenannte Subspace Codes sind Codes, die unter anderem für Zufalls-Netzwerk- Kodierung (auch Random Network Coding genannt) gebraucht werden, was wiederum ein Modell für Multicast-Kommunikation ist. Diese Codes werden als Mengen von Vek- torräumen über einem endlichen Körper definiert. Die zwei Hauptprobleme, mit denen man sich in der Forschung beschäftigt, sind zum einen die Konstruktion solcher Codes und zum anderen die Entwicklung von dazugehörigen effizienten Dekodieralgorithmen. In der vorliegenden Arbeit befassen wir uns mit beiden Problemen und verbessern die bereits bekannten Ergebnisse aus verschiedenen Aspekten. Dabei konzentrieren wir uns hauptsächlich auf Constant Dimension Codes, die eine Unterklasse der Subspace Codes sind, wobei alle Elemente des Codes die gleiche Dimension haben. Zunächst erläutern wir neue Konstruktionen für Constant Dimension Codes, die für gegebene Parameter wie Länge und Minimaldistanz Codes mit mehr Elementen erzeugen als die bekannten Konstruktionen. Dafür führen wir sogenannte Pending Dots und Pending Blocks ein und benutzen diese, um die Lifted Ferrers Diagram Rank Metric Code-Konstruktion zu erweitern. Mit diesen neuen Konstruktionen können wir für bestimmte Parameter grössere Codes als bisher bekannt erzeugen. Danach beschäftigen wir uns mit Orbit Codes und zeigen, dass diese Codes als Analogons zu den linearen Codes in der klassischen Block-Kodierungstheorie angesehen werden können. Wir untersuchen ausführlich die Unterklasse der zyklischen Orbit Codes und zeigen, welche Codes als zyklische Orbit Codes konstruiert werden können. Des weiteren entwickeln wir drei Dekodieralgorithmen, die im Vergleich zu den bereits bekannten Algorithmen für bestimmte Parameter effizienter arbeiten. Die zwei ersten Algorithmen sind Minimaldistanz-Dekodierer, der dritte hingegen ist ein allgemeinerer List-Dekodierer. Für den ersten Algorithmus nutzen wir die Struktur der sogenannten Desargueschen Spread Codes, um diese Codes in einem Erweiterungskörper des eigentlichen endlichen Körpers zu dekodieren. Der zweite Algorithmus ist ein Syndrom-Dekodieralgorithmus für Orbit Codes, ähnlich dem Syndrom-Dekodierer für lineare Block-Codes. Dann verwenden wir die Plücker-Einbettung, um Kugeln mit gegebenem Radius in der Menge aller Vektorräume mit gleicher Dimension zu beschreiben. Dies nutzen wir wiederum, um einen List-Dekodieralgorithmus in der Plücker-Einbettung zu beschreiben. Da man ausserdem die Familie der gelifteten Gabidulin-Codes mit Gleichungen in der Plücker-Einbettung beschreiben kann, erhalten wir einen List-Dekodierer für diese Codefamilie, der allein durch das Lösen eines Gleichungssystems funktioniert. Zusätzlich untersuchen wir die Isometrieklassen und Automorphismen von Sub- space Codes, was aus theoretischer Sicht interessante Ergebnisse liefert. Wir zeigen, welche Abbildungen Isometrien von generellen Subspace Codes sind und untersuchen die Iso-metrieklassen und Automorphismengruppen einiger bekannter Code-Konstruktionen.