Convolution circulaire
La convolution circulaire, également connue sous le nom de convolution cyclique, est un cas particulier de la convolution périodique, qui est le produit de convolution de deux fonctions périodiques ayant la même période. La convolution périodique apparaît, par exemple, dans le contexte de la transformée de Fourier à temps discret (en) (DTFT). En particulier, la DTFT du produit de deux séquences discrètes est la convolution périodique des DTFT des séquences individuelles. Et chaque DTFT est une sommation périodique d'une fonction de transformée de Fourier continue (voir paragraphe DTFT#Définition). Bien que les DTFT soient généralement des fonctions continues de la fréquence, les concepts de convolution périodique et circulaire sont également directement applicables aux séquences discrètes de données. Dans ce contexte, la convolution circulaire joue un rôle important en maximisant l'efficacité d'un certain type d'opération de filtrage courant.
Définitions
[modifier | modifier le code]La convolution périodique de deux fonctions T-périodiques, et peut être définie comme suit :
où to est un paramètre arbitraire. Une autre définition, en termes de notation de convolution linéaire ou apériodique normale, consiste à exprimer et comme des sommations périodiques (en) de composantes apériodiques et , c'est-à-dire :
Alors :
-
(Eq.1)
Les deux formes peuvent être appelées convolution périodique[3]. Le terme convolution circulaire[2],[4] provient du cas spécial important qui consiste à contraindre les parties non nulles de et de à l'intervalle La sommation périodique devient alors une extension périodique[5], qui peut aussi être exprimée comme une fonction circulaire:
Et les limites d'intégration se réduisent à la longueur de la fonction :
Séquences discrètes
[modifier | modifier le code]De même, pour des séquences discrètes, et un paramètre N, on peut écrire une convolution circulaire de fonctions apériodiques et comme:.
Cette fonction est N-périodique. Elle a au plus N valeurs uniques. Dans le cas particulier où les étendues non nulles de x et de h sont ≤ N, elle est réductible à un produit matriciel où le noyau de la transformation intégrale est une matrice circulante.
Exemple
[modifier | modifier le code]![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0a/Circular_convolution_example.svg/400px-Circular_convolution_example.svg.png)
Un cas d'un grand intérêt pratique est illustré dans la figure. La durée de la séquence x est N (ou moins), et la durée de la séquence h est nettement inférieure. De nombreuses valeurs de la convolution circulaire sont alors identiques aux valeurs de x∗h, ce qui est en fait le résultat souhaité lorsque la séquence h est un filtre à réponse impulsionnelle finie (RIF). En outre, la convolution circulaire est très efficace à calculer, en utilisant un algorithme de transformée de Fourier rapide (FFT) et le théorème de convolution circulaire et de corrélation croisée.
Il existe également des méthodes pour traiter une séquence x qui est plus longue qu'une valeur pratique de N. La séquence est divisée en segments (blocs) et traitée par morceaux. Les segments filtrés sont ensuite soigneusement reconstitués. Les effets de bord sont éliminés en "chevauchant" les blocs d'entrée ou les blocs de sortie. Pour mieux expliquer et comparer les méthodes, nous les examinons toutes deux dans le contexte d'une séquence h de longueur 201 et d'une taille FFT de N = 1024.
Blocs d'entrée superposés
[modifier | modifier le code]Cette méthode utilise une taille de bloc égale à la taille de la FFT (1024). Nous la décrivons d'abord en termes de convolution normale ou "linéaire". Lorsqu'une convolution normale est effectuée sur chaque bloc, il y a des transitoires de démarrage et de décroissance sur les bords du bloc, en raison de la "latence" du filtre (200 échantillons). Seules 824 des sorties de convolution ne sont pas affectées par les effets de bord. Les autres sont rejetées ou ne sont tout simplement pas calculées. Cela entraînerait des lacunes dans la sortie si les blocs d'entrée étaient contigus. Les lacunes sont évitées en chevauchant les blocs d'entrée de 200 échantillons. En quelque sorte, 200 éléments de chaque bloc d'entrée sont "sauvegardés" et reportés sur le bloc suivant. Cette méthode est appelée méthode de chevauchement sauvage (en)[8], bien que la méthode que nous décrivons ensuite nécessite une "sauvegarde" similaire avec les échantillons de sortie.
Lorsqu'une FFT est utilisée pour calculer les 824 échantillons DFT non affectés, nous n'avons pas la possibilité de ne pas calculer les échantillons affectés, mais les effets des bords avant et arrière sont superposés et ajoutés en raison de la convolution circulaire. Par conséquent, la sortie de la FFT inverse (IFFT) à 1024 points ne contient que 200 échantillons d'effets de bord (qui sont éliminés) et les 824 échantillons non affectés (qui sont conservés). Pour illustrer cela, la quatrième image de la figure de droite représente un bloc qui a été périodiquement (ou "circulairement") étendu, et la cinquième image représente les composantes individuelles d'une convolution linéaire effectuée sur l'ensemble de la séquence. Les effets de bord se situent là où les contributions des blocs étendus chevauchent les contributions du bloc d'origine. La dernière image est la sortie composite, et la section colorée en vert représente la partie non affectée.
Chevauchement des blocs de sortie
[modifier | modifier le code]Cette méthode est connue sous le nom de méthode d'addition par chevauchement (en)[8]. Dans notre exemple, elle utilise des blocs d'entrée contigus de taille 824 et remplit chacun d'eux de 200 échantillons à valeur nulle. Ensuite, il superpose et ajoute les blocs de sortie de 1024 éléments. Rien n'est rejeté, mais 200 valeurs de chaque bloc de sortie doivent être "sauvegardées" pour l'addition avec le bloc suivant. Les deux méthodes n'avancent que de 824 échantillons par IFFT de 1024 points, mais la méthode "overlap-save" évite la mise à zéro initiale et l'addition finale.
Voir aussi
[modifier | modifier le code]Bibliographie
[modifier | modifier le code]- (en) Alan V. Oppenheim, Alan S. Willsky et Syed Hamid Nawab, Signals and Systems, Pearson Education, (ISBN 0-13-814757-4).
Notes et références
[modifier | modifier le code]Notes
[modifier | modifier le code]- Le tableau suivant présente les résultats de l'analyse de l'évolution de l'indice de masse corporelle et de l'indice de masse corporelle dans le cadre de l'analyse de l'évolution de l'indice de masse corporelle.
Références
[modifier | modifier le code]- (en) Michel C. Jeruchim, Philip Balaban et K. Sam Shanmugan, Simulation of Communication Systems: Modeling, Methodology and Techniques, New York, Kluwer Academic Publishers, , 2e éd. (ISBN 0-30-646267-2), p. 73–74.
- (en) V. Udayashankara, Real Time Digital Signal Processing, India, Prentice-Hall, (ISBN 978-8-12-034049-7), p. 189.
- McGillem et Cooper 1984, p. 172 (4-6).
- (en) Roland Priemer, Introductory Signal Processing, vol. 6, Teaneck,N.J., World Scientific Pub Co Inc., coll. « Advanced Series in Electrical and Computer Engineering », (ISBN 9971-50-919-9, lire en ligne), p. 286–289.
- McGillem et Cooper 1984, p. 183 (4-51).
- Oppenheim, Schafer et Buck 1999, p. 559 (8.59).
- McGillem et Cooper 1984, p. 171 (4-22), présenté sous forme numérique.
-
(en) Lawrence R. Rabiner et Bernard Gold, Theory and application of digital signal processing, Englewood Cliffs,N.J., Prentice-Hall, (ISBN 0-13-914101-4, lire en ligne
), p. 63–67.
- (en) Alan V. Oppenheim, Ronald W. Schafer et John R. Buck, Discrete-time signal processing, Upper Saddle River,N.J., Prentice Hall, , 2e éd. (ISBN 0-13-754920-2, lire en ligne
), 548, 571
- (en) Clare D. McGillem et George R. Cooper, Continuous and Discrete Signal and System Analysis, Holt, Rinehart and Winston, , 2e éd. (ISBN 0-03-061703-0)
Liens externes
[modifier | modifier le code]