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

La convolution périodique de deux fonctions T-périodiques, $h_{_{T}}(t)$ et $x_{_{T}}(t)$ peut être définie comme suit :

$\int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau ,$  

où t_o est un paramètre arbitraire. Une autre définition, en termes de notation de convolution linéaire ou apériodique normale, consiste à exprimer $h_{_{T}}(t)$ et $x_{_{T}}(t)$ comme des sommations périodiques (en) de composantes apériodiques $h$ et $x$, c'est-à-dire :

$h_{_{T}}(t)\ \triangleq \ \sum _{k=-\infty }^{\infty }h(t-kT)=\sum _{k=-\infty }^{\infty }h(t+kT).$

Alors :

$\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).$

(Eq.1)

Démonstration de l'équation Eq.1

$${\begin{aligned}\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{aligned}}$$

Les deux formes peuvent être appelées convolution périodique. Le terme convolution circulaire provient du cas spécial important qui consiste à contraindre les parties non nulles de $h$ et de $x$ à l'intervalle $[0,T].$ La sommation périodique devient alors une extension périodique, qui peut aussi être exprimée comme une fonction circulaire:

$x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,$ (tout nombre réel)

Et les limites d'intégration se réduisent à la longueur de la fonction $h$:

$(h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .$.

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 $h$ et $x$ comme:.

$(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]}$

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

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,  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

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), 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 méthode d'addition par chevauchement (en). 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

• Théorème de convolution
• Matrice circulante
• Transformation de Hilbert discrète

Bibliographie

• (en) Alan V. Oppenheim, Alan S. Willsky et Syed Hamid Nawab, Signals and Systems, Pearson Education, 1998 (ISBN 0-13-814757-4).