Dans ce travail nous nous intéressons aux problèmes liés à l'amélioration des performances d'erreur des codes LDPC. Cette amélioration peut être faite pendant la construction des codes LDPC ou pendant leur processus de décodage. Nous concentrons notre attention vers l'amélioration du décodage. Nous proposons un algorithme de décodage itératif log-SPA modifié, qui minimise l'erreur du décodage pour les mots-codes qui ne peuvent pas être décodés par l'algorithme SPA connu. L'algorithme proposé est basé sur une dépendance entre le poids d'un syndrome et le poids de la séquence d'erreurs généré au cours des itérations du décodage. Nous analysons plus en détail cette dépendance et l'effet du décodage log-SPA moyenne sur les poids des vecteurs d'erreur et les poids du syndrome, et ce, sur les ensembles de piégeage. Concernant la construction des codes LDPC, on s'intéresse aux différents paramètres qui posent des problèmes dans la performance d'erreur : au plancher d'erreur, au périmètre du graphe de Tanner, à la distance minimale du code, aux ensembles de piégeage et aux ensembles d'arrêt. On présente différentes méthodes appliquées dans la construction des différents types de codes, pour éviter l'apparition des structures non-souhaitables dans le code. Nous faisons une comparaison entre la performance des codes pseudo-aléatoires et les codes structurés, basés sur les geometries finies euclidienne et géométrique. On présente aussi différentes méthodes de construction des codes LDPC quasi-cycliques, qui peuvent éviter la formation de certains types d'ensembles de piégeage. d'ensembles d'arrêt ainsi que les cycles courts dans le graphe de Tanner. Les méthodes proposées donnent de très bas planchers d'erreur et une faible complexité du codage.

À travers le temps et en présence des avancements de la technologie, l'utilisation de cette technologie afin de créer et de maintenir des communautés en ligne est devenue une occurrence journalière. Avec l'augmentation de l'utilisation de ces technologies, une tendance négative peut aussi se faire identifier; il y a une quantité croissante d'utilisateurs ayant des objectifs négatifs qui créent du contenu illicite ou nuisible à ces communautés. Afin de protéger ces communautés, il devient donc nécessaire de modérer les communications des communautés. Bien qu'il serait possible d'engager une équipe de modérateurs, cette équipe devrait constamment grandir afin de pouvoir modérer l'entièreté du contenu. Afin de résoudre ce problème, plusieurs se tournent vers des techniques de modération automatique. Deux exemples de techniques sont les "whitelists" et les "blacklists". Malheureusement, les utilisateurs néfastes peuvent facilement contourner ces techniques à l'aide de techniques subversives. Une des techniques populaires est l'utilisation de substitution où un utilisateur remplace un mot par un équivalent phonétique, ou une combinaison visuellement semblable au mot original. À travers ce mémoire, nous offrons une nouvelle technique de normalisation faisant usage de la phonétique à l'intérieur d'un normalisateur de texte. Ce normalisateur recrée la prononciation et infère le mot réel à partir de cette normalisation, l'objectif étant de retirer les signes de subversion. Une fois normalisé, un message peut ensuite être passé aux systèmes de classification. / Over time, the presence of online communities and the use of electronic means of communication have and keep becoming more prevalent. With this increase, the presence of users making use of those means to spread and create harmful, or sometimes known as toxic, content has also increased. In order to protect those communities, the need for moderation becomes a critical matter. While it could be possible to hire a team of moderators, this team would have to be ever-growing, and as such, most turn to automatic means of detection as a step in their moderation process. Examples of such automatic means would be the use of methods such as blacklists and whitelists, but those methods can easily be subverted by harmful users. A common subversion technique is the substitution of a complete word by a phonetically similar word, or combination of letters that resembles the intended word. This thesis aims to offer a novel approach to moderation specifically targeting phonetic substitutions by creating a normalizer capable of identifying how a word should be read and inferring the obfuscated word, nullifying the effects of subversion. Once normalized phonetically, the messages are then sent to existing means of classification for automatic moderation.

Les codes de convolution sont de puissants codes correcteurs d'erreurs utilisés, entre autres, par la NASA depuis 1967. Ce mémoire se veut une étude complète de ce type de codes à registres à décalage. On élabore les bases d'un système de communication permettant de représenter ces codes d'un point de vue algébrique, tout en utilisant éventuellement des graphiques pour illustrer ce qui se passe. Ces représentations permettent ainsi d'étudier la structure de l'encodage. On mentionne également quelques distances communes aux codes de convolution, lesquelles permettent d'optimiser les méthodes de décodage. De plus, on traite du décodage de Viterbi, pour lequel un programme MAPLE est donné, du décodage par liste et de deux méthodes de décodage séquentiel, à savoir les algorithmes de Fano et à pile.

Les travaux présentés dans cette thèse concernent des résultats d'homogénéisation et de correcteur pour des problèmes hyperboliques dans des milieux hétérogènes avec des conditions aux bords mixtes. Les problèmes de ce type modélisent la propagation des ondes dans des milieux hétérogènes. Dans le premier chapitre on rappelle une partie de l'ensemble des outils permettant l'étude asymptotique de problèmes posés dans un milieu hétérogène. Le second chapitre est consacré à l'étude de l'équation des ondes dans un domaine perforé de façon non périodique. Pour cela, on effectue une hypothèse de H^0-convergence sur la partie elliptique de l'opérateur. Cette notion introduite par M. Briane, A. Damlamian et P. Donato généralise la notion de H-convergence introduite quelques années auparavant par F. Murat et L. Tartar pour des domaines perforés. On démontre deux résultats principaux, un résultat d'homogénéisation et un second de correcteur qui permet d'améliorer la convergence de la solution du problème sous des hypothèses légèrement plus fortes. Pour cela on reprend le correcteur de G. Cardone, P. Donato et A. Gaudiello et on explicite quelques unes de ces propriétés. Dans le troisième chapitre, on considère une équation des ondes non-linéaire posée dans un domaine périodiquement perforé dont la non-linéarité porte sur la dérivée en temps de la solution. On suppose que la non-linéarité est majorée par une fonction polynomiale monotone dont l'exposant permet d'avoir une injection de Sobolev convenable. On étudie d'abord l'existence et l'unicité de la solution de ce problème à l'aide d'une méthode de Galerkin, puis on montre un résultat d'homogénéisation de ce problème. Dans le quatrième chapitre, on étudie le problème de l'équation des ondes dans un domaine non perforé. Dans un premier temps, on retrouve le résultat classique d'homogénéisation en utilisant la méthode de l'éclatement périodique introduite par D. Cioranescu, A. Damlamian et G. Griso. Ensuite, sous des hypothèses un peu plus fortes des données initiales on montre un résultat de correcteur faisant intervenir l'opérateur de moyennisation qui est l'adjoint de l'opérateur d'éclatement.

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.