Cette thèse aborde le problème de la reconstruction des composants d'un système de transmission à partir de l'interception d'une communication bruitée. Les deux grandes parties de ce travail s'intéressent successivement aux deux maillons principaux de la chaîne~: le brasseur et le code correcteur d'erreur, dans l'ordre où ils doivent être traités par l'attaquant, c'est-à-dire dans l'ordre inverse de leur apparition dans la chaîne de transmission.<br /><br />La première partie traite donc du problème de la reconstruction d'un code linéaire binaire à partir de la connaissance de mots de code bruités. Dans un premier temps, nous présentons et analysons une méthode suggérée par A. Valembois dans sa thèse. Cette analyse nous amène à présenter un nouveau test statistique permettant de trouver des mots susceptibles d'appartenir au dual du code utilisé lors de la transmission. Puis nous présentons un nouvel algorithme de décodage fondé sur les techniques classiques de décodage<br />itératif. Cet algorithme nous permet de corriger des erreurs même si certaines des équations de parité trouvées par le test statistique ne sont pas valides. Nous décrivons alors un nouvel algorithme de reconstruction utilisant cet algorithme de décodage.<br /><br />La seconde partie traite du problème de la reconstruction d'un brasseur linéaire. Dans un premier temps, nous supposons que l'attaquant dispose de la sortie exacte du brasseur. Nous présentons alors différentes techniques permettant de reconstruire un brasseur synchrone ou auto-synchronisant en fonction des hypothèses envisagées sur l'entrée du brasseur. Ensuite, nous nous intéressons au cas général et nous présentons alors une technique algébrique permettant de reconstruire un brasseur synchrone quand<br />l'attaquant connaît simplement l'image de sa sortie par une transformation linéaire par bloc et une partie de la suite en entrée.

Les systèmes de stockage actuels font face à une explosion des données à gérer. A l'échelle actuelle, il serait illusoire d'imaginer une unique entité centralisée capable de stocker et de restituer les données de tous ses utilisateurs. Bien que du point de vue de l'utilisateur, le système de stockage apparaît tel un unique interlocuteur, son architecture sous-jacente est nécessairement devenue distribuée. En d'autres termes, le stockage n'est plus assigné à un équipement centralisé, mais est maintenant distribué parmi de multiples entités de stockage indépendantes, connectées via un réseau. Par conséquent, la bande passante inhérente à ce réseau devient une ressource à prendre en compte dans le design d'un système de stockage distribué. En effet, la bande passante d'un système est intrinsèquement une ressource limitée, qui doit être convenablement gérée de manière à éviter toute congestion du système. Cette thèse se propose d'optimiser l'utilisation de la bande passante dans les systèmes de stockage distribués, en limitant l'impact du churn et des défaillances. L'objectif est double, le but est d'une part, de maximiser la bande passante disponible pour les échanges de données, et d'une autre part de réduire la consommation de bande passante inhérente aux opérations de maintenance. Pour ce faire, nous présentons trois contributions distinctes. La première contribution présente une architecture pair-à-pair hybride qui tient compte de la topologie bas-niveau du réseau, c'est à dire la présence de gateways entre les utilisateurs et le système. La seconde contribution propose un mécanisme de timeout adaptatif au niveau utilisateur, basé sur une approche Bayésienne. La troisième contribution décrit un protocole permettant la réparation efficace de données encodées via des codes à effacement. Enfin, cette thèse se conclut sur la possibilité d'utiliser des techniques d'alignement d'interférence, communément utilisées en communication numérique afin d’accroître l'efficacité des protocoles de réparation de données encodées. / Modern storage systems have to face the surge of the amount of data to handle. At the current scale, it would be an illusion to believe that a single centralized storage device is able to store and retrieve all its users' data. While from the user's viewpoint the storage system remains a single interlocutor, its underlying architecture has become necessarily distributed. In others words, storage is no longer assigned to a centralized storage equipment, but is now distributed between multiple independent storage devices, connected via a network. Therefore, when designing networked storage systems, bandwidth should now be taken into account as a critical resource. In fact, the bandwidth of a system is intrinsically a limited resource which should be handled with care to avoid congestion. The focus of this thesis is to optimize the available bandwidth of distributed storage systems, lowering the impact of churn and failures. The objective is twofold, on the one hand the purpose is to increase the available bandwidth for data exchanges and on the other hand, to decrease the amount of bandwidth consumed by maintenance. We present three distinct contributions in this manuscript. The first contribution of this thesis presents an hybrid peer-to-peer architecture taking into account the low level topology of the network i.e., the presence of gateways between the system and the users. The second contribution proposes an adaptive and user-level timeout mechanism, based on a Bayesian approach. The third contribution describes a repair protocol especially designed for erasure-coded stored data. Finally, this thesis concludes on the possibility of employing interference alignment techniques in order to increase the efficiency of repair protocols especially designed for encoded data.

Le multicast fiable est certainement la solution la plus efficace pour<br />la distribution de contenu a un très grand nombre (potentiellement des<br />millions) de récepteurs. Dans cette perspective les protocoles ALC et<br />FLUTE, standardisés à l'IETF (RMT WG), ont été adoptés dans 3GPP/MBMS<br />et dans le DVB-H IP-Datacast dans les contextes des réseaux<br />cellulaires 3G.<br /><br />Ce travail se concentre sur le multicast fiable et a comme requis<br />principal le passage à l'échelle massif en terme de nombre de client.<br />Ce travail se base sur les solutions proposées a l'IETF RMT WG. Ces<br />protocoles de multicast fiable sont construit autour de plusieurs<br />briques de base que nous avons étudié en détail:<br /><br />- La brique Forward Error Correction (FEC) :<br /><br /> Nous examinons la classe de codes grands blocs<br /> Low Density Parity Check (LDPC). Nous concevons des dérivées<br /> de ces codes, et les analysons en détail. Nous en concluons que les<br /> codes LDPC et leur implémentation ont des performances très<br /> prometteuses, surtout si ils sont utilisées avec des fichiers de taille<br /> importante.<br /><br />- La brique contrôle de congestion :<br /><br /> Nous examinons le comportement dans la phase de démarrage de<br /> trois protocoles de contrôle de congestion RLC, FLID-SL, WEBRC.<br /> Nous démontrons que la phase de démarrage a un grand impact sur<br /> les performances de téléchargement.<br /><br /><br />Cette thèse a aussi plusieurs contributions au niveau applicatif:<br /><br />- Extensions de FLUTE :<br /><br /> Nous proposons un mécanisme permettant d'agréger plusieurs<br /> fichiers dans le protocole FLUTE. Ceci améliore les performance de<br /> transmission.<br /><br />- Streaming vidéo :<br /><br /> Nous proposons SVSoA, une solution de streaming basé sur ALC.<br /> Cette approche bénéficie de tout les avantages de ALC en terme de<br /> passage à l'échelle, contrôle de congestion et corrections d'erreurs

Durant cette thèse, je me suis intéressés à la reconnaissance de codes correcteurs d'erreurs à partir d'une observation bruitée. Parmi ces codes, nous avons choisi d'étudier plus particulièrement les codes convolutifs et les turbo-codes. Le canal de transmission considéré pour nos travaux est le canal binaire symétrique. En s'appuyant sur les travaux de E. Filiol et J. Barbier, j'ai mis au point un algorithme, imaginé conjointement avec N. Sendrier. Nous avons créé une nouvelle méthode générique de reconnaissance des codes convolutifs (n; k) (k entrées et n sorties). Cette méthode améliore l'état de l'art grâce à l'utilisation exclusive d'opérations binaires d'algèbre linéaire dans l'algorithme. L'implémentation fournit de bons résultats, autant du point de vue du temps d'exécution que de la tolérance au bruit, pour tout type de code convolutifs. La seconde partie consiste en la mise au point d'une méthode de reconnaissance des turbo-codes. Cette méthode repose sur les hypothèses que nous sommes capable de retrouver le premier code convolutif à l'aide de notre méthode de reconnaissance de code convolutif et que le second code convolutif (suivant l'entrelaceur) possède une matrice génératrice systématique définie par P(D)/Q(D) (où P(D) et Q(D) sont les polynômes du codeur convolutif) de terme constant non nul. Cette dernière hypothèse forte mais réaliste nous permet de construire une méthode et un algorithme capable de retrouver à la fois l'entrelaceur et les polynômes P(D) et Q(D) du code convolutif. Cet algorithme est très rapide mais trouve ses limites lorsque le taux d'erreur croit. De plus, notre hypothèse rend impossible la reconstruction de turbo-codes poinçonnés sans modifier l'algorithme.

Dans ce document sont présentées mes thématiques de recherche concernant l'étude des codes correcteurs d'erreurs à des fins cryptographiques. L'essentiel de sa composition est dédié au sujet principal de mes recherches commené un an avant la fin de la thèse à savoir l'étude <br />des cryptosystémes fondés sur des familles de codes décodables en métrique rang.

Les systèmes de stockage actuels font face à une explosion des données à gérer. A l'échelle actuelle, il serait illusoire d'imaginer une unique entité centralisée capable de stocker et de restituer les données de tous ses utilisateurs. Bien que du point de vue de l'utilisateur, le système de stockage apparaît tel un unique interlocuteur, son architecture sous-jacente est nécessairement devenue distribuée. En d'autres termes, le stockage n'est plus assigné à un équipement centralisé, mais est maintenant distribué parmi de multiples entités de stockage indépendantes, connectées via un réseau. Par conséquent, la bande passante inhérente à ce réseau devient une ressource à prendre en compte dans le design d'un système de stockage distribué. En effet, la bande passante d'un système est intrinsèquement une ressource limitée, qui doit être convenablement gérée de manière à éviter toute congestion du système. Cette thèse se propose d'optimiser l'utilisation de la bande passante dans les systèmes de stockage distribués, en limitant l'impact du churn et des défaillances. L'objectif est double, le but est d'une part, de maximiser la bande passante disponible pour les échanges de données, et d'une autre part de réduire la consommation de bande passante inhérente aux opérations de maintenance. Pour ce faire, nous présentons trois contributions distinctes. La première contribution présente une architecture pair-à-pair hybride qui tient compte de la topologie bas-niveau du réseau, c'est à dire la présence de gateways entre les utilisateurs et le système. La seconde contribution propose un mécanisme de timeout adaptatif au niveau utilisateur, basé sur une approche Bayésienne. La troisième contribution décrit un protocole permettant la réparation efficace de données encodées via des codes à effacement. Enfin, cette thèse se conclut sur la possibilité d'utiliser des techniques d'alignement d'interférence, communément utilisées en communication numérique afin d'accroître l'efficacité des protocoles de réparation de données encodées.

Dans cette thèse, nous étudions deux problèmes de théorie des graphes largement étudiés ces trois dernières décennies: les codes correcteurs d'erreur et la domination.<br />Nous étudions d'abord deux généralisations des codes correcteurs d'erreurs : les codes parfaits sur des alphabets mixtes et les codes pondérés de rayon un. Ces problèmes ont beaucoup été étudiés sur la métrique de Hamming.<br />Nous les étudions dans la métrique de Lee, et nous montrons des résultats aussi bien d'existence que d'inexistence.<br />Nous montrons aussi que le rapport de dualité entre la domination et les codes est fort pour la grille carrée lorsque l'on considère des boules sans le centre.<br />Puis, nous étudions la domination dans les produits de graphes. Depuis que Vizing a conjecturé en 1968 que la domination est surmultiplicative pour le produit cartésien de graphes, les relations entre des variantes du nombre de domination d'un produit de graphes et ses facteurs ont attiré beaucoup d'attention. Après avoir donné quelques bornes sur le nombre de domination totale du produit direct de graphes, nous déterminons le nombre de domination de puissance des produits de chemins.<br />Puis, nous montrons une conjecture ``à la Vizing'' pour le nombre de domination totale supérieure du produit cartésien.<br />Ensuite, nous étudions la domination avec une approche structurelle. En continuation de l'étude de Favaron et Henning, nous fournissons plusieurs bornes supérieures sur le nombre de paire-domination des graphes sans étoiles, pour chaque nombre de branches, et des graphes sans P_5. Nous proposons aussi des familles infinies de graphes pour lesquels ces bornes sont atteintes.<br />Enfin, nous comparons la domination totale supérieure et la paire-domination supérieure, deux variantes de la domination qui ont attiré l'attention récemment, et nous donnons des bornes précises pour les arbres.

Texte remanié de : PhD : Cambridge, MIT : 2001. / Bibliogr. p. [337]-347. Index.

La théorie des codes géométriques s'est développée au début des années 80 sur l'impulsion d'un article de V.D. Goppa publié en 1981. Etant donnée une courbe algébrique projective lisse X sur un corps fini, on dispose de deux constructions de codes correcteurs d'erreurs. Une construction dite fonctionnelle qui fait intervenir certaines fonctions rationnelles sur X et une construction différentielle qui fait appel à certaines 1-formes différentielles rationnelles sur X . L'étude de ces codes construits sur des courbes a donné lieu à la publication de plusieurs centaines d'articles. Parallèlement à ces travaux, une généralisation de la construction fonctionnelle à des variétés algébriques de dimension quelconque est proposée par Y. Manin dans un article publié en 1984. On dénombre quelques dizaines de travaux publiés portant sur l'étude de tels codes. Cependant, aucun développement n'a été effectué dans le sens d'une généralisation de la construction différentielle. Dans cette thèse nous proposons une construction différentielle de codes sur des surfaces algébriques. Nous étudions ensuite les propriétés de ces codes et plus particulièrement leurs relations avec les codes fonctionnels. De façon un peu surprenante, on observe l'apparition d'une différence majeure avec le cas des courbes. En effet, si sur une courbe l'orthogonal d'un code fonctionnel est différentiel, ce fait est en général faux sur une surface. Ce résultat motive l'étude des orthogonaux de codes fonctionnels. Des formules pour l'estimation de la distance minimale de tels codes sont données en utilisant des propriétés de systèmes linéaires sur une variété. On montre également que, sous certaines conditions sur la surface, ces codes sont somme de codes différentiels et que des réponses à certains problèmes ouverts de géométrie algébrique "à la Bertini" fourniraient des informations supplémentaires sur les paramètres de ces codes.

Th. doct.--Électronique et communications--Paris--ENST, 1991. / Textes en français et en anglais. Bibliogr. p. 102-108.