Vignette d'image

Properties and constructions of codes with the rank and the subspace metric

Auteur(s)
Ravagnani, Alberto,
Editeur(s)
Date de parution
2016
Mots-clés
Résumé
En 2000, Ahlswede, Cai, Li et Yeung ont découvert que l'utilisation de techniques de codage dans la transmission des données aux niveau des nœuds intermédiaires d'un réseau peut significativement augmenter le débit d'information transmis. Ces résultats sont à l'origine d'une nouvelle branche de recherche, appelée <i>Network coding</i>, qui s'occupe de l'efficacité et de la fiabilité des communications sur les réseaux. <br> La théorie des codes pour les réseaux a commencé à attirer l'attention de la communauté mathématique lorsqu'en 2008 Kötter et Kschischang ont proposé un setup mathématique rigoureux pour la correction des erreurs et des effacements sur les réseaux. Leur approche est basée sur deux classes de codes correcteurs, appelées <i>rank-metric codes</i> et <i>subspace codes</i>. <br> Dans cette thèse, nous nous concentrons principalement sur des problèmes mathématiques motivés par des applications en <i>network coding</i>. Plus précisément, on étudie des propriétés structurelles et des constructions de <i>rank-metric codes</i> et de <i>subspace codes</i>. <br> Dans la première partie de la thèse, nous étudions différentes constructions de <i>subspace codes</i>. Nous commençons avec une famille de codes, que nous appelons <i>partial spread codes</i>, qui ont une capacité de correction maximale et cardinalité asymptotiquement optimale. Nous montrons que les <i>partial spread codes</i> existent pour tous les paramètres, sont maximales par rapport à l'inclusion et qui peuvent être décodés efficacement. <br> Ensuite, nous nous concentrons sur les <i>equidistant codes</i>, une classe de <i>subspace codes</i> où deux éléments du code sont à égale distance l'un de l'autre. Nous fournissons une classification presque complète de tels codes, et montrons en particulier que les <i>equidistant codes</i> optimaux ont une structure très simple. Puis, nous montrons comment construire des <i>equidistant codes</i> de cardinalité asymptotiquement optimale et comment les décoder de manière efficace. <br> Enfin, nous nous concentrons sur une technique spécifique qui produit des <i>subspace codes</i> de grande cardinalité (la <i>multilevel construction</i>) et y étudions une conjecture énoncée par T. Etzion et N. Siberstein concernant les matrices sur les corps finis avec un profil donné et dont le rang est borné par une constante. Nous prouvons la conjecture dans les cas les plus importants du point de vue du <i>network coding</i> et utilisons nos résultats pour construire de nouveaux <i>subspace codes</i> avec la plus grande cardinalité connue pour leurs paramètres. Nous étudions également la conjecture de Etzion-Silberstein sur les corps algébriquement fermés et montrons que dans ce cas elle est fausse. Pour cela, nous utilisons des méthodes de géométrie algébrique. <br> La deuxième partie de la thèse est dédiée aux propriétés structurelles des <i>rank-metric codes</i>. Nous comparons les deux théories de la dualité des codes de Delsarte et de Gabidulin et montrons que la première généralise la seconde. Ensuite, nous donnons une preuve simple des identités de MacWilliams pour la famille générale des codes de Delsarte. Ces identités ont été montrées par Delsarte en utilisant des méthodes sophistiquées de combinatoire. <br> Nous montrons également que les propriétés les plus importantes des <i>rank-metric codes</i> peuvent être vues comme de simples conséquences de ces identités. Dans la deuxième partie du chapitre, nous étudions les anticodes optimaux pour la métrique du rang, et obtenons de nouvelles bornes pour les paramètres des <i>rank-metric codes</i>. Nous décrivons également les codes qui atteignent ces bornes. Comme application de nos résultats, nous répondons à des questions de combinatoire concernant les matrices sur les corps finis. <br> Ensuite, nous définissons et étudions des invariants algébriques pour les <i>rank-metric codes</i> (que nous appelons <i>Delsarte generalized weights</i>) qui généralisent des invariants connus définis pour la sous-classe spéciale des codes de Gabidulin. Nous montrons que nos invariants décrivent les codes et anticodes optimaux et étudions leur comportement par rapport à la théorie de la dualité des <i>rank-metric codes</i>. Plus précisément, nous montrons que les <i>Delsarte generalized weights</i> d'un code et les <i>Delsarte generalized weights</i> de son code dual se déterminent les uns les autres via une relation précise que nous décrivons explicitement. <br> Finalement nous examinons dans le dernier chapitre certains liens entre la théorie des codes sur les groupes abéliens finis et la théorie combinatoire des ensembles partiellement ordonnés. Nous généralisons des résultats pour les codes classiques et les <i>rank-metric codes</i> établies par d'autres auteurs. Plus précisément, nous définissons une famille générale des <i>fonctions poids</i> sur les groupes abéliens finis qui donnent des identités de MacWilliams inversibles pour les codes additifs. Nous étudions ces fonctions poids en utilisant des méthodes de la théorie des treillis. Cela nous permettra également de fournir une méthodologie efficace pour obtenir les identités de MacWilliams pour les codes sur les groupes. <br> Tout au long de la thèse, l'accent est mis sur les aspects mathématiques des différents problèmes traités., In 2000 Ahlswede, Cai, Li, and Yeung discovered that employing coding techniques in network transmissions at the intermediate nodes of the network may give substantial gains in information throughput. These results originated a new research field, called <i>network coding</i>, concerned with efficiency and reliability of communications over networks. Network coding started to draw the attention of the mathematical community in 2008, when Kötter and Kschischang proposed a rigorous mathematical setup for errors and erasures correction over networks. Their approach is based on rank-metric and subspace codes, mathematical objects that guarantee the reliability of a network communication.<br> In this dissertation we concentrate on mathematical problems motivated by network coding applications, studying structural properties and constructions of rank-metric and subspace codes.<br> In the first part of the dissertation we investigate constructions of subspace codes. We start presenting a family of codes, which we call <i>partial spread codes</i>, that have maximum correction capability and asymptotically optimal cardinality. We show that partial spread codes exist for all parameters, that are maximal with respect to containment, and that can be efficiently decoded.<br> Then we concentrate on <i>equidistant codes</i>, i.e., codes where every two codewords are at the same distance. We provide an almost complete classification of such codes, proving in particular that the optimal ones have a very simple structure. Then we show how to construct equidistant codes of asymptotically optimal cardinality, and how to decode them efficiently. <br> Finally, we focus on a specific technique that produces subspace codes of large cardinality (the so-called <i>multilevel construction</i>) and study a related mathematical conjecture by T. Etzion and N. Silberstein concerning matrices over finite fields with given shape and rank bounded from below. We establish the conjecture in the cases that are most relevant from the point of view of network coding, and use our results to produce new examples of subspace codes with the largest known cardinality for their parameters. We also investigate the Etzion-Silberstein conjecture over algebraically closed fields, and disprove it in this case using methods from algebraic geometry.<br> The second part of the dissertation is devoted to structural properties of rank-metric codes. We start comparing the duality theories of Delsarte and Gabidulin rank-metric codes, proving that the former generalizes the latter. Then we give a simple proof for the MacWilliams identities for the general family of Delsarte codes, originally established by Delsarte using sophisticated methods from combinatorics. We also show that the most important properties of rank-metric codes can be regarded as simple consequences of such identities. In a second part of the chapter we study optimal anticodes in the rank-metric, and prove some new bounds on the parameters of rank-metric codes, characterizing those attaining them. As an application of our results, we answer some questions concerning matrices over finite fields. <br> Then we introduce and study algebraic invariants for rank-metric codes (which we call <i>generalized Delsarte weights</i>), that extend known invariants defined on the special sub-class of Gabidulin rank-metric codes. We show that our invariants characterize optimal codes and anticodes, and that behave well with respect to the duality theory of rank-metric codes. More precisely, we prove that 5 the generalized Delsarte weights of a code and the generalized Delsarte weights of its dual code determine each other via a precise relation, which we explicitly derive. <br> Finally, in the last chapter we investigate some connections between the theory of codes over finite abelian groups and the combinatorial theory of finite posets and lattices, extending in particular some results for classical and rank-metric codes established by other authors to a more general framework. More precisely, we introduce a general family of weight functions on finite abelian groups that give rise to invertible MacWilliams identities for additive codes, and study such weight functions employing lattice theory methods. This will also allow us to provide a computationally effective viewpoint on the theory of MacWilliams identities for codes over groups. <br> Throughout the whole dissertation the main emphasis is on the mathematical aspects of the problems under study.
Notes
Thèse de doctorat : Université de Neuchâtel, 2016
Identifiants
https://libra.unine.ch/handle/123456789/3342
_
10.35662/unine-thesis-2550
Type de publication
doctoral thesis
Dossier(s) à télécharger