~XIII: Die inverse diskrete Fourier-Transformation

Im letzten Beitrag wurde die diskrete Fourier-Transformation eingeführt. Eigentlich sind die Fourier-Koeffizienten als eine Art Baukasten eingeführt worden, denn sie sind Gewichte von gestauchten Sinus- und Kosinus-Funktionen, beispielsweise die Koeffizienten \(a_j\) für \(\cos(jx)\) oder die Koeffizienten \(c_k\) der komplexen Funktion \(\textrm{e}^{\textrm{i}kx}\). Diese Baukasten-Idee ist allerdings in gewissem Sinne die entgegengesetzte Richtung zur diskreten Fourier-Transformation. Während durch bestimmen der Fourier-Koeffizienten \(a_j,b_j\) oder der \(c_k\) eine Funktion \(f\) konstruiert wird, berechnet die diskrete Fourier-Transformation aus Abtastwerten von \(f\) eine Näherung für deren Fourier-Koeffizienten. Die Baukasten-Idee hingegen erzeugt aus der Wahl von Fourier-Koeffizienten eine Funktion \(f\), die wie in der Motivation der letzten beiden Beiträge, wieder nicht am Computer effizient verarbeitbar ist. Das Thema heute beschäftigt sich also mit der Frage: Gibt es eine Umkehrung, oder mathematisch Inversion, der Fourier-Transformation?

Mit Umkehrung ist hier folgendes gemeint: Sind die Werte \(y_j = f(x_j), j=0,\ldots,N-1\) gegeben, beispielweise aus einer Datei im Computer, so berechnet die diskrete Fourier-Transformation daraus die Koeffizienten \(\hat y_k = c_k^N(f), k=0,\ldots,N-1\). Dabei soll im folgenden das ^ stets andeuten, dass es sich bei den Werten um Fourier-Koeffizienten handelt, der Buchstabe aber der gleiche ist. Die Umkehrung bzw. Inversion ist dann eine Rechenregel, die aus den gegebenen Werten \(\hat y_k\) exakt die Werte \(y_j\) zurückbringt, die eigentliche Berechnung also rückgängig macht. Damit ließe sich eine Funktion \(f\) zumindest bezüglich an den diskreten Abtastwerte \(x_j\) so zusammenbauen, wie schon bei der Idee des Baukastenprinzips.

Die inverse diskrete Fourier-Transformation für gegebene Werte \(\hat y_k, k=0,\ldots,N-1\), ist definiert durch \[ y_j = \sum_{k=0}^{N-1} \hat y_k \text{e}^{2\pi\textrm{i}\frac{kj}{N}},\quad j=0,\ldots,N-1. \]

Das erste, was hier auffällt: Die Inverse Fourier-Transformation sieht der eigentlichen Transformation sehr ähnlich. Vor der Summe fehlt der VorfaktorTatsächlich hängt das von der Definition ab, er könnte auch hier stehen, stünde dann jedoch nicht for der DFT. Einige definieren das auch so. Er könnte auch aufgeteilt werden, indem vor beiden Transformationen der Faktor \(\frac{1}{\sqrt{N}}\) verwendet wird. Wichtig ist dann nur, dass man eine Definition konsequent beibehält. \(\frac{1}{N}\). In der Summe findet sich ein kleiner, aber feiner Unterschied: statt \(\text{e}^{-\textrm{i}kx}\) steht hier \(\text{e}^{+\textrm{i}kx}\), also ein Unterschied im Vorzeichen des ExponentenDas Gemeine hier ist, auch diese beiden Definitionen werden gerne vom Namen getauscht, denn welches die Vorwärts-, welches die Rückwärtsrichtung ist, ist nicht definiert. Das ändert allerdings lediglich die Namensgebung; es ändert nicht, dass diese Transformation hier aus den Fourier-Koeffizienten in Abtastwerte überführt..

Das Zweite was auffällt: Die Definition fällt einfach so vom Himmel. In der Tat ließe sie sich mit etwas mehr Wissen, wie die Fourier-Reihe (anstelle der Summe), den Aliasing-Fehler oder -Effekt auch direkt herleiten. Diese beiden Begriffe werden in diesem Blog allerdings erst später eine Rolle spielen. Hier soll eher der Trick durch die Hintertür verwendet werden, indem der Rest dieses Beitrags zeigt, dass die obige Berechnung aus gegebenen Werten \(c_k^N(f)\) eben genau die \(f(x_j\)) zurückliefert, welche als Eingabe der diskreten Fourier-Transformation vorlagen. Kurz: Obige Formel kehrt die Wirkungsweise der diskreten Fourier-Transformation um, invertiert also den Algorithmus. Daher auch die Unterscheidung in den Variablen, denn was die \(\hat y_k\) sind, ist zwar zu Beginn des Rechnens bekannt und die Werte \(y_j\) lassen sich damit berechnen; wie beide jedoch mit \(f\) in Beziehung stehen ist noch nicht geklärt. Die äquidistanten Punkte finden sich in der Formel indirekt, denn sie stehen nun explizit im Exponenten der \(\textrm{e}\)-Funktion.

Vor der eigentlichen Rechnung ist noch eine Vorüberlegung notwendig: Der Wert der Summe \[ \sum_{k=0}^{N-1} \textrm{e}^{2\pi\textrm{i}\frac{jk}{N}}, \] wobei \(j=0,\ldots,N-1\), eine ganze Zahl von \(0\) bis \(N-1\) ist. Den einfachsten Fall erhält man für \(j=0\) dann lautet jeder der \(N\) Summanden \(\textrm{e}^0 = 1\) und die Summe ergibt sich zu \(N\), denn es wird \(N\)-mal die \(1\) addiert.
Ist \(j\) von \(0\) verschieden, so liegt eine geometrische Summe vor. Diese lässt sich allgemein ausrechnen, die allgemeine Form steht in der nachfolgenden Formel links, das Ergebnis der Summe, rechts, lässt sich mit einigen Schritten herleiten: \[ \sum_{k=0}^{N-1} q^k = \frac{1-q^N}{1-q},\qquad \text{ falls }q\neq 1 \] Hier ist also insbesondere wichtig, dass \(q\) nicht \(1\) ist, denn dann würde man auf der rechten Seite durch \(0\) teilen, was man nicht darf. Da auf der linken Seite der Summenindex \(k\) als Exponent am \(q\) steht, ist für die Summe hier \(q = \textrm{e}^{2\pi\textrm{i}\frac{j}{N}}\) und für \(j=1,\ldots,N-1\) ist dieser Ausdruck von \(1\) verschieden, denn \(\frac{j}{N}\) ist keine ganze Zahl und somit \(2\pi\textrm{i}\frac{j}{N}\) kein ganzzahliges Vielfaches von \(2\pi\), dem KreisumfangFür \(j=N\) entsteht somit exakt die Situation, die für \(j=0\) entsteht.. Im Nenner auf der rechten Seite tritt nun ein \(q^N\) auf. Das lautet hier also nach den Potenzregeln \( \textrm{e}^{2\pi\textrm{i}\frac{j}{N}N} = \textrm{e}^{2\pi\textrm{i}j}\). Die Zahl \(j\) ist jedoch eine ganze Zahl und damit ist wegen \(q^N = 1\) der Nenner \(1-1 = 0\) und somit die Summe \(0\). Außer der Tatsache, dass \(\textrm{e}^{2\pi\textrm{i}} = \bigl(\textrm{e}^{\pi\textrm{i}}\bigr)^2 = (-1)^2 = 1\), wurden hier nur einfache Rechenregeln verwendet. Trotzdem ist das Ergebnis erstaunlich. Es gibt allerdings auch eine bildliche Erklärung. Die Abbildung 1 stellt die Werte in der Gaußschen Zahlenebene dar.

\(N\) 1 \(j\)    1
Darstellung der Summanden in der Gaußschen Zahlenebene für verschiedene \(N\) und \(j\le N\). Beim Überfahren eines Knoten zeigt die Grafik, mit welchen diese sich zu \(0\) addieren.

Für \(j=0\) ist dies \(N\)-mal der Wert \(1\), da \(\textrm{e}^0=1\) giltFür \(j=N\) sind die Summanden ebenso alle \(\textrm{e}^{2\pi\textrm{i}N} = 1\).. Für \(j=1\) sind dies die \(N\) gleichverteilten Punkte auf dem Kreis, bei denen sich für gerade Werte von \(N\) gegenüberliegende Werte zu \(0\) addieren. Dies wird durch die beiden Vektoren mit Länge \(\frac{1}{2}\) angezeigt, denn jeder Vektor tritt in allen gezeigten Vektoren zweimal auf, einmal bei seinem eigenen Wert, einmal beim gegenüberliegenden. Für ungerade \(N\) gibt es keinen Knoten, der auf dem Kreis direkt gegenüberliegt. Dort entsteht aber ein ähnlicher Effekt durch die Summe der beiden Punkte, die links und rechts des gegenüberliegenden Kreissegmentes liegen. Hier nimmt jeder Knoten an drei Pfeilpaaren teil: Zweimal als auf Länge \(\frac{1}{4}\) gekürzter Teil eines gegenüberliegenden Paares, einmal als auf Länge \(\frac{1}{2}\) gekürzter Vektor. Insgesamt tritt also für alle \(N\) jeder Vektor genau einmal in den Vektorpaaren auf. Alle Vektorpaare bzw. -dreiergruppen sind in der Grafik außerdem mit grauen Linien verbunden. Jede dieser Zweier- bzw. Dreiergruppen summiert sich einzeln bereits zu \(0\), so \(j\neq 0\) ist, womit auch die gesamte Summe in diesem Fall \(0\) ist.is \(j>1\), so treten in vielen Fällen nur ein Teil der Punkte auf. Genauer sind dies immer dann weniger, wenn die eigentliche Punktanzahl \(N\) durch \(j\) ohne Rest teilbar ist. Dies wird in der Grafik verdeutlicht, indem zu einem Knoten alle Werte \(k, k=0,1,\ldots N-1\) angezeigt werden, für die \(jk\) eben diesen Punkt (nur dann durch mehrfaches Umlaufen des Kreises) ergibt.

Zusammenfassend ist also, mit einer Fallunterscheidung, \[ \sum_{k=0}^{N-1} \textrm{e}^{2\pi\textrm{i}\frac{jk}{N}} = \begin{cases} N & \mbox{falls } j=0,\\ 0 & \mbox{falls } j=1,\ldots,N-1. \end{cases} \] Analog funktioniert diese Überlegung auch für \(j=-(N-1),\ldots,-1\).

Um zu prüfen, was die inverse diskrete Fourier-Transformation nun berechnet, seien die Abtastwerte \(f\bigl(\frac{2\pi j}{N}\bigr), j=0,\ldots,N-1\) gegeben und die diskreten Fourier-Koeffizienten \(c_k^N(f)\) nach der Formel im letzten Beitrag berechnet. Ziel ist es nun, zu zeigen, dass die inverse diskrete Fourier-Transformation mit den \(\hat y = c_k^N(f)\) als Eingabe eben genau die Abtastwerte wieder liefert. Als Formel seien diese also oben eingesetzt: Für ein festes \(j=0,\ldots,N-1\) gilt \[ y_j = \sum_{k=0}^{N-1} c_k^N(f) \text{e}^{2\pi\textrm{i}\frac{kj}{N}} = \sum_{k=0}^{N-1} \Bigl(\frac{1}{N}\sum_{l=0}^{N-1} f\bigl(\frac{2\pi l}{N}\bigr)\text{e}^{-2\pi\textrm{i}\frac{lk}{N}}\Bigr) \text{e}^{2\pi\textrm{i}\frac{kj}{N}}. \] Hier wurde wieder er explizite Wert jedes Abtastpunktes \(x_j\) eingesetzt. Außerdem wird die Variable \(l\) für die innere Summe verwendet, da das \(k\) sonst doppelt vergeben wäre. Da die Summen endlich sind, dürfen sie vertauscht werden, oder man multipliziert die große Klammer aus und fasst sie andersherum wieder zusammen. Dies ergibt für den zu bestimmenden Wert \[ y_j = \sum_{l=0}^{N-1}f\bigl(\frac{2\pi l}{N}\bigr) \Bigl(\frac{1}{N}\sum_{k=0}^{N-1} \text{e}^{2\pi\textrm{i}\frac{kj}{N}}\Bigr) \text{e}^{-2\pi\textrm{i}\frac{lk}{N}}. \] Hier darf das \(f\bigl(\frac{2\pi l}{N}\bigr)\) aus der inneren Summe ausgeklammert und somit vor die Summe geschrieben werden, da kein \(k\) darin vorkommt. Zieht man nun den hintersten Faktor noch in die Summe hinein, so erhält man \[ y_j = \sum_{l=0}^{N-1}f\bigl(\frac{2\pi l}{N}\bigr) \Bigl(\frac{1}{N}\sum_{k=0}^{N-1} \text{e}^{2\pi\textrm{i}\frac{(j-l)k}{N}}\Bigr). \] An dieser Stelle brauchen wir die Vorüberlegung: Jede innere Summe (über \(k\)) enthält einen festen Wert \(j-l\), der zwischen \(-(N-1)\) und \(N-1\) liegt. Ist \(j\neq l\), so ist dieser Wert eine der von \(0\) verschiedenen Zahlen. Dann ist die Summe \(0\) und es bleibt \(f\bigl(\frac{2\pi l}{N}\bigr)\frac{0}{N} = 0\), der Term verschwindet. Für \(j=l\) bleibt \(f\bigl(\frac{2\pi l}{N}\bigr)\frac{N}{N} = f\bigl(\frac{2\pi j}{N}\bigr)\). Insbesondere ändert sich das \(l\) im Argument von \(f\) zu \(j\), was erlaubt ist, da \(l=j\) gilt. Dies ist aber auch der einzige Term, der verbleibt. Das Ergebnis der inversen diskreten Fourier-Transformation mit den diskreten Fourier-Koeffizienten als Eingabe ist also \[ y_j = f\bigl(\frac{2\pi j}{N}\bigr),\quad j=1,\ldots,N \] Dies bedeutet aber, dass die inverse diskrete Fourier-Transformation, wenn sie Koeffizienten \(c_k^N(f)\) als Eingabe erhält, genau die Abtastwerte \(f(x_j)\) wieder zurückliefert. Somit ist sie die Umkehrung der diskreten Fourier-Transformation und genau so eine Rechenvorschrift war Ziel dieses Beitrags.

Schreibe einen Kommentar

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