Hallo,
ich wollte mich (wieder einmal mehr....) mit dem Thema FFT auseinander
setzen.
Anstatt zu versuchen, wie das ganze funktioniert, habe ich es mir
diesmal etwas einfacher gemacht und unter
http://www.jjj.de/fft/
Die fix_fft heruntergeladen, eine FFT-Funktion mit Festpunktarithmetik.
Erstmal habe ich mit Visual Studio ein bisschen damit herumgespielt, das
Programm scheint ansich zu funktionieren. Auch auf meinem Zielsystem,
einem ARM7-Rechner, läuft es ohne Probleme recht fix durch (Performance
habe ich allerdings noch nicht analysiert).
Aber, was mir nicht ganz klar ist:
Im Testprogramm der FFT wird eine komische "Umsortierung" der Samples
vorgenommen:
1 | for(i=0; i<N; i++)
|
2 | {
|
3 | x[i] = AMPLITUDE*cos(i*FREQUENCY*(2*3.1415926535)/N);
|
4 | if (i & 0x01) /* wozu braucht es diese if-Abfrage?! */
|
5 | fx[(N+i)>>1] = x[i];
|
6 | else
|
7 | fx[i>>1] = x[i];
|
8 | }
|
Mir ist klar, dass man bei der FFT erst diesen Bitreversal-Algorithmus
durchführen muss; aber in der eigentlichen FFT-Funktion wird auch etwas
derartiges gemacht. Im Kommentar heisst es lediglich "re-order data",
was auch immer das bedeuten mag.
Meine Frage jetzt:
1. Wozu ist diese if-Abfrage in obigem Codeschnipsel nötig? Kann ich der
FFT-Funktion nicht einfach die Rohdaten übergeben, welche ich von meinem
AD-Wandler kriege?
2. Wie kann ich testen, ob das, was aus der FFT raus kommt,
einigermassen korrekt ist? Ich habe mal versucht, ein DC-Signal
einzuspeisen; das funktioniert, aber nur wenn ich die Umsortierung der
Samples wie in oben gezeigtem Codeschnipsel mache. Sonst kommt Murks
raus.
Testweise habe ich auch alle Samples auf 0 gesetzt, bis auf das erste,
das den Wert 1000 erhielt. Nach durchführen der FFT über 256 Samples
hatten dann die ersten 128 Ausgangswerte den Wert 78, alle anderen 0.
Ist das jetzt richtig oder nicht?
Alles in allem zwar eine gute FFT-Routine, aber schlecht dokumentiert.
Hier noch der Link zum Sourcecode: http://www.jjj.de/fft/fix_fft.tar.gz
Wie gesagt - lässt sich problemlos compilieren und scheint auch zu
funktionieren; nur weiss ich nicht ob es richtig rechnet.
Gruss Tobias
PS: was mir noch einfällt: lässt sich diese riesen grosse Sinustabelle
zwecks Speicherersparnis noch etwas verkleinern? Wie ungenau wird die
FFT, wenn ich weniger Samples in der Sinustabelle habe?
Und lässt sich das ganze noch etwas optimieren?