Spread codes and more general network codes

Abstract

Netzwerk-Kodierung ist ein Teilbereich der Kodierungstheorie, der im Jahr 2000 aus einer Arbeit von Ahlswede et al. entstand. Es geht hierbei um ein Protokoll für Kommunikation in einem Netzwerk mit mehreren Quellen und mehreren Senken, auch als Multicast bezeichnet. Multicast wird heutzutage bei Internetprotokollen für Streaming Media, digitales Fernsehen und Peer-to-Peer Connections verwendet. Kötter und Kschischang stellten im Jahr 2008 ein neues mathematisches Modell für Netzwerk-Kodierung vor, woraus der Bedarf an neuen Code-Konstruktionen entstand. Die vorliegende Arbeit befasst sich mit diesem Thema, indem zwei mathematische Konstruktionen für Netzwerk-Codes, die sogenannten Spread Codes und Orbit Codes, und dazugehörige Dekodieralgorithmen vorgestellt werden. Spread Codes sind eine Familie von optimalen Codes mit maximaler Minimaldistanz. Ein Spread Code wird mithilfe der Algebra einer Begleitmatrix eines irreduziblen Polynoms konstruiert. Wir erläutern einen effizienten Minimaldistanz-Dekodieralgorithmus, welcher die Struktur dieser Algebra und ein neues Resultat uber Unterdeterminanten und die Faktorisierung von Polynomen über endlichen Körpern nutzt. Orbit Codes sind eine Familie von Codes, die man von der Gruppenaktion der Gruppe der invertierbaren Matrizen auf einem Vektorraum erhält. Diese Codes haben gewisse Ähnlichkeiten mit den linearen Codes aus der klassischen Kodierungstheorie. In dieser Arbeit konzentrieren wir uns auf die zyklischen Orbit Codes, das sind die Codes, die von einer zyklischen Untergruppe generiert werden. Wir bringen das Dekodieren von zyklischen Orbit Codes in Verbindung mit dem sogenannten “Rank Discrete Logarithm Problem”. Desweiteren erläutern wir ein Zugehörigkeitskriterium, welches erkennt, ob ein empfangener Vektorraum ein Element des Codes ist oder nicht. Dieses steht in Verbindung mit dem diskreten Logarithmus über einem endlichen Körper.


Network coding is a branch of coding theory that arose in 2000 from a work by Ahlswede et al. It is a protocol of communication through a network between many sources and many sinks, also called multicast communication. Multicast communication is employed nowadays in Internet protocol applications of streaming media, digital television and peer–to–peer networking. In 2008 Kötter and Kschischang introduced a new mathematical setting for network coding from which the need of new constructions of codes arose. This thesis gives new sensible contributions in this area by giving two original mathematical constructions of codes for network coding, called spread codes and orbit codes, with their related decoding algorithms. Spread codes are a family of optimal codes with maximum minimum distance. A spread code is constructed starting from the algebra defined by the companion matrix of an irreducible polynomial. We give an efficient minimum distance decoding algorithm based on the structure of the algebra and which uses an original result on minors of a matrix and the factorization of polynomials over finite fields. Orbit codes are a family of codes which are obtained by the right action of a subgroup of the group of invertible matrices on a linear space. These codes have some similarities with the family of linear codes in classical coding theory. We focus on cyclic orbit codes, i.e., obtained by cyclic subgroups. We relate the problem of decoding cyclic orbit codes to a problem called rank discrete logarithm problem. We present also a membership criterion for a received space to be an element of the code. This last one relates to the discrete logarithm problem over some multiplicative groups of a finite field.