De nombreux systèmes embarqués implémentent des applications de traitement du signal, notamment lors de communications. Certains de ces traitements sont effectués par des filtres linéaires, qu'il est donc nécessaire de mettre en oeuvre numériquement sur ces cibles. Les systèmes embarqués sont sujets à diverses contraintes qu'il faut optimiser tout en conservant des systèmes fiables en terme de performance et de précision. L'arithmétique virgule fixe est généralement préférée à l'arithmétique flottante pour des systèmes embarqués de traitement du signal, entre autres car elle est moins coûteuse, disponibles dans tous les systèmes, permet d'utiliser des largeurs arbitraires sur des cibles matérielles et est généralement suffisante en terme de précision pour les applications de traitement du signal. Le calcul en virgule fixe nécessite d'aligner les positions des virgules pour ainsi rendre cohérent des calculs à base de nombres entiers. Cela implique des quantifications et l'enjeu est donc de minimiser la répercussion de ces arrondis sur le résultat final, en proposant une garantie sur l'erreur sur la sortie. Une méthodologie a été proposée durant cette thèse qui, à partir d'un algorithme de filtre linéaire, utilise une méthode analytique pour implémenter cet algorithme en virgule fixe et générer du code. Cette méthodologie considère à la fois les implémentations logicielles, et les implémentations matérielles qui impliquent la résolution d'un problème d'optimisation. Un outil, nommé FiPoGen, a été développé pour mettre en oeuvre les méthodes proposées et fournir automatiquement un code virgule fixe implémentant un filtre donné avec garantie sur l'erreur sur la sortie. / Embedded systems implement signal processing systems, such as linear filters, for example for communication through networks. These devices are subject to various constraints, such as power consumption, time-To-Market, area consumption, and so on, that is necessary to optimize while guaranteeing reliability and accuracy of the implemented systems. Fixed-Point arithmetic is generally used instead of floating-Point arithmetic for signal processing embedded systems because it is less expensive, all devices support fixed-Point numbers (as they are implemented only using integers), allows arbitrary word-Lengths in hardware implementation and is enough accurate for signal processing programs. Fixed-Point computations need the operands of an operation to be aligned together with the same position of the binary point. This leads to quantification errors and the goal is to minimize these round-Off effects onto the final result, by proposing a guarantee on the output error. During this thesis, a methodology has been proposed which implements a given algorithm in fixed-Point using analytical approach, and generates some codes. This methodology consider both software and hardware targets. The hardware approach is realized solving a word-Length optimization problem. A tool, named FiPoGen, has been developed that realizes this methodology and automatically yields fixed-Point code corresponding to a given filter algorithm with a guarantee on the output error.

De nombreuses méthodes de traitement du signal reposent sur des résultats puissants d'approximation numérique. Un exemple significatif en est l'utilisation de l'approximation de type Chebyshev pour l'élaboration de filtres numériques.En pratique, le caractère fini des formats numériques utilisés en machine entraîne des difficultés supplémentaires pour la conception de filtres numériques (le traitement audio et le traitement d'images sont deux domaines qui utilisent beaucoup le filtrage). La majorité des outils actuels de conception de filtres ne sont pas optimisés et ne certifient pas non plus la correction de leurs résultats. Notre travail se veut un premier pas vers un changement de cette situation.La première partie de la thèse traite de l'étude et du développement de méthodes relevant de la famille Remez/Parks-McClellan pour la résolution de problèmes d'approximation polynomiale de type Chebyshev, en utilisant l'arithmétique virgule-flottante.Ces approches sont très robustes, tant du point de vue du passage à l'échelle que de la qualité numérique, pour l'élaboration de filtres à réponse impulsionnelle finie (RIF).Cela dit, dans le cas des systèmes embarqués par exemple, le format des coefficients du filtre qu'on utilise en pratique est beaucoup plus petit que les formats virgule flottante standard et d'autres approches deviennent nécessaires.Nous proposons une méthode (quasi-)optimale pour traîter ce cas. Elle s'appuie sur l'algorithme LLL et permet de traiter des problèmes de taille bien supérieure à ceux que peuvent traiter les approches exactes. Le résultat est ensuite utilisé dans une couche logicielle qui permet la synthèse de filtres RIF pour des circuits de type FPGA.Les résultats que nous obtenons en sortie sont efficaces en termes de consommation d'énergie et précis. Nous terminons en présentant une étude en cours sur les algorithmes de type Remez pour l'approximation rationnelle. Ce type d'approches peut être utilisé pour construire des filtres à réponse impulsionnelle infinie (RII) par exemple. Nous examinons les difficultés qui limitent leur utilisation en pratique. / The field of signal processing methods and applications frequentlyrelies on powerful results from numerical approximation. One suchexample, at the core of this thesis, is the use of Chebyshev approximationmethods for designing digital filters.In practice, the finite nature of numerical representations adds an extralayer of difficulty to the design problems we wish to address using digitalfilters (audio and image processing being two domains which rely heavilyon filtering operations). Most of the current mainstream tools for thisjob are neither optimized, nor do they provide certificates of correctness.We wish to change this, with some of the groundwork being laid by thepresent work.The first part of the thesis deals with the study and development ofRemez/Parks-McClellan-type methods for solving weighted polynomialapproximation problems in floating-point arithmetic. They are veryscalable and numerically accurate in addressing finite impulse response(FIR) design problems. However, in embedded and power hungry settings,the format of the filter coefficients uses a small number of bits andother methods are needed. We propose a (quasi-)optimal approach basedon the LLL algorithm which is more tractable than exact approaches.We then proceed to integrate these aforementioned tools in a softwarestack for FIR filter synthesis on FPGA targets. The results obtainedare both resource consumption efficient and possess guaranteed accuracyproperties. In the end, we present an ongoing study on Remez-type algorithmsfor rational approximation problems (which can be used for infinite impulseresponse (IIR) filter design) and the difficulties hindering their robustness.

This thesis deals with the concepts of numerical integrator using floating point arithmetic for solving partial differential equations. The integrator uses Euler method and Taylor series. Thesis shows parallel and serial approach to computing with exponents and significands. There is also a comparison between modern parallel systems and the proposed concepts.

Pour permettre l’accroissement de débit et de robustesse dans les futurs systèmes de communication sans fil, les processus itératifs sont de plus considérés dans les récepteurs. Cependant, l’adoption d’un traitement itératif pose des défis importants dans la conception du récepteur. Dans cette thèse, un récepteur itératif combinant les techniques de détection multi-antennes avec le décodage de canal est étudié. Trois aspects sont considérés dans un contexte MIMOOFDM: la convergence, la performance et la complexité du récepteur. Dans un premier temps, nous étudions les différents algorithmes de détection MIMO à décision dure et souple basés sur l’égalisation, le décodage sphérique, le décodage K-Best et l’annulation d’interférence. Un décodeur K-best de faible complexité (LC-K-Best) est proposé pour réduire la complexité sans dégradation significative des performances. Nous analysons ensuite la convergence de la combinaison de ces algorithmes de détection avec différentes techniques de codage de canal, notamment le décodeur turbo et le décodeur LDPC en utilisant le diagramme EXIT. En se basant sur cette analyse, un nouvel ordonnancement des itérations internes et externes nécessaires est proposé. Les performances du récepteur ainsi proposé sont évaluées dans différents modèles de canal LTE, et comparées avec différentes techniques de détection MIMO. Ensuite, la complexité des récepteurs itératifs avec différentes techniques de codage de canal est étudiée et comparée pour différents modulations et rendement de code. Les résultats de simulation montrent que les approches proposées offrent un bon compromis entre performance et complexité. D’un point de vue implémentation, la représentation en virgule fixe est généralement utilisée afin de réduire les coûts en termes de surface, de consommation d’énergie et de temps d’exécution. Nous présentons ainsi une représentation en virgule fixe du récepteur itératif proposé basé sur le décodeur LC K-Best. En outre, nous étudions l’impact de l’estimation de canal sur la performance du système. Finalement, le récepteur MIMOOFDM itératif est testé sur la plateforme matérielle WARP, validant le schéma proposé. / Recently, iterative processing has been widely considered to achieve near-capacity performance and reliable high data rate transmission, for future wireless communication systems. However, such an iterative processing poses significant challenges for efficient receiver design. In this thesis, iterative receiver combining multiple-input multiple-output (MIMO) detection with channel decoding is investigated for high data rate transmission. The convergence, the performance and the computational complexity of the iterative receiver for MIMO-OFDM system are considered. First, we review the most relevant hard-output and soft-output MIMO detection algorithms based on sphere decoding, K-Best decoding, and interference cancellation. Consequently, a low-complexity K-best (LCK- Best) based decoder is proposed in order to substantially reduce the computational complexity without significant performance degradation. We then analyze the convergence behaviors of combining these detection algorithms with various forward error correction codes, namely LTE turbo decoder and LDPC decoder with the help of Extrinsic Information Transfer (EXIT) charts. Based on this analysis, a new scheduling order of the required inner and outer iterations is suggested. The performance of the proposed receiver is evaluated in various LTE channel environments, and compared with other MIMO detection schemes. Secondly, the computational complexity of the iterative receiver with different channel coding techniques is evaluated and compared for different modulation orders and coding rates. Simulation results show that our proposed approaches achieve near optimal performance but more importantly it can substantially reduce the computational complexity of the system. From a practical point of view, fixed-point representation is usually used in order to reduce the hardware costs in terms of area, power consumption and execution time. Therefore, we present efficient fixed point arithmetic of the proposed iterative receiver based on LC-KBest decoder. Additionally, the impact of the channel estimation on the system performance is studied. The proposed iterative receiver is tested in a real-time environment using the MIMO WARP platform.

This thesis presents an investigation of the possibility of using the fixed-point arithmetic in the inertial navigation systems, which use the local level navigation frame mechanization equations. Two square root filtering methods, the Potter's square root Kalman filter and UD factorized Kalman filter, are compared with respect to the conventional Kalman filter and its Joseph's stabilized form. The effect of rounding errors to the Kalman filter optimality and the covariance matrix or its factors conditioning is evaluated for a various lengths of the fractional part of the fixed-point computational word. Main contribution of this research lies in an evaluation of the minimal fixed-point arithmetic word length for the Phi-angle error model with noise statistics which correspond to the tactical grade inertial measurements units.