Diskrete Fourier-Transformation

Um ein beliebiges periodisches Signal \(S\) über eine FOURIER-Reihe zu approximieren, müssen also die dem Grundfrequenzvielfachen \(n\) zugehörigen Koeffizienten \(A_n\) sowie die entsprechenden Phasenlagen \(\varphi_n\) bestimmt werden. Handelt es sich bei dem zu transformierenden Signal \(S\) um ein analoges Signal analog \(S\) bzw. um eine Funktion \(f(t)\), existiert zu jedem Zeitpunkt \(t\) ein entsprechender Wert \(S(t)\) bzw. \(f(t)\) , an dem der zu transformierende Werteverlauf ausgewertet werden kann. Liegt ein digitales Signal zur Auswertung mittels Fourier-Transformation vor, stehen jedoch nur endlich viele diskrete Stützstellen \(f_i(t_i)\) zur Approximation an den diskreten Zeitwerten \(t_i\) für \(\max i=0,1,\dots,i\) zur Verfügung.

Bei der diskreten FOURIER-Transformation wird das mit \(T\) periodische Signal \(S(t)\) also lediglich an diskreten Stützstellen \(f_k(t_k)\) ausgewertet. Dazu wird eine ausgewählte Periode (Integrationsintervall) in \(N\) gleiche Abschnitte mit der Breite \(\Delta t\) unterteilt, wobei die linken oberen Ecken der resultierenden Rechtecke, den durch \(S(t)\) definierten Stützstellen \(f_k(t_k)\) entsprechen. Bei der praktischen Anwendung dieser Diskretisierungsmethode (auch Treppenstufenmethode genannt) werden sofort einige Probleme ersichtlich. Entspricht der ausgewählte Fensterausschnitt nicht genau einem Vielfachen der tatsächlichen Periodendauer des Signals, kommt es zum sogenannten Leck-Effekt (leakage effect). Der Fehler, der bei der Transformation des Signals begangen wird, setzt sich periodisch fort, was unter anderem zu einer Verschiebung der Frequenzanteile führt. Ein weiteres Problem ergibt sich dann, wenn die digitalen Signalwerte nicht genau mit den durch die Teilung \(N\) definierten Stützstellen zusammenfallen. In diesem Fall ist es zweckmäßig, die bei \(t_k\) benötigten Werte \(f_k\) anhand der vorhandenen digitalen Signalwerte \(S_i\) zu approximieren, um den Fehler bei der diskreten Fourier-Transformation möglichst gering zu halten.

Die diskrete FOURIER-Transformation lässt sich also als Näherung des Ergebnis der numerischen Integration durch die Berechnung der komplexen \(C_n\) anhand diskreter Werte in einem sich periodisch wiederholendem Intervall beschreiben. Da es sich bei den auf diese Weise berechneten FOURIER-Koeffizienten lediglich um Näherungswerte handelt, sollen diese über kleine Buchstaben bezeichnet werden.

\[ \large{t_k=\dfrac{2\pi}{N}k \quad \text{für} \, k=0,1,2,\dots,N-1} \] \[ \large{w=e^{-\frac{2\pi}{N}i}} \] \[ \large{c_n=\dfrac{1}{N}\sum\limits_{k=0}^{N-1}w^{nk}\cdot f_k} \] \[ \large{W_{nk}=w^{nk}} \]

Aus den Stützstellen \(t_k\) und dem sogenannten „Kern“ kann nun die diskrete Fourier-Transformation als Matrix dargestellt werden.

\[ \large{\pmb{c}=\dfrac{1}{N}\pmb{W} \cdot \pmb{f}} \] \[ \large{\left( \begin{array}{c} c_0\\ c_1 \\ \dots \\ c_{n-1} \end{array}\right) =\left( \begin{array}{cccc} 1 & 1 & \dots & 1 \\ 1 & w^1 & \dots & w^{N-1} \\ \vdots & & & \vdots \\ 1 & w^{N-1} & \dots & w^{(N-1)(N-1)} \end{array}\right) \cdot \left( \begin{array}{c} f_0\\ f_1 \\ \dots \\ f_{N-1} \end{array}\right) } \]

Anhand der Matrixschreibweise wird deutlich, dass sich aus N äquidistanten Stützstellen eines Signals nur maximal \(N\) komplexe FOURIER-Koeffizienten bestimmen lassen. Die Kern-Matrix der DFT lässt sich in Form eines Polardiagramms des umlaufenden Zeigers w zur Veranschaulichung dargestellen. Die Zeilen unterhalb von \(N/2\) ergeben sich dabei durch Spiegelung der oberen Zeilenelemente, was mathematisch den konjugiert komplexen Elementen entspricht. Die zu berechnenden FOURIER-Koeffizienten \(c_n\) , sind somit ebenfalls„spiegelsymetrisch“ zur Zeile \(c_{N/2}\) , was bedeutet, dass bereits alle Informationen in der oberen Hälfte des berechneten Vektors \(\pmb{c}\) enthalten sind. Dies führt zu einem wichtigen Theorem der digitalen Signaltechnik, dem „Nyquist-Theorem“ oder kurz: Möchte man ein digitales periodisches Signal mittels DFT in Form einer FOURIER-Reihe mit n-Gliedern darstellen, benötigt man mindestens doppelt so viele äquidistante Stützstellen innerhalb einer Periode. Da lediglich die Bestimmung der oberen Hälfte des Vektors \(\pmb{c}\) notwendig ist, um die Reihenentwicklung vollständig durchzuführen, lässt sich der numerische Rechenaufwand nahezu halbieren. Diese Eigenschaft bildet die Grundlage der Fast-FOURIERTransformation, deren Algorithmen alltäglich zahlreiche Anwendungen finden.