Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse se consacre à l'étude de décodeurs itératifs, pour des codes correcteurd'erreurs binaires et non-binaires à faible densité (LDPC). Notre objectif est de modéliserdes décodeurs de complexité faibles et de faible latence tout en garantissantde bonne performances dans la région des très faibles taux d'erreur (error floor).Dans la première partie de cette thèse, nous étudions des décodeurs itératifssur des alphabets finis (Finite Alphabet iterative decoders, FAIDs) qui ont étérécemment proposés dans la littérature. En utilisant un grand nombre de décodeursFAIDs, nous proposons un nouvel algorithme de décodage qui améliore la capacité decorrections d'erreur des codes LDPC de degré dv = 3 sur canal binaire symétrique.La diversité des décodeurs permet de garantir une correction d'erreur minimale sousdécodage itératif, au-delà de la pseudo-distance des codes LDPC. Nous donnonsdans cette thèse un exemple detailé d'un ensemble de décodeur FAIDs, qui corrigetous les évènements d'erreur de poids inférieur ou égal à 7 avec un LDPC de petitetaille (N=155,K=64,Dmin=20). Cette approche permet de corriger des évènementsd'erreur que les décodeurs traditionnels (BP, min-sum) ne parviennent pas à corriger.Enfin, nous interprétons les décodeurs FAIDs comme des systèmes dynamiques etnous analysons les comportements de ces décodeurs sur des évènements d'erreur lesplus problématiques. En nous basant sur l'observation des trajectoires périodiquespour ces cas d'étude, nous proposons un algorithme qui combine la diversité dudécodage avec des sauts aléatoires dans l'espace d'état du décodeur itératif. Nousmontrons par simulations que cette technique permet de s'approcher des performancesd'un décodage optimal au sens du maximum de vraisemblance, et ce pourplusieurs codes.Dans la deuxième partie de cette thèse, nous proposons un nouvel algorithmede décodage à complexité réduite pour les codes LDPC non-binaires. Nous avonsappellé cet algorithme Trellis-Extended Min-Sum (T-EMS). En transformant le domainede message en un domaine appelée domaine delta, nous sommes capable dechoisir les déviations ligne par ligne par rapport à la configuration la plus fiable,tandis que les décodeurs habituels comme le décodeur EMS choisissent les déviationscolonne par colonne. Cette technique de sélection des déviations ligne parligne nous permet de réduire la complexité du décodage sans perte de performancepar rapport aux approches du type EMS. Nous proposons également d'ajouter une colonne supplémentaire à la représentation en treillis des messages, ce qui résoudle problème de latence des décodeurs existants. La colonne supplémentaire permetde calculer tous les messages extrinséque en parallèle, avec une implémentationmatérielle dédiée. Nous présentons dans ce manuscrit, aussi bien les architecturesmatérielles parallèle que les architectures matérielles série pour l'exécution de notrealgorithme T-EMS. L'analyse de la complexité montre que l'approche T-EMS estparticulièrement adapté pour les codes LDPC non-binaires sur des corps finis deGalois de petite et moyenne dimensions. / This thesis is dedicated to the study of iterative decoders, both for binary and non-binary low density parity check (LDPC) codes. The objective is to design low complexity and low latency decoders which have good performance in the error floor region.In the first part of the thesis, we study the recently introduced finite alphabet iterative decoders (FAIDs). Using the large number of FAIDs, we propose a decoding diversity algorithm to improve the error correction capability for binary LDPC codes with variable node degree 3 over binary symmetric channel. The decoder diversity framework allows to solve the problem of guaranteed error correction with iterative decoding, beyond the pseudo-distance of the LDPC codes. We give a detailed example of a set of FAIDs which corrects all error patterns of weight 7 or less on a (N=155,K=64,Dmin=20) short structured LDPC, while traditional decoders (BP, min-sum) fail on 5-error patterns. Then by viewing the FAIDs as dynamic systems, we analyze the behaviors of FAID decoders on chosen problematic error patterns. Based on the observation of approximate periodic trajectories for the most harmful error patterns, we propose an algorithm which combines decoding diversity with random jumps in the state-space of the iterative decoder. We show by simulations that this technique can approach the performance of Maximum LikelihoodDecoding for several codes.In the second part of the thesis, we propose a new complexity-reduced decoding algorithm for non-binary LDPC codes called trellis extended min sum (T-EMS). By transforming the message domain to the so-called delta domain, we are able to choose row-wise deviations from the most reliable configuration, while usual EMS-like decoders choose the deviations column-wise. This feature of selecting the deviations row-wise enables us to reduce the decoding complexity without any performance loss compared to EMS. We also propose to add an extra column to the trellis representation of the messages, which solves the latency issue of existing decoders. The extra column allows to compute all extrinsic messages in parallel, with a proper hardware implementation. Both the parallel and the serial hardware architectures for T-EMS are discussed. The complexity analysis shows that the T-EMS is especially suitable for high ratenon-binary LDPC codes on small and moderate fields.

Les modèles de pile de sable sont une sous-classe d'automates cellulaires. Bak et al. les ont introduit en 1987 comme une illustration de la notion intuitive d'auto-organisation critique.Le modèle de pile de sable Kadanoff est un système dynamique discret non-linéaire imagé par des grains cubiques se déplaçant de colonne parfaitement empilée en colonne parfaitement empilée. Pour un paramètre p fixé, une règle d'éboulement est appliquée jusqu'à atteindre une configuration stable, appelée point fixe : si la différence de hauteur entre deux colonnes consécutives est strictement supérieure à p, alors p grains chutent de la colonne de gauche, un retombant sur chacune des p colonnes adjacentes sur la droite.A partir d'une règle locale simple, décrire et comprendre le comportement macroscopique des piles de sable s'avère très rapidement compliqué. La difficulté consiste en la prise en compte simultanée des modalités discrète et continue du système : vue de loin, une pile de sable s'écoule comme un liquide ; mais de près, lorsque l'on s'attache à décrire exactement une configuration, les effets de la dynamique discrète doivent être pris en compte. Si par exemple nous ajoutons un unique grain à une configuration stable, celui-ci déclenche une avalanche qui ne modifie que la couche supérieure de la pile, mais dont la taille est très difficile à prédire car sensible au moindre changement sur la configuration.En analogie avec un sablier, nous nous intéressons en particulier à la séquence des points fixes atteints par l'ajout répété d'un nombre fini de grains à une même position, et à l'émergence de structures étonnamment régulières.Après avoir établi une conjecture sur l'émergence de motifs de vague sur les points fixes, nous nous pencherons dans un premier temps sur une procédure inductive de calcul des points fixes. Chaque étape de l'induction correspond au calcul d'une avalanche provoquée par l'ajout d'un nouveau grain, et nous en proposerons une description simple. Cette étude sera prolongée par la définition de trace des avalanches sur une colonne i, qui capture dans un mot d'un alphabet fini l'information nécessaire à la reconstitution du point fixe pour les colonnes à la droite de l'indice i. Des liens entre les traces à des indices successifs seront alors exploités, liens qui permettent de conclure l'émergence de traces régulières, pour lesquelles la reconstitution du point fixe implique la formation des motifs de vague observés. Cette première approche est concluante pour le plus petit paramètre conjecturé jusqu'ici, p=2.L'étude du cas général que nous proposons passe par la construction d'un nouveau système mêlant différentes représentations des points fixes, qui sera analysé par l'association d'arguments d'algèbre linéaire et combinatoires (liés respectivement aux modalités continue et discrète des piles de sable). Ce résultat d'émergence de régularités dans un système dynamique discret fait appel à des techniques nouvelles, dont la compréhension d'un élément de preuve reste en particulier à raffiner, ce qui permet d'envisager un cadre plus général d'appréhension de la notion d'émergence. / Sandpile models are a subclass of Cellular Automata. Bak et al. introduced them in 1987 for they exemplify the intuitive notion of Self-Organized Criticality.The Kadanoff sandpile model is a non-linear discrete dynamical system illustrating the evolution of cubic sand grains from nicely packed columns to nicely packed columns. For a fixed parameter p, a rule is applied until reaching a stable configuration, called a fixed point : if the height difference between two consecutive columns is strictly greater than p, then p grains fall from the left column, one landing on each of the p adjacent columns on the right.From a simple local rule, to describe and understand the macroscopic behavior of sandpiles is very quickly challenging. The difficulty consists in the simultaneous study of continuous and discrete aspects of the system: on a large scale, a sandpile flows like a liquid; but on a small scale, when we want to describe exactly the shape of a fixed point, the effects of the discrete dynamic must be taken into account. If for example we add a single grain on a stabilized sandpile, it triggers an avalanche that roughly changes only the upper layer of the configuration, but which size is hard to predict because it is sensitive to the tiniest change of the configuration.In analogy with an hourglass, we are particularly interested in the sequence of fixed points reached after adding a finite number of grains on one position, with the aim of explaining the emergence of surprisingly regular patterns.After conjecturing the emergence of wave patterns on fixed points, we firstly consider an inductive procedure for computing fixed points. Each step of the induction corresponds to the computation of an avalanche triggered by the addition of a new grain, for which we propose a simple description. This study is carried on with the definition of the trace of avalanches on a column i, which catches in a word among a finite alphabet enough information in order to reconstruct the fixed point on the right of index i. Links between traces on successive columns are then investigated, links allowing to conclude the emergence of regular traces, whose fixed point's reconstruction involves the appearance and maintain of the wave patterns observed. This first approach is conclusive for the smallest conjectured parameter so far, p=2.The study of the general case goes through the design of a new system meddling in different representations of fixed points, which will be analyzed via an association of arguments of linear algebra and combinatorics (respectively corresponding to the continuous and discrete modalities of sandpiles). This result stating the emergence of regularities in a discrete dynamical system put new technics into light, for which the comprehension of a particular point in the proof remains to be increased. This motivates the consideration of a more general frame of work tackling the notion of emergence.

Le système climatique génère un attracteur étrange, décrit par une distribution de probabilité, nommée la mesure SRB (Sinai-Ruelle-Bowen). Cette mesure décrit l'état et sa dynamique du système. Le but de cette thèse est d'une part de quantifier les modifications de cette mesure quand le climat change. Pour cela, la distance de Wasserstein venant de la théorie du transport optimal, permet de mesurer finement les différences entre distributions de probabilités. Appliquée à un modèle jouet de Lorenz non autonome, elle a permis de détecter et quantifier l'altération due à un forçage similaire à celui du forçage anthropique. La même méthodologie a été appliquée à des simulations de scénarios RCP du modèle de l'IPSL. Des résultats cohérents avec les différents scénarios ont été retrouvés. D'autre part, la théorie du transport optimal fournit un contexte théorique pour la correction de biais dans un contexte stationnaire : une méthode de correction de biais est équivalente à une loi jointe de probabilité. Une loi jointe particulière est sélectionnée grâce à la distance de Wasserstein (méthode Optimal Transport Correction, OTC). Cette approche étend les méthodes de corrections en dimension quelconque, corrigeant en particulier les dépendances spatiales et inter-variables. Une extension dans le cas non-stationnaire a également été proposée (méthode dynamical OTC, dOTC). Ces deux méthodes ont été testées dans un contexte idéalisé, basé sur un modèle de Lorenz, et sur des données climatiques (une simulation climatique régionale corrigée avec des ré-analyses SAFRAN). / The climate system generates a strange attractor, described by a probability distribution, called the SRB measure (Sinai-Ruelle-Bowen). This measure describes the state and dynamic of the system. The goal of this thesis is first, to quantify the modification of this measure when climate changes. For this, the Wasserstein distance, stemming from the optimal transport theory, allows us determine accurately the differences between probability distributions. Used on a non-autonomous Lorenz toy model, this metric allows us to detect and quantify the alteration due to a forcing similar to anthropogenic forcing. This methodology has been applied to simulation of RCP scenarios from the IPSL model. The results are coherent with different scenarios. Second, the optimal transport gives a theoretical context for stationary bias correction: a bias correction method is equivalent to a joint probability law. A specific joint law is selected with the Wasserstein distance (Optimal Transport Correction method, OTC). This approach allows us extending bias correction methods in any dimension, correcting spatial and inter-variables dependences. An extension in the non-stationary context has been also developed (dynamical OTC method, dOTC). Those two methods have been tested in an idealized case, based on a Lorenz model, and on climate dataset (a regional climate simulation corrected with respect to the SAFRAN reanalysis).

Cette thèse propose une infrastructure cognitive permettant de modéliser les comportements sensori-moteurs animaux et humains. La réflexion théorique ayant conduit à cette infrastructure s'inspire du cadre philosophique interactiviste et du paradigme de l'énaction : tout système est représenté par un ensemble de processus actifs, en interaction permanente avec leur environnement propre, ce qui inclut leur influence mutuelle. Tout organisme vivant ou système cognitif peut ainsi être décomposé de manière fractale, chaque niveau d'émergence reposant sur les mêmes principes. Ces principes aujourd'hui largement répandus sont apparus durant l'évolution des espèces vivantes. L'assimilation, la régulation, l'anticipation ou encore la coordination ont ainsi permis à des processus en concurrence pour des ressources limitées de coopérer, se développer et se maintenir à travers les âges. Cette évolution conjointe des conditions environnementales et des structures internes a conduit aux organismes modernes, capables de s'adapter à un environnement génétiquement imprévisible et d'une complexité croissante.<br /><br />Un modèle mathématique utilisant le formalisme des systèmes complexes est détaillé, ainsi que son implémentation informatique. La dynamique de l'agent y est modélisée par un champ d'activité sous l'influence permanente d'anticipations internes et de sensations externes. Le comportement global de l'agent résulte alors de la coordination implicite et stable de processus interactifs localisés. A ce niveau, le modèle étend et complète les réseaux de neurones artificiels et les modèles probabilistes classiques. Cette caractéristique essentielle permet d'appliquer le modèle à des domaines variés et d'unifier tous les niveaux de la cognition. Le modèle est validé par un ensemble d'applications s'étendant de la satisfaction de besoins physiologiques à la manipulation de systèmes mécaniques, en passant par la perception auditive et visuelle. Enfin, et afin de pouvoir étendre ce type de modèles à des problèmes plus complexes dans le futur, des contributions techniques touchant à l'optimisation et à la parallélisation des algorithmes sont développées.

Motivé par l'étude numérique de la dispersion de particules dans un écoulement turbulent, ce travail présente l'application et le développement de méthodes de réduction de modèles couplées à un système dynamique d'ordre bas pour les équations de Navier-Stokes. Ainsi, la première méthode appliquée est la décomposition orthogonale aux valeurs propres (POD). Couplée à un système dynamique d'ordre faible obtenu par projection de Galerkin des équations de Navier-Stokes sur la base POD, cette méthode montre son efficacité en terme de temps de simulation pour le calcul de la dispersion de particules. Cependant, la POD nécessite au préalable un échantillonage temporel de l'écoulement, ce qui est handicapant. Afin de palier ce problème, l'alternative envisagée dans ce travail est l'utilisation d'une méthode de réduction \emph{a priori}, l'APR, basée sur la construction itérative d'une base de l'écoulement.<br />La méthode APR est d'abord testée dans des cas modèles simples : l'équation de convection-diffusion 2D et les équations de Burgers 1D et 2D. Comparée aux méthodes de résolution classique, l'APR permet de diminuer fortement les temps de calcul tout en conservant une précision du même ordre de grandeur.<br />Les équations de Navier-Stokes sont ensuite résolues à l'aide d'un code volumes finis 2D, utilisant un découplage vitesse-pression de type Van Kahn. Un algorithme de réduction a priori adapté à l'algorithme de projection est alors présenté et appliqué pour le cas de la cavité entraînée 2D à Re=10000. Les résultats obtenus sur un court intervalle de temps sont assez encourageants. Enfin, une démarche d'avancement temporel basée sur le couplage d'APR et de systèmes dynamiques est présentée.

Divers algorithmes d'études locale d'ensembles invariants compacts de systèmes dynamiques sont présentés dans ce travail. Nous commençons par développer des méthodes de calcul numérique de la densité locale autour d'un point d'un ensemble de Julia de fraction rationnelle. Ce problème est important dans le domaine de l'étude des modèles hiérarchiques de la physique statistique. De plus, cette densité serait un des paramètres principaux de la caractérisation d'invariants compacts de systèmes dynamiques (attracteur étrange...). L'application de ces méthodes demande des algorithmes d'accès rapide à des régions (rectangle, cercle) du compact numériquement approche par un ensemble forme d'un grand nombre de points. Nous avons mis au point un algorithme, réellement implémentable et expérimentalement efficace, qui résout ce problème. Nous montrons que, sous certaines conditions, ce procédé permet l'estimation de quelques dimensions fractales de l'ensemble considère. Un logiciel, nomme Elsep et écrit en langage Pascal, qui regroupe et exploite tous ces algorithmes ponctue cette étude. Des résultats numériques et graphiques illustrent chacune des parties traitées

L'objectif de cette thèse consiste étudier et approfondir des techniques d'estimation de la densité et de classification dans des espaces de dimension élevée. Nous avons choisi de structurer notre travail en trois parties.<br /><br />La première partie, intitulée compléments sur les histogrammes modifiés, est composée de deux chapitres consacrés l'étude d'une famille d'estimateurs non paramétriques de la densité, les histogrammes modifiés, connus pour posséder de bonnes propriétés de convergence au sens des critères de la théorie de l'information. Dans le premier chapitre, ces estimateurs sont envisagés comme des systèmes dynamiques espace d'états de dimension infinie. Le second chapitre est consacré l'étude de ces estimateurs pour des dimensions suprieures un.<br /><br />La deuxième partie de la thèse, intituleé méthodes combinatoires en estimation de la densité, se divise en deux chapitres. Nous nous intéressons dans cette partie aux performances distance finie d'estimateurs de la densité sélectionnés à l'intérieur d'une famille d'estimateurs candidats, dont le cardinal n'est pas nécessairement fini. Dans le premier chapitre, nous étudions les performances de ces méthodes dans le cadre de la sélection des différents paramètres des histogrammes modifiés. Nous poursuivons, dans le deuxième chapitre, par la sélection d'estimateurs à noyau dont le paramètre de lissage s'adapte localement au point d'estimation et aux données.<br /><br />Enfin, la troisième et dernière partie, plus appliquée et indépendante des précédentes, présente une nouvelle méthode permettant de classer des courbes partir d'une décomposition des observations dans des bases d'ondelettes.

betaLorsque des réactions chimiques non-linéaires évoluent loin de leur état d'équilibre thermodynamique et sont couplées au processus de transport par diffusion moléculaire, des instabilités spatiales et spatio-temporelles peuvent apparaître. Dans un réacteur chimique entretenu par des flux de réactifs, nous étudions de tels systèmes de réaction-diffusion mis en oeuvre dans des gels de polyélectrolytes. Les variations volumiques du gel induites par les changements d'état chimique de la réaction génèrent une grande variété de structures morphologiques stationnaires ou dynamiques. Les changements de tailles du gel support contribuent à faire naître de nouvelles instabilités. Nous tentons de comprendre la contribution apportée par les différents processus (réaction-diffusion, changement de taille) sur la dynamique résultante du système. Ces études participent à la conception de nouveaux systèmes "intelligents" autonomes.

La théorie de la viabilité propose des concepts et méthodes pour contrôler un système dynamique afin de le maintenir dans un ensemble de contraintes de viabilité. Les applications sont nombreuses en écologie, économie ou robotique, lorsqu'un système meurt ou se détériore lorsqu'il quitte une certaine zone de son espace d'états. A partir du calcul du noyau de viabilité ou du bassin de capture d'un système, elle permet de définir des politiques d'action qui maintiennent le système dans l'ensemble de contraintes choisi. Cependant, les algorithmes classiques d'approximation de noyaux de viabilité ou de bassins de capture présentent certaines limitations ; notamment, ils souffrent de la malédiction de la dimensionnalité et leur application est réservée à des problèmes en petite dimension (dans l'espace d'état et des contrôles). L'objectif de cette thèse est de développer des algorithmes d'approximation de noyaux de viabilité et de bassin de capture plus performants, en utilisant une méthode d'apprentissage statistique particulière : les machines à vecteurs de support (Support Vector Machines - SVMs). Nous proposons un nouvel algorithme d'approximation d'un noyau de viabilité, basé sur l'algorithme de Patrick Saint-Pierre, qui utilise une méthode d'apprentissage pour définir la frontière du noyau. Après avoir rappelé les conditions mathématiques que la procédure doit respecter, nous considérons les SVMs dans ce contexte. Cette méthode d'apprentissage fournit une sorte de fonction barrière à la frontière du noyau, ce qui permet d'utiliser des méthodes d'optimisation pour trouver un contrôle viable, et ainsi de travailler dans des espaces de contrôle plus importants. Cette fonction "barrière" permet également de dériver des politiques de contrôle plus ou moins prudentes. Nous appliquons la procédure à un problème de gestion des pêches, en examinant quelles politiques de pêche permettent de garantir la viabilité d'un écosystème marin. Cet exemple illustre les performances de la méthode proposée : le système comporte 6 variables d'états et 51 variables de contrôle. A partir de l'algorithme d'approximation d'un noyau de viabilité utilisant les SVMs, nous dérivons un algorithme d'approximation de bassin de capture et de résolution de problèmes d'atteinte d'une cible en un temps minimal. Approcher la fonction de temps minimal revient à rechercher le noyau de viabilité d'un système étendu. Nous présentons une procédure qui permet de rester dans l'espace d'état initial, et ainsi d'éviter le coût (en temps de calcul et espace mémoire) de l'addition d'une dimension supplémentaire. Nous décrivons deux variantes de l'algorithme : la première procédure donne une approximation qui converge par l'extérieur et la deuxième par l'intérieur. La comparaison des deux résultats donne une évaluation de l'erreur d'approximation. L'approximation par l'intérieur permet de définir un contrôleur qui garantit d'atteindre la cible en un temps minimal. La procédure peut être étendue au problème de minimisation d'une fonction de coût lorsque celle-ci respecte certaines conditions. Nous illustrons cet aspect sur le calcul de valeurs de résilience. Nous appliquons la procédure sur un problème de calcul de valeurs de résilience sur un modèle d'eutrophication des lacs. Les algorithmes proposés permettent de résoudre le problème de l'augmentation exponentielle du temps de calcul avec la dimension de l'espace des contrôles mais souffrent toujours de la malédiction de la dimensionnalité pour l'espace d'état : la taille du vecteur d'apprentissage augmente exponentiellement avec la dimension de l'espace. Nous introduisons des techniques d'apprentissage actif pour sélectionner les états les plus "informatifs" pour définir la fonction SVM, et ainsi gagner en espace mémoire, tout en gardant une approximation précise du noyau. Nous illustrons la procédure sur un problème de conduite d'un vélo sur un circuit, système défini par six variables d'état.