Punktweise FFT effektiv realisieren

[Edi M. (Gast)]

Ich benötige eine FTT für sehr kurze Signale und leide an dem Problem, 
dass sie relativ fein aufgelöst sein muss. Die Schwierigkeit stellt sich 
nun so dar, dass bei einer angenommenen Zahl von 128 Stellen, zunächst 
nur alle 128 Punkte einen FFT mit 2x64 Frequenzen heraus kommt und das 
kurze Signal so ungünstig über die FFTs verteilt ist, dass es zwischen 
zwei FFTs hängt und zu stark gedämpft wird, weil es nur teilerfasst 
wird. FFT averagin scheidet aus, weil das Signal nicht periodisch ist 
und nur kurz auftritt.

Der erste Ansatz war, zwei FFTs zu überlappen, allerdings sieht es nun 
so aus, dass die Fensterung als Verzerrer wirkt. Ich arbeite mit einem 
engen Kaiserfenster und bekomme nur dann, wenn das Signal exakt mittig 
in der FFT oder exakt genau zwischen zweien (also im Zwischenraum) ist, 
zwei vergleichbare Spektren, anhand deren Verlauf ist Entscheidungen 
treffen kann.

Die Lösung ist nun (mit MATLAB verfiziert) für jede Punktgruppe eine FFT 
zu machen, als von

0...127
1...128
2...129
...
126 .. 253
127...254
128 ... 255
ab dann wieder weiter
129 ... 256

usw

Ich benötige also 128 parallele FFTs! Frage: Gibt es dafür einen 
optimierten Algorithmus? Oder muss ich de 128 sequenziell laufen lassen?

[abcd (Gast)]

Sieht man sich die Formel für die N Punkte DFT

$$X[n] = DFT_N{(x[n])} = \sum_{k=0}^{N-1} {x[k] \cdot e^{j 2 \pi k n /N}}$$

an, erkennt man, dass jeder Wert X[n] von jedem Eingangswert x[k] 
abhängt.

Nun schauen wir uns das Signal K Schritte später an.

$$\sum_{k=0}^{N-1} {x[k+K] \cdot e^{j 2 \pi k n /N} = X[n] \cdot e^{j 2 \pi K n/N}}$$

Letzteres gilt allerdings nur, falls das Signal periodisch ist. Also 
müssen wir uns noch mehr Gedanken machen.

Der Einfachheit halber nehmen wir mal an, wir haben X[n] gegeben und 
kriegen nun einen neunen x-Wert. Das neue Signal nennen wir y[n] und es 
gilt y[k] = x[k+1] für 0≤n<N-1.
y[N-1] = der neue x-Wert.

Jetzt kann man sich das ganze schön überlegen:

$$Y[n] = \sum_{k=0}^{N-1} {y[k] \cdot e^{j 2 \pi k n /N}} = y[N-1] e^{j 2 \pi n (N-1) /N} + \sum_{k=0}^{N-2} {y[k] \cdot e^{j 2 \pi k n /N}} =$$

$$y[N-1] e^{j 2 \pi n (N-1) /N} + e^{j 2 \pi n/N} \cdot \sum_{k=0}^{N-2} {x[k+1] \cdot e^{j 2 \pi k n /N}} = y[N-1] e^{j 2 \pi n (N-1) /N} + \sum_{k=0}^{N-2} {x[k+1] \cdot e^{j 2 \pi k (n+1) /N}}$$

Und da sehen wir schon etwas Grundsätzliches:

$$Y[n] = y[N-1] e^{j 2 \pi n (N-1) /N} + \cdot DFT_{N-1}(x[k+1])$$

$$DFT_{N-1}(x[k+1]) = \sum_{k=0}^{N-2} {x[k+1] \cdot e^{j 2 \pi k (n+1) /N}} = \sum_{k=-1}^{N-2} {x[k+1] \cdot e^{j 2 \pi k (n+1) /N}} - x[0] = DFT_{N}(x[k]) - x[0]$$

Daraus folgt, dass sich das neue Spektrum Y[n] aus dem alten X[n] ergibt 
aus:

$$Y[n] = y[N-1] e^{j 2 \pi n (N-1) /N} + DFT_{N}(x[k]) - x[0] = y[N-1] e^{j 2 \pi n (N-1) /N} + X[n] - x[0]$$

So. Habe alles aus dem Kopf und spontan aufgeschrieben. Also ist die 
Wahrscheinlichkeit groß, dass sich irgendwo ein Fehler eingeschlichen 
hat (irgendwie vermisse ich noch eine Phasenverschiebung des alten 
Spektrums). Aber das Grundprinzip sieht so aus. Am Besten einfach noch 
mal nachrechnen.

[abcd (Gast)]

Hab es gerade in Matlab getestet. So wie ich es ausgerechnet habe ist es 
definitiv falsch. Der Fehler liegt wahrscheinlich irgendwo darin, dass 
ich vergessen habe, dass bei der N-1 Punkte DFT in der 
Exponentialfunktion natürlich dann auch durch (N-1) geteilt werden muss 
und nicht durch N. Ich hoffe es hilft trotzdem weiter.

[Strubi (Gast)]

Moin,

den Ansatz von abcd unterschreib ich mal mit (modulo Normierung, so 
genau weiss ich das auch nie auswendig). Diesen 'sliding DFT'-Ansatz 
hätt ich jetzt auch mal als erstes rangenommen. Unter dem Stichwort 
sollte auch so einiges zu finden sein.
Trotzdem gibt es dann noch das Artefakt-Problem (bei fehlender 
Fensterung). Das muss man dann it einer sekundären Logik (Filterung) 
angehen, was die Sache wieder schrecklich kompliziert macht. Welche 
Fenster man da elegant innerhalb der Sliding DFT verwendet, wäre noch 
interessant.

[Ralle (Gast)]

Wenn man für das Fenster etwas einfaches, cosinusförmiges nähme, könnte 
man die so entstehenden Faktoren sicher irgendwie mit den Cos/Sin Werten 
verknüpfen, die aus der FFT kommen. Müsste man sich mal aufzeichnen...