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.