Un filtre numérique est un composant électronique permettant de réaliser une transformation d'un signal (audio, vidéo, réseau) en général de facon à en améliorer la qualité, ou en supprimer des composantes inutiles ; les exemples les plus classiques sont les filtres passe-bas, passe-haut, passe-bande, etc.
L'action du filtre dans le domaine fréquentiel est décrite mathématiquement par la donnée d'un polynôme (cas des filtres à reponse impulsionnelle finie) ou d'une fraction rationnelle (cas des filtres à reponse impulsionnelle infinie), sa fonction de transfert, qui résume ses propriétés. Aussi, la fonction de transfert d'un filtre passe-bas doit se rapprocher d'une fonction égale à 1 pour les basses fréquences, et nulle pour les hautes fréquences.
Diverses techniques d'approximation existent pour calculer des polynômes ou des fractions rationnelles vérifiant des contraintes en fréquence. Elles ont pour point commun de produire des polynômes ou des fractions rationnelles à coefficients réels, qui sont donc difficiles à implanter dans un composant, qui ne peut manipuler que des nombres à précision finie. Il faut donc réaliser une phase d'arrondi. L'expérience montre que les choix d'arrondi sont stratégiques, en ce sens qu'un bon choix peut permettre de diminuer significativement la difficulté d'implémentation du filtre à qualité égale.
L'objet du stage est d'étudier les stratégies d'arrondi pour ces fonctions de transfert. Il s'inscrit dans le prolongement des travaux réalisés pour obtenir une évaluation efficace des fonctions classiques (exp, cos, ln, ...) en machine, cf. [2,3] et surtout le chapitre 2 de [4]. Le stage débutera par l'étude du cas polynomial, utilisant des techniques de programmation linéaire et de réduction des réseaux euclidiens. Dans un second temps, la/le stagiaire prendra en compte les spécificités du cas rationnel ainsi que de l'application visée (difficultés liées à la variation des pôles en fonction du choix de l'arrondi) pour étudier des stratégies d'arrondi permettant d'améliorer l'existant. Le travail théorique et algorithmique effectué aura vocation à être implanté en logiciel.
Ce stage se situe à l'interface entre mathématiques et informatique. Les sujets scientifiques qui seront abordés relèveront principalement de la théorie algorithmique des nombres, tels que l'algorithme LLL [5,6,7,12] de réduction des réseaux, et de la programmation linéaire [8,11], voire de l'interaction entre ces deux domaines. Il comportera aussi des composantes de traitement du signal [1,9,10] bien sûr, d'analyse de Fourier, d'analyse complexe et d'implantation fine.
Le cadre de travail est celui de l'équipe AriC du LIP, qui occupe une position de pointe dans le domaine de l'arithmétique des ordinateurs. Elle se préoccupe de manière générale de l'amelioration de la qualité des calculs en machine et rassemble pour cela un ensemble de chercheurs balayant un spectre qui va de la théorie des nombres à l'implantation optimisée de puces FPGA.
Ce stage pourra faire l'objet d'une gratification, qui dépendra du profil de l'étudiant.
Ce sujet est susceptible de se poursuivre en une thèse.
Bibliographie
[1] M. Bellanger. Traitement numérique du signal : Théorie et pratique. Dunod, 8e édition (7 septembre 2006), collection Sciences Sup.
[2] N. Brisebarre and G. Hanrot. Floating-Point L2-Approximations, 18th IEEE Symposium on Computer Arithmetic (ARITH-18), Montpellier (France), pages 177-184, June 2007.
[3] N. Brisebarre, J.-M. Muller and A. Tisserand. Computing Machine-efficient Polynomial Approximations. ACM Transactions on Mathematical Software, Vol. 32, n. 2, Jun. 2006, 236-256.
[4] S. Chevillard. Évaluation efficace de fonctions numériques - Outils et exemples. Thèse de doctorat. École normale supérieure de Lyon - Université de Lyon, 2009.
[5] H. Cohen. A Course in computational algebraic number theory. GTM 138, Springer-Verlag.
[6] J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge, UK, 2nd edition.
[7] A.K. Lenstra, H.W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261:515--534, 1982.
[8] M. Minoux. Programmation mathématique - théorie et algorithmes, Tec & Doc Lavoisier; Édition : 2e édition (14 décembre 2007).
[9] A. V. Oppenheim and R. W. Schafer. Digital Signal Processing. Prentice Hall.
[10] A. V. Oppenheim, R. W. Schafer and J. R. Buck. Discrete-Time Signal Processing. Prentice Hall.
[11] A. Schrijver. Theory of Linear and Integer Programming. Wiley and sons, April 1998 .
[12] D. Stehlé. Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l'arrondi de fonctions mathématiques. Thèse de l'Université Henri Poincaré, Nancy 1, 2 décembre 2005.