Hoffen wir mal, dass die, die im Schlosspark liegen, was verpassen
heute.
Also, ich möchte heute nochmal das Thema, das wir zuletzt hatten, die
Polynom -Multiplikation mittels Fourier-Transformation, nochmal
manuell nachvollziehen und miterleben und dann wechseln zu dem Thema
der Signalverarbeitung, wo das Thema Fourier-Transformation auch
wieder eine wichtige Rolle spielt.
Ja, also nochmal zur Erinnerung, wir hatten gesagt, wir machen Polynom
-Multiplikation mittels schneller Fourier-Transformation, indem wir
sagen, wir haben ein Polynom p und ein Polynom q.
Anstatt die mit einem O-von-n-Quadrat-Algorithmus zu multiplizieren
und dann p mal q rauszukriegen, haben wir gesagt, stattdessen machen
wir eine Transformation.
Diese haben wir FFT genannt für schnelle Fourier-Transformation oder
DFT für diskrete Fourier-Transformation, wenn man es nicht auf die
Geschwindigkeit ankommen lässt.
Das, was rauskam, ging dann in einen einfachen O-von-n-Multiplizierer,
nämlich in der Punktedarstellung und dann haben wir es zurückgewandelt
mit der FFT hoch minus 1 und haben dann das Produkt herausgekriegt.
Das war die Idee.
Ich möchte das jetzt gerne mal für ein Beispiel manuell
nachvollziehen, so zum Miterleben.
Das Beispiel, das wir nehmen, ist das mit p gleich x plus 2 und q
gleich 2x minus 1.
So, wir haben jetzt p hat Grad 1 und q hat Grad 1,
das heißt p mal q hat ein Grad 2.
Das heißt, wir brauchen mindestens drei Punkte, um p mal q exakt
festzulegen.
Also wählen wir die DFT 4.
Die hat mindestens drei Punkte.
Und damit wir hinterher eine schnelle Fourier-Transformation machen
können, wählen wir halt eine Zweierpotenz.
Wir hätten es auch mit der DFT 3 machen können, sieht aber erstens
hässlich aus und zweitens kann man damit keine schnelle Fourier
-Transformation machen.
Also, betrachten wir jetzt den Vektor zu p, den Koeffizientenvektor.
Der ist also 2 mal x hoch 0, 1 mal x hoch 1, 0 und 0.
Dann den Koeffizientenvektor für q, der ist minus 1 mal x hoch 0, 2
mal x hoch 1, 0 und 0.
Das heißt, diese hohen Koeffizienten, x quadrat, x hoch 3, die füllen
wir nicht aus, da haben wir halt eben Koeffizienten 0.
Dann käme als nächster Schritt die DFT 4, diese Matrix, die wir
kennengelernt haben, mal der Vektor p, um das Polynom p an vier
Stellen auszuwerten.
Das heißt, wir brauchen diese DFT Matrix, die hat er ja hier überall
einzeln.
Dann haben wir die vierte Einheitswurzel, was hoch 4 ergibt 1, aber
nicht 1 selbst.
I quadrat ist minus 1, minus 1 zum Quadrat ist 1, also ist I eine
vierte Einheitswurzel.
Dann kommt hier I quadrat hin, das ist minus 1, hier I hoch 3, das ist
minus I.
Dann kommt hier unten I quadrat hin, also minus 1, dann I hoch 4, plus
1, I hoch 6, minus 1.
Und in der letzten Zeile, I hoch 3, das ist minus I, I hoch 6, das ist
minus 1 und I hoch 9, das ist plus I.
So, das ist die DFT 4, die wird jetzt multipliziert mit dem
Koeffizientenvektor 2, 1, 0, 0 von p.
Das ergibt, gar nicht mal so dramatisch, erste Zeile mit erster
Spalte, also 1 mal 2 plus 1 mal 1 plus 1 mal 0 plus 1 mal 0 ist 3.
Dann zweite Zeile, 1 mal 2 plus 1 mal I ist 2 plus I.
Die dritte Zeile, 1 mal 2 minus 1 mal 1 ist 1 und die letzte Zeile, 1
mal 2 minus 1 mal I, das ist 2 minus I.
So, was heißt das also?
Das heißt, das Polynom p geht durch die Punkte 1, 3, dann durch den
Punkt I, 2 plus I, dann durch den Punkt minus 1, 1 und schließlich
noch durch den Punkt minus I, 2 minus I.
Das haben wir jetzt festgestellt.
Wir haben also mit dieser Matrixmultiplikation das Polynom p an vier
Stellen ausgewertet.
An der Stelle 1, an der Stelle I, an der Stelle minus 1 und an der
Stelle minus I.
Oder mit anderen Worten, an der Stelle vierter Einheitswurzel hoch 0,
vierter Einheitswurzel hoch 1, vierter Einheitswurzel hoch 2 und
vierter Einheitswurzel hoch 3.
Also man könnte auch sagen, an diesen Stellen 1, I, minus 1, minus I.
An diesen Stellen haben wir das Polynom ausgewertet.
Jetzt müssen wir im Prinzip das gleiche nochmal für Q machen.
Also die DFT4 mal den Vektor Q.
Das ist hier zunächst mal die gleiche Matrix.
Ich deute das mal so an.
Mal minus 1, 2, 0, 0.
Das gibt 1, 1, 1, 1, 1.
Also minus 1 und 2 ist 1.
Dann einmal minus 1, plus 2 mal I, das ist also 2I minus 1.
Dann einmal minus 1, minus 1 mal 2, das ist minus 3.
Und zum Schluss einmal minus 1 und 2 mal minus I, das ist minus 2I
minus 1.
Ich mache das auswendig, also wenn ich mich verrechne, dann rufen Sie
dazwischen.
Okay, das heißt also jetzt, dass das Polynom Q auch durch vier Punkte
geht, nämlich durch die Punkte 1, 1, 2I minus 1, minus 1, minus 3 und
minus 2I minus 1.
So, jetzt haben wir also das Polynom P an vier Punkten ausgewertet,
das Polynom Q auch an den selben vier X-Koordinaten.
Das heißt jetzt, unter der Vorstellung wie wir es da vorhin hatten,
also aus dieser quadratischen Überkreuzmultiplikation machen wir eine
punktweise O-von-N-Multiplikation, dass jetzt die Fourier
-Transformierte, ich schreibe mal F, die Fourier-Transformierte von P
mal Q, das ist die Fourier-Transformierte von P. Und jetzt punktweise
multiplizieren, ich mache mal dieses Symbol dafür, mit der Fourier
-Transformierten von Q.
Also, 3, 2 plus I, 1, 2 minus I, punktweise multiplizieren mit 1, 2I
minus 1, minus 3, minus 2I minus 1.
Das ergibt, 3 mal 1 ist 3, dann hier 2 mal 2I, das sind 4I, dann plus
2I quadrat, minus I, plus 2 und hier unten 1 mal minus 3 ist minus 3.
Und die letzte Zeile, minus 4I, dann haben wir noch minus 2, dann plus
2I quadrat und plus I.
Jetzt fehlt hier irgendwo das Quadrat.
Das ist ein Quadrat.
So, das ist also 3 ist 3, dann haben wir hier 4I minus 1I, das sind 3I
und I quadrat ist minus 1.
Stimmt, hier muss ein minus stehen.
Danke, bitte, 2, hier muss ein minus stehen, genau.
Das ist minus 2 und noch mal minus 2 ergibt minus 4, dann hier minus 3
bleibt minus 3 und in der letzten Zeile haben wir minus 4I plus I, das
ist minus 3I und dann haben wir hier auch noch mal minus 4, genauso
wie oben.
Das heißt, das Polynom P mal Q, also das Produkt von P und Q geht
durch die Punkte 1, 3, I, 3I minus 4, minus 1, minus 3 und minus 3I
minus 4.
Jetzt wissen wir, durch welche Punkte das Produkt durchgeht, also wir
können sagen, P mal Q geht durch 1, 3, I, 3I minus 4, minus 1, minus 3
und minus 3I minus 4.
Minus I, minus 3I minus 4, wenn ich nicht was vergessen habe.
Okay, also das heißt, das Polynom P mal Q als Vektor dargestellt ist
jetzt was?
Naja, eben, das ist die DFT hoch minus 1 mal und zwar eben diese
Punkte 3, 3I minus 4, minus 3 und minus 3I minus 4.
Okay, jetzt brauchen wir nur noch die DFT 4 hoch minus 1.
DFT 4 hoch minus 1, das ist irgendeine Matrix, also wir hatten gesagt,
das ist ein Viertel oder ein Entel im Allgemeinen für die DFT N und
dann wird jeder Wert der ursprünglichen DFT Matrix invertiert.
Also ich schreibe nochmal die Originale hin, DFT 4 ist 1, 1, 1, 1, 1I,
minus 1, minus I, 1, minus 1, 1, minus 1, 1, minus I, minus 1, I.
So, jetzt jeden Wert invertieren, die Inversen von 1 sind alle 1, also
bleibt hier überall 1 stehen.
Die Inverse von I, 1 durch I, was ist 1 durch I?
Welche Zahl mit I multipliziert ergibt 1?
Minus I, bravo.
Dann die Inverse von minus 1 ist minus 1 und dann ist entsprechend die
Inverse von minus I plus I.
Minus 1 ist minus 1, 1 ist 1, minus 1 ist minus 1 und das hatten wir
ja schon, die Inverse von minus I ist I, von minus 1 minus 1 und von I
minus I.
So, jetzt können wir es also ausrechnen.
DFT 4 hoch minus 1 mal PQ, mal diesen Vektor, das ist das hier.
Machen wir den Strich weg.
Mal 3, 3I minus 4, minus 3, minus 3I minus 4.
Das ist also, jetzt haben wir hier 3 plus 3I minus 4, minus 3, minus
3I minus 4.
Das ist die erste Zeile.
Die zweite Zeile, einmal 3 ist 3, minus I, also minus 3I quadrat.
Dann die minus 1, das gibt mit der minus 3, gibt plus 3.
Oh, halt, minus 4I habe ich vergessen.
Also, minus 4I, dann minus 1 mal minus 3 ist plus 3 und I mal das ganz
unten, das ist minus 3I quadrat, minus 4I.
So, dritte Zeile, einmal 3 ist 3, minus 1 mal die Sache, das gibt
minus 3I plus 4.
Einmal minus 3 ist minus 3 und minus 1 mal das ganz unten, das gibt
also plus 3I plus 4.
Und die letzte Zeile noch, einmal 3 ist 3, I mal diese Geschichte,
gibt also plus 3I quadrat, minus 4I.
Ja, ich habe schon ein Fehlerchen entdeckt, das muss ein Plus sein,
gell?
Okay, und dann gehen wir weiter hier unten, machen wir noch fertig.
Minus 1 mal minus 3 gibt plus 3 und minus I mal die ganze Geschichte
gibt plus 3I quadrat plus 4I.
So, jetzt noch zusammenfassen, das ist, hier oben haben wir, können
wir jetzt schön, 3 und 3 fällt weg, 3I und 3I fällt weg, bleibt also
noch minus 8.
Bitte?
Der Kommentar war, dass ein Viertel fehlt noch, stimmt, das habe ich
noch nicht hingeschrieben, ist aber auch nicht weiter tragisch, mal
ein Viertel, also ein Viertel.
Okay, weiter, dann nächste Zeile, hier haben wir plus 4I minus 4I
fällt weg, dann haben wir 3I quadrat, das ist, I quadrat ist minus 1,
also 3I quadrat ist minus 3 mal minus 1 ist plus 3.
Das gleiche hier, also haben wir 3 plus 3 plus 3 plus 3 ist 12.
Hier haben wir minus 3I plus 3I fällt weg, 3 minus 3 fällt weg, dann
haben wir noch 2 mal die 4, das gibt 8.
Und jetzt können Sie gleich vorhersagen, was unten rauskommen muss,
weil das Ergebnis des Polynoms ist ja dritten Grades, also muss hier
unten ein 0 sein, wir können es trotzdem nachprüfen.
Wir haben hier minus 4I plus 4I, dann haben wir 3I quadrat, das ist
minus 3, 3I quadrat ist minus 3, hier haben wir die 3 in einmal mit
plus und nochmal mit plus, also kommt tatsächlich ein 0 raus.
Jetzt noch mit ein Viertel multipliziert, haben wir also minus 2, 3,
2, 0.
Machen wir wieder richtige Farben hier.
Also das p mal q von x können wir jetzt schreiben, einfach hier
ablesen als minus 2 plus 3x plus 2x quadrat.
So funktioniert diese Multiplikation über die diskrete Fourier
-Transformation.
Was wir jetzt aber nicht gemacht haben, war die schnelle Fourier
-Transformation.
Und das gucken wir uns jetzt mal an, was daran jetzt so viel einfacher
wäre.
Jetzt schnell, also FFT statt DFT, wobei das eigentlich ja nicht statt
ist, sondern FFT ist ein Algorithmus, um die DFT-Multiplikation zu
berechnen.
Es ist ja nicht irgendwas völlig verschiedenes, man kann die DFT so
wie wir es eben berechnet haben, oder aber auch schnell machen, so wie
wir es jetzt machen.
Also ich schreibe nochmal hin, der Vektor p war 2, 1, 0, 0.
Also p war 2, 1, 0, 0 und der Vektor q war 1, minus 2, 0, 0.
So und jetzt FFT heißt.
Die Matrix ist die gleiche, die FFT 4.
Bitte?
Q hatte andersrum die Vorzeichen?
Moment, eben habe ich doch nachgeguckt.
Tatsächlich, minus 1, 2.
Die Matrix ist die gleiche, also FFT 4 mal p, das ergibt.
Ich rechne jetzt nur mal dieses eine für p aus, also das q soll uns
mal nicht interessieren, das wird ja dann nur langweilig.
Also nur diese eine Polynom-Auswertung für p, das gibt also diese
Matrix 1, 1, 1, 1, 1, 1, i, minus 1, minus i, 1, minus 1, 1, minus 1,
1, minus i, minus 1, i.
Weiß man inzwischen auswendig.
Mal 2, 1, 0, 0.
So und jetzt kommt die schnelle Geschichte.
Wir sagen, wir gucken uns die obere Hälfte der Matrix an und die
untere kriegen wir dann geschenkt.
Also obere Hälfte,
da steht 1, 1, 1, 1, 1, i, minus 1, minus i, mal 2, 1, 0, 0.
Und jetzt erinnern Sie sich, haben wir das nochmal aufgeteilt in
gerade und ungerade.
Also gerade, das war 1, 1 und 1, minus 1.
Kann ich nochmal andeuten, das sind diese hier,
die mit 0 und 2, Position 0 und 2.
Mal hier jetzt die Geraden, das ist 2 und 0, also diese hier, Position
0 und 2.
Und die andere Hälfte, die ungeraden, das ist 1, 1, i, minus i.
Können wir auch markieren, das wären eben diese da, an den Positionen
1 und 3.
Auch hier wieder multipliziert mit den entsprechenden ungeraden
Stellen von P, also mal 1, 0.
So, das gibt 1 mal 2 plus 1 mal 0 ist 2, 1 mal 2 minus 1 mal 0 ist 0.
Ziemlich einfache Rechnung und die Rechnung hier ist 1 mal 1 und i mal
1.
So, fertig.
Warum wir jetzt schon fertig sind, das können wir gleich sehen.
Ich habe ja gesagt, wir können uns die untere Hälfte sparen.
Rechnen aber trotzdem, was passiert wäre und sehen dann, warum wir es
uns hätten sparen können.
Also die untere Hälfte, die wäre dann 1, minus 1, 1, minus 1, 1, minus
i, minus 1, i, multipliziert mit 2, 1, 0, 0.
Auch wieder auftrennen in gerade.
Das gibt 1, 1, 1, minus 1, mal 2, 0.
Sehen Sie, hätte man es sparen können.
Ist genau die gleiche Rechnung wie eben.
Ist 2, 0.
Ich kann es nochmal markieren.
Das hier.
Tatsächlich.
Aber auf jeden Fall muss es das gleiche sein.
1 mal 2, genau.
Auf jeden Fall auch hier.
Die allergleiche, völlig identische Rechnung.
Und die andere Seite, die ungerade Seite, die sieht einen Hauch anders
aus.
Da haben wir halt jetzt hier, da stehen minus 1, minus 1 und unten
minus i, i.
Sieht ein bisschen anders aus, aber wenn Sie gucken, dann sehen Sie,
diese Matrix hier, diese minus 1, minus 1, minus i, i, ist genau das
Negative von der 1, 1, i, minus i.
Also wenn wir das mit 1, 0 multiplizieren, dann kommt genau raus,
minus 1, minus i.
Hätten wir es auch sparen können, das ist nämlich einfach nur das
Negative von dem Ungeraden hier.
Hier haben wir ja schon 1, i ausgerechnet.
Wir müssen nur die Vorzeichen umkippen, schon haben wir diesen Anteil.
Das heißt, wir hätten uns tatsächlich diese ganze untere Hälfte
-Geschichte sparen können.
Und die ganzen Ergebnisse, die wir dafür brauchen, haben wir schon
berechnet, indem wir diese Multiplikation in der oberen Hälfte gemacht
haben.
Was jetzt noch fehlt, ist einfach nur noch die Summe.
Wir haben hier also 2, 2 und 1, i.
Wir haben gesagt, gerade und ungerade muss aufaddiert werden, das
ergibt also 3, 2, plus i.
Und unten haben wir 2, 2, plus minus 1, minus i.
Das ergibt, 2, minus 1, ist 1 und 2, minus i, ist 2, minus i.
So, jetzt können wir noch vergleichen, ob das stimmt.
3, 2, plus i, 1, 2, minus i.
Kommt tatsächlich genau das gleiche raus.
Und wenn Sie jetzt mal zählen, wie viele Multiplikationen haben wir
hier bei dem Zu-Fuß-Weg gerechnet und wie viele Multiplikationen haben
wir mit der FFT gemacht, dann werden Sie feststellen, dass es deutlich
weniger sind.
Diese ganze untere Hälfte-Geschichte können wir uns sparen.
So also hilft uns die schnelle Fourier-Transformation.
Beim Auswerten von Polynomen.
Und das wiederum brauchen wir zum Multiplizieren von Polynomen oder
auch von großen Zahlen.
Aber nicht nur das.
Und das wäre dann das nächste Thema.
Also hier steht es nochmal nicht ganz so ausführlich, aber besser
leserlich da.
Und damit kommen wir zum nächsten Thema, nämlich der Fourier
-Transformation im allgemeinen Fall, nicht nur im digitalen Fall.
Und das ist durchaus auch ein für Informatiker ziemlich interessantes,
relativ wichtiges Thema.
Ich habe hier mal ein paar Anwendungen hingemalt, kopiert, wo Sie
sehen können, wo überall so eine Fourier-Transformation Verwendung
findet.
Also wenn Sie zum Beispiel JPEG-Bilder gesehen haben und wenn Sie im
Internet surfen, sehen Sie die dauernd, dann wird in diesen JPEG
-Bildern zur Kompression die Fourier-Transformation verwendet.
Wenn Sie schon mal MP3-Audios abgespielt haben, und wer hat das nicht,
auch darin wird die Fourier-Transformation verwendet, um diese Audios
zu komprimieren.
Wenn wir Spracherkennung machen, das ist das, was wir am Institut
besonders gern machen, dann schicken wir erstmal dieses Sprachsignal
durch eine Fourier-Transformation und arbeiten dann weiter.
Sogar Videos, auch MPEG-Videos, auch die verwenden Fourier
-Transformation, um bestimmte Sachverhalte aus einem Video zu
erfassen, die wichtig sind, die Unwichtigen wegzulassen und so das
Ding zu komprimieren.
Ich habe da mal oben ein paar Bilder genommen von mir und dazu
geschrieben, auf wie viele Bytes man das runter komprimieren kann,
wenn man bei einer JPEG-Abspeicherung verschiedene Kompressionsraten
angibt.
Das stimmt zwar irgendwie nicht ganz mit den Prozenten, aber naja, ich
habe einfach mal diese Prozente eingegeben und das ist, was
rausgekommen ist.
Wenn wir das Bild als ganz normales Windows-BMP hernehmen, dann hat es
24 KB.
Als GIF ist es schon ein bisschen weniger, nur noch 17 KB knapp.
Aber als JPEG auf 75%, also die 75% Kompression liefert natürlich
deutlich mehr als nur auf 75% runter, reduziert die File-Größe auf
5889 Bytes, also schon deutlich weniger und eigentlich kann man kaum
Qualitätsunterschiede erkennen.
Ich sehe genauso hübsch aus wie auf dem ersten Bild.
Bei 25% da fängt es dann schon an, ein bisschen unsauber zu werden,
ist aber auch schon wieder deutlich kleiner.
Bei 10% da merkt man, da kann man die Person noch erkennen, vielleicht
auch sogar bei 5%.
Aber interessanterweise, selbst bei 1%, wo dann wirklich nur noch
grobe Klötze da sind, kann man, wenn man so ein bisschen die Augen
zukneift, immer noch erkennen, um wen es sich handelt.
Und die Daten sind ziemlich klein geworden, nur noch so ein gutes
Kilobyte, also heftig reduziert.
Ja, und die Frage ist, wie macht man das?
Wie berechnet man sowas sinnvollerweise?
Naja, was diese Fourier-Transformation macht, ist, sie stellt
tatsächlich fest, aus welchen Anteilen ist dieses Bild
zusammengesetzt.
Das Bild besteht aus vielen Anteilen, aus grobmaschigen Anteilen,
könnte man sagen, und aus feinmaschigen Anteilen.
Und es sagt sich einfach, diese feinmaschigen Anteile, also welche
Muster da jetzt genau auf der Krawatte sind, das ist ziemlich
unwichtig.
Das machen wir raus und lassen nur noch diese grobmaschigen übrig.
Und dann kommt eben etwas derartiges raus wieder hinten.
Ja, und heute und nächstes Mal wollen wir uns angucken, wie das
gemacht wird.
Ja, dazu fangen wir mal an.
Also wie könnte man denn überhaupt irgendein Signal,
ein Video, ein Bild oder eine Tonaufnahme, zerstückeln in irgendwas
Fein - und irgendwas Grobmaschiges?
Die Standardvorstellung ist hierbei die, und wir fangen mal jetzt im
eindimensionalen Fall an, also wir kümmern uns ab jetzt nur noch um
eindimensionale Sachen, also wie zum Beispiel Sprachsignale, da ist
die Vorstellung, wir könnten so ein Signal zerstückeln oder ansehen
als Summe von irgendwelchen gewichteten, einfachen Funktionen, zum
Beispiel Kosinussen und Sinussen.
Das wäre so eine Vorstellung, wie wäre es, wenn wir sagen würden, wir
versuchen ein Signal so darzustellen, dass wir schreiben, es ist, also
das wäre f von x, f von x ist sowas wie ein Halb a null, also
irgendein Offset von der x-Achse weg, und dann irgendein Faktor a1 mal
Kosinus x und ein Faktor b1 mal Sinus x und dann noch etwas stärkere
Schwingungen wie Kosinus 2x und Sinus 2x jeweils mit a2 und b2
multipliziert und so weiter, ganz allgemein bis an Kosinus nx und bn
Sinus nx und meinetwegen unendlich lang weiter.
Das sind wieder diese Pünktchen, wo der zweite Satz hier fehlt.
So, vielleicht hatten Sie das schon in der Mathematik, wenn nicht,
dann erwähne ich es.
So eine Reihe, wie sie da steht, nennen wir trigonometrische Reihe.
Also so eine Summe von gewichteten Sinusen und Kosinusen mit
unterschiedlichen Frequenzen hier drin.
Also so ein Sinus x sieht ja so aus und so ein Sinus 2x sieht ja so
aus, ungefähr.
Und so ein Sinus 3x sieht dann halt eben noch schneller schwingend aus
und so weiter.
Und Sinus nx ist natürlich eine Funktion, die ganz brutal schnell rauf
und runter geht.
Je nachdem, wie groß das n wird, umso höher wird die Frequenz.
Deswegen können wir sagen, n ist sozusagen die Frequenz von dem Sinus.
Ja, und wenn wir so eine trigonometrische Reihe haben, dann ist die
durch diese Werte a0 bis an und b0 bis bn spezifiziert.
Damit ist die angegeben, das sind also die Koeffizienten dieser Reihe.
Jetzt könnte es natürlich sein, dass die gar nicht konvergiert.
Kann schon sein, ja.
Wissen wir noch nicht, aber interessiert an der Stelle noch nicht so
sehr, ob sie konvergiert oder nicht.
Das sollen die Mathematiker machen.
Für uns reicht es zu wissen, wenn sie konvergiert, an irgendeiner
Stelle t, also wenn f von t echt definiert ist, dann natürlich auch f
von t plus 2pi, weil Sinus t und Sinus t plus 2pi ist das gleiche.
Genauso bei Kosinus.
Kosinus t und Kosinus t plus 2pi ist auch das gleiche.
Und es gibt natürlich auch für Kosinus nx und auch für Sinus nx, also
das funktioniert immer.
Also ganz allgemein, wenn sie an irgendeiner Stelle konvergiert, an
der Stelle t, dann auch bei t plus beliebliche Vielfache von 2pi.
Soweit alles klar?
Ja, wenn es jetzt so wäre, dass sie überall konvergiert, dann ist sie
automatisch periodisch.
Dann ist sie ja, genauso wie Sinus und Kosinus periodisch sind, ist
die Funktion auch periodisch.
Ein paar Spezialfälle können wir uns angucken, wenn wir nämlich alle
As auf 0 setzen oder alle Bs auf 0 setzen.
Wenn alle As 0 sind, das heißt, alle Kosinus haben keinen Faktor vorne
dran stehen.
Dann haben wir also irgendwas mit Sinus plus Sinus plus Sinus plus
Sinus.
Und Sie wissen, dass der Sinus eine ungerade Funktion ist, also Sinus
x ist Sinus minus x.
Und das gilt natürlich auch für Sinus 2x, 3x und so weiter.
Also ist auch die ganze Summe ungerade.
Und umgekehrt, wenn wir die Bs alle auf 0 setzen, dann fallen alle
Sinus weg und wir haben nur noch Kosinus plus Kosinus plus Kosinus.
Also gerade Funktion plus gerade plus gerade, es bleibt gerade.
Also kommen wir dann auf eine gerade Funktion.
Das ist nur so eine Vorweguberlegung, später werden wir dann sehen, an
welcher Stelle sich das wiederfindet.
So, und jetzt war das...
Warum steht es hier noch nicht, dass es eine Furie-Reihe ist?
Naja gut, dann verpätze ich es halt an der Stelle schon.
Diese Vorstellung, dass man eine Funktion so schreiben kann, als Summe
von irgendwelchen Sinusen und Kosinusen, die geht zurück auf, wie hieß
er, Jean-Joseph-Baptiste Fourier.
Einer von den genialen Mathematikern aus der Zeit, als in Frankreich
noch die Mathematik richtig Weltruhm hatte.
Und dem seine Idee war, eigentlich kann man jede Funktion so
schreiben, jede beliebige.
Und natürlich hat er da viel Ärger geerntet, da kamen dann die anderen
Mathematiker, die da schon etabliert waren, und haben gesagt, das ist
so ein Spinner.
Wenn wir Sinus und Kosinus aufaddieren, die sind rund, und wenn wir
beliebig viele Runde aufaddieren, kommen nur runde Sachen raus.
Da kann unmöglich was Eckiges rauskommen.
Und so haben sie sich halt über den lächerlich gemacht.
Aber Fourier, seine Theorie war sauber, war völlig okay, und hat nicht
lange gedauert, bis man dann doch ihm recht geben musste, dass
tatsächlich, also zunächst mal so wie es hier steht, sich alle
periodischen Funktionen so schreiben lassen.
Ja, und dann ist die Frage, könnten wir alle periodischen Funktionen,
oder zumindest auf einem bestimmten Bereich periodische Funktionen,
mit so einer Summe darstellen.
Wozu könnte man das gebrauchen?
Ich illustriere das mal an so einer Anwendung hier.
Wir haben hier so ein kleines Programmchen, dass wenn man hier ins
Mikrofon etwas reinspricht, dann kommt dann auch ein sogenanntes
Spektrum heraus.
Also, ich fange einfach mal an.
Sie haben sicher sowas schon mal zu Hause gesehen.
Das, was Sie hier oben sehen, das Grüne, das sind die Schallwellen, so
wie sie aufgezeichnet werden.
Und das, was Sie hier unten sehen, das ist eine Auflösung in
Frequenzen.
Also, das ist...
Das kann ich jetzt hier nicht malen, weil...
Also, die X-Achse ist die Zeit, das sieht man ja offensichtlich.
Und die Y-Achse ist die Frequenzachse.
Unten niedrige Frequenzen, oben hohe Frequenzen.
Ich kann mal zum Beispiel einen Ton machen, sowas wie...
Dann sehen Sie, das war ziemlich genau eine Frequenz in einer
bestimmten Höhe.
Ich kann auch mal was singen, dann sieht das ein bisschen lustiger
aus, sowas wie...
Dies Bildnis ist bezaubernd schön, wie noch kein Auge je gesehen.
Ich fühle es, ich fühle es, wie dies Götterbild mein Herz mit neuer
Regung füllt.
Mein Herz mit neuer Regung füllt.
Ja, auch das Klatschen hat eine ganz charakteristische Darstellung,
wie man hier sieht.
Und am einfachsten zu erkennen, was hier passiert, ist natürlich, wenn
ich pfeife, also wenn ich sowas mache, wie...
...oder...
Also hier sehen Sie dann, was passiert.
Was wir hier sehen, sind also die Frequenzanteile, wie viele Sinusse,
ganz unten mit Frequenz 0 und ganz oben mit, naja, was sind das, 11
.025 halbe Hertz.
Also hier unten sind ungefähr 0 Hertz, hier oben sind ungefähr 5,5
Kilohertz.
Wie viele Sinusse mit den Anteilen, wie viele mit den, wie viele mit
den Anteilen, wenn man die alle machen würde und aufaddieren würde,
mit der Gewichtung, wie man sie da sieht.
Also schwarz heißt Gewichtung 0, blau heißt ein bisschen mehr
gewichtet und grün halt noch mehr und gelb, rot und so weiter am
stärksten gewichtet.
Dann kommt insgesamt eine Welle raus, hier oben, so eine grüne, die
sich eben so anhört, wie das, was halt da durch die Soundkarte
reinkommt.
Und jetzt würde uns interessieren, wie berechnen wir das?
Wie kriegen wir sowas raus?
Also wie sieht so ein typisches bla bla bla bla, wie sieht so ein
typisches Teil hier aus?
Wie kriegen wir das ausgerechnet?
Aus diesem grünen Teil, was da in die Soundkarte reinkommt, wollen wir
so ein Bild unten ausrechnen, wie das.
Vielleicht kennen Sie das anderswo her, zum Beispiel von Ihrem
Equalizer.
Das hatten wir hier in diesem MP3-Player, da gibt es auch solche
Equalizer, die dann auch so mit der Musik hoch und runter dopsen.
Ist im Prinzip das Gleiche, nur dass wir hier keine Zeitachse haben,
dann müssen wir halt hier so noch eine Zeitachse hinmalen.
Und wenn wir das dann über die Zeit hin hier rüber malen würden, dann
würde es eben so aussehen, wie das, was wir eben gesehen haben.
Ja, wie machen wir das?
Gut, fangen wir mal an.
Die Mathematik ist eigentlich gar nicht so kompliziert.
Gehen wir von der Situation aus, wir haben so eine Funktion f, die
habe mal die Periode 2π.
Wenn sie jetzt nicht periodisch ist und so weiter, dann wollen wir uns
noch nicht damit auseinandersetzen.
Und die Frage ist, können wir f jetzt irgendwie als eine solche
trigonometrische Reihe darstellen?
Und das heißt natürlich, als Reihe darstellen, können wir diese
Koeffizienten herauskriegen.
Also, ein paar Sachen, wie man es machen kann, das werden wir jetzt
gleich sehen, wie man da drauf kommt, dass man es so macht.
Durch Rumspielen mit der Mathematik halt.
Zum Beispiel weiß man aus der Mathematik, wer weiß aus welcher Klasse,
dass wenn wir einen Kosinus mit einem Sinus multiplizieren, und die
haben unterschiedliche Frequenzen, dass dann das Integral von 0 bis 2π
0 ergibt.
Das heißt, der Kosinus geht genauso oft drüber wie drunter, der Sinus
geht genauso oft drüber wie drunter, und die multiplizieren sich auch
nicht gegenseitig auf die gleiche Seite.
Wenn n und m verschieden sind, dann ist das quasi dekorreliert, nicht
wirklich dekorreliert, aber es ist einfach so, dass genauso viel wie
oberhalb der x-Achse ist, genauso viel kommt auch unten raus.
Und somit können wir einfach festhalten, das Integral auf dem Stück 0
bis 2π von einem Kosinus mit einem Sinus multipliziert, mit
unterschiedlichen Frequenzen, n und m, ist 0.
Wenn wir uns angucken, was ist mit zwei Kosinussen, das gleiche gilt
auch bei zwei Kosinussen.
Auch hier haben wir einen Teil, der genauso oft oben wie unten drunter
ist, und wenn die m und m verschieden sind, dann gleicht sich das
wieder aus.
Wenn n gleich m wäre, dann hätten wir hier ja Kosinusnx mal Kosinusnx,
und das wäre Kosinusquadratnx, also das wäre immer positiv, dann würde
natürlich nicht 0 herauskommen.
So, jetzt haben wir hier oben also so eine Gleichung, f von x gleich
irgendwas mit Sinussen und Kosinussen, und jetzt wäre die Idee, was
wäre denn, wenn wir hier zum Beispiel beide Seiten mit einem Sinus
oder Kosinus multiplizieren und dann integrieren, dann würde doch ganz
viel wegfallen.
Na, das ist die Idee.
Wir haben hier oben Sinusnx, Sinusn plus 1x und so weiter, Kosinus 1x,
Kosinus 2x und so weiter.
Wenn wir diese Reihe oben mit einem Sinus oder einem Kosinus
multiplizieren und dann das Integral davor schreiben, dann haben wir
doch lauter Nullen, nur an ganz wenigen Stellen, wo halt m gleich n
ist, also an einer einzigen konkreten, haben wir was, was nicht 0 ist.
Ja, so schwierig ist das gar nicht, machen wir es mal.
Also, die linke Seite mit Kosinus multiplizieren und Integral von 0
bis 2pi davor schreiben, das gleiche auf der rechten Seite, Integral
von 0 bis 2pi davor schreiben und mit Kosinus multiplizieren, einmal
dieser konstante Anteil a0 und dann die Summe von n1 bis unendlich
über alle an.
So, wenn wir jetzt gucken, das Integral von der Summe ist die Summe
der Integrale, also können wir gucken, was ist hier das Integral über
diesem ersten Teil, a0 mal Kosinus mx von 0 bis 2pi, das ist
garantiert immer 0, außer m gleich 0 natürlich, wenn m gleich 0 wäre,
dann haben wir hier nicht Kosinus x, sondern Kosinus 0, also immer den
konstanten Wert 1, dann ist das was anderes.
Also, wenn m ungleich 0 ist, dann haben wir in diesem Teil auf jeden
Fall das Integral 0.
In dem hinteren Teil haben wir jetzt sowas wie ein Kosinus mal Kosinus
und ein Sinus mal Kosinus, das hatten wir vorhin festgestellt, der
Sinus mal Kosinus ist immer 0, die kriegen sich nie auf irgendwas
immer positives oder negatives, die gleichen sich immer aus, kommt
immer 0 raus.
Nur bei den Kosinus haben wir gesagt, da ist es nicht wirklich immer
so, sondern nur wenn m ungleich n ist, dann haben wir hier 0.
Also das Integral vom Produkt von zwei Kosinussen verschiedener
Frequenz ist nur dann 0, wenn die Frequenz echt verschieden ist.
Wenn jetzt m doch gleich n ist, dann haben wir da stehen Kosinus
Quadrat nx.
Wenn n 0 ist, dann heißt das, wir haben Kosinus Quadrat x, also 1.
Und das von 0 bis 2 Pi, warum gibt das Pi?
Achso, hier unten, natürlich ist er 2 Pi.
Also wenn m gleich n gleich 0 ist, dann haben wir eben das Integral
von 0 bis 2 Pi über 1, also 2 Pi.
Und wenn m gleich n ist, aber nicht 0, also irgendeine tatsächliche
Frequenz, dann haben wir Kosinus Quadrat x, also einfach einen
normalen Kosinus, wo die Teile, die unterhalb der x-Achse sind,
hochgeklappt sind quasi, dann kommt nicht 0 raus, sondern Pi, und zwar
bei egal welcher Frequenz.
Also das ist dann hier egal, ob der Kosinus jetzt so geht oder ob er
noch schneller geht.
Also wenn wir das hochklappen, kommt auf jeden Fall immer Pi raus als
Integral.
Würde auch zu weit in die Mathematik gehen, sich noch weiter darüber
auszulassen.
Auf jeden Fall können wir jetzt sagen, nach dieser Umformung, beide
Seiten der Gleichung, m von x gleich trigonometrische Reihe, beide
Seiten mit Kosinus mx multiplizieren und ein Integral von 0 bis 2 Pi
davor schreiben, liefert uns die folgende Gleichung hier unten.
Wenn m ungleich 0 ist, dann haben wir da stehen, Integral von 0 bis 2
Pi m von x mal Kosinus nx, das ist das, was hier oben steht, das
Identische, gleich.
Und jetzt haben wir da stehen, alles fällt weg, das ist immer 0.
Hier, dieser hintere Teil, Sinus mal Kosinus, das ist immer 0.
Und hier vorne ist nur in einem einzigen Fall etwas ungleich 0,
nämlich dann, wenn m gleich n ist.
Dann ist es nämlich Pi.
Das muss dann noch multipliziert werden mit dem dazugehörigen an, und
das war's.
Also für n ungleich 0 können wir sagen, das Integral von m von x mal
Kosinus nx dx ist Pi mal an.
Würden wir uns jetzt also für das an interessieren, können wir das
gleich auflösen.
Also an ist einfach ein Pi-Till von dem, was da vorne steht.
Also 1 geht Pi mal Integral.
Den Spezialfall m gleich n gleich 0 können wir auch noch hinschreiben,
was ist, wenn doch das eintritt.
Wenn m gleich n ist, 0 ist, dann haben wir hier einfach hier vorne,
dann gilt es eben nicht mehr, dass es immer 0 ist.
Dann haben wir hier einfach a0 mal 1 halb.
Das Ganze von 0 bis 2 Pi integriert gibt eben Pi mal a0.
Jetzt sehen Sie vielleicht auch, vielleicht haben Sie sich gefragt,
warum steht vor dem a0 ausgerechnet 1 halb und vor dem anderen nicht.
Das sieht man jetzt daran, jetzt kommt die Symmetrie schön zustande.
Nämlich jetzt können wir ganz allgemein schreiben, wenn wir das
jeweils nach an auflösen, steht zweimal genau das gleiche da.
Das steht also hier.
Wenn wir das nach an auflösen, kommt jedes Mal genau das raus, ob für
a0 oder für a1.
Es kommt immer raus, 1 durch Pi mal das Integral von 0 bis 2 Pi über
der Funktion f von x mal Kosinus nx dx.
Wollen wir also wissen, wie hoch der Anteil der Schwingung mit der
Frequenz n in der Funktion f ist, dann multiplizieren wir f mit
Kosinus nx, integrieren von 0 bis 2 Pi, dividieren durch Pi und haben
den Anteil.
Genauso können wir es machen, wenn wir mit Sinus auf beiden Seiten
multiplizieren und dann integrieren.
Das läuft ganz symmetrisch ab.
Dann führt es eben dazu, dass die a's alle 0 sind und die b's Werte
kriegen.
Und analog können wir dann auch ableiten, dass bn ist das Integral
über der Funktion multipliziert mit Sinus nx.
Auch wieder 1 durch Pi vorne dran.
Somit können wir also sagen, wollen wir eine Funktion f zusammensetzen
aus Sinusen, Kosinusen, jeweils mit den Frequenzen nx und wir wollen
wissen, mit welchem Anteil müssen wir die da reintun, dann können wir
die auf die Art berechnen.
an ist die obere Formel, bn die untere.
Und damit kommt dann unsere hübsche Funktion raus.
Gut, also ich gehe jetzt mal nicht auf die Mathematik ein, was ist,
wenn das nicht integrierbar ist und so weiter und so weiter.
Das ist Mathematikersache.
Wir gehen mal davon aus, dass bei uns in der Informatik nur sinnvolle
Probleme auftreten.
Ist also integrierbar, wenn es so ist, dass das von 0 bis 2Pi
integrierbar ist, dann können wir die a0, a1 bis bn alle berechnen.
Und diese Koeffizienten heißen dann die Fourier-Koeffizienten, benannt
nach diesem Mathematiker Fourier.
Und die gesamte Reihe nennen wir dann eben Fourier-Reihe dieser
Funktion.
Ist vielleicht ein bisschen schade, dass es unendlich viele ns gibt,
also dass diese Pünktchen, Pünktchen ins Unendliche gehen.
Wäre schön, wenn es irgendwo aufhören würde, ist aber im Allgemeinen
halt nicht so.
Okay, jetzt haben wir aber gesagt, unter all diesen Bedingungen, wir
haben die Periode von 0 bis 2Pi.
So eine Funktion lässt sich natürlich prima mit Sinus und Kosinus
zusammenbauen.
Was ist, wenn die Funktion eine andere Periode hat?
Ist im Prinzip gar nicht nennenswert problematisch.
Das sehen wir jetzt, das ist deswegen nicht problematisch, weil wenn
wir...
Okay, erstmal in diese Richtung.
Ich rede jetzt hier mal weiter.
Ne, wo ist es?
Genau, hier.
Wenn die Periode nun mal nicht 2Pi ist, sondern irgendwas T ungleich
2Pi, dann haben wir einfach statt die Kosinusse Nx, multiplizieren wir
einfach den ihre Periode mit 2Pi durch T.
Das funktioniert ganz einfach.
Wenn wir das dann auch auflösen nach aN und bN, kommen die gleichen
Formeln raus, nur das wo halt vorher 1 stand, wir halt jetzt 2Pi durch
T stehen haben.
Entsprechend, weil halt hier vorne 1 durch Pi war, haben wir halt 2
durch T stehen.
Also die Periode tut uns nicht weh.
Wir können also zum Weiterrechnen so tun, als sei sie mal 2Pi.
Für andere Perioden sieht nur die Mathematik vielleicht ein klein
bisschen komplizierter aus, mehr nicht.
Okay, was können wir noch festhalten?
Wir können noch festhalten, dass wenn wir annehmen, dass diese
Funktion periodisch ist mit der Periode 2Pi, das heißt, das was sie an
der Stelle x hat, das hat sie auch an der Stelle x plus 2Pi.
Dann ist es natürlich egal, ob wir das Integral von 0 bis 2Pi
berechnen oder von irgendwo bis irgendwo plus 2Pi.
Muss immer das gleiche rauskommen.
Und da wir Informatiker sind, sind wir auch hier pragmatisch, wenn wir
sagen, und was ist, wenn die gar nicht periodisch ist?
Wenn F überhaupt nicht periodisch ist, dann sagen wir, okay, wir
betrachten einen Ausschnitt von 0 bis 2Pi, den Rest vergessen wir und
tun so, als wäre es da auch periodisch.
Dann haben wir eine Funktion, die periodisch ist und wir können damit
weitermachen.
Denn typischerweise sind unsere Signale ja gar nicht unendlich.
Wenn wir uns so eine Schallwelle da angucken, dann hört die natürlich
irgendwann auf.
Also ist es gar nicht nötig anzunehmen, dass die wirklich unendlich
periodisch ist.
Fast alles, was praktische Relevanz hat, ist nicht unendlich
periodisch.
Und deswegen tun wir dann einfach so, als wäre es und sind trotzdem
glücklich.
Ja, wie ich vorhin angedeutet habe, eigentlich haben wir unendlich
viele A's und B's.
Das ist ja auch eine unbefriedigende Geschichte.
Vielleicht brauchen wir ja A eine Million oder A eine Milliarde, damit
sich diese F von X erst sinnvoll darstellen lässt, mit Hilfe der
trigonometrischen Reihe.
Zum Glück ist das nicht so.
Denn wenn wir uns angucken, was kommt denn so raus, wenn wir für große
N's die Sache uns angucken.
Also wenn wir uns diese, das ist ja diese F von X mal CosinusNX, das
ist ja das, was bei uns auf der linken Seite stand, mit dem Integral
davor, von nirgendwo bis irgendwo, wenn wir hier das N gegen unendlich
laufen lassen, was hat es dann zur Folge?
Das hat dann zur Folge, dass wir diese Funktion F von X in dem
Intervall a, b mit immer stärker oszillierenden Cosinussen
multiplizieren.
Man könnte sagen, der Cosinus zerhackt das F immer brutaler.
Und je weiter wir das N nach oben tun, umso brutaler oszilliert der
Cosinus und umso mehr Hackfleisch wird aus dem F, das wird quasi
wirklich voll ausgenullt.
Nicht wirklich, aber auf jeden Fall der Limit, wenn wir N gegen
unendlich laufen lassen, ist null.
Ob das jetzt ein Cosinus oder ein Sinus ist, ist sogar egal.
Eine Funktion mit einer immer schneller oszillierenden Funktion,
multipliziert, integriert, gibt null.
Ja, ja, keine Spezialfälle wie in der Mathematik jetzt.
Was ist, wenn, aber F von X und so weiter, ist an der Stelle nicht
wichtig.
Also, wenn wir uns das angucken, und das ist ja die Definition für bN
und das ist die Definition für aN.
Das heißt, dass also auch der Limit von aN für N gegen unendlich und
der von bN für N gegen unendlich null ist.
Mit anderen Worten, diese a´s und b´s werden immer kleiner mit großem
N.
Oder mit anderen Worten, die Anteile, die wir dazu aufaddieren müssen,
in die Gesamtsumme der trigonometrischen Reihe, die werden immer
kleiner, diese Anteile.
Somit wird also auch die Annäherung der Funktion F immer genauer.
Wenn wir also jetzt nicht mehr schreiben von N gleich 1 bis unendlich,
das war ja die ursprüngliche Definition der Reihe, sondern von N
gleich 1 bis N, dann haben wir eine endliche Reihe, die, je größer das
N ist, unsere Funktion F immer mehr annähert.
Auch dazu können wir uns ein Beispiel angucken.
Nicht?
Ja.
Gleich passiert.
Das ist das hier.
Wir haben hier so einen Schieberegler, der uns eine Funktion
zusammensetzt aus lauter Sinussen und Kosinussen.
Also jetzt haben wir zunächst mal 0 Sinusse.
Jetzt kommt 1.
So, das ist der erste Sinus.
Das sieht so aus.
Also das Rote, was man hier sieht, ist immer die letzte Kurve, die wir
dazu gemacht haben.
Das ist Sinus 1x.
Jetzt gehen wir mit dem Schieberegler 1 weiter.
Sinus 2x ist jetzt das Rote.
Und wenn wir jetzt Sinus 2x plus Sinus 1x, also plus das Grüne nehmen,
dann kommt das Schwarze raus.
Jetzt machen wir noch Sinus 3x dazu.
Dann Sinus 3x ist wieder das Rote.
Die Grünen sind alles in der Vergangenheit.
Nicht politisch gemeint.
Und dann zusammen gibt Rot und Grün Schwarz.
Auch nicht politisch gemeint.
Und das gibt dann diese Kurve.
Und wenn wir jetzt noch weitermachen, zum Beispiel 4x, Sinus von 4x
dazu tun.
Dann kommt diese noch schneller schwingende Rote dazu.
Sinus von 5x sieht dann so aus und das können wir dann durchziehen bis
ganz viele.
Und das, was dann eben rauskommt als Summe, ist etwas, was so eckig
aussieht.
Das ist jetzt nicht wirklich eckig, aber wie wir gleich sehen werden,
es nähert diese eckige Funktion an.
Ja, das hatte ich schon.
Das ist nämlich hier die Frage, wie berechnet man diese Koeffizienten,
die wir brauchen, um so eine eckige Funktion anzunähern?
Also, sagen wir mal, wir haben so eine Funktion gegeben, f von x.
Und nennen diese Funktion Vorzeichen von x.
Also, die ist minus 1 bei negativen x, plus 1 bei positiven.
Allerdings müssen wir halt, um der Mathematik genügend zu tun, sagen,
okay, meine Wege, da schneiden wir halt ab.
Bei minus Pi und plus Pi und sagen, ab hier ist alles periodisch.
Also es wiederholt sich halt, sodass wir im Prinzip nur diesen einen
Teil hier von minus Pi bis plus Pi betrachten.
Also so eine ständig sich wiederholende Stufe.
Oder man nennt es halt eben auch Rechteckfunktion.
Das wäre so eine, wo damals die Kollegen von Fourier gesagt haben, das
geht nicht, diese Funktion ist eckig.
Da kann ich noch so viele Sinusse und Kosinusse drauf addieren, das
wird nicht eckig.
Aber setzen wir es doch einfach mal in unsere Formel ein.
Wir haben ja hier, wenn wir das a n berechnen wollen, unsere normale
Formel von vorhin, das f von x multipliziert mit Kosinus n x,
integriert von minus Pi bis Pi, hätten auch von 0 bis 2 Pi machen
können, muss das gleiche rauskommen.
Das ergibt dann unser a n.
Mathematik ist so ziemlich trivial fast an der Stelle.
Also hier hat man gesagt, Signum von x mal Kosinus x.
Wie sieht das aus?
Kosinus fängt hier oben an, geht runter bis hier hin, mal Signum von
x.
Also es geht hier hinten noch in die andere Richtung.
Also minus Pi ist ungefähr hier, plus Pi ist hier.
Das multipliziert mit dem Vorzeichen.
Dann kippt hier ein Teil, dann sehen Sie was passiert, es wird einfach
nur umgekippt.
Mit dem Vorzeichen multipliziert, dann kommt eben raus sowas.
Also diese Seite kippt um.
Also ähnlich.
Auf jeden Fall genauso viel oben wie unten wieder.
Das Integral gibt 0.
Also die a n sind alle 0.
Mit anderen Worten, das was wir vor die Kosinusse schreiben müssen,
ergibt immer 0.
Okay, was müssen wir vor die Sinusse schreiben?
Probieren wir mal die b n auszurechnen.
Also Integral von f von x mal Sinus x.
Auch wieder von minus Pi bis Pi.
Der Sinus, wenn wir den jetzt mit dem Vorzeichen multiplizieren, das
klappt nicht mehr.
Weil der Sinus ist ja selbst von minus Pi bis Pi, wie das Vorzeichen.
Also müssen wir ein kleines bisschen Mathematik machen, aber auch
nicht nennenswert.
Was rauskommt ist einfach eben, das 1 durch Pi bleibt vorne dran.
Hier hinten kriegen wir dann entweder 0 durch n oder 2 durch n.
Je nachdem ob n gerade oder ungerade ist.
Wenn wir eine ungerade Frequenz im Sinus haben, also Sinus 3x, 5x und
so weiter, dann liefert das Integral was.
Und wenn wir eine gerade Potenz haben, dann liefert das Integral
nichts.
Man kann es also so schreiben, das ist 1 minus minus 1 auf n.
Wenn wir hier 0 einsetzen für n, dann kommt 1 minus 1, also 0 raus.
Wenn wir 1 einsetzen, kommt 2 raus und so weiter.
Also das schwingt immer zwischen 0 und 2.
0, 2, 0, 2 und so weiter.
Mit anderen Worten, diese Koeffizienten bn sind immer 0 durch nPi oder
2 durch nPi, 4 durch nPi, 6 durch nPi und so weiter.
1 minus minus 1 ist 2.
Achso, natürlich, Quatsch, bei den ungeraden kommt natürlich was.
Also genau, bei den geraden kommt 0 raus, bei den ungeraden kommt 2
raus.
Das heißt, bei den ungeraden haben wir einen Faktor 0, bei den geraden
haben wir einen Faktor 2 mal 2, also 4.
Wir haben also 4 durch Pi oder 0 durch Pi und dann jeweils halt
multipliziert mit dem geraden oder ungeraden.
Die geraden fahren alle weg, also bleibt noch Sinus von 1x plus Sinus
3x plus Sinus 5x und jeweils halt noch dieses n drunter.
Also Sinus 1x durch 1 plus Sinus 3x plus 3 plus Sinus 5x durch 5 und
so weiter.
Das ist das, was ich vorhin mit dem ersten Sinus meinte, das war der
zweite, der dritte.
Wenn wir die alle aufaddiert hatten, dann kam diese eckige Kurve raus,
die wir da vorhin hatten.
Und wir sehen, dass der Schwarze sich immer mehr dieser Rechteckform
annähert.
Und selbst wenn wir ganz bis zum Schluss durchziehen, bis nach 19, ist
es immer noch nicht ganz eine Rechteckkurve, aber etwas, was sehr
ähnlich aussieht wie eine Rechteckkurve.
Vielleicht eine Kuriosität am Rande, es wird tatsächlich nie wirklich,
also der Limes ist eine Rechteckkurve, aber diese Punkte hier, diese
Ausläufer, wenn Sie davon die Werte berechnen, die werden niemals auf
1 oder minus 1 kommen.
Das ist ein bisschen komisch, aber macht ja nichts, Hauptsache der
Limes nähert sich an dieser Rechteckfunktion an.
Ja, so könnte man das machen.
Das ist hier nochmal dargestellt.
Ja, ich weiß nicht, ob das jetzt so deutlich sichtbar ist, aber da
wird es auch wieder gemeint, hier diese Rechteckkurve.
Das Grüne, das ist der Sinus, der erste Sinus.
Das ist schon mal eine Annäherung, die ist noch nicht besonders gut,
aber dann das Dunkelblaue ist dann die zweite Annäherung und so
weiter.
Wenn wir die alle aufaddieren, dann kommt eben, wie es hier rechts
dargestellt ist, etwas heraus, was der anzunähernden Kurve, der
Rechteckkurve immer ähnlicher wird.
Okay, so, jetzt haben wir aber, nur mal wieder zurück den Bogen
schließen zu unserer Fourier-Transformation.
Wir haben also gesehen, wir können beliebige Funktionen, von denen wir
annehmen, dass sie periodisch sind, wenn sie es nicht sind, dann
betrachten wir halt nur einen Teil und sagen, der Rest ist halt
genauso, die können wir als Fourier-Reihe darstellen.
Um jetzt den Übergang zu machen, das war jetzt immer noch ein bisschen
diskret, wir haben immer noch diskrete Asn und Bsn.
Um jetzt den Übergang zu machen zu etwas Kontinuierlichem, was ist,
wenn die Frequenzanteile eben nicht Sinus 3x, Sinus 4x, sondern Sinus
3,5x sind?
Was ist dann A 3,5?
Haben wir nicht so, gell?
Deswegen müssen wir uns ein bisschen Gedanken machen, was ist für den
Fall, dass wir eben völlig beliebige Funktionen ansehen, die nicht nur
zusammengesetzt werden aus Sinusen und Kosinussen von ganz bestimmten
Frequenzen.
Wenn wir wissen wollen, was ist eben der Frequenzanteil von Sinus 3
,5x?
Um auf den Weg dahin zu kommen, gucken wir uns mal an, wie wir diese
Sinusse und Kosinusse noch anders schreiben könnten.
Vielleicht hatten Sie das schon in der Mathematik, hatten Sie es
schon, diese Taylor-Reihen?
Hört sich gut an, okay, dann erwähne ich es nur nochmal kurz.
Also die Taylor-Reihe für Sinus x ist x durch 1 Fakultät, minus x hoch
3 durch 3 Fakultät, plus x hoch 5 durch 5 Fakultät, minus x hoch 7
durch 7 Fakultät und so weiter.
Die für ein Kosinus sieht fast genauso aus, nur dass eben da die
geraden Anteile dabei sind und die ungeraden weg sind.
Dann haben Sie vielleicht aber auch die kennengelernt, die Taylor
-Reihe für e hoch x.
Die wird jetzt plötzlich komplex, oder nein, noch nicht komplex, aber
gleich werden wir es sehen, wenn wir es komplex machen.
Also die Taylor-Reihe für e hoch x ist einfach alle Potenzen, x,
Quadrat, hoch 3, hoch 4, jeweils durch die entsprechende Fakultät
geteilt aufaddiert.
Wenn wir jetzt e hoch ix ausrechnen wollen, nicht e hoch x, sondern e
hoch ix, dann müssen wir also hier i einsetzen, also ix einsetzen.
Dann sieht diese Sache so aus, wir haben hier 1, das bleibt, hier
haben wir ix durch 1 Fakultät, hier haben wir i Quadrat, x Quadrat
durch 2 Fakultät, also minus 1.
Dann haben wir plus i hoch 3, also minus i mal x hoch 3, i hoch 4 gibt
1 und so weiter.
Hier ist nochmal diese komplexe Ebene dargestellt mit i, i Quadrat, i
hoch 3, i hoch 4.
Und wenn wir e hoch minus ix in diese Taylor-Reihenentwicklung
reinstecken, dann sieht das ähnlich aus, dann haben wir hier eben
statt i minus i, minus i Quadrat ist auch minus 1, minus i hoch 3 ist
i, das sehen Sie auch hier wieder, minus i ist da unten, minus i
Quadrat heißt diesen Winkel von der x-Achse bis dahin verdoppeln, das
heißt nochmal so viel, dann sind wir bei i Quadrat.
Ja,
das ist also e hoch ix und e hoch minus ix.
Jetzt sehen Sie vielleicht schon, wir haben hier zum Beispiel die
gleichen Teile hier, also hier haben wir bei e hoch ix x Quadrat durch
2 Fakultät, hier unten auch, und auch der Vorfaktor minus 1 ist
gleich, während bei den Ungeraden haben wir hier bei e hoch ix als
Vorfaktor ein Plus-i und bei e hoch minus ix ein Vorfaktor Minus-i.
Also das Gleiche wie oben, nur mit einem anderen Vorzeichen.
Das ist allgemein so, immer bei den Geraden haben wir oben und unten
das Gleiche, den gleichen Vorfaktor, bei den Ungeraden haben wir
einfach das Negative davon.
Das bietet sich ja geradezu an, die beiden zusammen zu addieren und
gucken, was rauskommt.
Hier steht es nochmal da, die Teilereihe für e hoch ix und für e hoch
minus ix und wenn wir die zusammen addieren, dann kommt ständig immer
0 raus bei diesen Ungeraden-Stellen, weil wir einmal oben Plus-i
haben, unten Minus-i, dann oben Minus-i, unten Plus-i und an den
Geraden -Stellen kommt immer das Gleiche raus, also das Doppelte von
dem, was in jeder Reihe steht.
Also bei der 1 haben wir dann eine 2, bei x² durch 2 Fakultät 2, x²
durch 2 Fakultät und so weiter.
Und bei x hoch 4 durch 4 Fakultät 2, x hoch 4 durch 4 Fakultät.
Wenn wir das jetzt mit der Teilereihe vom Kosinus-x vergleichen,
stellen wir fest, wenn wir die 2 ausklammern, ist es genau der
Kosinus.
Wir könnten also den Kosinus schreiben als e hoch ix plus e hoch minus
ix halbe.
Das steht hier.
Wenn wir die Differenz von diesen beiden, e hoch ix und e hoch minus
ix bilden, dann fallen eben die Geraden weg.
Dann haben wir als Differenz, da wo hier eine 1 war, ziehen wir hier
die 1 wieder ab.
Da wo wir hier minus 1 mal x² durch 2 Fakultät hatten, ziehen wir es
hier wieder ab.
Das heißt, die Geradenanteile fallen alle weg und die Ungeraden
bleiben übrig.
Und wenn wir uns das dann angucken mit der Teilereihe für den Sinus,
dann sieht es genauso aus wie der Sinus, nur halt eben mit diesen
Vorfaktoren 2i noch da dran.
Also können wir sagen, der Sinus-x lässt sich auch schreiben als e
hoch ix minus e hoch minus ix geteilt durch 2i.
Das kann uns die Sache ganz schön erleichtern und später das Rechnen
uniformer gestalten.
Okay, so halten wir das mal so fest und gucken uns jetzt an, was wir
eigentlich aus mathematischer Sicht haben wollen.
Denn wenn uns interessiert, was passiert im Computer, wenn wir digital
mit Signalen arbeiten, die aber eigentlich nicht digital, sondern
analog sind, dann müssen wir uns überlegen, was passiert dabei.
Also in der Wirklichkeit ist ja so ein Sprachsignal was analoges.
Diese Druckwellen, die vom Mund rausgehen, haben beliebige Werte und
im Computer haben wir nur bestimmte Diskrete.
Also gucken wir uns mal an, könnten wir denn, und das ist jetzt die
Fourier -Transformation im analogen Fall, eine beliebige Funktion f
und t jetzt nicht als trigonometrische Reihe schreiben, sondern
meinetwegen als trigonometrisches Integral.
Also während wir vorhin hatten, ja, vorhin hatten wir hier eine Summe,
wo wir jetzt das Integral haben.
Vorhin hatten wir hier an und bn, wo wir dieses f von Omega haben.
Und vorhin hatten wir Sinus und Kosinus, wo wir jetzt das e hoch minus
i Omega t haben.
Sie sehen, dass es voll analog ist.
Wir könnten Sinus und Kosinus schreiben als e hoch i Omega t, nur
statt in an und bn, die vorhin diskrete Werte haben, nehmen wir jetzt
irgendeine Laufvariable Omega, die beliebige Werte annehmen kann und
sagen halt statt an, bn, f von Omega.
Unser Ziel ist also, angenommen wir hätten eine Funktion f und t, wie
groß ist der Anteil der Frequenz Omega in dieser Funktion?
Das würde uns interessieren.
Das können wir genauso wie vorhin auflösen, da wo wir vorhin an und bn
berechnet haben, genau so kommt hier auch raus, dass f von Omega ist
das Integral der Funktion f und t, jetzt halt nicht mit Sinus oder
Kosinus multipliziert, sondern mit diesem e hoch i Omega t.
Diese Funktion nennen wir jetzt die, manche sagen noch dazu, die
kontinuierliche, aber wenn man es nicht sagt, ist es damit gemeint,
diese Funktion f nennen wir die Fourier-Transformierte von kleinen f.
Oft wird es auch in der Literatur als Spektrum bezeichnet, also f von
irgendwas geht an, mit welchem Anteil das irgendwas in dem kleinen f
vorhanden ist.
Deswegen Spektrum.
Vorhin als ich gepfiffen hatte, wenn wir hier Omega haben und hier f
von Omega und ich nehme jetzt die Funktion Pfiff, also f ist Pfiff,
dann würden wir erwarten, dass das f von Omega so aussieht, überall
Nullfrequenzanteile, an irgendeiner Stelle gibt es eine Frequenz, je
nachdem wie laut ich gepfiffen habe, und dann geht es wieder auf.
Also das wäre f von Pfiff hoch und wenn ich einen tiefen Pfiff gemacht
hätte, wäre das irgendwo hier unten gewesen.
Ein lauter tiefer wäre vielleicht so gewesen, ein lauter hoher wäre
vielleicht da irgendwo gewesen.
Also so würde das f von Omega von einem Pfiff aussehen.
Das f von Omega von einem Klatschen oder von einer Sprache, das würde
dann irgendwie ganz chaotisch aussehen.
Irgendwie sowas, was auch immer.
Also für alle Omegas irgendwas und gleich Null.
Denn ein schöner Sinuston, so ein schöner ganz uniformer Pfeifton, der
würde, wenn man es richtig macht, an nur einer einzigen Stelle für ein
einziges Omega einen Ausschlag liefern und für alle anderen gar nichts
liefern.
Und ganz allgemein kann man auch hier wieder sagen, wir können diese
Funktion f dann darstellen als, naja, jetzt wirklich unendliche Summe
von allen Schwingungen, wobei eben f von Omega angeht, mit welchem
Anteil die Schwingung Omega reingeht.
Nur wobei das jetzt Summe zu nennen ist vielleicht ein bisschen
unmathematisch, weil es ist ja im Prinzip das Integral, was wir hier
machen.
Also es ist nicht irgendwas Plus, Plus, Plus, sondern unendlich viele
in unendlich kleinen Abständen aufsummierte f von Omegas.
Ja, das ist die Vorstellung, die wir gerne hätten.
Also diese Definition haben wir hier.
Genauso umgeformt können wir also die f von Omegas wie vorhin, die a
ab n zum b n berechnen, indem wir dieses Integral berechnen.
Gucken wir uns ein Beispiel an.
Zum Beispiel die Funktion, die so aussieht.
Die ist überall 0 und dann ist sie zwischen, was ist das, t, ne, t ist
1.
Achso, zwischen minus 1 und 1 ist sie 1 und ansonsten ist sie überall
0.
Also so einfach ein Kasten.
Eine Rechteckfunktion, die aber nicht sich wiederholt, sondern die
überall 0 ist, nur da dazwischen nicht.
Die Frage ist, wie würde man das, davon jetzt die vorher
transformierte berechnen?
Nun setzen wir es einfach in die Formel ein.
Also eigentlich ist ja die Formel, um sie komplett auszuschreiben, f
von Omega ist das Integral von minus unendlich bis unendlich von f von
t mal e hoch i Omega t dt.
So, nachdem unser f ja überall 0 ist, jenseits von minus 1 und plus 1,
reicht es, wenn wir das Integral von minus 1 bis plus 1 berechnen.
Und dazwischen ist f von t gleich 1.
Also was wir brauchen, ist das Integral von minus 1 bis 1 über e hoch
i Omega t.
Auch wieder im Formelbuch nachgucken.
Was rauskommt, ist, wenn wir als Frequenz 0 annehmen, dann haben wir e
hoch 0.
e hoch 0 ist 1.
Das Integral von minus 1 bis 1 über 1 ist 2.
Und falls wir doch etwas eine Frequenz ungleich 0 haben, dann haben
wir hier Sinus Omega durch Omega mal 2.
Das steht in der Formelsammlung, das leite ich nicht her.
Ja, das was rauskommt, sehen wir uns hier an.
Also hier steht zum Beispiel dieses Sinus x durch x oder Sinus Omega
durch Omega.
In der Tat ist es sogar für Omega 0 das gleiche.
Das konvergiert hier gegen diesen gleichen Wert, zum Glück.
Ja, und jetzt wissen wir, wenn wir wissen wollen, welche
Frequenzanteile müssen wir denn von e hoch i zählen.
Das hier.
Also wie oft e hoch i zählen t in f von t.
Also wenn wir f von t zusammenstellen wollen, jetzt nicht aus Sinus
und Kosinus, wie wir es bisher kennen, sondern aus diesen e hoch i
Omega t.
Es sind ja eigentlich Sinus und Kosinus, nur eben komplex.
Aber Sie erinnern sich an diese Taylor-Reihen, mit denen man e und
Sinus hin und her wandeln kann.
Dieses e hoch i Omega t ist eine Schwingung, nur halt eben komplex.
Nicht so einfach wie Sinus und Kosinus.
Deswegen auch nicht so einfach darzustellen, nicht so schön zu malen.
Aber ist trotzdem eine.
Ja, also wenn wir wissen wollen, wie oft muss also quasi e hoch 10 t
in diesem Ding enthalten sein, dann gucken wir hier nach und stellen
fest, das ist sowas wie minus 0,06 oder so.
Also wenn wir das Ganze aufbauen wollten aus lauter solchen e hoch i
irgendwas, dann müssen wir das an der Stelle 10, wo Omega 10 ist, mit
minus 0,6 gewichten.
Glauben Sie nicht, dass das Rote hier jetzt die Annäherung an dieses
Ding sein soll.
Das ist nicht die Annäherung.
Das ist nur der Anteil der Frequenzen in dieser Funktion f von t.
Was wir hier zum Beispiel sehen ist, dass der höchste Anteil, der
höchste Frequenzanteil hat die Frequenz 0.
Also die Frequenz 0 kommt, hat hier, also das ist jetzt Sinus x durch
x, eigentlich müssen wir es hier noch mit der 2 multiplizieren, also
die Frequenz 0 hat den Anteil 2 mal 1.
Das ist der höchste Anteil.
Und dann kommt noch ein bisschen davon, ein bisschen davon.
Ich fürchte, man kann es nicht so hübsch machen wie mit dem
Schieberegler vorhin.
Der Schieberegler hat schön stufenweise die Sinusse aufaddiert, hier
haben wir halt was Kontinuierliches.
So, noch als Schluss für heute, bevor Ihnen das Gehirn platzt, ein
paar Eigenschaften der Fourier-Transformation, bei denen ich Ihnen
empfehlen würde, sich selbst nachzuprüfen, ob das auch stimmt, die uns
aber dann für später hilfreich sein werden.
Also, wir bezeichnen jetzt mit Großfett f von einer kleinen f-Funktion
die Fourier-Transformierte f von Omega, wenn klein f eben über diese
Variable t definiert ist.
Dann gibt es vielleicht die hübscheste, oder eine der hübschesten
Eigenschaften ist diese Linearitätseigenschaft.
Die Linearkombination von zwei Funktionen, wenn wir die Fourier
-Transformieren, also mit e hoch minus i Omega t multiplizieren,
Integral davor machen, dann kommt das gleiche raus, als würden wir
jede einzelne Funktion erst Fourier-Transformieren und dann mit c1 und
c2 Gewichte zusammenaddieren.
Das heißt, die Fourier-Transformation ist linearitätsinvariant.
Die Fourier-Transformation von f mal c ist die c mal die Fourier
-Transformation von f.
Und auch die Fourier-Transformation von der Summe von zwei Funktionen
ist die Summe der Fourier-Transformierten.
Okay, das ist vielleicht neu für uns.
Was wir wahrscheinlich nicht brauchen werden, sind solche einfachen
Eigenschaften wie die Ableitung, die n-te Ableitung von f, das dann
Fourier -Transformiert, das ist die Fourier-Transformierte von f,
multipliziert mit einem einfachen Vorfaktor.
Auch wieder komplex.
Ähnlich ist es auch so, dass diese Fourier-Transformation
zeitverschiebungsinvariant ist.
Das heißt, wenn wir nicht die Funktion f von t nehmen, sondern f von t
minus T, also das Ganze verschieben um T, dann kommt die Fourier
-Transformierte der Funktion auch wieder mit einem einfachen
Vorfaktor.
Ähnlich sieht es aus, wenn wir es nicht in der Zeit verschieben,
sondern in der Frequenz verschieben, also aus einem A ein A machen,
dann sieht es in der Fourier-Transformation auch entsprechend ähnlich
aus.
Dann ist der Fourier-Transformationswert von Omega, der der Omega
minus Omega Null ist bei der nicht-Transformierten.
Und jetzt kommt als letzte Eigenschaft eine, die Ihnen, wenn Sie genau
hingucken, bekannt vorkommt.
Nämlich die Eigenschaft einer Faltung.
Wissen Sie, was eine Faltung ist?
Ja, nein?
Naja, wie auch immer.
Es ist hier definiert, was eine Faltung ist.
f mit g gefaltet, also eine Funktion f, eine normale Funktion f mit
einer normalen Funktion g gefaltet.
An der Stelle t ist definiert als eben das Integral, das gucken wir
uns sechsmal genauer an, als das Integral von f von t minus tau mal g
von tau d tau.
Wenn Sie das jetzt zum Beispiel anders darstellen als Summe, dann
fällt es Ihnen vielleicht wie Schuppen von den Augen.
f gefaltet g, jetzt nicht kontinuierlich, sondern diskret an der
Stelle n, ist die Summe aller f von t minus, sagen wir j, g von j.
Fällt es Ihnen jetzt auf?
Was steht hier?
Das ist eine Polynom-Multiplikation.
Genauso hatten wir die Polynom-Multiplikation definiert.
Wenn wir den n-ten Koeffizienten haben wollen, müssen wir von der
einen fn-j nehmen, von der anderen gj nehmen.
Die beiden aufmultipliziert gibt dann eben genau n.
Und Sie sehen hier unsere gute alte Polynom-Multiplikationsregel.
Polynome multiplizieren oder auch Zahlen multiplizieren ist im Prinzip
nichts anderes als diskret falten, wozu wir hier die analoge
kontinuierliche Version dargestellt haben.
Oh, ist alles weg.
Ja, und das Hübsche an dieser Faltung ist, wenn wir zwei Funktionen
falten, f mit g und davon die Fourier-Transformierte berechnen, kommt
das Gleiche raus, wie wenn wir die Fourier-Transformierten normal
multiplizieren.
Genau das haben wir mit der schnellen Fourier-Transformation gemacht.
Wir haben die Polynome, statt sie zu falten, statt jedes mit jedem zu
multiplizieren, haben wir sie Fourier-Transformiert und dann nur noch
normal punktweise multipliziert.
Also das war unsere punktweise Multiplikation, das war unsere brutale
Multiplikation bei den Polynomen und das f ist diese Fourier
-Transformation, die wir da gemacht haben.
Das ist genau das Gleiche, was wir da gemacht haben, nur haben wir es
jetzt aus einer anderen Richtung betrachtet.
So, ja, ich denke das reicht mal für heute.
Gucken Sie sich das nochmal an, damit wir am Mittwoch dann
weitermachen können an dieser Stelle.
Bis dann!