Hallo,
ich bin gerade verwirrt!
Wir haben einen Kunden, der unsere Messungen nachvollziehen will -
allerdings andere Ergebnisse erhält.
Dazu macht er eine FFT mit 1000 Stützstellen.
Auf meinen Hinweis, dass es 1024 (Zweierpotenz) sein müssten, meinte er,
dass sei egal, dafür gebe es ja den Fenster-Filter - den er ebenfalls
über 1000 Werte laufen lässt.
Ich hab inzwischen so viel gelesen und bin einfach nur verunsichert,
zumal ich weiß, dass Theorie und Praxis teilweise 2 Paar Schuhe sind und
der Kunde ist schon 35 Jahre im Geschäft, ich quasi Newbie - will mich
da mit niemandem "anlegen".
Ist eine FFT mit Nicht-2er-Potenzen möglich (oder müsste dann nicht eine
DFT genutzt werden) - und kann man das über die Fensterung kaschieren?
Eine FFT nach Cooley und Tukey funktioniert ausschließlich mit
Blocklängen, die Zweiterpotenzen entsprechen. Gleiches gilt auch für die
meisten davon abgeleiteten Verfahren, bei denen z.B. Multiplikationen
teilweise durch Additionen ersetzt werden, usw..
Es gibt jedoch den sog. Bluestein-FFT-Algorithmus, der nicht auf
Zweierpotenzen basiert; dies wird auch als Chirp-z-Transformation
bezeichnet. Solange aber nicht explizit dieses Verfahren ausgewählt
wurde, sollte man schon davon ausgehen, dass es sich um eine
"klassische" FFT handelt.
https://de.wikipedia.org/wiki/Bluestein-FFT-Algorithmus
blub schrieb:> Zero-Padding sollte funktionieren
Natürlich funktioniert das, aber es gibt dann ggf. ganz erhebliche
Artefakte. Wenn man sich ein Zeitsignal vorstellt, dann bedeutet das ein
periodisches "Knacken" bzw. einen Phasensprung.
Newbie schrieb:> Ist eine FFT mit Nicht-2er-Potenzen möglich (oder müsste dann nicht eine> DFT genutzt werden) - und kann man das über die Fensterung kaschieren?
Eine FFT ist eine effiziente Implementierung einer DFT für den
Spezialfall, dass die Blocklänge einer Zweierpotenz entspricht.
Im Ergebnis ist es daher im Grunde Egal, nur nicht so effizient zu
berechnen.
Die Funktionen 'fft' z.B. in Matlab oder Python berechnen eine DFT
beliebiger Länge in schnell. Wenn die Länge eine 2er Potenz ist wird das
Radix-2 Verfahren (vermutlich) angewendet, ansonsten wird eine
Primfaktorzerlegung duchgeführt, und sofern es ausreichend viele
Faktoren gibt ist sie auch schnell. Im schlimmsten Fall ist sie langsam.
Es wird jedoch immer 'richtig' ohne Zero-Padding gerechnet.
Insbesondere da 1000=2^3*5^3 kann man bei 1000 von eine fft sprechen.
(und natürlich die FFTW kann auch alle Längen, sogar immer in schnell:
http://www.fftw.org/fftw3_doc/Introduction.html)
Meiner Meinung nach gibt es keine aktuelle FFT Bibliotheken (ausser
selbstgestrickte :-), die nur Potenzen von 2 zulassen.
Hallo,
falls das wer selber programmieren möchte oder sich für den Algorithmus
interessiert. Hier zwei ältere Artikel von Singleton
Algorithm 338: algol procedures for the fast Fourier transform
https://dl.acm.org/doi/abs/10.1145/364139.364167
Algorithm 339: an algol procedure for the fast Fourier transform with
arbitrary factors
https://dl.acm.org/doi/abs/10.1145/364139.364168
Wegen COVID-19 gibt es bei ACM DL freien Zugriff auf die Artikel bis
Ende Juni.
Newbie schrieb:> Okay, danke für die Antworten.> Also ist der Fehler woanders zu suchen.
Das könnte an dem Fenster-Filter liegen. Weißt Du welches der Kunde
einsetzt? Und hast Du bei Euren Messungen eines verwendet? Wenn
unterschiedlich, könnte das die Abweichungen der Ergebnisse erklären...
Newbie schrieb:> Also ist der Fehler woanders zu suchen.
Synthetisiere Werte ähnlich des fraglichen Signals und lass die beiden
FFT darauf los.
Dann wirst du ja sehen, welche davon (oder ob überhaupt eine) richtig
arbeitet.
Andreas S. schrieb:> Natürlich funktioniert das, aber es gibt dann ggf. ganz erhebliche> Artefakte. Wenn man sich ein Zeitsignal vorstellt, dann bedeutet das ein> periodisches "Knacken" bzw. einen Phasensprung.
Das stimmt so nicht. Es hängt von der Fensterung ab und der Art, wie die
Messfrequenz in die 1024 passt. Ich habe schon genau solche Tricks
angewendet, um die FFT für Teiler von 800/ 700/ 600/ anzuwenden, weil
die zu messenden Frequenzen dem entsprechen. Letztlich ist die eine
nicht besser, als die andere. Deine Aussage zu C.T. stimmt auch nur
insofern, als dass die Vereinfachungen, die rechenmäßig angewendet
werden es zwingend erfordern, dass 2 hoch N Daten genutzt werden. Sobald
einige davon NULL sind tragen die Koeffizienten auch nichts zur
Summenbildung bei.
Newbie schrieb:> Dazu macht er eine FFT mit 1000 Stützstellen.
Die Frage ist: WIE??? hat er das gemacht? Hat er Zero-Padding betrieben,
oder hat er eine ganzzahlige Vielfachung der Messperiode gewählt?
Es kann durchaus Sinn machen, eine bestimmte Länge zu nehmen. Eine FFT
kann auch mit 773 Stellen gerechnet werden. Sie kann nur nicht mehr in
eine einfache Berechnung mit Butterfly und Mehrfachnutzung von Termen
berechnet werden.
Rechenfreak schrieb:> Das stimmt so nicht. Es hängt von der Fensterung ab und der Art, wie die> Messfrequenz in die 1024 passt.
Naja, die Fensterung dient eigentlich nur der Symptombekämpfung, weil im
Allgemeinen natürlich nicht sichergestellt werden kann, dass die
Periodizitäten aller im Signal enthaltenen Frequenzen exakt zum
Abtastinterval passen.
Ja, das ist bekannt, allerdings kann man ja das FEnst auf eben diese
1000 auslegen und damit auf die zu messenden Bereiche anpassen. Zudem
kann man parallel mit mehreren FEnstern messen, um auf andere Frequenzen
zu optimieren, sprich: "die unpassenden in ihrer Auswirkung zu bremsen".
Newbie schrieb:> Wir haben einen Kunden, der unsere Messungen nachvollziehen will -> allerdings andere Ergebnisse erhält.
Was ist denn anders? Stimmen die 'Amplituden' nicht oder die
'Frequenzen'?
Ich würde auch mit bekannten Signalen (Sinus) die Implementierung
vergleichen bzw. testen.
Eine eigene Frage?
Dieser Thread ist über 6 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
