Hallo, geht es eigentlich noch schneller als FFT? Momentan scheint kein Algorithmus zu existieren, der weniger Multiplikationen und Additionen braucht. Ist nachgewiesen, dass es nicht noch effizienter geht? Wie hoch ist die theoretisch notwendige Komplexität?
Gast
#2472056
Sie Dir mal die Quellen der FFTQ an. Dort gibt es einige Hinweise auf Untersuchungen. Die FFT an sich ist mit Sicherheit das Effektivste, allerdings gibt es je nach Rechnerarchitktur unterschiedliche Ansätze der Realisation, die unterschiedlich schnell sein können.
Gast
#2472060
Eine übertragfreie Implementation über einem Galoiskörper scheinst Du noch nicht in Betracht gezogen zu haben.
Gast
#2472191
> Eine übertragfreie Implementation über einem Galoiskörper > scheinst Du noch nicht in Betracht gezogen zu haben. Ich gestehe wir verlassen jetzt so langsam Gebiet meiner mathematischen Kenntnisse, aber ist dies nicht sowieso die Grundidee die in jeder Transformation steckt? Olaf
Gast
#2474801
Stefan Helmert schrieb: > geht es eigentlich noch schneller als FFT? Von welcher der vielen Implementierungen der FFT sprichst Du überhaupt. Gerade bei der FFT gibt es sooo viele verschiedene Implementierungen für "Spezialfälle" um in irgend eine Richtung zu optimieren. (Radix-2, Radix-4, Radix-16, split Radix, real valued, in place usw.) Gruß Anja
Olaf schrieb: > aber ist dies nicht sowieso die Grundidee die in jeder > Transformation steckt? ääähhhh nein :D
Im "Meyer-Baese" ISBN 9783540726128 sind noch ein paar exotische Varianten erwähnt, mit ternären Zahlendarstellungen oder Zahlensystemen ohne Null.
Gast
#2508805
Gerade gesehen, s. http://www.physorg.com/news/2012-01-faster-than-fast-fourier.html
Gast
#2510280
Naja, die bewerten nochmal die Gewichtungen. Das geht jetzt aber mehr in die logische Verwendung des Algos. Die Annahme, dass die meisten (hier 57 von 64) Frequenzen nicht so wichtig seien, ist natürlich sehr vom Fall abhängig. Schon jetzt kranken ja einige Anwendungen daran, dass sie hart am Kompromiss zwischen frequenzgenauer und amplitudengenauer FFT (Fensterung) hängen und die FFT nicht genügend genau abbildet. Und die Apps, in denen man Frequenzen gewichten und nur die wichtigen untersuchen muss oder will, können das auch mit dedizierten Frequenzen und DFT oder Görzel machen.