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.