Warum hat DFT nur $N$ Komponenten?
Warum hat die DFT nur $N$Komponenten drin? Ich kann sehen, dass nach N Komponenten die Frequenzkomponente periodisch ist und sich mit denselben Werten wiederholt, aber das scheint nicht zu erklären, warum wir nur haben können$N$Komponenten. Hängt dies mit dem Stichprobensatz zusammen? Wie hängt das alles zusammen?
Antworten
Die DFT ist sowohl in Zeit- als auch in Frequenzbereichen diskret mit der gleichen Anzahl von Abtastwerten in jedem Bereich. Dies bedeutet, dass die Eingabe in die Transformation und die Ausgabe der Transformation beide diskret sind und beide haben $N$Proben. Dies ist in der Formel für die DFT definiert, in der wir haben$N$ Proben in der Zeit indiziert als $n = 0$ zu $N-1$ und $N$ Samples in Frequenz indiziert als $k = 0$ zu $N-1$. Die Abtastfrequenz liegt bei$k = N$.
$$ X[k] = \sum_{n=0}^{N-1}x[n]e^{-j k \frac{2\pi}{N} n}$$
Dies ist per Definition, da zum Beispiel die DTFT eine kontinuierliche Frequenz hat, die durch gegeben ist
$$ X(e^{j\omega}) = \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n}$$
Wie wir in der DFT-Formel sehen, jede Probe $k$ im $X[k]$ ist eine Korrelation (Summe von Produkten) der Zeitbereichswellenform $x[n]$ mit dem Frequenzton gegeben durch $e^{-j k \frac{2\pi}{N} n}$ - Beachten Sie, dass die Form $e^{j\phi}$ ist ein Zeiger mit Größe $1$ und Winkel $\phi$, so sehen wir das für jeden Wert von $k$ dass wir wählen, $e^{-j k \frac{2\pi}{N} n}$ ist nur ein Zeiger, der sich mit einer anderen Geschwindigkeit dreht, definiert durch $k$. Dies bewirkt, dass die Korrelation maximiert wird, wenn$k$ ist gleich oder nahe an der Frequenz von $x[n]$.
Der Grund für $N$Samples ist auch sehr intuitiv, da sich die Transformation nach Ansicht des OP mathematisch genauso verhält, als ob die Zeitbereichswellenform periodisch wäre: Dies ähnelt der Fourier Series Expansion (FSE), die jede einzelne wertige analytische Funktion in eine unendliche Reihe von diskreten zerlegt Frequenzen, wobei jede Frequenz ein ganzzahliges Vielfaches der Grundwelle ist, wobei die Grundwelle durch gegeben ist$f=1/T$ Hz wo $T$ist die Dauer des Zeitbereichssignals in Sekunden: Dies ist sinnvoll, da sich der FSE auch so verhält, als ob diese Zeitbereichswellenform als periodische Wellenform bis unendlich fortgesetzt würde; wenn wir eine beliebige Wellenform wiederholen$T$ Sekunden hat es eine Grundfrequenz bei $1/T$Hz. Es muss auch diskret sein, da sich jede der einzelnen Komponenten, die durch die höheren Harmonischen gegeben sind, auch nur über die Dauer wiederholt$T$und wir erstellen die Wellenform neu, indem wir jede dieser Komponenten summieren (also jede Komponente, die sich nicht wiederholt hat) $T$ würde unsere Fähigkeit dazu verletzen).
So wissen wir, dass wir haben $N$ Abtastungen in der Zeit wäre dann die Grundfrequenz bei $1/N$. Wir wissen auch, dass die Abtastrate bei bin liegt$k = N$ in der Frequenz liegt also die Grundfrequenz bei $k=1$und da muss es dann sein $N$ Gesamtfrequenz-Samples (einige können gleich 0 sein), jedes ist das ganzzahlige Vielfache der Grundwelle, genau wie das FSE!
Warum enthält die DFT nur N Komponenten?
Wie Sie wies darauf hin, die DFT könnte eine Unendlichkeit von Komponenten darin haben, dass alle N Einträge wiederholen. Bis zu einem gewissen Grad geht es beim Aliasing darum - Sie setzen diese "fehlenden" Bits wieder ein.
Es gibt zwei Gründe (oder vielleicht eineinhalb) , um die DFT auf N Komponenten zu begrenzen, aber: Eine Wirtschaft ist - Sie müssen nicht benötigen mehr als N - Komponenten. Das andere ist die Vollständigkeit - wenn Sie eine Transformation mit einer Umkehrung haben möchten , führt das Vorhandensein zusätzlicher Punkte in Vorwärtsrichtung zu einer unbestimmten Transformation in Rückwärtsrichtung.
In gewisser Weise können Sie die DFT als Multiplikation eines Vektors mit einer quadratischen Matrix betrachten. So kann man sagen$$X = \mathbf{A}_{DFT}\ x$$ wo $X$ ist ein Vektor von Abtastwerten im Frequenzbereich und $x$ ist ein Vektor von Proben im Zeitbereich. $\mathbf{A}_{DFT}$ ist definiert als $$\mathbf{A}_{DFT} = \begin{bmatrix} 1 && 1 && \cdots && 1 && \cdots && 1\\ 1 && e^{-2i \pi 2/N} && \cdots && e^{-2i \pi m/N} && \cdots && e^{-2i \pi (N-1)/N} \\ && && && \vdots && && \\ 1 && e^{-2i \pi n/N} && \cdots && e^{-2i \pi\ n\,m/N} && \cdots && e^{-2i \pi (N-1)n/N} \\ && && && \vdots && && \\ 1 && e^{-2i \pi (N-1)/N} && \cdots && e^{-2i \pi\ (N-1)\,m/N} && \cdots && e^{-2i \pi (N-1)^2/N} \end{bmatrix}$$
(Arbeiten Sie das selbst aus - erstens, weil es tiefgreifend ist, und zweitens, weil ich dort wahrscheinlich irgendwo einen dummen Tippfehler gemacht habe).
Es stellt sich heraus, dass $\mathbf{A}_{DFT}$ ist eine quadratische hermitianische orthoganale Matrix und nur ein Skalierungsfaktor von orthonormal entfernt.
Das Schlimme daran ist, dass es das Ganze in eine schwer zu fassende Matrixnotation versetzt. Das Schöne daran ist, dass die inverse DFT direkt in Ihren Schoß fällt:$$x = \mathbf{A}_{IDFT} X$$und so kann man das durch Inspektion sagen$$\mathbf{A}_{IDFT} = \mathbf{A}_{DFT}^{-1}$$
Und deshalb halten wir an N Punkten in unserer DFT an: weil jeder der N Punkte in der 'Ausgabe' einer DFT eindeutig definiert ist und diese N-Punkt-DFT alle Informationen im ursprünglichen Vektor enthält$x$ohne Vervielfältigung . Das bedeutet wiederum, dass es eine inverse Transformation gibt - die wir sogar mit linearer Algebra finden können, wenn wir in einer Stimmung sind.
Die diskrete Fourier-Transformation (DFT) ist eine Transformation von einem Signal in ein Spektrum, wobei beide diskrete Sequenzen sind. Die Werte im Signal werden als Abtastwerte und die Werte im Spektrum als Bins bezeichnet. Das Signal kann typischerweise realwertig oder komplex sein, aber das Spektrum muss normalerweise komplex sein. Es gibt Signale mit streng realen Spektren.
Die Definition legt für die Berechnung einen einzelnen Bin-Wert aus einem Bereich von Stichprobenwerten fest, der als Frame bezeichnet wird:
$$ X[k] = ? \cdot \sum_{n=L}^{H} x[n] e^{-i \frac{2\pi}{N} kn} $$
Die DFT-Definition macht keine Annahmen über die Werte des Signals außerhalb des Rahmens.
Übliche Notation ist:
$\quad X[\,]$ ist das Spektrum
$\quad k$ ist der Bin-Index
$\quad x[\,]$ ist das Signal
$\quad n$ ist der Signalindex
$\quad N$ ist die Stichprobenanzahl, die auch als DFT-Rahmengröße bezeichnet wird
Weitere Notation ist:
$\quad ?$ ist der Normalisierungsfaktor (normalerweise nicht gezeigt, kein herkömmliches Symbol)
$\quad L$ ist der niedrigste Stichprobenindex
$\quad H$ ist der höchste Stichprobenindex
Die Definition der DFT kann basierend auf den verwendeten Konventionen variieren. Der erste ist der Normalisierungsfaktor. Die drei vorherrschenden sind:
$\quad ? = 1 $ Dies ist die konventionellste und das, was Sie bei den meisten Codebibliotheken finden.
$\quad ? = 1/N $ Dies ist die aussagekräftigere in Bezug auf die Verwendung, und IMO ist "The Correct One".
$\quad ? = 1/\sqrt{N} $ Dies ist die bevorzugte lineare Algebra, da dadurch die Matrixdarstellung (TimWescotts Antwort) einheitlich wird.
Der Eingabebereich als zwei gemeinsame Bereiche:
$\quad L,H = 0,N-1 $ Ist das übliche in Codebibliotheken und Verwendung.
$\quad L,H = -M,M $Dies ist eine Domäne mit ungerader Größe, die auf Null zentriert ist. Diese Konfiguration ist die "natürlichere", bei der$N = 2M+1$. Das Symbol$M$ ist keine Konvention.
Aufgrund der Art des Exponentialausdrucks in der Definition, $X[k]$ wird sein $N$periodisch. Daher enthält ein Spektrum von N Behältern alle verfügbaren Informationen, und zusätzliche Berechnungen sind redundant. (Die Antwort, die gesucht wird, nehme ich an).
Der Wert von $k$repräsentiert die Frequenz des entsprechenden Basisvektors im Signalraum in Einheiten von Zyklen pro Rahmen. Aufgrund der diskreten Natur des Signals und der Funktionsweise der zugrunde liegenden trigonometrischen Funktionen können Werte von$k$ größer als $N/2$oder kleiner als $-N/2$ (bekannt als Nyquist Bin für gerade $N$ Werte) sind von Werten innerhalb dieses Bereichs nicht zu unterscheiden und werden als Aliasfrequenzen bezeichnet.
Es ist üblich, die DFT für die Fächer 0 bis auszuwerten $N-1$Dies geschieht normalerweise, wenn der Eingangsbereich ebenfalls 0 bis 0 beträgt $N-1$. Die zweithäufigste ist die Bewertung des Bereichs von$-M$ zu $M$im Falle des entsprechenden Eingabebereichs. Es gibt nichts, was besagt, dass Sie einen oder alle Behälter berechnen müssen. Die Periodizität erleichtert die Konvertierung zwischen verschiedenen Auswahlmöglichkeiten, ohne dass eine Neuberechnung erforderlich ist.
$$ X[k] = X[k+N]$$
Die inverse DFT entspricht mathematisch der Vorwärts-DFT ohne das negative Vorzeichen im Exponenten. Der Normalisierungsfaktor sollte so gewählt werden, dass das Produkt der beiden Normalisierungsfaktoren ist$1/N$. Dies ist keine Voraussetzung und viele Codebibliotheken bieten eine nicht normalisierte IDFT.
Ob sich das negative Vorzeichen in der Vorwärtstransformation oder das inverse befindet, ist für komplexe Töne relevant, da es ein Signal wünscht, das ein reiner komplexer Frequenzton ist $k$ Zyklen pro Frame sollten durch bin dargestellt werden $k$im Spektrum. Da ein realer reiner Ton ein Durchschnitt aus zwei komplexen reinen Tönen mit gleicher Größe, aber entgegengesetzten Vorzeichenfrequenzen ist, wird er in bin dargestellt$k$ und bin $-k=N-k$ unabhängig vom Zeichen.
Wie die Vorwärts-DFT ist die inverse DFT in ihrer Ausgabe periodisch. Wenn Sie also die Umkehrung des Spektrums eines Signals nehmen, ist das von Ihnen erzeugte Signal ein neues Signal, das genau im Rahmen mit dem ursprünglichen Signal übereinstimmt und außerhalb davon N periodisch ist.
Die "ideale Verwendung" einer DFT besteht darin, ein periodisches Signal über eine ganze Anzahl von Zyklen zu erfassen. In diesem Fall stimmen die Umkehrung des Spektrums und das Signal innerhalb und außerhalb des Rahmens überein. Da ein periodisches Signal immer als gewichtete Summe eines Satzes von harmonischen Tönen dargestellt werden kann und harmonische Töne Frequenzen haben, die ganze ganzzahlige Vielfache der Grundwelle sind, können die Werte der Gewichte direkt aus Bin-Werten bestimmt werden.
Die N-Periodizität der Ausgabe ist trivial, um direkt aus der Definition zu beweisen:
$$ X[k+N] = ? \cdot \sum_{n=L}^{H} x[n] e^{-i \frac{2\pi}{N} (k+N)n} = ? \cdot \sum_{n=L}^{H} x[n] e^{-i \frac{2\pi}{N} kn } e^{-i 2\pi n} = X[k] $$
Wo $e^{-i 2\pi n}$ ist immer gleich 1 wenn $n$ ist eine ganze Zahl.
Dies kann direkt aus Eulers Formel gezeigt werden:
$$ \begin{aligned} e^{i\theta} &= \cos( \theta ) + i \sin( \theta ) \\ e^{-i 2\pi n} &= \cos(-2\pi n) + i \sin(-2\pi n) \\ &= 1 + i0 = 1 \end{aligned} $$
Beachten Sie, dass diese Antwort keine Abhängigkeit vom entsprechenden fortlaufenden Fall hat oder sogar dessen Existenz voraussetzt.
Eine Darstellung von a $N=16$ DFT:
Das animierte GIF ist noch cooler, aber viel zu groß zum Posten.