Hallo Leute,
ich bin gerade dabei, eine FFT-Routine auf PIC-Hardware zu entwickeln. Als Vorlage für den Algorythmus habe ich ein Stück Pseudocode auf Wikipedia gewählt. Der grundsätzliche Programmablauf ist mir klar, nur bei der Berechnung von x_links,neu und x_rechts,neu wirds kritisch. Bei Sprut wird die Verhackstückung der einzelnen Samples für "Dummies" erklärt, da werden Vektoren (also die Samples aus Real- und Imaginärteil des Eingangssignals) gedreht und addiert. Das addieren ist ja offensichtlich, nur der Term

verschliesst sich mir aufgrund nur rudimentär vorhandenen Wissens über das Rechnen mit imaginären Zahlen. Er muss wohl für die Drehung zuständig sein, wobei der Bruch quasi den Winkel angibt. Kann man diesen Term als

auffassen oder stell ich mir das zu einfach vor?

Zur Erzeugung der komplexen Samples hat Sprut auch was, er samplet das Eingangssignal mit der 4fachen Samplingrate und wirft dann die Hälfte davon weg, die andere Hälfte wird als Real- und Imaginarteil behandelt. Er beschreibt diese Methode als unsauber, warscheinlich weil Real- und Imaginärteil nicht zur gleichen Zeit gemessen werden. Ist dieser Fehler vernachlässigbar oder kommt man ohne große Einbußen in der Qualität nicht um Mischer etc. herum?

_________________
Fnord ist die Quelle aller Nullbits in deinem Computer.
Fnord ist die Angst, die Erleichterung, und ist die Angst.
Fnord schläft nie.

Zitat :

bin gerade dabei, eine FFT-Routine auf PIC-Hardware zu entwickeln.

Du bist sicher, dass du wirklich FFT machen willst und nicht etwa DCT oder Goertzel?
Hast du denn einen, der die Bit-reverse-Adressierung beherrscht und genügend RAM mitbringt?
Dann brauchst du vermutlich das Rad nicht neu zu erfinden, sondern nur in die Applikationsberichte schauen.

Zitat :

Du bist sicher, dass du wirklich FFT machen willst und nicht etwa DCT oder Goertzel?

Komplexe Mathematik werd ich wohl überall machen müssen, also sollte es keinen großen Unterschied machen, zudem ist die FFT imho das "bekannteste" Verfahren zur Umrechnung eines Signals vom Zeit- in den Frequenzbereich.

Ich wollte das mit einem PIC18 machen, die haben genug RAM und einen 8bit Hardwaremultiplizierer. Die Adressierung mach ich entweder per Tabelle oder mit einer wilden shift-Orgie So wahnsinnig hochauflösend will ich auch garnicht werden, 256 Frequenzen reichen völlig aus, die Samples wollte ich mit 8bit auflösen.

Ich hab hier einen Beispielcode für eine FFT, sie läuft auf einem PIC17, einer den PIC18 nicht unähnliche Familie. Wenn ich mich da ausreichend reingedacht habe, werde ich ihn etwas umschreiben und portieren.

_________________
Fnord ist die Quelle aller Nullbits in deinem Computer.
Fnord ist die Angst, die Erleichterung, und ist die Angst.
Fnord schläft nie.