Optimization of fixed-point circuits represented by Taylor Series and real-valued polynomials including analysis of precision and range

In this thesis, our research focuses on fixed-point arithmetic circuits. Fixed-point representation is important in low power Application-Specific Integrated Circuits (ASICs) and in Programmable Logic Devices (PLDs). There are two aspects of the data representation problem: the precision problem and the range problem. Both of these are addressed in this thesis. We use the new technique based on Arithmetic Transform (AT) which is a canonical and efficient representation for digital circuits to avoid the disadvantages of past methods, and design an efficient algorithm which can compose detached modules to obtain the overall AT for a complex circuit.First the precision problem is processed. The typical imprecise circuits expressed in terms of Taylor series are addressed in our research. Imprecise factors including finite terms and input quantization are analyzed by AT, and algorithms are designed to verify and optimize imprecise circuits in terms of different constraints. A hybrid method performs range analysis to handle the range problem and allocates the smallest integer bit-widths. Having devised the individual methods for precision and range analysis, we then combine the two together to find the optimized implementation. Furthermore, we extend the method to analyze floating-point circuits and feedback circuits.The proposed algorithms in the thesis overcome disadvantages of past explorations. They are more flexible in processing both Taylor series and multivariate polynomials and obtain more precise results, resulting in better implementations under various constraints.Dans ce manuscrit, notre recherche se concentre sur les circuits de l'arithmétique à virgule fixe. La représentation à virgule fixe est un facteur important dans les applications d'une faible consommation pour les ASICs (Application Specific Integrated Circuit) ainsi que les circuits logiques programmables (PLD). Au point de la représentation des données, généralement, il y a deux aspects de problèmes dont la précision et la gamme. Dans ce manuscrit, nous adressons principalement à ces deux éléments. Une nouvelle technique basée sur une transformée arithmétique (AT) est utilisée. Ceci est une représentation canonique et efficace pour les circuits numériques qui permet d'éviter les inconvénients des méthodes passées et de concevoir un nouvel algorithme efficace afin de composer des modules détachés en obtenant une AT le plus générale pour les circuits complexes.Un travail préliminaire sur le problème de précision est effectué. Les circuits imprécis généraux s'expriment en termes d'une série de Taylor a été mis en œuvre dans notre recherche. Y compris des facteurs imprécis tels que les termes finis, la quantification d'entrée qui est analysée par AT ainsi que les algorithmes qui sont conçus pour vérifier et optimiser les circuits imprécis en termes de contraintes différentes. Une méthode d'une façon hybride est effectuée afin de traiter le problème de la gamme et d'allouer un entier le plus petit de bit-widths. Mise au point sur les différentes méthodes pour la précision et l'analyse de la gamme, nous combinons les deux ensembles afin de trouver une implémentation optimisée. En outre, nous étendons la méthode pour analyser des circuits en virgule flottante et les circuits de rétroaction.Les algorithmes proposés dans ce manuscrit est de surmonter les inconvénients des explorations passées. Ces algorithmes sont plus flexibles dans le traitement de la série de Taylor et des polynômes à plusieurs variables. Ceux-ci nous permettent d'obtenir les résultats plus précis ainsi d'entraîner les meilleures implémentations sous diverses contraintes