Forum: Digitale Signalverarbeitung / DSP FFT mit nicht-2er-Potenzen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Newbie (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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?

von blub (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Zero-Padding sollte funktionieren

von Andreas S. (Firma: Schweigstill IT) (schweigstill) Benutzerseite


Bewertung
3 lesenswert
nicht lesenswert
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

von Andreas S. (Firma: Schweigstill IT) (schweigstill) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Newbie (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Die Auswertung erfolgt meines Wissens in Matlab, welche Funktionen zur 
Anwednung kommen weiß ich nicht.

von Systemgewinner (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Komisch, warum geht er überhaupt noch mit nem Filter über das Signal?

von El Ef (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von dumdidum (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von dumdidum (Gast)


Bewertung
0 lesenswert
nicht lesenswert
(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.

von Newbie (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Okay, danke für die Antworten.
Also ist der Fehler woanders zu suchen.

von Alexander S. (alesi)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Mathias A. (mrdelphi)


Bewertung
0 lesenswert
nicht lesenswert
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...

von Hp M. (nachtmix)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Rechenfreak (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Rechenfreak (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Andreas S. (Firma: Schweigstill IT) (schweigstill) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Rechenfreak (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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".

von Bernd (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.