An iterated tabu search algorithm for the design of fir filters

Les systèmes modernes de télécommunication sans fils occupent une place majeure dans la société actuelle. Dans les dernières années, la complexité des outils qui en découlent n'a cessé d'augmenter car, en plus de prendre en charge les tâches basiques de communication vocale, ceux-ci doivent également supporter une quantité croissante de modules et d'applications parallèles (connexion internet, capture vidéo, guidage par satellite, etc.). En conséquence, l'évolution rapide subie par ces outils qui, dans la majorité des cas, sont alimentés par batteries, a singulièrement accru l'importance du rôle joué par la consommation énergétique, et a ainsi fait de l'efficacité énergétique et de l'informatique éco-responsable des caractéristiques essentielles dans les développements récents de la micro-éléctronique. Afin d'offrir une solution à ces problèmes énergétiques, une partie des recherches s'est focalisée sur la conception de filtres numériques efficaces. Les filtres numériques sont la pierre angulaire de tous les systèmes de traitement de signal numérique. Chaque filtre est implanté par un circuit intégré, qui, lui-même, est composé d'une liste d'éléments de base incluant des additionneurs, des multiplicateurs, des inverseurs, etc. La piste principale suivie par les chercheurs dans le but de réduire la quantité d'énergie consommée par les filtres numériques propose de remplacer les multiplicateurs dans les circuits par des éléments moins énergivores, tels que des additionneurs, des décaleurs et des inverseurs. L'objectif des méthodes introduites dans ce sens consiste généralement à remplacer les multiplicateurs tout en utilisant le moins d'additionneurs possible. En effet, en l'absence de multiplicateurs dans les circuits, les additionneurs deviennent l'élément le plus demandant en ressource énergétique. Dans les faits, la quantité d'additionneurs contenue dans un circuit sans multiplicateurs, aussi connue comme son coût en additionneurs, est communément utilisée afin d'estimer sa consommation énergétique. Nos travaux se concentrent sur la conception de filtres numériques sans multiplicateurs énergétiquement efficaces. Ils se décomposent en deux contributions majeures: un nouveau modèle de représentation efficace des circuits intégrés, et un algorithme innovateur destiné à la conception de filtres numériques efficaces. Dans un premier temps, notre modélisation des circuits sous la forme de graphes pondérés a l'avantage d'offrir une représentation concise des circuits intégrés, tout en annulant la symétrie présente dans les modèles de représentation actuels.Dans un second temps, notre métaheuristique, qui combine à la fois une recherche tabou et une recherche tabou itérée, offre un contrôle direct du niveau d'énergie consommée par le circuit qu'elle construit, en fixant la quantité d'additionneurs qu'il contient avant le démarrage du processus de conception. En outre, contrairement aux méthodes existantes, notre approche ne se réfère à aucune architecture spécifique afin de concevoir un circuit. Ce degré de liberté permet à notre méthode d'atteindre une optimisation plus globale de la structure du circuit en comparaison des autres méthodes et, ainsi, de posséder un contrôle plus précis de sa consommation énergétique. L'algorithme proposé est testé sur un jeu de données contenant plus de 700 filtres de complexité variée. Les résultats obtenus démontrent les performances élevées de notre approche car, en se basant sur le coût en additionneurs, dans plus de 99% des cas, notre méthode conçoit des filtres numériques avec un niveau de consommation énergétique total équivalent au niveau induit uniquement par l'architecture à laquelle les méthodes actuelles se réfèrent. En parallèle, notre méthode fournit également un meilleur contrôle de la longueur de mot interne dans les circuits, qui représente un autre aspect crucial de leur efficacité énergétique. La comparaison avec l'algorithme Heuristic cumulative benefit (Hcub) qui, à ce jour, est la méthode la plus performante montre que les filtres construits par notre algorithme utilisent 55% moins d'additionneurs que Hcub, tout en réduisant la taille de ces additionneurs de 33%. Ces améliorations sont obtenues au simple coût d'une augmentation de 17% du nombre de délais dans les circuits. Cependant, la consommation énergétique d'un délai étant de l'ordre de 20% de celle d'un additionneur, si l'on considère le nombre et la taille des additionneurs ainsi que la quantité de délais inclus dans nos circuits afin d'estimer leur consommation énergétique, on peut s'attendre à une économie globale de l'ordre de 65% en comparaison de la meilleure méthode actuelle.