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.

Nous définissons la résilience comme la capacité d'un Système Homme-Machine (SHM) à s'adapter positivement face à des situations critiques engendrées par des évènements sans précédent dont la fréquence d'occurrence est invraisemblable et dont les conséquences sur le système sont critiques voire catastrophiques.Nous présentons d'abord un état de l'art reposant sur le concept de résilience que nous positionnons par rapport aux approches classiques de la sureté de fonctionnement pour l'évaluation et la gestion des risques dans les SHM. Nous présentons ensuite des méthodes et des outils d'aide à la réaction et à la récupération des systèmes face à l'imprévu. Nous nous intéresserons également à l'apport des techniques d'apprentissage itératif pour le management de la résilience des SHM. Nous proposons alors une méthode d'évaluation de la résilience basée sur un couple d'indicateurs multicritères. Un estimateur reposant sur un réseau de neurones à apprentissage renforcé est proposé pour évaluer les indicateurs derésilience non mesurables ''en ligne''. Pour fiabiliser l'estimation, nous proposons unapprentissage itératif associé soit à un renforcement des paramètres d'estimation, soit à un renforcement de la base de connaissances, soit les deux simultanément.Nous appliquons nos propositions lors d'une simulation de vol d'un Groupe de Ravitaillement en Vol, composé d'un équipage tournant de 4 personnes. L'analyse des résultats expérimentaux montre la pertinence de nos contributions. Certaines perspectives de recherche sont ensuite abordées notamment l'extension de l'étude aux événements de criticité moindre et dont on disposerait d'une base de connaissances " experte ".

Nous définissons la résilience comme la capacité d’un Système Homme-Machine (SHM) à s’adapter positivement face à des situations critiques engendrées par des évènements sans précédent dont la fréquence d’occurrence est invraisemblable et dont les conséquences sur le système sont critiques voire catastrophiques.Nous présentons d’abord un état de l’art reposant sur le concept de résilience que nous positionnons par rapport aux approches classiques de la sureté de fonctionnement pour l’évaluation et la gestion des risques dans les SHM. Nous présentons ensuite des méthodes et des outils d’aide à la réaction et à la récupération des systèmes face à l’imprévu. Nous nous intéresserons également à l’apport des techniques d’apprentissage itératif pour le management de la résilience des SHM. Nous proposons alors une méthode d’évaluation de la résilience basée sur un couple d’indicateurs multicritères. Un estimateur reposant sur un réseau de neurones à apprentissage renforcé est proposé pour évaluer les indicateurs derésilience non mesurables ‘‘en ligne’’. Pour fiabiliser l’estimation, nous proposons unapprentissage itératif associé soit à un renforcement des paramètres d’estimation, soit à un renforcement de la base de connaissances, soit les deux simultanément.Nous appliquons nos propositions lors d’une simulation de vol d’un Groupe de Ravitaillement en Vol, composé d’un équipage tournant de 4 personnes. L’analyse des résultats expérimentaux montre la pertinence de nos contributions. Certaines perspectives de recherche sont ensuite abordées notamment l’extension de l’étude aux événements de criticité moindre et dont on disposerait d’une base de connaissances « experte ». / We define resilience as the ability of a Human-Machine System (HMS) to adapt itself positively facing critical situations resulting from the unprecedented events whose frequency of occurrence is unlikely and the consequences on the system are critical even catastrophic. We first present a state of the art based on the concept of resilience that we position compared to classic dependability approaches for HMS risk evaluation and management. We then present methods and support tools for the reaction and the recovery of systems facing the unexpected. We also detail the contribution of iterative learning techniques for the management of the SHM resilience. We propose then a method for resilience assessment based on a couple of multi-criteria indicators. An estimator based on a neural network with reinforced learning process is proposed to evaluate the ''online'' not measurable resilience indicators. For reliable estimation, we propose an iterative learning associated with a estimation parameters reinforcement process, or knowledge base reinforcement process, or both simultaneously. We apply our proposals during a flight simulation of a ‘‘Groupe de Ravitaillement en Vol’’, consisting of a rotating crew of 4 persons. The analysis of experimental results shows the effectiveness of our contributions. Some research perspectives are then discussed in particular the extension of the study to less critical events which would provide an "expert" knowledge base.

.

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.