Unterschied zwischen angepassten FFT und analytischer Fourier Transformation, warum?

mit matplotlib, NumPy, pandas, SciPy, SymPy und weiteren mathematischen Programmbibliotheken.
Antworten
Tassou
User
Beiträge: 3
Registriert: Sonntag 16. April 2017, 11:16

Hallo allerseits,

ich bin gerade dabei, ein mathematisches Modell zu implementieren. Da alle meine Gleichungen analytisch beschrieben sind, stoße ich immer wieder auf Unstimmigkeiten zwischen Informatik und Mathematik bzw. hier gerade zwischen der Ansicht der Mathematik (analytisch integrieren) und der, der Informatik (np.fft).

Ich habe ein Skript geschrieben, wo ich versuche beide anzupassen. Es scheint aber ein Offset zwischen meiner FFT und meiner analytischen Fourrier-Transformierter Funktion. (Dazu siehe bitte plots ganz unten oder angehängte Bilder)

http://www.directupload.net/file/d/4693 ... 8c_png.htm
http://www.directupload.net/file/d/4693 ... ec_png.htm

PS: lässt euch von den Frequenzen f0 und fs nicht verwirren da mein Script eigentlich länger ist, als das was ich für euch gepostet habe.. fs: zur Abtastung und f0 ist meine richtige Frequenz.

Code: Alles auswählen

import pylab as plt
import numpy as np


def fkt(t):
    "The example-function to be transformed"
    return (1/tau)*np.exp(-t/tau) 



def Fkt(f):
    "The analytical solution of the Fourier-transformation of the example-function."
    om = 2*np.pi*f
    return  1/(1+1j*om*tau)



def fourier_transform(t, fkt):
    """
    Calculates the Fourier-Transformation of fkt with FFT. 
    The output Fkt of the Fourier-Transformation of fkt 
        is correctly normed (multiply with dt)
        is correctly ordered (swap first and second half of output-array).
    Calculates the frequencies from t.
    """
    dt = t[1]-t[0]
    
    f=np.linspace(-1/(2*dt), 1/(2*dt), t.size, endpoint=False)
    Fkt = np.fft.fft(fkt)*dt
    
    # swap first and second half of output-array
    Fkt2 = np.fft.fftshift(Fkt)
    
    return f, Fkt2



fs =5e6          #Abtastfrequenz
f0 = fs/2/102    # Frequenz mit der, ich anrege
t_min = 0 
dt = 1./fs       # zeitschritt
t_max = (10772) * dt     # The size of the whole signal is 10772
t = np.arange(t_min,t_max,dt)
Td = 1./f0
Time_bin_p = int(np.floor(Td / dt)) # Bins pro Periode Td


tp_n = t[0:int(np.floor(Time_bin_p)/2)]  # Nur einen Abschnitt der Zeit betrachten, bzw. eine halbe Periode 0.5*Td
tau =1e-6

s = fkt(tp_n)
f, S1 = fourier_transform(tp_n, s)
S2 = Fkt(f)



plt.figure()
plt.title("Time Domain")
plt.figtext(.6, .5, 
            r"$s(t) = \frac{1}{\tau} * e^{-\frac{t}{\tau}}$" "\n\n" +
            (r"$\tau = %G$" % tau) + "\n"
            ,
            fontsize=20)
plt.plot(tp_n,s)
plt.grid(True)


plt.figure()
plt.title("Fourier-Analysis")
plt.figtext(.13, .25,
          r"$S(f)=\frac{1}{1+j2\pi f*\tau}$",
          fontsize=24)
plt.plot(f,S2.real,              label="analytic real")
plt.plot(f,S2.imag,              label="analytic imag")
plt.plot(f,np.abs(S2),           label="analytic abs")
plt.plot(f,S1.real,   ".",       label="from FFT real")
plt.plot(f,S1.imag,   ".",       label="from FFT imag")
plt.plot(f,np.abs(S1), ".",      label="from FFT abs")
plt.grid(True)
plt.legend()

plt.show()
Zuletzt geändert von Anonymous am Sonntag 16. April 2017, 14:42, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@Tassou: ich glaube Du mißverstehst hier etwas. FFT berechnet die diskrete Fourier-Transformierte auf einem Raster, das sich periodisch fortsetzt. Die Funktion e^-x ist nicht diskret, aber viel entscheidender, sie ist nicht periodisch. Das sieht man schön daran, dass der Imaginärteil Deiner „analytischen“ Lösung am Rand einen Sprung macht, während die diskrete Transformierte stetig weitergeht.

Du hast hier keine Unstimmigkeit zwischen Informatik und Mathematik, sondern den Unterschied zwischen einem unendlichen Fourierintegral und der diskreten Fouriersumme.
Tassou
User
Beiträge: 3
Registriert: Sonntag 16. April 2017, 11:16

Sirius3 hat geschrieben:@Tassou: ich glaube Du mißverstehst hier etwas. FFT berechnet die diskrete Fourier-Transformierte auf einem Raster, das sich periodisch fortsetzt. Die Funktion e^-x ist nicht diskret, aber viel entscheidender, sie ist nicht periodisch. Das sieht man schön daran, dass der Imaginärteil Deiner „analytischen“ Lösung am Rand einen Sprung macht, während die diskrete Transformierte stetig weitergeht.

Du hast hier keine Unstimmigkeit zwischen Informatik und Mathematik, sondern den Unterschied zwischen einem unendlichen Fourierintegral und der diskreten Fouriersumme.
Hallo Sirius3 und danke für deine Antwort. Das kann natürlich auch sein, dass ich was missverstanden habe. Aber laut der Erklärung hier http://www.magben.de/?h1=mathematik_fue ... schreibung sollte das gleiche raus kommen. MIr geht es darum, eine geschickte Methode zu finden,um die analytische fourier Transformation einer Funktion zu implementieren. Die Funktion e^-x ist nur ein Beispiel. In meinem Fall, habe ich ein gemessenes Signal, das periodisch ist. Dieses Signal muss ich analysieren und um was zu bestimmen brauche ich die fourier Transformation von dem Signal. Einfach die FFT oder DFT zu nehmen hat nicht das richtige Ergebnis wiedergegeben leider. Was würdest du denn vorschlagen ? um aus signal(t) ein signal(f) zu berechnen ? Danke im voraus.
Benutzeravatar
MagBen
User
Beiträge: 799
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

Das Fourier Integral geht von Minus Unendlich bis Plus Unendlich.
Die diskrete Zeitreihe für die FFT kann aber nicht unendlich sein. Das Ergebnis der FFT entspricht deshalb einer FT, wenn man sich die Zeitreihe unendlich periodisch fortgesetzt vorstellt. Es ist deshalb wichtig, dass die Zeitreihe bei Null anfängt und bei Null aufhört. Das tut aber Deine Funktion nicht.
a fool with a tool is still a fool, www.magben.de, YouTube
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@Tassou: was in Deinem verlinkten Artikel als Sichtweisen umschrieben wird, sind mathematisch gesehen eigentlich unterschiedliche Transformationen. Jede für sich ist mathematisch sehr gut verstanden und exakt. Wenn man aber anfängt, wild mit den Begriffen um sich zu schmeißen, kann man leicht etwas durcheinanderbringen. Zuerst sei da die Fouriertransformation, die beschreibt, wie man eine beliebige stetige Funktion f(x) in ihre Fouriertransformierte F(x) umrechnen kann. Verwandt dazu ist die Fourier-Reihe, die beliebige stetige periodische Funktionen f(x+2*pi*n) in eine unendliche Reihe a_m umrechnet. Und als drittes gibt es da noch die diskrete Fouiertransformation, die eine endliche Folge, die man sich periodisch fortgesetzt denkt, in eine andere endliche Folge umrechnet. Alle drei Methoden sind mathematisch exakt und haben eine inverse Transformation, die wieder die ursprüngliche Funktion erzeugt.

Warum macht man das überhaupt? Es gibt einige Probleme, die sich im Frequenzraum einfacher lösen lassen. Signal- oder Bildverarbeitung, Kompression, Filter, Faltung, etc. Wenn man jetzt noch ein diskretes, endliches Signal hat, bietet es sich an, eine diskrete Fouiertransformation zu benutzen. Unter der Annahme, dass das Signal zwischen den Messstellen brav ist, kann man die Näherung machen, dass hohe Frequenzen verschwinden und man hat aus der unendlichen Fourierreihe eine endliche gemacht. Somit lassen sich viele Eigenschaften von Fouierreihen auf diskrete Signale übertragen, solange gilt, dass das Signal periodisch ist.

Was tun, wenn das Signal nicht periodisch ist? Zuerst einmal können wir gar nicht sagen, dass das Signal nicht periodisch ist, weil bei einer endlichen diskreten Abtastung haben wir gar keine Information darüber, wie das Signal außerhalb des Bereichs aussieht. Trotzdem ist es manchmal unschön, dass das Aussehen der linken Seite sich rechts bemerkbar macht und umgekehrt. Will man das nicht, gibt es das Padding, d.h. man fügt rechts und links genügend viele (meist konstante Werte, meist 0) hinzu, um das Übersprechen der linken auf die rechte Seite zu dämpfen.

Ach ja, das unsägliche FastFourier. Eigentlich ist es in der Informatik üblich, zu beschreiben, was eine Funktion macht und nicht wie. Alle fft-Funktionen sollten eigentlich dft heißen, weil sie eine diskrete Fouriertransformation durchführen. Da kann man sich geschickt anstellen oder ungeschickt. Und das hat auch nichts mit Computern zu tun. Gauß stand schon 150 Jahre vor den ersten richtigen Computern vor dem Problem, Fouriertransformierte zu berechnen und hat sich die Arbeit einfacher gemacht.

Zusammenfassung: FFT ist eigentlich DFT, die diskrete Fouriertransformation, die diskretisierte Form der Fourierreihe. Funktioniert für periodische Strukturen und hat nur entfernt etwas mit der Fouriertransformation zu tun.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@MagBen: nein, die Zeitreihe muß periodisch sein. Eine gute Näherung ist es schon einmal, wenn die Funktion keine Sprünge macht, aber auch dann noch kann es zu Artefakten kommen, weil die linke Seite auf die rechte und umgekehrt überspricht.
Tassou
User
Beiträge: 3
Registriert: Sonntag 16. April 2017, 11:16

Sirius3 hat geschrieben:@Tassou: was in Deinem verlinkten Artikel als Sichtweisen umschrieben wird, sind mathematisch gesehen eigentlich unterschiedliche Transformationen. Jede für sich ist mathematisch sehr gut verstanden und exakt. Wenn man aber anfängt, wild mit den Begriffen um sich zu schmeißen, kann man leicht etwas durcheinanderbringen. Zuerst sei da die Fouriertransformation, die beschreibt, wie man eine beliebige stetige Funktion f(x) in ihre Fouriertransformierte F(x) umrechnen kann. Verwandt dazu ist die Fourier-Reihe, die beliebige stetige periodische Funktionen f(x+2*pi*n) in eine unendliche Reihe a_m umrechnet. Und als drittes gibt es da noch die diskrete Fouiertransformation, die eine endliche Folge, die man sich periodisch fortgesetzt denkt, in eine andere endliche Folge umrechnet. Alle drei Methoden sind mathematisch exakt und haben eine inverse Transformation, die wieder die ursprüngliche Funktion erzeugt.

Warum macht man das überhaupt? Es gibt einige Probleme, die sich im Frequenzraum einfacher lösen lassen. Signal- oder Bildverarbeitung, Kompression, Filter, Faltung, etc. Wenn man jetzt noch ein diskretes, endliches Signal hat, bietet es sich an, eine diskrete Fouiertransformation zu benutzen. Unter der Annahme, dass das Signal zwischen den Messstellen brav ist, kann man die Näherung machen, dass hohe Frequenzen verschwinden und man hat aus der unendlichen Fourierreihe eine endliche gemacht. Somit lassen sich viele Eigenschaften von Fouierreihen auf diskrete Signale übertragen, solange gilt, dass das Signal periodisch ist.

Was tun, wenn das Signal nicht periodisch ist? Zuerst einmal können wir gar nicht sagen, dass das Signal nicht periodisch ist, weil bei einer endlichen diskreten Abtastung haben wir gar keine Information darüber, wie das Signal außerhalb des Bereichs aussieht. Trotzdem ist es manchmal unschön, dass das Aussehen der linken Seite sich rechts bemerkbar macht und umgekehrt. Will man das nicht, gibt es das Padding, d.h. man fügt rechts und links genügend viele (meist konstante Werte, meist 0) hinzu, um das Übersprechen der linken auf die rechte Seite zu dämpfen.

Ach ja, das unsägliche FastFourier. Eigentlich ist es in der Informatik üblich, zu beschreiben, was eine Funktion macht und nicht wie. Alle fft-Funktionen sollten eigentlich dft heißen, weil sie eine diskrete Fouriertransformation durchführen. Da kann man sich geschickt anstellen oder ungeschickt. Und das hat auch nichts mit Computern zu tun. Gauß stand schon 150 Jahre vor den ersten richtigen Computern vor dem Problem, Fouriertransformierte zu berechnen und hat sich die Arbeit einfacher gemacht.

Zusammenfassung: FFT ist eigentlich DFT, die diskrete Fouriertransformation, die diskretisierte Form der Fourierreihe. Funktioniert für periodische Strukturen und hat nur entfernt etwas mit der Fouriertransformation zu tun.
@Sirius3: Erstmal vielen Dank für die ausführliche Erklärung. Diese hat mir vieles klar gemacht! Danke. Nun besteht mein echtes Problem darin, dass ich dabei bin, ein mathematisches Modell zu implementieren. Zusammengefasst sieht es so aus :
Ich messe ein Signal mit einer Abtastungsfrequenz Fs, dieses Signal kommt aus einer Anregung, die eine Frequenz F0<Fs/2 hat. Das Signal werde ich so betrachten : Über einer Periode 1/F0 zerlege ich es in 2 Hälften : signal_pos(t) and signal_negativ(t). Wichtig hierbei ist : signal_negativ(t) = -signal_positiv(-t). Und signal_positiv(t) = signal(t)*r(t), signal_negativ(t) = -signal(-t)*r(t). Mit r(t) = 1/tau * exp(-t/tau) und signal(t) eine Point-spread function. Jetzt möchte ich das ganze im Frequenzbereich betrachten um diese Tau auszurechnen und zwar heißt es stetig so schön : tau =( S_pos*(f) + S_neg(f) ) /[(S_pos*(f)- S_neg(f))* 2*pi*f] wo F{signal_positiv(t)} = S_pos und F{signal_negativ(t)} = S_neg = -S_pos*. Ich hoffe du verstehst gerade warum, ich eine ähnlich Transformation suche wie die analytische Transformation. Das Problem ist, wenn ich einfach nur die np.fft.fft nehme, ist das Ergebnis der unterstrichenen Gleigung falsch und ich komme nicht auf tau wieder. Hättest Du dazu einen Vorschlag vielleicht, wie ich am besten dran gehen soll ?
Benutzeravatar
MagBen
User
Beiträge: 799
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

Sirius3 hat geschrieben:die Zeitreihe muß periodisch sein
Sehe ich anders. Will man das Frequenzspektrum z.B. von einem Geigenton aufnehmen, dann wird der Ton kurz angestrichen und dabei aufgenommen. Die Aufnahme fängt bei Null an (im Studio herscht absolute Stille) und hört bei Null auf (wenn die Geige nicht mehr nachklingt). Diese endliche Aufnahme kann deshalb wie eine unendlich lange Aufnahme behandelt werden. Den vor und nach der Aufnahme sind nur Nuller und diese machen keinen Beitrag zum Fourier Integral. Auf die Aufnahme kann man nun eine FFT anwenden und am Spektrum kann man dann sehen, ob es eine Thoman Geige oder eine Stradivari Geige ist (und ob der Geiger geigen kann).

Will man in einem Gebäude für alle hörbaren Frequenzen die Übertragungsfunktion von einem Stockwerk ins andere messen (d.h. wie breitet sich Lärm in Abhängigkeit der Frequenz aus), dann verursacht man in dem einen Stockwerk einen Knall (angenäherte Delta-Funktion, enthält alle Frequenzen) und misst die Geräusche in beiden Stockwerken. Beide Geräusche sind nicht periodisch, sondern endlich und müssen bei Null anfangen und aufhören, dann können beide mit FFT transformiert werden, man dividiert die Spektren und schon hat man die Übertragungsfunktion.

Den Test auf meiner Seite
http://www.magben.de/?h1=mathematik_fue ... urier_code
braucht man um testen zu können ob man die FFT richtig anwendet. Dazu muss man was transformieren wovon man das Spektrum schon kennt: eine analytische Funktion. Und wie kennt man das Spektrum? Durch die Forier Transformation. Also hat man das Problem, das Ergebnis der FT und der FFT in Übereinstimmung zu bringen.

Klar ist die FFT eine DFT und die FFT ist "lediglich" eine Implementation. Aber wäre die Implementation nicht die FFT würde vieles aus Performance Gründen nicht funktionieren. Deshalb sprechen Macher meistens nur von FFT.
Und manchmal auch von FFTW: Fastest Fourier Transform in the West, der Name klingt einfach krass.
a fool with a tool is still a fool, www.magben.de, YouTube
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@MagBen: wieder falsch. Erstens hast Du kein Fourierintegral, sondern nur eine diskrete Summe, die auch nicht von -∞ bis +∞ geht, sondern eben nur über einen endlichen Bereich, und diesen mußt Du Dir als periodisch fortgesetzt denken, also ein sich ständig wiederholender Geigenton, oder ein andauernder Knall. Nun mag das für Deine Beispiele nicht relevant sein. Da ist es dann auch nicht relevant, ob die bei 0 anfangen oder irgendwo anders. Es ist einfach falsch, ein unendliches Integral mit einer endlichen Summe vergleichen zu wollen. Bei geschickt gewählten Randbedingungen sieht das Ergebnis vielleicht ähnlich aus, das eine setzt sich aber periodisch fort, das andere nicht.
Es gibt etliche Varianten, um eine diskrete Fouriertransformation zu berechnen, alles wird heutzutage als FFT verkauft, weil sich das als Synonym für DFT eingebürgert hat. Mathematisch gesehen ist das alles eine Summation; will man also die mathematischen Eigenschaften erklären, reicht auch die simple Summe aus.
Antworten