Implementierung von FFT auf uC

Hi,

Im Rahmen der diversen Projekte mit dem R8C gabs im Elektor eine FFT. Ich meine, es war das Projekt "R8c als Oszilloskop" (03/06). Außerdem gabs im R8C-Ideenwettbewerb eine Sprachsteuerung mit FFT.

Vielleicht sind da ja nützliche Anregungen drin.

Gruß Michael Kutscher

• sind die Eingangsdaten real oder komplex ?
• soll die Berechnung in Festkomma oder Float erfolgen ?
• HW-Multiplizierer vorhanden ( M16 hat vermutlich einen ) ? In den 80ern wurde auf 68000ern z.B. Winograd-FFT verwendet die kompliziert ist aber die Zahl der Multiplikationen minimiert.
• Rücktransformation nötig ? Die Fast Hartley Transform ( keine FFT ) ist zwar nicht schneller als Fourier aber vom Programmspeicher angeblich kompakter wenn man Rücktransformation auch haben will.

Man hat typisch ohnehin nur die Wahl 256 512 1024 usw. Wenn man hohe Auflösung an bestimmten Frequenzen haben will:

• DFT weil die mit krummmer Zahl von Punkten kann und einzelne Linien berechnet. Problem hier: man müsste auch sin/cos-Tabellen für die krumme Punktzahl haben * Chirp-Z-Transform als effiziente DFT-Variante
• "Zoom"-FFT: Spielerei mit Interpolation und Mischer. Wurde aber glaube ich bei den Bruel & Kjaer FFT-Analysatoren gerne verwendet.

Abhängig von der Anwendung sind natürlich oft auch andere Verfahren als FFT von LPC bis Walsh denkbar.

MfG JRD

Rafael Deliano schrieb:

Reelle Eingangsdaten sind es. Ich habe aber durchaus schon Verfahren gefunden, mit denen man trotzdem eine komplexe FFT ausnutzen kann, indem man z.B. zwei FFTs in einem Durchlauf berechnet.

Ja, der M16C hat einen 16-Bit x 16-Bit Hardwaremultiplizierer.

Und da ich ich die vorhandenen Hardwarerecheneinheiten gerne effizient nutzen würde, scheidet Fließkomma eigentlich aus. Das müsste nämlich in Software emuliert werden.

Eine Rücktransformation wird zu einem späteren Zeitpunkt auch nötig sein.

CU Christian

Wenn du dir die 2 Operationen pro Punkt im Nachhinein leisten kannst ;-) Was an der Methode aber bei Festkommaarithmetik den Nachteil hat, das die Eingabe der "einen" FFT durch Rundungsfehler in beide Ausgaben kommt. Das ist ein Effekt, denn man manchmal nicht ignorieren kann, zB. bei stark unterschiedlichen Grössenordnungen der beiden Eingangsdaten.

Je nach FFT-Grösse kommt es bei Festkomma auf passende Skalierungsschritte zwischen den einzelnen FFT-Phasen an. Deren Position im Ablauf hat einen grossen Einfluss auf die Genauigkeit des Resultats. Da muss man dann etwas rumspielen...

Die 16 Bit 512 Punkte Festkomma-Implementierungen aus den 80ern verwendeten bestenfalls 12 Bit A/D-Wandler. Sonst wirds mit der Skalierung wohl eng.

Dafür ist dann wohl komplexe FFT nötig.

MfG JRD

Christian Zietz schrieb:

Mit einer FFT-ähnlichen Operation kann man die reellen Eingangsdaten in zwei halb so grosse Portionen aufteilen, die man dann in die komplexe FFT stopft. Für "normale" Gleitkommaarithmetik finde ich die Einleitung im Numerical Recipes ganz gut. Ältere Ausgaben in diversen Programmiersprachen gibt es umsonst im Netz, man braucht allerdings ein decodierungs-Plugin für den AcrobatReader, welches auch umsonst ist (bisschen merkwürdig das Ganze).