~XII: Die diskrete Fourier-Transformation

Die Quadratur oder numerische Integration aus dem letzten Beitrag liefert einen wichtigen Baustein, um die eine diskrete Variante der Berechnung der Fourier-Koeffizienten anzugeben: die diskrete Fourier-Transformation, eine näherungsweise Berechnung der Fourier-Koeffizienten, die sich am Computer durchführen lässt. Mit der Quadratur basiert die Berechnung lediglich auf einer gegebenen endlichen Folge von Zahlen, den Abtastwerten \(f\bigl(\frac{2\pi k}{N}\bigr),\ k=0,1,\ldots, N-1,\) der Funktion \(f\). Um diese näherungsweise Berechnung der Fourier-Koeffizienten und welche Eigenschaften diese mit sich bringt, soll es in diesem Beitrag gehen.

Anstelle der bisherigen Definition mit analytischer Integration der Fourier-Koeffizienten einer periodischen Funktion \(f(x)\) über eine Periode, wie das Intervall \([-\pi,\pi)\), soll also in diesem Beitrag der Fourier-Koeffizient \(c_k(f),\ k\in\mathbb Z,\) näherungsweise bestimmt werden. Die Definition lautet \(c_k(f) = \frac{1}{2\pi}\int_{-\pi}^{\pi} f(x)\textrm{e}^{-\textrm{i}kx}\ \textrm{d}x\). Für eine gegebene Anzahl \(N\in\mathbb N\) an Abtastwerten wurden im letzten Beitrag die äquidistanten Punkte \(x_j = \frac{2\pi j}{N}\) eingeführt. Läuft hier \(j=0,1,\ldots,N-1\), so liegen nicht alle Punkte im Intervall \([-\pi,\pi)\), aber da die Funktion \(f(x)\) periodisch ist, sind die Funktionswerte \(f(x_j)\) und \(f\bigl((x_j)_{2\pi}\bigr)\) identisch. Sind diese Werte bekannt, lässt sich ein beliebiger Fourier-Koeffizient \(c_k(f)\) annähern, denn ausgehend von diesen einzelnen Werten sind auch die Abtastwerte der Funktion \(g(x_j) = f(x_j)\textrm{e}^{-\textrm{i}kx_j}\) bestimmen und die numerische Integration der Funktion \(g(x)\) liefert die gewünscht Näherung des Fourier-Koeffizienten. Da für diese Näherung nicht nur die Anzahl Abtastpunkte von großer Bedeutung ist, sondern die Näherung selbst im Folgenden sehr häufig verwendet wird, soll sie einen eigenen Namen bekommen.

Gegeben sei eine feste Anzahl \(N\in\mathbb N\) und die Abtastwerte \(f(x_j)\) mit \(x_j = \frac{2\pi j}{N},\ j=0,\ldots,N-1\). Dann sind Werte \(c_k^N(f)\) gegeben durchHier steht das \(N\) nicht als Exponent am Koeffizienten, sondern besagt lediglich, dass die dazugehörige Zahl nicht nur von \(k\) und \(f\), sondern eben auch von \(N\) abhängt. Man liest hier also \(c_k^N(f)\) als einen festen Bezeichner. \[ c_k^N(f) = \frac{1}{N}\sum_{j=0}^{N-1} f(x_j)\textrm{e}^{-\textrm{i}kx_j},\qquad k=0,\ldots,N-1. \] Die Berechnung all dieser \(N\) Koeffizienten heißt die diskrete Fourier-Transformation (der Länge \(N\)). Ein einzelner Wert \(c_k^N(f)\) heißt diskreter Fourier-Koeffizient (der DFT mit Länge \(N\)). Die übliche Abkürzung für die diskrete Fourier-Transformation lautet DFT.

Die diskrete Fourier-Transformation ist ein Algorithmus, der neben der Anzahl \(N\) als Eingabe exakt \(N\) Abtastwerte der Funktion \(f\) benötigt. Dies sind etwa bei einem üblichen Audio-Signal \(44.100\) Werte pro Sekunde, da die Einheit 1 Hertz (kurz Hz) ein Signal bzw. Impuls pro Sekunde bezeichnet, wird dies kurz mit \(44.100\,\mathrm{Hz}\) oder \(44.1\,\mathrm{kHz}\). Das Ergebnis des Algorithmus sind wieder \(N\) Werte \(c_k^N(f),\ k=1,\ldots,N-1\). Aber wieso sind das nur \(N\) Werte, wo doch die Fourier-Koeffizienten \(c_k(f)\) für alle \(k\in\mathbb Z\) existieren? Dazu gibt es zwei Antworten, die erste ist die mathematische, die zweite die dazugehörige Interpretation.

Da die diskrete Fourier-Transformation bisher sehr abstrakt eingeführt worden ist, sollen die folgenden Beispiele die Definition verbildlichen und ihre Wirkungsweise illustrieren. Im Allgemeinen ist das Ergebnis der diskreten Fourier-Transformation nicht unbedingt reellwertig. In der folgenden Abbildung sind daher im linken Bild stets zwei Werte zu sehen. Die dunklen Punkte verdeutlichen den Realteil, die hellen den Imaginärteil der Fourier-Koeffizienten.

\(N\) 1 Fkt. \(f\) 
Beispiel einiger diskreter Fourier-Transformationen (rechts) der abgetasteten Funktion \(f\) (links). Dabei sind die hellen Punkte der Imaginärteil, die dunklen der Realteil. Was fällt bei den beiden Sinus-Funktionen auf?

Zurück zu der Anmerkung, dass bei den \(c_k^N(f)\), das \(k\) nur einige und nicht alle ganzen Zahlen durchläuft. Betrachtet man einen der nichtgenannten Indizes \(h\), so ist dieser also entweder \(h\) kleiner als \(0\) oder \(h\) größer als \(N-1\). Er kann dann allerdings durch Verschieben um ein Vielfaches von \(N\) in die Menge \(\{0,1,\ldots,N-1\}\) zurückgebracht werden. In Formeln: Es gibt ein \(k\), so dass \(h = k + lN\) gilt, wobei \(l\in\mathbb Z\setminus\{0\}\) eine von \(0\) verschiedene Zahl ist und bei der Division mit Rest auch Ganzzahlquotient genannt wird. Der entsprechende Wert \(k\) ist nichts anderes als der ganzzahlige Rest beim Teilen von \(h\) durch \(N\). Berechnet man nun den diskreten Fourier-Koeffizienten \(c_h^N(f)\) und nutzt dabei diesen Zusammenhang zum gerade gefundenen \(k\), so gilt \[ c_h^N(f) = \frac{1}{N}\sum_{j=0}^{N-1} f(x_j)\textrm{e}^{-\textrm{i}hx_j} = \frac{1}{N}\sum_{j=0}^{N-1} f(x_j)\textrm{e}^{-\textrm{i}(k+Nl)x_j} = \frac{1}{N}\sum_{j=0}^{N-1} f(x_j)\textrm{e}^{-\textrm{i}kx_j}\textrm{e}^{-\textrm{i}Nlx_j}\text{.} \] Der letzte Faktor \(\textrm{e}^{-\textrm{i}Nlx_j}\) in jedem Summanden, d.h. für jedes \(j=0,1,\ldots,N-1\) lässt sich mit dem Wissen über den entsprechenden Wert \(x_j = \frac{2\pi j}{N}\) umschreiben. Es gilt mit der Gleichung \(\textrm{e}^{-\textrm{i}\pi} = -1\), dass \[ \textrm{e}^{-\textrm{i}Nlx_j} = \textrm{e}^{-\frac{\textrm{i}2\pi j N l}{N}} = \textrm{e}^{-\textrm{i}2\pi j l} = \bigl(\textrm{e}^{-\textrm{i}\pi}\bigr)^{2 j l} = \bigl((-1)^2\bigr)^{j l} = 1 \] Wobei in der vorletzten Gleichung wieder die Rechengesetze Für Potenzen genutzt wurden und in der letzten, dass beide Zahlen \(j,l\) ganzzahlig sind. Insgesamt vereinfach sich also jeder Summand der Summe des diskrete Fourier-Koeffizient zu \[ c_h^N(f) = \frac{1}{N}\sum_{j=0}^{N-1} f(x_j)\textrm{e}^{-\textrm{i}kx_j}\cdot 1 = c_k^N(f)\text{.} \] Die diskreten Fourier-Koeffizienten wiederholen sich also, so gilt beispielsweise für \(k=0\) und \(l=1,2\) die Gleichheit \(c_0^N(f) = c_{N}^N(f) = c_{2N}^{N}(f)\) oder mit anderen Worten: Durch \(c_k^N(f), k=0,\ldots,N-1\) kennen wir bereits alle diskreten Fourier-Koeffizienten.

Die gerade mathematisch hergeleitete Möglichkeit, sich bei den diskreten Fourier-Koeffizienten \(c_k^N(f)\) auf die Indizes \(k=0,1,\ldots,N\) zu beschränken ergibt, dass die Fourier-Transformation aus \(N\) Eingabewerten, den Abtastwerten von \(f\), genau \(N\) Ausgabewerte produziert. Auch wenn \(f\) selbst unendlich viele \(c_k(f)\) benötigt um beschrieben zu werden, wie etwa bei der Hut-Funktion im Beitrag VII, ist dies für die abgetastete, diskrete Variante anders. Hier bleibt alles endlich und somit am Computer berechenbar.

Insgesamt bietet die diskrete Fourier-Transformation also eine einfache Rechenvorschrift, wie aus \(N\) Datenwerten, die als äquidistante Abtastwerte \(f(x_j)\) einer Funktion \(f\) entstehen, eine Näherung der \(N\) zugehörigen Fourier-Koeffizienten \(c_k(f)\), die sogenannten diskreten Fourier-Koeffizienten \(c_k^N(f)\) bestimmt werden können.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.