Warum wird in DSP eine zirkuläre Faltung verwendet? Warum nicht lineare Faltung?
On November 29, 2020 by admin-
Warum verwenden wir die zirkuläre Faltung in DSP?
-
Was ist der Hauptgrund für die Verwendung in der digitalen Verarbeitung?
-
Warum ist das Konzept des Rundschreibens? Faltung kommt häufiger als lineare Faltung?
Kommentare
- Sie werden feststellen, dass alle Ihre Antworten eine Erwähnung enthalten der diskreten Fourier-Transformation, die mit der FFT am effizientesten implementiert wird. Die DFT erweitert inhärent periodisch die an sie übergebenen Sequenzen endlicher Länge (die kreisförmig sind). Die kreisförmige Faltung ist selten das Ziel, normalerweise die lineare Faltung ist das Ziel. Wenn jedoch die DFT ‚ s $ X [k] $ und $ H [k] $ miteinander multipliziert werden, entspricht dies der kreisförmigen Faltung Von den beiden periodisch erweiterten Sequenzen, $ x [n] $ und $ h [n] $, die an die DFTs übergeben wurden, besteht das Problem darin, dies irgendwie in eine lineare Faltung umzuwandeln.
Antwort
Bei einem zeitdiskreten LTI-System mit Impulsantwort $ h [n] $ kann man seine Antwort auf jede Eingabe $ x [n] $ mit einem Faltung Summe: $$ y [n] = x [n] \ star h [n] = \ sum_ {k = – \ infty} ^ {\ infty} {h [k] x [nk]} \ tag {1} $$
Ohne weitere Angabe gilt die obige Definition für die lineare Faltung (aperiodische Faltung) zwischen $ h [n] $ und $ x [n] $ sind aperiodische zeitdiskrete Sequenzen von möglicherweise unendlicher Länge, sofern nicht anders angegeben. Dies unterscheidet sich von einer kreisförmigen Faltung , die zwischen zwei periodischen Sequenzen der Periode $ liegt N $ und über einen einzelnen Zeitraum berechnet.
Sie können eine lineare berechnen Faltung im Zeitbereich nach Gleichung 1 oder im Frequenzbereich unter Verwendung der folgenden DTFT-Eigenschaft (zeitdiskrete Fourier-Transformation): $$ y [n] = x [n] \ star h [n] \ impliziert Y (e ^ {j \ omega}) = X (e ^ {j \ omega}) H (e ^ {j \ omega}) \ tag {2} $$
DTFT hängt natürlich mit der linearen Faltung zusammen, da es sich um theoretisch vorhandene aperiodische Sequenzen handelt, die sich von $ – \ infty $ bis $ \ infty $ spiegelt sich in seinen Grenzen der definierenden Summe wider: $$ X (e ^ {j \ omega}) = \ sum_ {n = – \ infty} ^ {\ infty} x [n] e ^ {- j \ omega n} \ tag {3} $$
Wenn Sie eine Berechnung durchführen möchten von Hand mit symbolischen Ausdrücken für Signale wie $ x [n] = a ^ nu [n] $ und $ h [n] = b ^ nu [n] $ können Sie die Ergebnisse in Zeit- oder Frequenzbereichen wie oben beschrieben berechnen.
Wenn Sie dasselbe Ergebnis mithilfe eines Computers berechnen möchten, können Sie den Zeitbereichsansatz verwenden, der auf einer LCCDE-Rekursion (für IIR-Systeme) oder einer direkten endlichen Faltungssumme (für FIR-Systeme) basiert. ABER der Frequenzbereichsansatz funktioniert nicht mit DTFT, da er hauptsächlich zur Entwicklung der Mathematik der Signaltheorie & verwendet wird und nicht für digitale Computer geeignet ist Implementierungen, da die Variable $ \ omega $ eine echte kontinuierliche number.
Stattdessen wird die DFT (diskrete Fourier-Transformation) definiert, die als $$ X [k] = X (e ^ {j \ omega}) | _ {\ omega = \ frac {2 \ pi k} {N}} \ tag {4} $$
wobei $ k = 0,1, …, N-1 $ und $ N $ ist die Länge der DFT, die dann als N-Punkt DFT des Signals $ x [n] $ .
Gleichung 4 impliziert, dass die DFT-Sequenz $ X [k] $ als einheitliche Abtastwerte der DTFT $ X (e ^ {j \ omega}) $ , was eine periodische Funktion ist, daher ist DFT $ X [k] $ ebenfalls periodisch, aber wir betrachten nur die erste Periode von $ k = 0 $ bis $ N-1 $ .
Da DFT-Sequenzen von Natur aus periodisch sind, sind ihre Faltungen ebenfalls periodisch (zirkulär).Während also eine lineare Faltung zwischen aperiodischen Signalen $ x [n] $ und $ y [n] $ wird durch den I-DTFT-Ausdruck $$ y [n] = \ impliziert mathcal {I-DTFT} \ {X (e ^ {j \ omega}) H (e ^ {j \ omega}) \} $$ statt Die zirkuläre Faltung zwischen zwei periodischen Sequenzen wird durch den I-DFT-Ausdruck $$ \ tilde {y} [n] = \ mathcal {impliziert I-DFT} \ {X [k] H [k] \} $$
Da wir also eine lineare Faltung zwischen zwei aperiodischen Sequenzen berechnen möchten $ x [n] $ und $ h [n] $ der Längen $ L_x $ bzw. $ L_h $ unter Verwendung des Frequenzbereichs anhand ihrer $ N $ -Punkt-DFTs, $ X [k] $ und $ H [k] $ müssen wir tatsächlich eine zirkuläre Faltung zwischen den periodischen Erweiterungen der Signale $ berechnen \ tilde {x} [n] $ und $ \ tilde {h} [n] $ von Perioden $ N $ .
Der Schlüssel liegt in der Auswahl einer richtigen Länge $ N $ der DFTs, die lang genug sein muss, um Zeitdomänen Aliasing der Sequenz $ \ tilde {y} [n] $ , zurückgegeben durch die IDFT-Berechnung: $$ \ tilde {y} [n] = \ sum_ {r = – \ infty} ^ {\ infty} y [n-rN] \ tag {5 } $$
wobei $ y [n] $ das Ergebnis der linearen Faltung ist, die von der theoretischen Umkehrung zurückgegeben würde DTFT und $ \ tilde {y} [n] $ ist das periodische Ergebnis der periodischen (kreisförmigen) Faltung, die durch die inverse DFT impliziert wird.
Beachten Sie, dass, wenn eines der Signale unendlich lang ist, NICHT möglich ist Die Berechnung ihrer linearen Faltung unter Verwendung des DFT-Ansatzes, da $ N $ ins Unendliche gehen würde, ist praktisch unmöglich. Die Implementierung einer linearen Faltung über DFT hat dann die folgenden Schritte:
-
Wählen Sie N gemäß den folgenden Kriterien: $$ N \ geq L_x + L_h -1 $$ , der eine aliasfreie Rekonstruktion des inversen Signals garantiert $ y [n] $ aus seiner DFT $ Y [k] $ der berechneten Kreisfaltung über $ X [k] H [k] $ .
-
Berechnen Sie N-Punkt-DFTs $ X [k] $ und $ H [k] $ von $ x [n] $ und $ h [n] $ .
-
Berechne $ Y [k] = X [k ] H [k] $
-
Berechnen Sie die inverse N-Punkt-DFT von $ Y [k] $ um die Ausgabe zu erzeugen $ y [n] $
Antwort
Beantwortung Ihrer Fragen:
- Warum verwenden wir die zirkuläre Faltung in DSP?
In DSP werden normalerweise diskrete Sequenzen endlicher Länge behandelt (selbst wenn das untersuchte Signal unendlich ist, können wir jeweils nur einen endlichen Teil davon analysieren ). Wenn es darum geht, ein Signal zu verarbeiten, muss die Art und Weise, wie es verarbeitet wird, in einem diskreten Logikgerät implementiert werden können (nämlich einem Gerät, das keine kontinuierlichen Werte speichern kann, da diese Werte unendlich sind und eine begrenzte Menge an Speicher, Speicher usw. haben). Dies erklärt, warum die diskrete Zeit-Fourier-Transformation (DTFT), die eine diskrete Zeitsequenz in eine kontinuierliche Frequenzsequenz umwandelt, nicht in Hardware implementiert werden kann. Die lineare Faltung in der Zeit entspricht der Multiplikation von DTFTs mit zwei Sequenzen. Da DTFT jedoch nicht in Hardware implementiert werden kann, ist dies nicht der Weg, um eine lineare Faltung zu erhalten. Diskrete Fourier-Transformation (DFT) transformiert andererseits eine diskrete Zeitsequenz in eine diskrete Frequenzsequenz und diese ermöglicht die Implementierung in Hardware. Das Multiplizieren von 2 Sequenz-DFTs entspricht jedoch im Prinzip der Zirkularfaltung (eine lineare Faltung kann auch erhalten werden, wenn die Zeitsequenzen zuvor mit genügend Nullen aufgefüllt wurden, siehe Erklärung unten).Der Grund, warum das Multiplizieren von DFTs mit zwei Sequenzen einer kreisförmigen und nicht linearen Faltung entspricht, liegt in der Tatsache, dass die DFT für eine Sequenz mit endlicher Zeitlänge der Discrete Fourier Series (DFS) derselben Sequenz mit endlicher Zeitlänge entspricht, die periodisch verlängert wird (Verkettung der endliche Zeitlängenfolge unendlich in der Zeitachse) über einen Zeitraum genommen. DFS ist auch im Frequenzbereich periodisch, so dass dort keine lineare Faltung angewendet wird (siehe 8.2.5 und 8.6.5 von Oppenheims Discrete Time Signal Processing, 3. Ausgabe)
- Was ist der Hauptgrund für die Verwendung in der digitalen Verarbeitung?
Es wird durch DFT-Multiplikation erhalten und DFT kann leicht in Hardware implementiert werden. Darüber hinaus existieren sehr effiziente Algorithmen wie FFT zur Berechnung der DFT
- Warum kommt das Konzept der zirkulären Faltung häufiger vor als lineare Faltung?
Das hängt von der Anwendung ab. Die kreisförmige Faltung kann auch die lineare Faltung ergeben. Nehmen wir zum Beispiel an Wir arbeiten mit Signal A der Länge N und Signal B auch der Länge N (dies kann auch für verschiedene Längen durchgeführt werden). Die kreisförmige Faltung hat die Länge N. Um eine lineare Faltung zu erhalten, müssen sowohl A als auch B mit Nullen aufgefüllt werden, bis sie eine Länge von mindestens 2 * N – 1 erreichen. Dann wird die DFT auf beide angewendet, multipliziert und umgekehrt DFT gibt Ihnen die lineare Faltung
Antwort
Hier „ist ein bisschen Intuition:
Wenn Sie Wenn Sie mit Signalen digital umgehen, haben Sie es immer mit einem endlichen Signal zu tun. Dies liegt daran, dass Sie nur mit einer endlichen Menge von Datenpunkten verarbeiten können.
Das Problem ist jedoch, dass Sie Transformationen in den Frequenzbereich mit durchführen Die DFT, per Definition kann ein Signal nicht endlich sein. Wenn Sie also eine DFT-Operation ausführen, ändert sich Ihr Signal implizit von endlich zu periodisch, selbst wenn Ihr Signal nicht periodisch ist.
Dies Die Periodizität des Signals führt dazu, dass die Faltung kreisförmig verwendet werden muss.
Antwort
Die DFT / FFT ist ein nützlicher rechnerischer „Hammer“, aber alle seine Transformationsbasisvektoren haben eine kreisförmige (ganzzahlige periodische) Apertur und können als periodische Funktionen unendlich erweitert werden, was einige Benutzer mit der Art ihrer Eingabedaten verwechseln.
Wenn Sie einen ausreichenden Nullpunkt auffüllen, führt die kreisförmige Faltung zum gleichen Ergebnis wie die lineare Faltung, jedoch mit einem etwas höheren Rechenaufwand als die kreisförmige.
Schreibe einen Kommentar