Les code en métrique rang attirent l’attention depuis quelques années en raison de leur application possible au codage réseau linéaire aléatoire (random linear network coding), à la cryptographie à clé publique, au codage espace-temps et aux systèmes de stockage distribué. Une construction de codes algébriques en métrique rang de cardinalité optimale a été introduite par Delsarte, Gabidulin et Roth il y a quelques décennies. Ces codes sont considérés comme l’équivalent des codes de Reed – Solomon et ils sont basés sur l’évaluation de polynômes linéarisés. Ils sont maintenant appelés les codes de Gabidulin. Cette thèse traite des codes en bloc et des codes convolutifs en métrique rang avec l’objectif de développer et d’étudier des algorithmes de décodage efficaces pour ces deux classes de codes. Après une introduction dans le chapitre 1, le chapitre 2 fournit une introduction rapide aux codes en métrique rang et leurs propriétés. Dans le chapitre 3, on considère des approches efficaces pour décoder les codes de Gabidulin. Lapremière partie de ce chapitre traite des algorithmes rapides pour les opérations sur les polynômes linéarisés. La deuxième partie de ce chapitre résume tout d’abord les techniques connues pour le décodage jusqu’à la moitié de la distance rang minimale (bounded minimum distance decoding) des codes de Gabidulin, qui sont basées sur les syndromes et sur la résolution d’une équation clé. Ensuite, nous présentons et nous prouvons un nouvel algorithme efficace pour le décodage jusqu’à la moitié de la distance minimale des codes de Gabidulin. Le chapitre 4 est consacré aux codes de Gabidulin entrelacés et à leur décodage au-delà de la moitié de la distance rang minimale. Dans ce chapitre, nous décrivons d’abord les deux approches connues pour le décodage unique et nous tirons une relation entre eux et leurs probabilités de défaillance. Ensuite, nous présentons un nouvel algorithme de décodage des codes de Gabidulin entrelacés basé sur l’interpolation des polynômes linéarisés. Nous prouvons la justesse de ses deux étapes principales — l’interpolation et la recherche des racines — et montrons que chacune d’elles peut être effectuée en résolvant un système d’équations linéaires. Jusqu’à présent, aucun algorithme de décodage en liste en temps polynomial pour les codes de Gabidulin n’est connu et en fait il n’est même pas clair que cela soit possible. Cela nous a motivé à étudier, dans le chapitre 5, les possibilités du décodage en liste en temps polynomial des codes en métrique rang. Cette analyse est effectuée par le calcul de bornes sur la taille de la liste des codes en métriques rang en général et des codes de Gabidulin en particulier. Étonnamment, les trois nouvelles bornes révèlent toutes un comportement des codes en métrique rang qui est complètement différent de celui des codes en métrique de Hamming. Enfin, dans le chapitre 6, on introduit des codes convolutifs en métrique rang. Ce qui nous motive à considérer ces codes est le codage réseau linéaire aléatoire multi-shot, où le réseau inconnu varie avec le temps et est utilisé plusieurs fois. Les codes convolutifs créent des dépendances entre les utilisations différentes du réseau aun de se adapter aux canaux difficiles. Basé sur des codes en bloc en métrique rang (en particulier les codes de Gabidulin), nous donnons deux constructions explicites des codes convolutifs en métrique rang. Les codes en bloc sous-jacents nous permettent de développer un algorithme de décodage des erreurs et des effacements efficace pour la deuxième construction, qui garantit de corriger toutes les séquences d’erreurs de poids rang jusqu’à la moitié de la distance rang active des lignes. Un résumé et un aperçu des problèmes futurs de recherche sont donnés à la fin de chaque chapitre. Finalement, le chapitre 7 conclut cette thèse. / Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed–Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed–Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code.

Network coding has emerged as a new paradigm for communication in networks, allowing packets to be algebraically combined at internal nodes, rather than simply routed or replicated. The very nature of packet-mixing, however, makes the system highly sensitive to error propagation. Classical error correction approaches are therefore insufficient to solve the problem, which calls for novel techniques and insights. The main portion of this work is devoted to the problem of error control assuming an adversarial or worst-case error model. We start by proposing a general coding theory for adversarial channels, whose aim is to characterize the correction capability of a code. We then specialize this theory to the cases of coherent and noncoherent network coding. For coherent network coding, we show that the correction capability is given by the rank metric, while for noncoherent network coding, it is given by a new metric, called the injection metric. For both cases, optimal or near-optimal coding schemes are proposed based on rank-metric codes. In addition, we show how existing decoding algorithms for rank-metric codes can be conveniently adapted to work over a network coding channel. We also present several speed improvements that make these algorithms the fastest known to date. The second part of this work investigates a probabilistic error model. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of long packet length and/or large field size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has fairly low decoding complexity and a probability of failure that decreases exponentially both in the packet length and in the field size in bits. Extensions of the scheme are provided for several variations of the channel. A final contribution of this work is to apply rank-metric codes to a closely related problem: securing a network coding system against an eavesdropper. We show that the maximum possible rate can be achieved with a coset coding scheme based on rank-metric codes. Unlike previous schemes, our scheme has the distinctive property of being universal: it can be applied on top of any communication network without requiring knowledge of or any modifications on the underlying network code. In addition, the scheme can be easily combined with a rank-metric-based error control scheme to provide both security and reliability.

Network coding has emerged as a new paradigm for communication in networks, allowing packets to be algebraically combined at internal nodes, rather than simply routed or replicated. The very nature of packet-mixing, however, makes the system highly sensitive to error propagation. Classical error correction approaches are therefore insufficient to solve the problem, which calls for novel techniques and insights. The main portion of this work is devoted to the problem of error control assuming an adversarial or worst-case error model. We start by proposing a general coding theory for adversarial channels, whose aim is to characterize the correction capability of a code. We then specialize this theory to the cases of coherent and noncoherent network coding. For coherent network coding, we show that the correction capability is given by the rank metric, while for noncoherent network coding, it is given by a new metric, called the injection metric. For both cases, optimal or near-optimal coding schemes are proposed based on rank-metric codes. In addition, we show how existing decoding algorithms for rank-metric codes can be conveniently adapted to work over a network coding channel. We also present several speed improvements that make these algorithms the fastest known to date. The second part of this work investigates a probabilistic error model. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of long packet length and/or large field size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has fairly low decoding complexity and a probability of failure that decreases exponentially both in the packet length and in the field size in bits. Extensions of the scheme are provided for several variations of the channel. A final contribution of this work is to apply rank-metric codes to a closely related problem: securing a network coding system against an eavesdropper. We show that the maximum possible rate can be achieved with a coset coding scheme based on rank-metric codes. Unlike previous schemes, our scheme has the distinctive property of being universal: it can be applied on top of any communication network without requiring knowledge of or any modifications on the underlying network code. In addition, the scheme can be easily combined with a rank-metric-based error control scheme to provide both security and reliability.

Dans cette thèse, nous avons envisagé l’utilisation des codes en métrique rang pour des applications de communication sans fil en général, et les réseaux de capteurs en particulier. Après avoir introduit les codes en métrique rang, ces codes, qui ont été proposés dans le contexte de la cryptographie, sont adaptés par la suite pour la correction d’erreurs. Pour cela, une étude est faite sur le comportement de ces familles de codes dans un scénario de transmission sans fil en utilisant le codage réseau. Dans ce contexte, trois types d’erreurs sont considérés : le bruit de fond, les erreurs injectés dans le réseau par un utilisateur malveillant et les effacements qui peuvent être dus aux pannes des nœuds. L’analyse qui a été faite sur la famille des codes Low Rank Parity Check (LRPC) a montré que ces derniers sont plus adaptés aux réseaux de capteurs sans fil par rapport aux codes Gabidulin utilisés dans la littérature. Cette analyse a été généralisée dans le contexte multi-sources et a montré que les codes LRPC sont plus efficaces dans ce contexte. Ces contributions apportent un nouveau souffle à l’utilisation des codes en métrique rang et offrent des perspectives de poursuite intéressantes. / In this thesis, we have considered the rank metric codes for wireless sensor networks. Firstly, we have introduced the rank metric codes. Then, we adapted these codes, which were originally dedicated to cryptography applications, for error correction. To this end, we have studied the behavior of the family of rank metric codes in a wireless communication scenario using network coding. In this context, three types of errors are considered, background noise, errors injected into the network by a malicious user and erasures caused by node failures. Our analysis of the Low Rank Parity Check codes (LRPC) has shown that they are more suited to wireless sensor networks and they perform better than Gabidulin codes used in the literature. This analysis has been generalized in the multisource context and has shown that LRPC codes are more efficient in this context compared to Gabidulin codes. These contributions give a new incentive for the use of rank metric codes and offer interesting perspectives.

Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed-Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed-Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code.

Ce manuscrit traite de la fiabilisation des CPL-BE dans le contexte smart grid avec l’application des techniques de codage correcteur d’erreurs et d’effacements. Après une introduction sur le concept de smart grid, le canal CPL-BE est caractérisé précisément et les modèles qui le décrivent sont présentés. Les performances des codes à métrique rang, simples ou concaténés avec des codes convolutifs, particulièrement intéressants pour combattre le bruit criss-cross sur les réseaux CPL-BE sont simulées et comparées aux performances des codes Reed-Solomon déjà présents dans plusieurs standards. Les codes fontaines qui s’adaptent à n’importe quelles statistiques d’effacements sur le canal CPL sont utilisés et les performances de schémas coopératifs basés sur ces codes fontaines sur des réseaux linéaires multi-sauts sont étudiés. Enfin des algorithmes permettant de combiner le codage réseau et le codage fontaine pour la topologie particulière des réseaux CPL pour les smart grid sont proposés et évalués. / This PhD dissertation deals with the mitigation of the impact of the Narrowband PowerLine communication (NB-PLC) channel impairments e.g., periodic impulsive noise and narrowband noise, by applying the error/erasure correction coding techniques. After an introduction to the concept of smart grid, the NB-PLC channels are characterized precisely and models that describe these channels are presented. The performance of rank metric codes, simple or concatenated with convolutional codes, that are particularly interesting to combat criss-cross errors on the NB-PLC networks are simulated and compared with Reed- Solomon (already present in several NB-PLC standards) codes performance. Fountain codes that can adapt to any channel erasures statistics are used for the NB-PLC networks and the performance of cooperative schemes based on these fountain codes on linear multi-hop networks are studied. Finally, algorithms to combine the network coding and fountain codes for the particular topology of PLC networks for the smart grid are proposed and evaluated.

Cette thèse a pour cadre les transmissions sur les réseaux CPL-BE et les réseaux de capteurs à faible capacité. L'état de l'art classique sur la protection de l'information dans la transmission par réseaux de capteurs fait référence à l'utilisation de codage distribué où les relais implémentent des opérations de parité (mélange des flux) sur les data issues des capteurs. Cependant, il est difficile, de par la nature variable de la qualité des liens en liaisons sans fil, de contrôler la qualité du codeur équivalent construit et de maintenir ses performances au cours du temps. C'est pourquoi nous nous sommes orientés dans cette thèse vers la recherche de schémas de codage différents qui résistent mieux à la variation de qualité des liaisons à travers le réseau. Notre choix s'est porté sur le codage par sous-espace inspiré des travaux de Gabidulin. Le but est de former un code qui utilise une métrique simple et résistante pour sécuriser les transmissions sur le réseau. Les codes à métrique de rang répondent bien à ce besoin car il n'y a qu'à contrôler le rang de la matrice obtenue en réception pour vérifier l'intégrité de la transmission. Les codes à métrique de rang et leur algorithme de décodage ont été étudiés dans un premier temps. Puis, les performances du code LRPC proposé concaténé avec les codes convolutifs sont testées dans des schémas de transmission des contextes différents. / This thesis considers the context of transmissions on CPL-BE networks and low-capacity sensor networks. The state of the art on information protection intransmission by sensor networks refers to the use of distributed coding, where therelays implement parity operations (mixing of streams) on data transmitted by thesensors. However, due to the varying nature of the quality of the wireless links, it is difficult to control the quality of the equivalent encoder constructed and to maintain its performance over time. Therefore, in this thesis, we have focused on the search for different coding schemes that are better resist the variation in the quality of the links across the network. Our choice was based on the sub-space coding inspired by Gabidulin's work. The goal is to form a code that uses a simple and resistant metric to secure transmission across the network. Rank metric codes respond well to this need because it only has to control the rank of the matrix obtained in reception to verify the integrity of the transmission. The rank metric codes and their decoding algorithm were studied in a first step. Then, the performance of the proposed LRPC code concatenated with the convolutional codes is tested in transmission schemes of different contexts.

The classical binary error correcting codes, and subspace codes for error correction in random network coding are two different forms of error control coding. We identify common features between these two forms and study the relations between them using the aid of lattices. Lattices are partial ordered sets where every pair of elements has a least upper bound and a greatest lower bound in the lattice. We shall demonstrate that many questions that connect these forms have a natural motivation from the viewpoint of lattices. We shall show that a lattice framework captures the notion of Singleton bound where the bound is on the size of the code as a function of its parameters. For the most part, we consider a special type of a lattice which has the geometric modular property. We will use a lattice framework to combine the two different forms. And then, in order to demonstrate the utility of this binding view, we shall derive a general version of Singleton bound. We will note that the Singleton bounds behave differently in certain respects because the binary coding framework is associated with a lattice that is distributive. We shall demonstrate that lack of distributive gives rise to a weaker bound. We show that Singleton bound for classical binary codes, subspace codes, rank metric codes and Ferrers diagram rank metric codes can be derived using a common technique. In the literature, Singleton bounds are derived for Ferrers diagram rank metric codes where the rank metric codes are linear. We introduce a generalized version of Ferrers diagram rank metric codes and obtain a Singleton bound for this version. Next, we shall prove a conjecture concerning the constraints of embedding a binary coding framework into a subspace framework. We shall prove a conjecture by Braun, Etzion and Vardy, which states that any such embedding which contains the full space in its range is constrained to have a particular size. Our proof will use a theorem due to Lovasz, a subspace counting theorem for geometric modular lattices, to prove the conjecture. We shall further demonstrate that any code that achieves the conjectured size must be of a particular type. This particular type turns out to be a natural distributive sub-lattice of a given geometric modular lattice.