DSP - DFT Circular Convolution
Nehmen wir zwei Sequenzen endlicher Dauer x 1 (n) und x 2 (n) mit einer ganzzahligen Länge als N. Ihre DFTs sind X 1 (K) bzw. X 2 (K), was unten gezeigt wird -
$$ 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 $$Nun werden wir versuchen, die DFT einer anderen Sequenz x 3 (n) zu finden, die als X 3 (K) angegeben ist.
$ X_3 (K) = X_1 (K) \ mal X_2 (K) $
Wenn wir die IDFT der oben genannten nehmen, erhalten wir
$ x_3 (n) = \ frac {1} {N} \ Anzeigestil \ Summe \ Grenzen_ {n = 0} ^ {N-1} X_3 (K) e ^ {\ frac {j2 \ Pi kn} {N}} $
Nachdem wir die obige Gleichung gelöst haben, erhalten wir schließlich
$ x_3 (n) = \ Anzeigestil \ Summe \ Grenzen_ {m = 0} ^ {N-1} x_1 (m) x_2 [((nm)) _ N] \ quad m = 0,1,2 ... N- 1 $
| Vergleichspunkte | Lineare Faltung | Kreisfaltung |
|---|---|---|
| Verschiebung | Lineares Schalten | Kreisverschiebung |
| Proben im Faltungsergebnis | $ N_1 + N_2−1 $ | $ Max (N_1, N_2) $ |
| Antwort eines Filters finden | Möglich | Möglich ohne Polsterung |
Methoden der Kreisfaltung
Im Allgemeinen gibt es zwei Methoden, die angewendet werden, um eine kreisförmige Faltung durchzuführen, und sie sind:
- Konzentrische Kreismethode,
- Matrixmultiplikationsmethode.
Konzentrische Kreismethode
Sei $ x_1 (n) $ und $ x_2 (n) $ zwei gegebene Sequenzen. Die Schritte für die zirkuläre Faltung von $ x_1 (n) $ und $ x_2 (n) $ sind
Nehmen Sie zwei konzentrische Kreise. Zeichnen Sie N Abtastwerte von $ x_1 (n) $ auf den Umfang des äußeren Kreises (wobei aufeinanderfolgende Punkte mit gleichem Abstand beibehalten werden) gegen den Uhrzeigersinn.
Für $ x_2 (n) $, Grundstück N Proben von $ x_2 (n) $ im Uhrzeigersinn auf dem inneren Kreis Plotten Ausgangsprobe an der gleichen Stelle angeordnet , wie 0 th Probe von $ x_1 (n) $
Multiplizieren Sie die entsprechenden Samples auf den beiden Kreisen und fügen Sie sie hinzu, um die Ausgabe zu erhalten.
Drehen Sie den inneren Kreis mit jeweils einer Probe gegen den Uhrzeigersinn.
Matrix-Multiplikationsmethode
Die Matrixmethode repräsentiert die beiden gegebenen Sequenzen $ x_1 (n) $ und $ x_2 (n) $ in Matrixform.
Eine der gegebenen Sequenzen wird durch kreisförmige Verschiebung von jeweils einer Probe wiederholt, um eine NXN-Matrix zu bilden.
Die andere Sequenz wird als Spaltenmatrix dargestellt.
Die Multiplikation zweier Matrizen ergibt das Ergebnis einer Kreisfaltung.