Filtrage RIF rapide : algorithmes et architectures

Z.J. Mou (1)

1 CRPE - Centre de recherches en physique de l'environnement terrestre et planétaire

(FRE) Le filtre à réponse impulsionnelle finie (RIF) joue un rôle des plus importants dans le traitement numérique du signal et représente souvent la principale charge de calcul dans une application soit en logiciel soit en matériel. Cette thèse est divisé en deux parties. La première partie de la thèse traite le problème de la réduction de la complexité arithmétique du filtre RIF. Nous fournissons un ensemble d'algorithmes permettant de 'casser' le filtre habituel en plusieurs sous-filtres échantillonnés, de telle manière que le nombre d'opérations à effectuer se trouve réduit. La deuxième partie étudie non seulement l'implantation de ces sous-filtres mais plus généralement l'architecture des filtres RIF en vue de leur intégration VLSI. Nous présentons une approche unifiée pour tous les algorithmes rapides de filtrage RIF. Le théorème du reste chinois (TRC) constitue la base de l'approche. Tout d'abord nous formulons le filtrage RIF comme un produit polynomial. Ensuite l'application du TRC se fait en trois étapes: 1) interpolation; 2) filtrage; 3) reconstruction. L'approche se termine par le recouvrement. Sous une présentation pseudocyclique, il est facile de démontrer quelques propriétés utiles des algorithmes. Les algorithmes classiques sont examinés dans ce cadre. Mais l'unification de ces algorithmes n'est pas notre seul objectif. Nous présentons aussi des nouvelles possibilités apportées par cette approche, qui permet d'établir en particulier tous les algorithmes intermédiaires entre traitements temporels et fréquentiels. Nous traitons les algorithmes de petite longueur en détail. Ces algorithmes permettent de réduire la complexité arithmétique en gardant comme brique de base des filtres RIF d'ordre plus petit. Ils sont donc ouverts à diverses implantations. Nous étudions ensuite l'aspect arithmétique du multiplieur-accumulateur d'une part, et de nouvelles architectures d'autre part. Une conception compacte et régulière de l'arbre de Wallace est proposée pour surmonter les difficultés qui empêchaient l'application de cette structure par ailleurs très efficace au niveau du temps de calcul. Nous présentons quelques nouveaux accumulateurs rapides. L'architecture du filtre RIF par l'arithmétique distribuée est analysée en détail. Nous présentons de nouvelles structures ayant les caractéristiques suivantes: sans ROM; avec l'additionneur carry-save comme brique de base; avec accumulation rapide. En particulier, un nouveau codage est proposé pour profiter de la symétrie des coefficients afin de réduire la quantité de matériel et d'accélérer le calcul. (ENG)The finite impulse response (FIR) filter plays one of the most important rôles in digital signal processing. It often represents the major computational load in a System either in software or in hardware. The dissertation is divided in two parts. The first part deals with the problem of reducing the arithmetic complexity in FIR filtering. We présent a class of algorithms allowing to "eut" a usual filter into several subfilters in such a way that the number of opérations is reduced. The second part studies not only the implementation of thèse subfilters but more generally the architecture of FIR filters for Very Large Scale Intégration (VLSI). We présent a unified approach to ail the fast FIR filtering algorithms. The Chinese Remainder Theorem (CRT) constitutes the basis of the approach. First of ail, we formulate the FIR filtering équation as a polynomial product. Then the application of CRT is made in three steps: 1) interpolation; 2) fitering; 3) reconstruction. The approach finishes by overlapping. Under a pseudocyclic présentation, some interesting properties of algorithms are demonstrated. The classical FIR filtering algorithms are examined in the context of this approach. But the unification of ail the FIR filtering algorithms is not our only objective. We présent also several new possibilities promised by the approach, which in particular allows to establish ail the intermediate algorithms between processings in time and in frequency domain. We explain the short-length FIR filtering algorithms in détail. Thèse algorithms allow to reduce the arithmetic complexity while maintaining moderate-length FIR filters as building blocks. Hence they are open to various implementations. Our study is then concerned with the arithmetic aspect in one hand and new architectures in the other hand for VLSI implementation of FIR filters. Some improved structures are presented for Wallace-tree and fast accumulators. The distributed arithmeic implementation of FIR filters is also analyzed in more détail. We propose new structures having the following characteristics: without ROM; with carry-save adder as building block; with fast accumulators. In particular a new encoding technique is suggested for implementing symmetric FIR filters.

Domaines: Sciences de la Terre

Z.J. Mou. Filtrage RIF rapide : algorithmes et architectures. [Rapport de recherche] Note technique - CRPE n° 187, Centre de recherches en physique de l'environnement terrestre et planétaire (CRPE). 1990, 165 p., figures, caractères chinois. ⟨hal-02191379⟩