FFT - Zweierpotenz

[Lydi (Gast)]

Hallo!

Könnte mir jemand erklären, aus welchem Grund die Datenpunkte bei der 
Segmentierung von EEG-Daten für die FFT eine Zweierpotenz sein sollen?

Wäre super!

Mfg,

Lydi

[Andreas S. (andreas) (Admin)]

Weil der FFT-Algorithmus eine rekursive Aufteilung in FFTs der jeweils 
halben Länge vornimmt. Siehe 
http://de.wikipedia.org/wiki/Schnelle_Fourier-Transformation.

[Bastler (Gast)]

Das liegt an der DFT-Implementierung. Man kann die DFT mit 
mathematischen Umformungen sehr effektiv implementieren, die man dann 
FFT nennt. Damit man diese Umformungen anwenden kann, muss die Anzahl 
der Stützstellen eine Potenz von 2 bei einer Radix-2-FFT, von 4 bei 
einer Radix-4-FFT, usw. sein.

[I_ H. (i_h)]

Man kann auch andere Primfaktoren als Grundlage für die FFT benutzen 
(zB. 3), und man kann eine FFT auch mit nahezu beliebig vielen Werten 
verwenden, indem man die Primfaktorenzerlegung betrachtet.
2^n enthält, wenn ich mich richtig erinnere, O(n) DFTs der Länge 2 und 
noch ein bissel Zusatzgerechne. Genauso ließe sich auch 3^n realisieren, 
wobei die DFTs dann eben auf 3 Werte angewendet sind. Ebenso könnte man 
auch eine FFT auf 6 Werte über eine DFT auf 2 und eine DFT auf 3 Werte 
berechnen, oder ganz allgemein 2^n*3^m.

Die Primfaktoren gehen glaub mit konstantem Faktor ein, das heist eine 
FFT auf 3^n ist konstant langsamer als eine auf 2^m mit 2^m=3^n. 
Desswegen, und weil 2 die meisten möglichen Werte anbietet (liegt halt 
immer Faktor 2 dazwischen), nimmt man 2 als Basis.