Die Fourier-Transformation begegnet einem oft in der Physik und der Mathematik, was bedeutet, dass sie auch viele alltägliche Anwendungen hat.
Kurz gesagt nimmt die Fourier-Transformation ein Eingangssignal, oft im Zeit- oder Ortsbereich, und wandelt es in den Frequenzbereich um. Konkret: Bei einem Eingangssignal, das aus einem Durcheinander (also einer Superposition) verschiedener Frequenzen besteht, trennt die Transformation die einzelnen Frequenzen heraus und zeigt ihre relativen Stärken.
Das macht die Transformation zu einem wichtigen Werkzeug in der Signalverarbeitung (z. B. Filterung, Kompression usw.) und in vielen Anwendungen der Datenwissenschaft. Deshalb wird sie vielleicht weiter verbreitet eingesetzt, als man zunächst denkt, was sie zugleich zu einem Paradebeispiel dafür macht, dass imaginäre Zahlen unverzichtbar sind, denn die Ausgabe der Fourier-Transformation ist im Allgemeinen eine komplexe Zahl.
Die Fourier-Transformation hat zwar eine Integralformulierung, aber wir arbeiten digital, also interessiert uns die diskrete Version. Die Herleitung der Transformation sprengt den Rahmen dieser Übung, doch die diskrete Transformation (in den Frequenzbereich) hat die folgende Form:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
Dabei läuft die Summe über n, und N ist die Anzahl der Abtastwerte, k ist die Frequenz, i die imaginäre Einheit und xₙ ein einzelner Abtastwert.
Die Fourier-Transformation ist zwar äußerst nützlich, aber naiv implementiert etwas langsam (O(n²)). Die schnelle Fourier-Transformation (FFT) ist ein Algorithmus, der das drastisch beschleunigt. Das geschieht üblicherweise mit einer Teile-und-herrsche-Strategie, die einige Symmetrien in der Formulierung ausnutzt und asymptotisch zu einer Komplexität von O(Nlog(N)) führt. Diese Beschleunigung verbessert die Praktikabilität und die Bandbreite der Anwendungen, für die sich die Transformation eignet, erheblich.
