Dans cette thèse, nous analysons les problèmes liés à la représentation finie des nombres réels et nous contrôlons la déviation induite par cette approximation. Nous nous intéressons particulièrement à deux problèmes. Le premier est l'étude de l'influence de la représentation finie sur les protocoles de confidentialité différentielle. Nous présentons une méthode pour étudier les perturbations d'une distribution de probabilité causées par la représentation finie des nombres. Nous montrons qu'une implémentation directe des protocoles théoriques pour garantir la confidentialité différentielle n'est pas fiable, tandis qu'après l'ajout de correctifs, la propriété est conservée en précision finie avec une faible perte de confidentialité. Notre deuxième contribution est une méthode pour étudier les programmes qui ne peuvent pas être analysés par composition à cause de branchements conditionnels au comportement trop erratique. Cette méthode, basée sur la théorie des systèmes de réécriture, permet de partir de la preuve de l'algorithme en précision exacte pour fournir la preuve que le programme en précision finie ne déviera pas trop.

Cette thèse CIFRE, réalisée en collaboration industrielle entre l'IRCCyN et PSA Peugeot-Citroën, s'intéresse à l'aspect numérique de l'implémentation, au sein de calculateurs embarqués, de lois de contrôle/commande.<br /> <br />Ces travaux ont porté sur l'implémentation de lois de contrôle-commande (provenant de l'automatique ou du traitement du signal) sous les contraintes de précision finie.<br />Le processus d'implémentation amène de nombreuses dégradations de la loi et nous nous intéressons plus particulièrement à la quantification des coefficients intervenant dans les calculs.<br /><br />Pour une loi (filtre ou régulateur) donnée, il existe une infinité de réalisations numériques possibles qui, bien que mathématiquement équivalentes, ne le sont plus en précision finie : de nombreuses réalisations équivalentes existent : forme d'état, réalisations en delta, formes directes, structures retour d'état observateur, décompositions en cascade, en parallèle, ...<br /><br />Après avoir présenté ces différentes possibilités, ce mémoire de thèse, propose un formalisme mathématique — la forme implicite spécialisée —qui permet de décrire de manière unifiée un ensemble élargi d'implémentations. Celui-ci, bien que macroscopique, permet d'exprimer précisément les calculs à réaliser et les paramètres réellement mis en jeu. Différentes mesures, appliquées à ce formalisme et qui permettent d'évaluer l'impact de la quantification (en virgule fixe et virgule flottante) et d'analyser la dégradation induite, sont ensuite proposées.<br />Via un problème d'optimisation, la réalisation qui présente la meilleure robustesse face aux détériorations induites par les processus d'implémentation en précision finie est trouvée.

Les surfaces de subdivision fournissent une méthode alternative prometteuse dans la modélisation géométrique, et ont des avantages sur la représentation classique de trimmed-NURBS, en particulier dans la modélisation de surfaces lisses par morceaux. Dans ce mémoire, nous considérons le problème des opérations géométriques sur les surfaces de subdivision, avec l'exigence stricte de forme topologique correcte. Puisque ce problème peut être mal conditionné, nous proposons une approche pour la gestion de l'incertitude qui existe dans le calcul géométrique. Nous exigeons l'exactitude des informations topologiques lorsque l'on considère la nature de robustesse du problème des opérations géométriques sur les modèles de solides, et il devient clair que le problème peut être mal conditionné en présence de l'incertitude qui est omniprésente dans les données. Nous proposons donc une approche interactive de gestion de l'incertitude des opérations géométriques, dans le cadre d'un calcul basé sur la norme IEEE arithmétique et la modélisation en surfaces de subdivision. Un algorithme pour le problème planar-cut est alors présenté qui a comme but de satisfaire à l'exigence topologique mentionnée ci-dessus. / Subdivision surfaces are a promising alternative method for geometric modelling, and have some important advantages over the classical representation of trimmed-NURBS, especially in modelling piecewise smooth surfaces. In this thesis, we consider the problem of geometric operations on subdivision surfaces with the strict requirement of correct topological form, and since this problem may be ill-conditioned, we propose an approach for managing uncertainty that exists inherently in geometric computation. We take into account the requirement of the correctness of topological information when considering the nature of robustness for the problem of geometric operations on solid models, and it becomes clear that the problem may be ill-conditioned in the presence of uncertainty that is ubiquitous in the data. Starting from this point, we propose an interactive approach of managing uncertainty of geometric operations, in the context of computation using the standard IEEE arithmetic and modelling using a subdivision-surface representation. An algorithm for the planar-cut problem is then presented, which has as its goal the satisfaction of the topological requirement mentioned above.

Les surfaces de subdivision fournissent une méthode alternative prometteuse dans la modélisation géométrique, et ont des avantages sur la représentation classique de trimmed-NURBS, en particulier dans la modélisation de surfaces lisses par morceaux. Dans ce mémoire, nous considérons le problème des opérations géométriques sur les surfaces de subdivision, avec l'exigence stricte de forme topologique correcte. Puisque ce problème peut être mal conditionné, nous proposons une approche pour la gestion de l'incertitude qui existe dans le calcul géométrique. Nous exigeons l'exactitude des informations topologiques lorsque l'on considère la nature de robustesse du problème des opérations géométriques sur les modèles de solides, et il devient clair que le problème peut être mal conditionné en présence de l'incertitude qui est omniprésente dans les données. Nous proposons donc une approche interactive de gestion de l'incertitude des opérations géométriques, dans le cadre d'un calcul basé sur la norme IEEE arithmétique et la modélisation en surfaces de subdivision. Un algorithme pour le problème planar-cut est alors présenté qui a comme but de satisfaire à l'exigence topologique mentionnée ci-dessus. / Subdivision surfaces are a promising alternative method for geometric modelling, and have some important advantages over the classical representation of trimmed-NURBS, especially in modelling piecewise smooth surfaces. In this thesis, we consider the problem of geometric operations on subdivision surfaces with the strict requirement of correct topological form, and since this problem may be ill-conditioned, we propose an approach for managing uncertainty that exists inherently in geometric computation. We take into account the requirement of the correctness of topological information when considering the nature of robustness for the problem of geometric operations on solid models, and it becomes clear that the problem may be ill-conditioned in the presence of uncertainty that is ubiquitous in the data. Starting from this point, we propose an interactive approach of managing uncertainty of geometric operations, in the context of computation using the standard IEEE arithmetic and modelling using a subdivision-surface representation. An algorithm for the planar-cut problem is then presented, which has as its goal the satisfaction of the topological requirement mentioned above.

L'implantation efficace des algorithmes de traitement numérique du signal (TNS) dans les systèmes embarqués requiert l'utilisation de l'arithmétique virgule fixe afin de satisfaire les contraintes de coût, de consommation et d'encombrement exigées par ces applications. Le codage manuel des données en virgule fixe est une tâche fastidieuse et source d'erreurs. De plus, la réduction du temps de mise sur le marché des applications exige l'utilisation d'outils de développement de haut niveau, permettant d'automatiser certaines tâches. Ainsi, le développement de méthodologies de codage automatique des données en virgule fixe est nécessaire. Dans le cadre des processeurs programmables de traitement du signal, la méthodologie doit déterminer le codage optimal, permettant de maximiser la précision et de minimiser le temps d'exécution et la taille du code. L'objectif de ce travail de recherche est de définir une nouvelle méthodologie de compilation d'algorithmes spécifiés en virgule flottante au sein d'architectures programmables en virgule fixe sous contrainte de respect des critères de qualité associés à l'application. Ce travail de recherche s'articule autour de trois points principaux. Le premier aspect de notre travail a consisté à définir la structure de la méthodologie. L'analyse de l'influence de l'architecture sur la précision des calculs montre la nécessité de tenir compte de l'architecture cible pour obtenir une implantation optimisée d'un point de vue du temps d'exécution et de la précision. De plus, l'étude de l'interaction entre les phases de compilation et de codage des données permet de définir le couplage nécessaire entre les phases de conversion en virgule fixe et le processus de génération de code. Le second aspect de ce travail de recherche concerne l'évaluation de la précision au sein d'un système en virgule fixe à travers la détermination du Rapport Signal à Bruit de Quantification (RSBQ). Une méthodologie permettant de déterminer automatiquement l'expression analytique du RSBQ en fonction du format des données en virgule fixe est proposée. Dans un premier temps, un nouveau modèle de bruit est présenté. Ensuite, les concepts théoriques pour déterminer la puissance du bruit de quantification en sortie des systèmes linéaires et des systèmes non-linéaires et non-récursifs sont détaillés. Finalement, la méthodologie mise en oeuvre pour obtenir automatiquement l'expression du RSBQ dans le cadre des systèmes linéaires est exposée. Le troisième aspect de ce travail de recherche correspond à la mise en oeuvre de la méthodologie de codage des données en virgule fixe. Dans un premier temps, la dynamique des données est déterminée à l'aide d'une approche analytique combinant deux techniques différentes. Ces informations sur la dynamique permettent de déterminer la position de la virgule de chaque donnée en tenant compte de la présence éventuelle de bits de garde au sein de l'architecture. Pour obtenir un format des données en virgule fixe complet, la largeur de chaque donnée est déterminée en prenant en compte l'ensemble des types des données manipulées au sein du DSP. La méthode sélectionne la séquence d'instructions permettant de fournir une précision suffisante en sortie de l'algorithme et de minimiser le temps d'exécution du code. La dernière phase du processus de codage correspond à l'optimisation du format des données en vue d'obtenir une implantation plus efficace. Les différentes opérations de recadrage sont déplacées afin de minimiser le temps d'exécution global tant que la précision en sortie de l'algorithme est supérieure à la contrainte. Deux types de méthode ont été mis en {\oe}uvre en fonction des capacités de parallélisme au niveau instruction de l'architecture ciblée. Cette méthodologie a été testée sur différents algorithmes de traitement numérique du signal présents au sein des systèmes de radio-communications de troisième génération. Les résultats obtenus montrent l'intérêt de notre méthodologie pour réduire le temps de développement des systèmes en virgule fixe.