Linear time-invariant (LTI) filters are widely used in digital signal processing (DSP). Such filters can be designed out of a frequency specification (amplify some frequency bands, attenuate others), and a wide body of techniques exist to transform such a specification into an actual implementation consisting of additions and multiplications. The linearity property (the L of LTI) is essential at all the steps of this design process. However, actual implementations in hardware or software cannot be linear, due to the rounding of intermediate results: rounding is necessary to keep the result of a multiplication on the same number of bits as its inputs. But rounding is not linear, for instance the function that rounds a real to the nearest integer is not linear. So implementations of LTI filters are actually not linear, and this loss of linearity destroys in principle most mathematical foundations on which they are built. The workaround found by the DSP community so far is quite simple: ignore the problem, and hope for the best. Most of the times it works, and indeed your mobile phone is full of such filters. When it doesn’t, strange (and sometimes catastrophic) things will happen, and the community has devised all sorts of tricks and patches to evade them.

This talk will first present a gentle (but incomplete) introduction to LTI filters, their design, and the issue of non-linearity. It will then introduce a simple formalization that reconciles LTI filters and their
implementations. An additional benefit of this unified view is that filter design and implementation becomes a well-formed single global optimisation problem. The talk will conclude with the latest developments towards solving this problem.

Bio:

Anastasia Volkova est maître de conférences à l’Université de Nantes et membre de l’équipe OGRE au LS2N. Avant de commencer à Nantes en 2019, elle a été chercheuse postdoctorale à Intel San Diego, au Max-Plank Institute à Saabrucken, et à l’Inria à Lyon. Dans sa recherche elle se focalise sur des problématiques de précision finie dans des applications numériques, notamment l’analyse d’erreurs, mais aussi sur le compromis entre la précision et la performance. Elle s’intéresse en particulier à la conception et à l’implémentation logicielle ou matérielle des filtres LTI avec garantie de qualité  numérique, et à l’optimisation des ressources matérielles, e.g. sur FPGA.

Florent de Dinechin est professeur à l’INSA-Lyon après un doctorat de l’Université of Rennes-1 en 1997, un post-doctorat à Imperial College à Londres, et un premier poste à l’École Normale Supérieure de Lyon. Il s’intéresse à l’arithmétique des ordinateurs dans ses aspects mathématiques, matériels et logiciels, et particulièrement aux fonctions élémentaires, à la virgule flottante, et à l’arithmétique pour les FPGA.