128point FFT in ASM

[niels laugwitz (Gast)]

Fast Fourier Transformation
IN ASSEMBLER!
627 words code
352 word constants (incl. 128 words Beispiel Daten)
Timing: 86.1ms per MHz Taktfrequenz

getestet mit AVR-Studio4 und Zielhardware ATMega8. Andere MEGA-AVRs
sollten auch gehen. Wer eine Multiplikations-Rountine einbindet, kann
sicher auch auf kleineren AVRs damit arbeiten.

Programmstruktur und Variablennamen wurden dem FFT-Algorithmus in
"Numerical recipes in C" entlehnt.
Dort sind Theorie und die ganze Mathematik im Detail erklärt (dort
Programm: realft). Das Programm funktioniert mit FFT-Längen nn2=128 und
weniger (Länge ist immer Power of 2 !).
Input: nn2 reele Datenpunkte mit Wertebereich -16384 bis +16384.
Output: überschreibt input Daten und hat denselben Wertebereich (-2^14
... +2^14).
Das Output-array ist wie folgt aufgebaut:
f 0,f N/2),           *
Re(f 1),Im(f 1),
Re(f 2),Im(f 2),
Re(f 3),Im(f 3),
.
.
.
Re(f N/2-1),Im(f N/2-1)

*Anm.: Die ersten zwei Datenpunkte im Array sind bereits reelwertig!
Die DC-komponente hat natürlich keine Phaseninformation, und auch für
die Nyquist-frequenz gibt es grundsätzlich keine Phaseninformation.

Um den Code nicht unnötig aufzublähen wurde auf korrektes Runden
verzichtet. Daher ist die Genauigkeit der Ergebnisse etwa: +/-8. Bei
Ausnutzung des Wertebereichs ist damit immerhin eine bessere Auflösung
als die des ADC gegeben.

Längere FFTs würden 16bit Zählvariablen und ähnliche Unannehmlichkeiten
bedeuten. Vorerst reichen mir die 64 Frequenzen, die ich mit dieser
Version berehcnen kann.

Have fun!