L’algorithme de basculement de bits à descente de gradient probabiliste (Probabilistic Gradient Descent Bit Flipping :PGDBF) est récemment introduit comme un nouveau type de décodeur de décision forte pour le code de contrôle de parité à faible densité (Low Density Parity Check : LDPC) appliqué au canal symétrique binaire. En suivant précisément les étapes de décodage du décodeur déterministe Gradient Descent Bit-Flipping (GDBF), le PGDBF intègre en plus la perturbation aléatoire dans l'opération de basculement des Nœuds de Variables (VNs) et produit ainsi une performance de décodage exceptionnelle qui est meilleure que tous les décodeurs à basculement des bits (BF : Bit Flipping) connus dans la littérature, et qui approche les performances du décodeur de décision souple. Nous proposons dans cette thèse plusieurs implémentations matérielles du PGDBF, ainsi qu'une analyse théorique de sa capacité de correction d'erreurs. Avec une analyse de chaîne de Markov du décodeur, nous montrons qu’en raison de l'incorporation de la perturbation aléatoire dans le traitement des VNs, le PGDBF s'échappe des états de piégeage qui empêchent sa convergence. De plus, avec la nouvelle méthode d'analyse proposée, la performance du PGDBF peut être prédite et formulée par une équation de taux de trames erronées en fonction du nombre des itérations, pour un motif d'erreur donné. L'analyse fournit également des explications claires sur plusieurs phénomènes de PGDBF tels que le gain de re-décodage (ou de redémarrage) sur un motif d'erreur reçu. La problématique de l’implémentation matérielle du PGDBF est également abordée dans cette thèse. L’implémentation classique du décodeur PGDBF, dans laquelle un générateur de signal probabiliste est ajouté au-dessus du GDBF, est introduite avec une augmentation inévitable de la complexité du décodeur. Plusieurs procédés de génération de signaux probabilistes sont introduits pour minimiser le surcoût matériel du PGDBF. Ces méthodes sont motivées par l'analyse statistique qui révèle les caractéristiques critiques de la séquence aléatoire binaire requise pour obtenir une bonne performance de décodage et suggérer les directions possibles de simplification. Les résultats de synthèse montrent que le PGDBF déployé avec notre méthode de génération des signaux aléatoires n’a besoin qu’une très faible complexité supplémentaire par rapport au GDBF tout en gardant les mêmes performances qu’un décodeur PGDBF théorique. Une implémentation matérielle intéressante et particulière du PGDBF sur les codes LDPC quasicyclique (QC-LPDC) est proposée dans la dernière partie de la thèse. En exploitant la structure du QCLPDC, une nouvelle architecture pour implémenter le PGDBF est proposée sous le nom d'architecture à décalage des Nœuds de Variables (VNSA : Variable-Node Shift Architecture). En implémentant le PGDBF par VNSA, nous montrons que la complexité matérielle du décodeur est même inférieure à celle du GDBF déterministe tout en préservant la performance de décodage aussi élevée que celle fournie par un PGDBF théorique. Enfin, nous montrons la capacité de cette architecture VNSA à se généraliser sur d'autres types d'algorithmes de décodage LDPC. / Probabilistic Gradient Descent Bit Flipping (PGDBF) algorithm have been recently introduced as a new type of hard decision decoder for Low-Density Parity-Check Code (LDPC) applied on the Binary Symmetric Channel. By following precisely the decoding steps of the deterministic Gradient Descent Bit-Flipping (GDBF) decoder, PGDBF additionally incorporates a random perturbation in the ipping operation of Variable Nodes (VNs) and produces an outstanding decoding performance which is better to all known Bit Flipping decoders, approaching the performance of soft decision decoders. We propose in this thesis several hardware implementations of PGDBF, together with a theoretical analysis of its error correction capability. With a Markov Chain analysis of the decoder, we show that, due to the incorporation of random perturbation in VN processing, the PGDBF escapes from the trapping states which prevent the convergence of decoder. Also, with the new proposed analysis method, the PGDBF performance can be predicted and formulated by a Frame Error Rate equation as a function of the iteration, for a given error pattern. The analysis also gives a clear explanation on several phenomenons of PGDBF such as the gain of re-decoding (or restarting) on a received error pattern. The implementation issue of PGDBF is addressed in this thesis. The conventional implementation of PGDBF, in which a probabilistic signal generator is added on top of the GDBF, is shown with an inevitable increase in hardware complexity. Several methods for generating the probabilistic signals are introduced which minimize the overhead complexity of PGDBF. These methods are motivated by the statistical analysis which reveals the critical features of the binary random sequence required to get good decoding performance and suggesting the simpli cation directions. The synthesis results show that the implemented PGDBF with the proposed probabilistic signal generator method requires a negligible extra complexity with the equivalent decoding performance to the theoretical PGDBF. An interesting and particular implementation of PGDBF for the Quasi-Cyclic LPDC (QC-LPDC) is shown in the last part of the thesis. Exploiting the structure of QC-LPDC, a novel architecture to implement PGDBF is proposed called Variable-Node Shift Architecture (VNSA). By implementing PGDBF by VNSA, it is shown that the decoder complexity is even smaller than the deterministic GDBF while preserving the decoding performance as good as the theoretical PGDBF. Furthermore, VNSA is also shown to be able to apply on other types of LDPC decoding algorithms.

Ces travaux portent sur la validation de modèles de systèmes sur puce (SoC) au niveau transactionnel (TLM). Ces modèles servent notamment au développement du logiciel embarqué. Le matériel est intrinsèquement parallèle mais le simulateur utilise un seul processeur. Les principales entités parallèles du matériel (processeurs, DMA, arbitres de bus, ...) sont représentées en TLM par des processus asynchrones, qui doivent être ordonnancés lors des simulations. Cet ordonnancement est indéterministe afin de mieux représenter le parallélisme physique.<br /><br />Cela pose un problème pour la validation par simulations : il faut couvrir l'espace des ordonnancements en plus de celui des données. En effet, un ordonnanceur déterministe peut cacher des erreurs, car il ne montre qu'un comportement parmi d'autres. Des ordonnancements aléatoires permettent d'observer plus de comportements mais la couverture est incertaine. Un parcours exhaustif de tous les ordonnancements serait beaucoup trop long pour des tests réels.<br /><br />Nous présentons une solution pour couvrir efficacement l'espace des ordonnancements. Celle-ci est basée sur de la réduction d'ordre partiel dynamique. L'idée est d'observer l'influence de l'ordonnancement sur les communications entre processus, pour générer dynamiquement de nouveaux ordonnancements, menant très probablement à des états finaux différents. En itérant sur chaque nouvel ordonnancement, nous obtenons un jeu complet d'ordonnancements, qui garantit la détection, pour un jeu fixé de données, de toutes les erreurs locales et de tous les inter-blocages.<br /><br />Toujours avec l'objectif d'une meilleure représentativité du matériel, les développeurs ont ajouté du temps imprécis à leurs modèles TLM, sous forme de délais bornés. Pour la validation par simulations, cela oblige à couvrir aussi l'espace des temporisations. Nous présentons une extension à la réduction d'ordre partiel dynamique pour résoudre ce problème. Le nouvel algorithme et son prototype retournent un ensemble de jeux de durées, qui garantit de nouveau la détection complète des erreurs locales et inter-blocages pour des données fixées.<br /><br />Enfin, nous étudions comment paralléliser le simulateur SystemC afin de profiter des machines multiprocesseurs, tout en respectant la spécification de SystemC et les particularités des modèles TLM.

Nos travaux portent sur les Expressions Numériques Approximatives (ENA), définies comme des expressions linguistiques impliquant des valeurs numériques et un adverbe d'approximation, telles que "environ 100". Nous nous intéressons d’abord à l’interprétation d’ENA non contextualisées, dans ses aspects humain et computationnel. Après avoir formalisé des dimensions originales, arithmétiques et cognitive, permettant de caractériser les ENA, nous avons conduit une étude empirique pour collecter les intervalles de plages de valeurs dénotées par des ENA, qui nous a permis de valider les dimensions proposées. Nous avons ensuite proposé deux modèles d'interprétation, basés sur un même principe de compromis entre la saillance cognitive des bornes des intervalles et leur distance à la valeur de référence de l’ENA, formalisé par un front de Pareto. Le premier modèle estime l’intervalle dénoté, le second un intervalle flou représentant l’imprécision associée. Leur validation expérimentale à partir de données réelles montre qu’ils offrent de meilleures performances que les modèles existants. Nous avons également montrél’intérêt du modèle flou en l’implémentant dans le cadre des requêtes flexibles de bases de données. Nous avons ensuite montré, par une étude empirique, que le contexte et les interprétations, implicite vs explicite, ont peu d’effet sur les intervalles. Nous nous intéressons enfin à l’addition et à la multiplication d’ENA, par exemple pour évaluer la surface d’une pièce d’"environ 10" par "environ 20 mètres". Nous avons mené une étude dont les résultats indiquent que les imprécisions liées aux opérandes ne sont pas prises en compte lors des calculs. / Approximate Numerical Expressions (ANE) are imprecise linguistic expressions implying numerical values, illustrated by "about 100". We first focus on ANE interpretation, both in its human and computational aspects. After defining original arithmetical and cognitive dimensions allowing to characterize ANEs, we conducted an empirical study to collect the intervals of values denoted by ANEs. We show that the proposed dimensions are involved in ANE interpretation. In a second step, we proposed two interpretation models, based on the same principle of a compromise between the cognitive salience of the endpoints and their distance to the ANE reference value, formalized by Pareto frontiers. The first model estimates the denoted interval, the second one generates a fuzzy interval representing the associated imprecision. The experimental validation of the models, based on real data, show that they offer better performances than existing models. We also show the relevance of the fuzzy model by implementing it in the framework of flexible database queries. We then show, by the mean of an empirical study, that the semantic context has little effect on the collected intervals. Finally, we focus on the additions and products of ANE, for instance to assess the area of a room whose walls are "about 10" and "about 20 meters" long. We conducted an empirical study whose results indicate that the imprecisions associated with the operands are not taken into account during the calculations.

Dans le cadre de cette thèse, nous proposons une prothèse de mémoire « intelligente », appelée CAPTAIN MEMO, destinée aux malades d’Alzheimer, pour pallier leurs problèmes mnésiques. Cette prothèse est basée sur l’ontologie temporelle, floue et multilingue appelée MemoFuzzyOnto.Cette prothèse offre des interfaces accessibles à cette classe particulière d’utilisateurs. Nous proposons, pour mettre en œuvre ces interfaces, une méthodologie de conception appelée InterfaceToAlz pour concevoir des interfaces accessibles aux malades d’Alzheimer, et qui offre un guide de 146 bonnes pratiques ergonomiques. De plus, nous proposons un outil de visualisation d’ontologies appelé Memo Graph qui génère un graphe dont la visualisation et la manipulation sont accessibles aux malades d’Alzheimer. Cette proposition est motivée par le fait que CAPTAIN MEMO a besoin de générer et d’éditer le graphe de la famille et de l’entourage du patient, à partir de l’ontologie MemoFuzzyOnto qui structure sa base de connaissances. Memo Graph est fondé sur notre guide de bonnes pratiques ergonomiques et notre approche, appelée Incremental Key-Instances Extraction and Visualisation, qui permet une extraction et une visualisation incrémentale du résumé des assertions ABox de l’ontologie. Il supporte également la visualisation des données ouvertes liées (Linked Data) et le passage à l’échelle. Par ailleurs, nous proposons, dans le cadre de cette thèse, une typologie de l’imperfection des données saisies (principalement due à la discordance mnésique provoquée par la maladie), et une méthodologie pour permettre à CAPTAIN MEMO d’être tolérante à la saisie des données fausses. Nous proposons un modèle d’évaluation de la crédibilité et une approche, nommée Data Believability Estimation for Applications to Alzheimer Patients, permettant d’estimer qualitativement et quantitativement la crédibilité de chaque donnée saisie. Enfin, pour que CAPTAIN MEMO soit tolérante à la saisie des intervalles temporels imprécis nous proposons deux approches : l’une basée sur un environnement précis et l’autre basée sur un environnement flou. Dans chacune des deux approches, nous étendons l’approche 4D-fluents pour représenter les intervalles temporels imprécis et les relations temporelles qualitatives, puis nous étendons l’algèbre d’Allen pour prendre en compte les intervalles imprécis dans le cadre de notre ontologie MemoFuzzyOnto. Nos contributions sont implémentées et évaluées. Nous avons évalué l’accessibilité de ses interfaces utilisateurs, le service de CAPTAIN MEMO qui a pour but de stimuler la mémoire du patient, notre approche pour l’estimation quantitative de la crédibilité des données saisies ainsi que la visualisation du graphe générée à l’aide de Memo Graph. Nous avons également évalué la performance de Memo Graph et son utilisabilité par des experts du domaine. / In the context of this thesis, we propose a “smart” memory prosthesis, called CAPTAIN MEMO, to help Alzheimer’s disease patients to palliate mnesic problems. It is based on a temporal, fuzzy and multilingual ontology named MemoFuzzyOnto. It provides accessible user interfaces to this demographic. To design these interfaces, we propose a methodology named InterfaceToAlz which serves as an information base for guiding and evaluating the design of user interfaces for Alzheimer’s disease patients. It identifies 146 design guidelines.Besides, we propose an ontology visualization tool called Memo Graph which offers an accessible and understandable visualization to Alzheimer’s disease patients. In fact, in the context of CAPTAIN MEMO, there is a need to generate the patient entourage/family tree from its personal data structured according to MemoFuzzyOnto. Memo Graph is based on our design guidelines and our approach, named Incremental Key-Instances Extraction and Visualisation, to extract and visualize descriptive instance summarizations from a given ontology and generate “summary instance graphs” from the most important data. It supports Linked Data visualization and scaling.Furthermore, we propose a typology of the imperfection of the data entered (mainly due to the memory discordance caused by this disease), and a methodology to allow false data entry. We propose a believability model and an approach called Data Believability Estimation for Applications to Alzheimer Patients to estimate qualitatively and quantitatively the believability of each data entered. Finally, CAPTAIN MEMO allows imprecise time intervals entry. We propose two approaches: a crisp-based approach and a fuzzy-based approach. The first one uses only crisp standards and tools and is modeled in OWL 2. The second approach is based on fuzzy sets theory and fuzzy tools and is modeled in Fuzzy-OWL 2. For the two approaches, we extend the 4D-fluents model to represent imprecise time intervals and qualitative interval relations. Then, we extend the Allen’s interval algebra to compare imprecise time interval in the context of MemoFuzzyOnto. Our contributions are implemented and evaluated. We evaluated the service of CAPTAIN MEMO which has the aim to stimulate the patient’s memory, the accessibility of its user interfaces, the efficiency of our approach to estimate quantitatively the believability of each data entered and the visualization generated with Memo Graph. We also evaluated Memo Graph with domain expert users.