DSP - Convolution circulaire DFT

Prenons deux séquences de durée finie x 1 (n) et x 2 (n), de longueur entière égale à N. Leurs DFT sont respectivement X 1 (K) et X 2 (K), ce qui est montré ci-dessous -

$$ X_1 (K) = \ sum_ {n = 0} ^ {N-1} x_1 (n) e ^ {\ frac {j2 \ Pi kn} {N}} \ quad k = 0,1,2 .. .N-1 $$ $$ X_2 (K) = \ sum_ {n = 0} ^ {N-1} x_2 (n) e ^ {\ frac {j2 \ Pi kn} {N}} \ quad k = 0 , 1,2 ... N-1 $$

Maintenant, nous allons essayer de trouver la DFT d'une autre séquence x 3 (n), qui est donnée par X 3 (K)

$ X_3 (K) = X_1 (K) \ fois X_2 (K) $

En prenant l'IDFT de ce qui précède, nous obtenons

$ x_3 (n) = \ frac {1} {N} \ displaystyle \ sum \ limits_ {n = 0} ^ {N-1} X_3 (K) e ^ {\ frac {j2 \ Pi kn} {N}} $

Après avoir résolu l'équation ci-dessus, enfin, nous obtenons

$ x_3 (n) = \ Displaystyle \ sum \ limits_ {m = 0} ^ {N-1} x_1 (m) x_2 [((nm)) _ N] \ quad m = 0,1,2 ... N- 1 $

Points de comparaison Convolution linéaire Convolution circulaire
Déplacement Déplacement linéaire Déplacement circulaire
Échantillons dans le résultat de la convolution $ N_1 + N_2−1 $ $ Max (N_1, N_2) $
Trouver la réponse d'un filtre Possible Possible avec zéro rembourrage

Méthodes de convolution circulaire

En règle générale, il existe deux méthodes adoptées pour effectuer une convolution circulaire et elles sont -

  • Méthode du cercle concentrique,
  • Méthode de multiplication matricielle.

Méthode du cercle concentrique

Soit $ x_1 (n) $ et $ x_2 (n) $ deux séquences données. Les étapes suivies pour la convolution circulaire de $ x_1 (n) $ et $ x_2 (n) $ sont

  • Prenez deux cercles concentriques. Tracez N échantillons de $ x_1 (n) $ sur la circonférence du cercle extérieur (en maintenant les points successifs à égale distance) dans le sens anti-horaire.

  • Pour tracer $ x_2 (n) $, tracez N échantillons de $ x_2 (n) $ dans le sens des aiguilles d'une montre sur le cercle intérieur, en commençant l'échantillon placé au même point que le 0 ème échantillon de $ x_1 (n) $

  • Multipliez les échantillons correspondants sur les deux cercles et ajoutez-les pour obtenir la sortie.

  • Faites pivoter le cercle intérieur dans le sens inverse des aiguilles d'une montre avec un échantillon à la fois.

Méthode de multiplication matricielle

La méthode matricielle représente les deux séquences données $ x_1 (n) $ et $ x_2 (n) $ sous forme matricielle.

  • L'une des séquences données est répétée par décalage circulaire d'un échantillon à la fois pour former une matrice NXN.

  • L'autre séquence est représentée sous forme de matrice de colonnes.

  • La multiplication de deux matrices donne le résultat d'une convolution circulaire.