Eine Anwendung: Diskrete Fouriertransformation

Zusammenfassung:

Wir wissen aus Kapitel 8.1, dass die Entwicklung einer $2 \pi$ -periodischen Funktion $f$ in ihre Fourierreihe auf die Auswertung der Integrale

$$\frac{1}{2 \pi}\int^{2 \pi}_{0} f (t) \exp ( - i k t) dt$$

führt. Approximiert man ein solches Integral durch eine Summe, erhält man

$$\frac{1}{2 \pi}\int^{2 \pi}_{0} f ( t) \exp ( - i k t) dt \approx... ...^{N-1}_{\ell = 0} f ( \frac{2\pi\ell}{N} ) \exp ( - \frac{2 \pi i k \ell}{N} ).$$

Ein zweites Problem, das auf die Berechnung von Summen des gleichen Typs führt, ist die optimale Interpolation von diskreten periodischen Daten durch trigonometrische Probleme. Auch im Bereich der Datenkompression tritt eine ähnliche Situation auf: Beim Breitband-Filter werden extreme (hohe) Frequenzen eines Signals abgeschnitten und man muss zu endlich vielen Daten $(f_0 , \ldots, f_{N-1})$ die Summen $\hat{f}_k \, : = \, \sum^{N-1}_{\ell = 0} \, f_k \exp ( - \frac{2 \pi i k \ell}{N} )$ berechnen (vgl. Satz von Shannon, 8.18). Analog möchte man aus den Frequenzdaten $(\hat{f}_0 , \ldots, \hat{f}_{N-1} )$ die Signaldaten $(f_0 , \ldots, f_{N-1} )$ zurück gewinnen.
Alle genannten Probleme werden unter dem Thema ``Diskrete Fouriertransformation'' zusammengefasst. Es handelt sich dabei um nichts anderes als einen Basiswechsel in $\mathbb{C}^N$ . Er erfordert in der Regel $N^2$ Multiplikationen. Da $N$ sehr groß sein kann, ist es von größtem Interesse, den Rechenaufwand zu verringern. Dies gelingt mit der schnellen Fouriertransformation (englisch: Fast Fourier Transformation, FFT), die mit $O(N \log(N))$ Multiplikationen auskommt.

Wie oben schon dargestellt, führt die angenäherte Berechnung der Fourierkoeffizienten einer $2\pi$ -periodischen Funktion oder die Interpolation diskreter periodischer Daten auf Summen der Form

$$\hat{f}_k := \sum_{\ell=0}^{N-1} f_\ell \exp (- \frac{2\pi i k \ell}{N}).$$

Wir fassen die Daten $(\hat{f}_k)_{k = 0, \ldots, N-1}$ und $(f_{\ell})_{\ell = 0, \ldots, n-1}$ als Vektoren des $\mathbb{C}^N$ auf.
Die Zuordnung $(f_n) \rightarrow (\hat{f}_k)$ wird diskrete Fouriertransformation genannt. Wir werden diese im folgenden Satz als Basiswechsel im $\mathbb{C}^N$ interpretieren und dabei gleichzeitig die Inverse $(\hat{f}_k) \rightarrow (f_k)$ der diskreten Fouriertransformation beschreiben.

Ist $v \, = \, (v_0 , \ldots, v_{N-1} )^t$ ein (Spalten-) Vektor in $\mathbb{C}^N$ , so bezeichnen wir mit $\overline{v} = ( \overline{v}_0 , \ldots, \overline{v}_{N-1} )^t$ den konjugiert komplexen Vektor.

Satz 10.39   Sei $N \in \mathbb{N}$ und $\omega = \exp ( \frac{2 \pi i}{N} )$ . Sei $v_k = ( 1, \overline{\omega}^k , \overline{\omega}^{2k} , \ldots, \overline{\omega}^{(N-1)k} )^t$ . Dann ist $\{ v_0 , \ldots, v_{N-1} \}$ eine Basis von $\mathbb{C}^N$ .
Ist $F_N$ die mit $v_0, \ldots, v_{N-1}$ als Spaltenvektoren gebildete Matrix, $F_N = (v_0, \ldots, v_{N-1})$ , so ist $F^{-1}_N \, = \, \frac{1}{N} ( \overline{v}_0 , \ldots, \overline{v}_{N-1})$ .

Beweis: Dass $\{ v_0 , \ldots, v_{N-1} \}$ eine Orthonromalbasis bezüglich des Skalarprodukts $[u\vert v] := (u\vert v)/N$ ($(u\vert v)$ : das kanonische Skalarprodukt) ist, wurde in Beispiel 1, S. , gezeigt. Dann ist aber $F^{-1}_N \, = \, \frac{1}{N} \overline{F}_{N} = \frac{1}{N} ( \overline{v}_0, \ldots, \overline{v}_{N-1} )$ , wie man direkt nachrechnet.$\Box$

Bezeichnet man, abweichend von unserer bisherigen Schreibweise, mit $\{ e_0, \ldots, e_{N-1} \}$ die kanonische Orthonormalbasis, also $e_k = (0, 0, \ldots, 0, \underbrace{1}_{k+1. \mbox{Stelle}} , 0, \ldots, 0)^t$ und $f \, = \, \sum^{N-1}_{j=0} \, f_j e_j$ , dann erhält man die Koordinaten von $f$ bezüglich der neuen Basis $B = \{ v_0 , \ldots, v_{N-1} \}$ gerade als $\hat{f} \, = \, F_N f$ . Umgekehrt berechnen sich die Koordinaten von $f$ bezüglich der Basis $\{ e_0 , \ldots, e_{N-1} \}$ aus denen bezüglich $B$ gerade durch $f \, = \, F^{-1}_N \, \hat{f} \, = \,\frac{1}{N} \overline{F}_N \hat{f}$ . Also: $f_k = \frac{1}{N} \sum_{\ell = 0}^{N - 1} \hat{f}_k \exp(\frac{2\pi i k \ell}{N})$ .