Les systèmes de chiffrement à flot (stream ciphers) sont couramment utilisés puisqu'ils permettent un chiffrement rapide des données tout en consommant peu d'énergie. Leur principe de fonctionnement est relativement simple: un générateur de pseudo-aléa produit une séquence binaire qui est X-orée au message clair, engendrant ainsi le message chiffré (cryptogramme). Le destinataire, muni d'un générateur identique, déchiffre le message reçu en lui appliquant la même opération. La sécurité de ce système repose entièrement sur la difficulté de produire la séquence pseudo-aléatoire: toute personne en mesure de la générer pourra en effet déchiffrer le cryptogramme qu'elle aura intercepté. L'objet de cette thèse était de proposer de nouvelles attaques sur de tels systèmes. Plus précisément, nous nous sommes intéressés à la cryptanalyse à clair connu des registres filtrés: le générateur de pseudo-aléa est, dans ce cas, constitué d'un unique registre à décalage linéaire (LFSR) filtré par une fonction booléenne. La structure de ces deux composantes est supposée entièrement connue du cryptanalyste, lequel dispose, par ailleurs, de quelques bits de la séquence pseudo-aléatoire. Seule l'initialisation du registre à décalage est secrète et conditionne entièrement la sortie du générateur: elle constitue donc la clé secrète du système de chiffrement et notre objet sera précisément de la déterminer. Le document sera organisé de la façon suivante: dans un premier chapitre, nous décrivons la structure du système de chiffrement qu'est le registre filtré, et nous intéressons aux théories auxquelles ses différentes constituantes renvoient naturellement. Nous proposons, dans un second chapitre, un état de l'art des attaques non-algébriques du registre filtré. Suit un chapitre qui présente les fondements du décodage itératif et quelques résultats de simulation permettant d'évaluer l'impact de différents paramètres du système, celui du canal booléen notamment. Nous décrivons ensuite une nouvelle attaque dont le principe s'inspire de celui du décodage itératif, qui utilise non plus des contraintes linéaires mais celles de la fonction booléenne. Le quatrième chapitre est dédié aux attaques par treillis: nous présentons en premier lieu une attaque déterministe, qui, lorsque les conditions d'application sont réunies, permet de cryptanalyser le registre filtré très efficacement, et sans aucune probabilité d'erreur. Les conditions d'application de cet algorithme étant assez restrictives, nous avons étendu son principe à des systèmes moins spécifiques, perdant de ce fait le caractère déterministe de l'attaque originelle. Enfin, dans un dernier chapitre, nous avons développé deux algorithmes: le "SOJA" et le "Probability-Matching". Tous deux exploitent conjointement la structure de la fonction booléenne et l'existence d'équations vectorielles, le SOJA afin de générer des probabilités a posteriori sur les bits de la séquence d'entrée, le Probability-Matching afin d'identifier des vecteurs d'entrée de la fonction présentant des propriétés remarquables.

Au cours des cinq dernières années, mes thèmes de recherche furent orientés autour des trois axes suivants : •la conception et l'optimisation asymptotique de récepteurs itératifs pour les communications numériques, comme par exemple l'analyse et l'optimisation des codes LDPC ou familles dérivées pour différents types de canaux, turbo-égalisation, décodage source-canal conjoint ; •la conception, le décodage et l'optimisation de codes définis sur les graphes pour les tailles finies, comme par exemple l'optimisation des codes LDPC non binaires à taille finie et certaines familles dérivées ou le décodage itératif non binaire de codes binaires ; •l'allocation de ressources, la conception et l'optimisation de systèmes à composantes itératives pour les canaux sans fil (par exemple système à retransmissions (HARQ) pour canaux sélectifs en fréquence, AMC pour l'ultra-large bande, protection inégale contre les erreurs et allocation de codes correcteurs).

Les codes Low-Density Parity-Check (LDPC) sont au coeur de larecherche des codes correcteurs d'erreurs en raison de leur excellenteperformance de décodage en utilisant un algorithme de décodageitératif de type propagation de croyances (Belief Propagation - BP).Cet algorithme utilise la représentation graphique d'un code, ditgraphe de Tanner, et calcule les fonctions marginales sur le graphe.Même si l'inférence calculée n'est exacte que sur un graphe acyclique(arbre), l'algorithme BP estime de manière très proche les marginalessur les graphes cycliques, et les codes LDPC peuvent asymptotiquementapprocher la capacité de Shannon avec cet algorithme.Cependant, sur des codes de longueurs finies dont la représentationgraphique contient des cycles, l'algorithme BP est sous-optimal etdonne lieu à l'apparition du phénomène dit de plancher d'erreur. Leplancher d'erreur se manifeste par la dégradation soudaine de la pentedu taux d'erreur dans la zone de fort rapport signal à bruit où lesstructures néfastes au décodage sont connues en termes de TrappingSets présents dans le graphe de Tanner du code, entraînant un échec dudécodage. De plus, les effets de la quantification introduite parl'implémentation en hardware de l'algorithme BP peuvent amplifier ceproblème de plancher d'erreur.Dans cette thèse nous introduisons un nouveau paradigme pour ledécodage itératif à précision finie des codes LDPC sur le canalbinaire symétrique. Ces nouveaux décodeurs, appelés décodeursitératifs à alphabet fini (Finite Alphabet Iterative Decoders – FAID)pour préciser que les messages appartiennent à un alphabet fini, sontcapables de surpasser l'algorithme BP dans la région du plancherd'erreur. Les messages échangés par les FAID ne sont pas desprobabilités ou vraisemblances quantifiées, et les fonctions de miseà jour des noeuds de variable ne copient en rien le décodage par BP cequi contraste avec les décodeurs BP quantifiés traditionnels. Eneffet, les fonctions de mise à jour sont de simples tables de véritéconçues pour assurer une plus grande capacité de correction d'erreuren utilisant la connaissance de topologies potentiellement néfastes audécodage présentes dans un code donné. Nous montrons que sur demultiples codes ayant un poids colonne de trois, il existe des FAIDutilisant 3 bits de précision pouvant surpasser l'algorithme BP(implémenté en précision flottante) dans la zone de plancher d'erreursans aucun compromis dans la latence de décodage. C'est pourquoi lesFAID obtiennent des performances supérieures comparées au BP avecseulement une fraction de sa complexité.Par ailleurs, nous proposons dans cette thèse une décimation amélioréedes FAID pour les codes LDPC dans le traitement de la mise à jour desnoeuds de variable. La décimation implique de fixer certains bits ducode à une valeur particulière pendant le décodage et peut réduire demanière significative le nombre d'itérations requises pour corriger uncertain nombre d'erreurs fixé tout en maintenant de bonnesperformances d'un FAID, le rendant plus à même d'être analysé. Nousillustrons cette technique pour des FAID utilisant 3 bits de précisioncodes de poids colonne trois. Nous montrons également comment cettedécimation peut être utilisée de manière adaptative pour améliorer lescapacités de correction d'erreur des FAID. Le nouveau modèle proposéde décimation adaptative a, certes, une complexité un peu plus élevée,mais améliore significativement la pente du plancher d'erreur pour unFAID donné. Sur certains codes à haut rendement, nous montrons que ladécimation adaptative des FAID permet d'atteindre des capacités decorrection d'erreur proches de la limite théorique du décodage au sensdu maximum de vraisemblance. / At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by message-passing algorithms which are traditionally based on the belief propagation (BP) algorithm. The BP algorithm operates on a graphical model of a code known as the Tanner graph, and computes marginals of functions on the graph. While inference using BP is exact only on loop-free graphs (trees), the BP still provides surprisingly close approximations to exact marginals on loopy graphs, and LDPC codes can asymptotically approach Shannon's capacity under BP decoding.However, on finite-length codes whose corresponding graphs are loopy, BP is sub-optimal and therefore gives rise to the error floor phenomenon. The error floor is an abrupt degradation in the slope of the error-rate performance of the code in the high signal-to-noise regime, where certain harmful structures generically termed as trapping sets present in the Tanner graph of the code, cause the decoder to fail. Moreover, the effects of finite precision that are introduced during hardware realizations of BP can further contribute to the error floor problem.In this dissertation, we introduce a new paradigm for finite precision iterative decoding of LDPC codes over the Binary Symmetric channel (BSC). These novel decoders, referred to as finite alphabet iterative decoders (FAIDs) to signify that the message values belong to a finite alphabet, are capable of surpassing the BP in the error floor region. The messages propagated by FAIDs are not quantized probabilities or log-likelihoods, and the variable node update functions do not mimic the BP decoder, which is in contrast to traditional quantized BP decoders. Rather, the update functions are simple maps designed to ensure a higher guaranteed error correction capability by using the knowledge of potentially harmful topologies that could be present in a given code. We show that on several column-weight-three codes of practical interest, there exist 3-bit precision FAIDs that can surpass the BP (floating-point) in the error floor without any compromise in decoding latency. Hence, they are able to achieve a superior performance compared to BP with only a fraction of its complexity.Additionally in this dissertation, we propose decimation-enhanced FAIDs for LDPC codes, where the technique of decimation is incorporated into the variable node update function of FAIDs. Decimation, which involves fixing certain bits of the code to a particular value during the decoding process, can significantly reduce the number of iterations required to correct a fixed number of errors while maintaining the good performance of a FAID, thereby making such decoders more amenable to analysis. We illustrate this for 3-bit precision FAIDs on column-weight-three codes. We also show how decimation can be used adaptively to further enhance the guaranteed error correction capability of FAIDs that are already good on a given code. The new adaptive decimation scheme proposed has marginally added complexity but can significantly improve the slope of the error floor performance of a particular FAID. On certain high-rate column-weight-three codes of practical interest, we show that adaptive decimation-enhanced FAIDs can achieve a guaranteed error-correction capability that is close to the theoretical limit achieved by maximum-likelihood decoding.

Les techniques de décodage itératif pour les codes modernes dominent actuellement le choix pour la correction des erreurs dans un grand nombre d'applications. Les Turbo codes, présentés en 1993, ont déclenché une révolution dans le domaine du codage de canal parce que ils permettent de s'approcher de la limite de Shannon. Ensuite, les codes LDPC (low-density parity-check) ont été redécouverts. Ces codes sont actuellement omniprésents dans le contexte des communications mobiles sans fil, mais aussi dans d'autres domaines d'application. Dans cette thèse, l'accent est mis sur la conception de décodeurs VLSI à basse consommation destinés aux communications sans fil. Les dispositifs nomades sont généralement alimentés par des batteries et ils ont besoin d'une bonne efficacité énergétique et d'une haute performance, le tout dans une surface de silicium minimale. En outre, les décodeurs de canal sont généralement responsables d'une part importante de la consommation d'énergie dans la chaîne de traitement en bande de base d'un récepteur sans fil. Nous nous concentrons sur les décodeurs LDPC. Au niveau algorithmique nous étudions les compromis entre la performance, l'efficacité énergétique et la surface de silicium pour les différents algorithmes de décodage. Au niveau de l'architecture nous étudions le point essentiel des mémoires. Ce point est particulièrement important pour la consommation et la surface finale du décodeur. Enfin, au niveau du système, nous proposons des stratégies pour la gestion dynamique de la puissance pour les décodeurs Turbo et LDPC. Ces stratégies sont basées sur la prédiction et le contrôle dynamique du nombre d'itérations de décodage.

Nous nous intéressons dans cette thèse à la définition et l'évaluation de techniques de détection multi-utilisateurs pour le traitement des interférences co-canal sur la voie retour des systèmes de communication multifaisceaux par satellite. L'utilisation de ces techniques peut en effet permettre de tolérer des C/I plus faibles que ceux des systèmes classiques, et ainsi autoriser des motifs de réutilisation de fréquence plus efficaces d'un point de vue capacité. L'accès et les formes d'ondes envisagés sont inspirés de la norme DVB-RCS. Nous proposons des algorithmes d'élimination itérative d'interférence adaptés au contexte envisagé. Ces algorithmes incluent notamment la ré-estimation de certains paramètres du canal (réponses en amplitude et en phase des signaux sur les différents faisceaux, fréquences des signaux). Ils sont dans un premier temps évalués en terme d'erreur d'estimation et de taux d'erreurs binaire sur des configurations d'interférences fictives. Nous montrons qu'ils permettent d'obtenir des dégradations (par rapport au cas d'un utilisateur seul) très réduites sur des configurations caractérisées par des C/I très faibles. Nous nous intéressons dans un second temps à l'évaluation de ces algorithmes sur une couverture multifaisceaux. Des simulations effectuées sur une couverture construite à partir d'un modèle d'antenne multi-sources à réflecteur permettent une comparaison des différents algorithmes envisagés dans un contexte réaliste.

Ces dernières années ont vu naitre un intérêt grandissant pour les décodeurs correcteurs d'erreurs opérant sur des circuits non fiables. En effet, la miniaturisation croissante des composants électroniques ainsi l'échelonnage agressif de la tension d'alimentation ont pour conséquence la diminution de la fiabilité des systèmes. Par conséquent, les futures générations de circuits électroniques seront intrinsèquement non fiables. En outre, les décodeurs correcteurs d'erreurs sont indispensables non seulement pour assurer une transmission fiable de l'information mais aussi pour concevoir des systèmes de stockage performants.Nous nous intéressons, dans cette thèse, plus particulièrement aux décodeurs à précision finie Min-Sum (MS), Self-Corrected Min-Sum (SCMS) et Stochastiques.Nous commençons par effectuer une analyse statistique du décodeur Min-Sum opérant sur des circuits à comportement probabiliste. Pour ce faire nous introduisons des modèles d'erreurs probabilistes pour les composants logiques et les opérateurs arithmétiques du décodeur et étudions leurs propriétés de symétrie. Puis nous effectuions une analyse asymptotique rigoureuse et en déduisons les équations d'évolution de densité du décodeur Min-Sum bruité. Nous mettons ainsi en évidence l'effet positif, dans certains cas, du bruit issu du circuit sur la capacité de correction du décodeur. Nous révélons ensuite l'existence d'un phénomène de seuil particulier que nous nommons seuil fonctionnel. Ce dernier peut être considéré comme la généralisation du seuil classique pour les décodeurs non fiables. Nous corroborons ensuite les résultats asymptotiques par des simulations Monte-Carlo.Nous implémentons des décodeurs LDPC bruités pour plusieurs paramètres de bruit et montrons que les décodeurs LDPC bruité ont des résultats très proches de ceux des décodeurs non bruités. Nous pouvons par conséquent considérer le circuit d'autocorrection comme un patch bruité appliqué au décodeur MS bruité afin d'améliorer la robustesse du décodeur face au bruit issu des composants non fiables. Nous évaluons par railleurs l'impact de l'ordonnancement et montrons qu'un ordonnancement série dégrade fortement la robustesse des décodeurs bruités MS et SCMS qui ne parviennent plus à atteindre une capacité de correction acceptable.Pour finir nous étudions les performances des décodeurs stochastiques pourvus de mémoires d'arêtes et opérant sur des circuits non fiables. Nous proposons deux modèles d'erreurs décrivant le comportement probabiliste des composants du décodeur. Nous montrons que, dans certains cas, le bruit issu du circuit non fiable permet de réduire le plancher d'erreur. Nous en déduisons alors que le décodeur stochastique est intrinsèquement tolérant aux fautes. / Over the past few years, there has been an increasing interest in error correction decoders built out of unreliable components. Indeed, it is widely accepted that future generation of electronic circuit will be inherently unreliable, due to the increase in density integration and aggressive voltage scaling. Furthermore, error correction decoders play a crucial role both in reliable transmission of information and in the design of reliable storage systems. It is then important to investigate the robustness of error correction decoders in presence of hardware noise.In this thesis we focus on LDPC decoders built out of unreliable computing units. We consider three types of LDPC decoders: the finite-precision Min-Sum (MS) decoder, the Self-Corrected Min-Sum (SCMS) decoder and the Stochastic decoder.We begin our study by the statistical analysis of the finite-precision Min-Sum decoder with probabilistic components. To this end, we first introduce probabilistic models for the arithmetic and logic units of the decoder and discuss their symmetry properties. We conduct a thorough asymptotic analysis and derive density evolution equations for the noisy Min-Sum decoder. We highlight that in some particular cases, the noise introduced by the device can increase the correction capacity of the noisy Min-Sum with respect to the noiseless decoder. We also reveal the existence of a specific threshold phenomenon, referred to as functional threshold, which can be viewed as the generalization of the threshold definition for noisy decoders. We then corroborate the asymptotic results through Monte-Carlo simulations.Since density evolution cannot be defined for decoders with memory, the analysis of noisy Self-corrected Min-Sum decoders and noisy Stochastic decoders was restricted to Monte-Carlo simulations.We emulate the noisy SCMS decoders with various noise parameters and show that noisy SCMS decoders perform close to the noiseless SCMS decoder for a wide range of noise parameters. Therefore, one can think of the self-correction circuit as a noisy patch applied to the noisy MS decoder, in order to improve its robustness to hardware defect. We also evaluate the impact of the decoder scheduling on the robustness of the noisy MS and SCMS decoders and show that when the serial scheduling is used neither the noisy MS decoder nor the noisy SCMS decoder can provide acceptable error correction.Finally, we investigate the performance of stochastic decoders with edge-memories in presence of hardware noise. We propose two error models for the noisy components. We show that in some cases, the hardware noise can be used to lower the error floor of the decoder meaning that stochastic decoders have an inherent fault tolerant capability.

La géométrie de l'information est la théorie mathématique qui applique les méthodes de la géométrie différentielle dans le domaine des statistiques et de la théorie de l'information. C'est une technique très prometteuse pour l'analyse et l'illustration des algorithmes itératifs utilisés en communications numériques. Cette thèse porte sur l'application de cette technique ainsi que d'autre technique d'optimisation bien connue, l'algorithme itératif du point proximal, sur les algorithmes itératifs en général. Nous avons ainsi trouvé des interprétations géométriques (basée sur la géométrie de l'information) et proximales (basée sur l'algorithme du point proximal)intéressantes dans le cas d'un algorithme itératif de calcul de la capacité des canaux discrets sans mémoire, l'algorithme de Blahut-Arimoto. L'idée étant d'étendre cette application sur une classe d'algorithmes itératifs plus complexes. Nous avons ainsi choisi d'analyser l'algorithme de décodage itératif des modulations codées à bits entrelacés afin de trouver quelques interprétations et essayer de proposer des liens existant avec le critère optimal de maximum de vraisemblance et d'autres algorithmes bien connus dans le but d'apporter certaines améliorations par rapport au cas classique de cet algorithme, en particulier l'étude de la convergence.Mots-clefs : Géométrie de l'information, algorithme du point proximal, algorithme de Blahut-Arimoto, décodage itératif, Modulations codées à bits entrelacés, maximum de vraisemblance.

La géométrie de l’information est la théorie mathématique qui applique les méthodes de la géométrie différentielle dans le domaine des statistiques et de la théorie de l’information. C’est une technique très prometteuse pour l’analyse et l’illustration des algorithmes itératifs utilisés en communications numériques. Cette thèse porte sur l’application de cette technique ainsi que d’autre technique d’optimisation bien connue, l’algorithme itératif du point proximal, sur les algorithmes itératifs en général. Nous avons ainsi trouvé des interprétations géométriques (basée sur la géométrie de l’information) et proximales (basée sur l’algorithme du point proximal)intéressantes dans le cas d’un algorithme itératif de calcul de la capacité des canaux discrets sans mémoire, l’algorithme de Blahut-Arimoto. L’idée étant d’étendre cette application sur une classe d’algorithmes itératifs plus complexes. Nous avons ainsi choisi d’analyser l’algorithme de décodage itératif des modulations codées à bits entrelacés afin de trouver quelques interprétations et essayer de proposer des liens existant avec le critère optimal de maximum de vraisemblance et d’autres algorithmes bien connus dans le but d’apporter certaines améliorations par rapport au cas classique de cet algorithme, en particulier l’étude de la convergence.Mots-clefs : Géométrie de l’information, algorithme du point proximal, algorithme de Blahut-Arimoto, décodage itératif, Modulations codées à bits entrelacés, maximum de vraisemblance. / Information geometry is a mathematical theory that applies methods of differential geometryin the fields of statistics and information theory. It is a very promising technique foranalyzing iterative algorithms used in digital communications. In this thesis, we apply this technique, in addition to the proximal point algorithm, to iterative algorithms. First, we have found some geometrical and proximal point interpretations in the case of an iterative algorithmfor computing the capacity of discrete and memoryless channel, the Blahut-Arimoto algorithm.Interesting results obtained motivated us to extend this application to a larger class of iterative algorithms. Then, we have studied in details iterative decoding algorithm of Bit Interleaved Coded Modulation (BICM) in order to analyse and propose some ameliorations of the classical decoding case. We propose a proximal point interpretation of this iterative process and find the link with some well known decoding algorithms, the Maximum likelihood decoding.

du fait de l'explosion actuelle des télécommunications, les opérateurs sont victimes d'une crise de croissance les obligeant à installer toujours plus de relais, à découper les cellules (zone de couverture d'un relais) en micro-cellules dans les grandes villes, afin de faire face à la demande toujours grandissante de communications. Les concepteurs des nouveaux réseaux de transmission sont donc constamment à la recherche d'une utilisation plus efficace des ressources disponibles

L'augmentation du trafic sur les réseaux sans fil ne permet plus de traiter les données en utilisant les protocoles standard des réseaux filaires, qui sont eux sans interférences. Ainsi, les nœuds des réseaux sans fil doivent coopérer en exploitant les corrélations inhérentes à la proximité des utilisateurs afin d'exploiter au mieux la capacité d'un tel réseau.Dans cette thèse, nous considérons tout d'abord le problème de codage de source avec information adjacente compressée. Le nœud coopératif, ayant accès à un signal corrélé avec celui de la source, peut en envoyer une version compressée au destinataire sur un lien indépendant, permettant d'économiser du débit sur le lien principal. En utilisant une caractérisation des cellules de Voronoi du quantificateur utilisé, nous avons pu améliorer un algorithme de décodage itératif basé sur des codes LDPC.La seconde partie de la thèse traite des problèmes de codage de canal, où les nœuds coopératifs sont des relais. L'exemple le plus simple d'une telle communication est le canal à relais, où un relais aide à la communication entre la source et la destination. Alors que dans le problème de codage de source, le canal de corrélation entre la source et le nœud coopératif est fixé, dans le codage de canal, la question est de savoir quelle opération effectuer au relais. Tout d'abord, nous considérons un problème quelque peu dual au problème de codage de source avec information adjacente compressée, en considérant des bruits corrélés au relais et la destination. Puis, nous étudions des bornes sur la capacité et des débits atteignables pour deux extensions du canal à relais, le canal à relais bidirectionnel avec des bruits corrélés au relais et aux destinations, où deux sources échangent leurs données avec l'aide d'un relais, et le canal multidirectionnel avec liens directs (qui modélisent la proximité des utilisateurs), où les utilisateurs sont regroupés dans des clusters et échangent leurs données localement au sein d'un même cluster avec l'aide d'un relais. / The current wireless data traffic growth cannot be handled by classical multi-hop network protocols as in interference-free wired networks, thus it has been recognized that network nodes need to cooperate in order to take advantage of source and/or channel signal correlations, which is needed to achieve fundamental capacity limits.This thesis first considers a cooperative source coding problem, namely binary source coding with coded side information (CoSI): the helper node has access to a signal that is correlated with the source and may send a compressed version on a separate link to the destination, thus rate can be saved on the main source-destination link. Using a characterization of the Hamming-space Voronoi regions of the quantizer at the helper node, an improved practical scheme based on LDPC codes is proposed.The second part of the thesis considers cooperative channel coding, where helper nodes are relays. The simplest example of such a communication is the relay channel, in which a relay node helps the source to send its message to the destination. Whereas in the source coding problem, the correlation between source and side information is given, in channel coding, the main question is to find the best relaying operation. First, a somewhat dual problem to source coding with CoSI is studied, by considering correlated noises at the relay and destination. Then, various extensions of the relay channel are characterized using upper bounds on capacity and achievable rates: the two-way relay channel with correlated noises at the relay and destinations, where two sources wish to exchange their data with the help of a relay, and the multiway relay channel with direct links, where users, grouped into fully connected clusters (users in a cluster can overhear each others' messages), wish to exchange their messages locally within a cluster with the help of one relay.