Voir la source de Convolution circulaire

{{Homon|convolution}}
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 {{Lien|trad=discrete-time Fourier transform|fr=transformée de Fourier à temps discret}} (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 [[:en:DTFT#Definition|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 ==
La ''convolution périodique'' de deux fonctions T-périodiques, <math>h_{_T}(t)</math> et <math>x_{_T}(t)</math> peut être définie comme suit :
:<math>\int_{t_o}^{t_o+T} h_{_T}(\tau)\cdot x_{_T}(t - \tau)\,d\tau,</math> &nbsp; <ref name=Jeruchim/>{{,}}<ref name=Udayashankara/>

où ''t''<sub>o</sub> est un paramètre arbitraire. Une autre définition, en termes de notation de convolution linéaire ou apériodique normale, consiste à exprimer <math>h_{_T}(t)</math> et <math>x_{_T}(t)</math> comme des {{lien|trad=Periodic summation|fr=sommation périodique|texte=sommations périodiques}} de composantes apériodiques <math>h</math> et <math>x</math>, c'est-à-dire :

:<math>h_{_T}(t) \ \triangleq \ \sum_{k=-\infty}^\infty h(t - kT) = \sum_{k=-\infty}^\infty h(t + kT).</math>

Alors ''':'''
{{NumBlk|:|<math>
\int_{t_o}^{t_o+T} h_{_T}(\tau)\cdot x_{_T}(t - \tau)\,d\tau = \int_{-\infty}^\infty h(\tau)\cdot x_{_T}(t - \tau)\,d\tau\ \triangleq\ (h *x_{_T})(t) = (x * h_{_T})(t).</math>|{{EquationRef|Eq.1}}}}

{{Démonstration|titre=Démonstration de l'équation '''Eq.1'''|contenu=
<math display="block">\begin{align}
\int_{-\infty}^\infty h(\tau)\cdot x_{_T}(t - \tau)\,d\tau
&=\sum_{k=-\infty}^\infty \left[\int_{t_o+kT}^{t_o+(k+1)T} h(\tau)\cdot x_{_T}(t - \tau)\ d\tau\right] \quad t_0 \text{ est un paramètre arbitraire}\\
&=\sum_{k=-\infty}^\infty \left[\int_{t_o}^{t_o+T} h(u + kT)\cdot \underbrace{x_{_T}(t-u-kT)}_{x_{_T}(t-u), \text{ par périodicité}}\ du\right] \quad \text{substituant } u\triangleq \tau-kT\\
&=\int_{t_o}^{t_o+T} \left[\sum_{k=-\infty}^\infty h(u + kT)\cdot x_{_T}(t - u)\right]\ du\\
&=\int_{t_o}^{t_o+T} \underbrace{\left[\sum_{k=-\infty}^\infty h(u + kT)\right]}_{\triangleq \ h_{_T}(u)}\cdot x_{_T}(t - u)\ du\\
&=\int_{t_o}^{t_o+T} h_{_T}(\tau)\cdot x_{_T}(t - \tau)\ d\tau \quad \text{substituant } \tau \triangleq u
\end{align}</math>}}

Les deux formes peuvent être appelées ''convolution périodique''{{sfn|McGillem|Cooper|1984|p=172 (4-6)
}}. Le terme ''convolution circulaire''<ref name=Udayashankara/>{{,}}<ref name=Priemer/> provient du cas spécial important qui consiste à contraindre les parties non nulles de <math>h</math> et de <math>x</math> à l'intervalle <math>[0,T].</math> La sommation périodique devient alors une ''extension périodique''{{sfn|McGillem|Cooper|1984|p=183 (4-51)}}, qui peut aussi être exprimée comme une ''fonction circulaire'':''
:<math>x_{_T}(t) = x(t_{\mathrm{mod}\ T}), \quad t\in\mathbb{R}\,</math> ([[Nombre#Nombres_réels|tout nombre réel]]){{sfn|Oppenheim|Schafer|Buck|1999|p=559 (8.59)}}

Et les limites d'intégration se réduisent à la longueur de la fonction <math>h</math>''':'''

:<math>(h *x_{_T})(t) = \int_{0}^{T} h(\tau)\cdot x((t - \tau)_{\mathrm{mod}\ T})\ d\tau.</math>{{efn|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.}}{{,}}{{sfn|McGillem|Cooper|1984|p=171 (4-22), présenté sous forme numérique
}}.

== Séquences discrètes ==
De même, pour des séquences discrètes, et un paramètre '''N''', on peut écrire une '''convolution circulaire''' de fonctions apériodiques <math>h</math> et <math>x</math> comme''':'''.

:<math>
(h * x_{_N})[n] \ \triangleq \ \sum_{m=-\infty}^\infty  h[m] \cdot \underbrace{x_{_N}[n-m]}_{\sum_{k=-\infty}^\infty x[n -m -kN]}
</math>

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 ==
[[Image:Circular convolution example.svg|thumb|400px|La convolution circulaire peut être accélérée par l'algorithme de FFT, elle est donc souvent utilisée avec un filtre RIF pour calculer efficacement les convolutions linéaires. Ces graphiques illustrent comment cela est possible. Notez qu'une taille de FFT plus grande (N) éviterait le chevauchement qui fait que le graphique 6 ne correspond pas tout à fait à l'ensemble du graphique 3.]]
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''',&nbsp; 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&nbsp;''N''&nbsp;=&nbsp;1024.

=== Blocs d'entrée superposés ===

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 ''{{Lien|trad=Overlap–save method|fr=méthode de chevauchement sauvage}}''<ref name=Rabiner/>, 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 ===

Cette méthode est connue sous le nom de ''{{lien|trad=Overlap–add method|fr=méthode d'addition par chevauchement}}''<ref name=Rabiner/>. 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 ==
*[[Produit de convolution|Théorème de convolution]]
*[[Matrice circulante]]
*[[Transformée de Hilbert#Transformation de Hilbert discrète|Transformation de Hilbert discrète]]

== Bibliographie ==
*{{ouvrage|langue=en |auteur1=Alan V. Oppenheim|auteur2=Alan S. Willsky|auteur3=Syed Hamid Nawab |titre=Signals and Systems |éditeur=Pearson Education |année=1998 |isbn=0-13-814757-4}}.

== Notes et références ==
=== Notes ===
{{notes}}

=== Références ===
{{reflist|refs=
<ref name=Rabiner>
{{Ouvrage 
 |langue=en
 |auteur1=Lawrence R. Rabiner
 |auteur2=Bernard Gold
 |titre=Theory and application of digital signal processing
 |passage=63–67
 |année=1975
 |éditeur=Prentice-Hall
 |lieu=Englewood Cliffs,N.J.
 |isbn=0-13-914101-4
 |accès url=inscription
 |url=https://archive.org/details/theoryapplicatio00rabi/page/63
}}.</ref>

<ref name=Priemer>
{{Ouvrage 
 |langue=en
 |nom=Priemer
 |prénom=Roland 
 |titre=Introductory Signal Processing
 |passage=286–289
 |éditeur=World Scientific Pub Co Inc.
 |collection=Advanced Series in Electrical and Computer Engineering
 |volume=6
 |date=July 1991
 |lieu=Teaneck,N.J.
 |url=https://books.google.com/books?id=QBT7nP7zTLgC&q=Priemer,+Roland
 |isbn=9971-50-919-9
}}. </ref>

<ref name=Jeruchim>
{{Ouvrage 
 |langue=en
 |nom1=Jeruchim
 |prénom1=Michel C.
 |nom2=Balaban
 |prénom2=Philip
 |nom3=Shanmugan
 |prénom3=K. Sam
 |titre=Simulation of Communication Systems: Modeling, Methodology and Techniques
 |passage=73–74
 |éditeur=Kluwer Academic Publishers
 |numéro édition=2
 |date=Octobre 2000
 |lieu=New York
 |isbn=0-30-646267-2
}}. </ref>

<ref name=Udayashankara>
{{Ouvrage 
 |langue=en
 |nom=Udayashankara
 |prénom=V.
 |titre=Real Time Digital Signal Processing
 |passage=189
 |éditeur=Prentice-Hall
 |date=Juin 2010
 |lieu=India
 |isbn=978-8-12-034049-7
}}. </ref>
}}
{{refbegin}}
#<li value="5">{{ouvrage 
 |langue=en
<!-- |ref=Oppenheim -->
 |nom1=Oppenheim
 |prénom1=Alan V.
 |lien auteur=Alan V. Oppenheim
 |nom2=Schafer
 |prénom2=Ronald W.
 |lien auteur2=Ronald W. Schafer
 |nom3=Buck
 |prénom3=John R.
 |titre=Discrete-time signal processing
 |passage=[https://archive.org/details/discretetimesign00alan/page/548 548], 571
 |année=1999
 |éditeur=Prentice Hall
 |lieu=Upper Saddle River,N.J.
 |isbn=0-13-754920-2
 | numéro édition=2
 |accès url=inscription
 |url=https://archive.org/details/discretetimesign00alan
}}
#{{ouvrage 
 |langue=en
<!-- |ref=McGillem -->
 |nom1=McGillem
 |prénom1=Clare D.
 |nom2=Cooper
 |prénom2=George R.
 |titre=Continuous and Discrete Signal and System Analysis
 |éditeur=Holt, Rinehart and Winston
 |numéro édition=2
 |date=1984
 |isbn=0-03-061703-0
}}

== Liens externes ==
{{refend}}
{{liens}}

{{Portail|physique}}

[[Catégorie:Analyse fonctionnelle]]
[[Catégorie:Traitement d'image]]
[[Catégorie:Algèbre générale]]
[[Catégorie:Théorie de l'intégration]]
[[Catégorie:Opération]]