Application de la théorie des nombres à la conception optimale et à l'implémentation de très faible complexité des filtres numériques

The main objective of our study is to develop fast algorithms for an optimal design and an implementation with low complexity of digital filters. The optimization criterion is the mean squared error at the filter output. Thus, we have studied and developed new algorithms for synthesis of finite impulse response (FIR) filters related to the two techniques of block filtering, overlap-save (OLS) and overlap-add (OLA). These two filtering techniques consist in processing the signal by blocks and use the fast Fourier transform (FFT) to reduce the complexity of the convolution calculation. Our algorithms, based on the matrix model development of the OLA and OLS structures, use the linear algebra properties, especially those of circulant matrices. To further reduce the complexity and the distortion, we have looked further into the mathematical foundations of the Fermat Number Transform (FNT). This transform is a particular case of the Number Theoretic Transforms (NTT) defined in the Galois field. Compared to the FFT, the FNT allows a calculation without rounding error and a large reduction of the number of multiplications necessary to carry out the convolution product. To highlight this transform, we have proposed and studied a new design of OLS and OLA filtering using the FNT. We have developed a low complexity algorithm for the optimal synthesis of filters using the properties of circulant matrices that we have developed in the Galois field. The simulation results of the block filtering with fixed-point implementation have shown that the use of the FNT instead of the FFT reduces the complexity and the filtering errors, as well as the cost of optimal filter synthesis.L'objectif principal de notre étude est de développer des algorithmes rapides pour une conception optimale et une implantation de très faible complexité des filtres numériques. Le critère d'optimisation choisi est celui de la minimisation de l'erreur quadratique moyenne. Ainsi, nous avons étudié et développé de nouveaux algorithmes de synthèse des filtres à réponse impulsionnelle finie (RIF) associés aux deux techniques de filtrage par blocs, overlap-save (OLS) et overlap-add (OLA). Ces deux techniques de filtrage RIF consistent à traiter le signal par blocs au moyen de la transformée de Fourier rapide (TFR) et permettent ainsi de réduire la complexité arithmétique des calculs de convolution. Les algorithmes que nous avons proposés sont basés sur le développement du modèle matriciel des structures OLS et OLA et sur l'utilisation des propriétés de l'algèbre linéaire, en particulier celles des matrices circulantes. Pour réduire davantage la complexité et la distorsion de filtrage, nous avons approfondi les bases mathématiques de la transformée en nombres de Fermat (FNT : Fermat Number Transform) qui est amenée à trouver des applications de plus en plus diverses en traitement du signal. Cette transformée, définie sur un corps de Galois d'ordre égal à un nombre de Fermat, est un cas particulier des transformées en nombres entiers (NTT : Number Theoretic Transform). Comparé à la TFR, la FNT permet un calcul sans erreur d'arrondi ainsi qu'une large réduction du nombre de multiplications nécessaires à la réalisation du produit de convolution. Pour mettre en évidence cette transformée, nous avons proposé et étudié une nouvelle conception des filtres blocs OLS et OLA mettant en oeuvre la FNT. Nous avons ensuite développé un algorithme de très faible complexité pour la synthèse du filtre optimal en utilisant les propriétés des matrices circulantes que nous avons développées dans le corps de Galois. Les résultats de l'implantation en virgule fixe du filtrage par blocs ont montré que l'utilisation de la FNT à la place de la TFR permettra de réduire la complexité et les erreurs de filtrage ainsi que le coût de synthèse du filtre optimal