Forum: Digitale Signalverarbeitung / DSP / Machine Learning FFT für Vielfache von 360°


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 Andi (chefdesigner)


Lesenswert?

Ich suche nach einer Möglichkeit die Berechnung für 360 Wertepaare zu 
optimieren. Ist da etwas bekannt?

Bislang fahren wir jeweils 512 Punkte und interpolieren, was nicht so 
gut gelingt und deshalb besteht die Überlegung, auf 1024 zu wechseln und 
dann die Ergebnisse auf 360 abzubilden.

Es müssen 360 sein weil das Frequenzen sind, die mit Phasenwinkeln 
korellieren.

Idee?

von Thorsten S. (thosch)


Lesenswert?

Die FFT nutzt die Symmetrien der DFT bei Längen von 2^n für die 
vereinfachte Berechnung.
Daher ist eine FFT prinzipbedingt stets nur mit Längen von 
Zweierpotenzen möglich.

Die DFT unterliegt dieser Beschränkung nicht und kann über beliebige 
Längen berechnet werden. Der Rechenaufwand ist allerdings erheblich 
höher als bei der FFT.

von Daniel G. (denial)


Lesenswert?

Eine klassische FFT hat eine Laufzeit von O(n*log2(n)), weil sie aus 
log2(n) hintereinandergeschalteten Stufen von n butterfly Operationen 
besteht. Mit jeder Stufe werden die Ergebnisse von halb so großen FFTs 
miteinander verrechnet.

Das ganze lässt sich auch auf Zahlen erweitern, die keine Zweierpotenzen 
sind. Bei der 360 hat man als Faktoren neben drei 2en auch zwei 3en und 
eine 5. Für eine 3 hätte man dann eine Stufe die drei FFTs verrechnet, 
die ein Drittel so groß sind und für die 5 eine Stufe, die fünf FFTs 
verrechnet, die ein Fünftel so groß sind. Bibliotheken wie FFTW machen 
die Primfaktorzerlegung von selbst und haben für kleine Faktoren 
vorgefertigte Codeschnipsel, die dann verkettet werden.

: Bearbeitet durch User
von Andi (chefdesigner)


Lesenswert?

Die abschnittsweise Reduzierung der Rechnung habe ich in Erinnerung. 
Wurde im Studium vorgerechnet und verstanden. Leider aber nun 25 Jahre 
her und nicht mehr in Erinnerung. Code-Fragemente die ich 
hintereinnderschalten könnte, wären sicher eine Hilfe. Ein Suche war 
aber bisher noch erfolglos.

von M. K. (sylaina)


Lesenswert?

Man könnte jetzt entsprechend Aufwand treiben mit der FFT und 
entsprechenden Umrechnungen. Man könnte natürlich auch erstmal prüfen, 
ob eine DFT für die Aufgabe nicht hinreichend schnell ist sodass man 
sich das gezumpel mit der FFT nicht sparen kann. Für nicht genutzte 
Rechenkapazität gilt das selbe wie für nicht genutzt Speicherkapazität: 
Dafür gibts kein Geld zurück ;)

von Larius (Gast)


Lesenswert?

Doofe Frage: Warum kann man nicht einfach die nächst größere FFT nehmen 
und die überzähligen Ergebnisse ignorieren?

von Arc N. (arc)


Lesenswert?

http://www.fftw.org/ kann sowas auch in O(n log n)
"Arbitrary-size transforms. (Sizes with small prime factors are best, 
but FFTW uses O(N log N) algorithms even for prime sizes.)"
360 = 2  2  2  3  3 * 5 sollte also auch schnell gehen.

von Dergute W. (derguteweka)


Lesenswert?

Moin,

Michael L. schrieb:
> Doofe Frage: Warum kann man nicht einfach die nächst größere FFT
> nehmen
> und die überzähligen Ergebnisse ignorieren?

Weil das genauso clever ist, wie wenn man zur Samplerateconversion 
einfach mal ein paar Samples weglaesst oder welche wiederholt.
Kann man so machen, wird halt shice.
Zum Originalproblem: Wuerd' ich auch nicht lange rummachen und das Rad 
versuchen wollen selber zu erfinden, sondern eher gucken, dass ich fftw 
fuer die eigene HW compiliert krieg'.

Gruss
WK

von Larius (Gast)


Lesenswert?

Dergute W. schrieb:
> Weil das genauso ist, wie wenn man zur Samplerateconversion
> einfach mal ein paar Samples weglaesst
Da sehe ich den Zusammenhang nicht.
Die FFT wird nicht verfälscht, wenn man mehr Frequenzen berechnet und 
diese nicht benutzt. Der Rest ist nicht tangiert. (???)

von Dergute W. (derguteweka)


Lesenswert?

Moin,

Michael L. schrieb:
> Dergute W. schrieb:
>> Weil das genauso ist, wie wenn man zur Samplerateconversion
>> einfach mal ein paar Samples weglaesst
> Da sehe ich den Zusammenhang nicht.
Dann solltest du da genauer hinschauen ;-)

scnr,
WK

von Jürgen S. (engineer) Benutzerseite


Angehängte Dateien:

Lesenswert?

Bei der FFT bilden sich "Frequenznummern" mit ganzzahliger Teilung der 
Abtastfrequenz anhand der FFT-Tiefe. Will man das auf ein anderes 
"Raster" bringen, muss man entweder die Ergebnisse interpolieren, was 
der TE offenbar nicht nöchte, oder (wenn man es in Echtzeit physikalisch 
braucht) die Abtastfrequenz ändern und die Eingangswerte interpolieren. 
Beides hat seine Vor- und Nachteile. Die Methode 2 wende ich bei einem 
meiner Audio-GEQ an, der aus das Signal wieder zusammensetzt, profitiere 
aber von einem geschickt gestrickten Interpolationsfilter und der 
massiven Überabtastung, die ich im FPGA benutze.

Für DSPs und Software ist eine Interpretation der Ergebnisse mit 
Interpolation einfacher.

Auch beim FPGA ist das oft der Weg, wenn es nicht so genau sein muss, 
wie bei einer Anzeige: Einfach die reinrauschenden FFT-Ergebnisse aus 
dem Core mit einem einfachen Fenster summieren und jeweils den oberen 
Bereich benutzen. Eine 2k-FFT löst bis auf 1 Hz auf, wenn man es 
Oktaven-weise kaskadiert.

von Andi (chefdesigner)


Lesenswert?

Arc N. schrieb:
> 360 = 2  2  2  3  3 * 5 sollte also auch schnell gehen.

Das hatte ich mir angesehen.

von Dergute W. (derguteweka)


Lesenswert?

Andi F. schrieb:
> Arc N. schrieb:
>> 360 = 2  2  2  3  3 * 5 sollte also auch schnell gehen.
>
> Das hatte ich mir angesehen.

Und?

von Andi (chefdesigner)


Lesenswert?

Wegen Aufwand verworfen :-)

von Jürgen S. (engineer) Benutzerseite


Lesenswert?


Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.