Folgende Aufgabe wird gestellt: Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird ausgenullt!!!) FFT mit einer größe von Typ short(16 Bit mit Vorzeichen) soll so effektiv wie möglich auf einem Atmega32 (16 Mhz Taktung) implementiert werden. Ich möchte einfach mal wissen, wo hier der max. Rekord liegt. Ich habe 35 ms für die normale FFT und 52 ms für die IFFT gebraucht. Wenn das einer von Euch überbieten kann, so schreibt bitte einen Beitrag ,wie er es gemacht hat. Mit einem PIC (8 Bit Busbreite mit 36 Mhz taktung) hat jemand in 140 ms die IFFT geschaft. Andere 16 Bit Controller brauchen im schnitt bei 16 Mhz 60 ms für die IFFT. Ich behaupte einfach mal ,das ich mit den Werten 35 und 52 schon Recht gut liege. Ein kollege hat mir einen Ansatz genannt, wie ich meinen Algorithmus nocheinmal um 13 ms verbessern könnte. Ob das klappt ,erfahrt Ihr selbstverständlich auch hier. Ich freue mich über Eure Vorschläge. Auf Anfrage gebe ich Euch auch meinen FFT Algorithmus optimiert für die ATMega8 -128 Reihe.
Was richtig klasse wäre, wenn Du/ihr das im Wiki austragen würde(s)t...
Hallo Thomas ich arbeite zwar mit nem Pic, mich würde aber trotzdem Dein Algorithmus interessieren. Ich arbeite an einem mobilen Messsystem, das online eine FFT machen soll. Soll also möglichst effektiv sein. Ich habe zwar ne C-Bibliiotek für FFT, die läuft aber nur auf nem PIC30, aber nicht auf dem PIC18. Ich würde mich freuen, wenn Du Deinen mir Deinen Code mailen könntest. -> gunzelg@arcor.de Danke im Vorraus Gerhard
hi!! ist IFFT die ruecktransformation??? spiele ein bischen mit nem mega128 rum und wuerde mich ueber den algorithmus sehr freun!!!
hallo thomas du schreist: >Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird >ausgenullt!!!) was macht das in der praxis für einen sinn wenn der imaginärteil gleich null ist? und wäre nicht das berechnen der sinus und cosinus werte ein teil der erheblich zeit brauchen würde? gruss tobias
Das kann doch problemlos sein, wenn du rein reelle Daten hast. Eine zweidimensionale FFT auf einem reellen Bilddatensatz ist z.B. ein Beispiel. Bei der IFFT darfst du den Im-Teil natürlich nicht vernachlässigen, das stimmt.
du schreist: >Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird >ausgenullt!!!) was macht das in der praxis für einen sinn wenn der imaginärteil gleich null ist? Wenn man z.B. einen Audiostream hat und diesen in sein Spektrum zerlegen will ,dann muß man den Imaginärteil sogar ausnullen ,da es in der Zeitlichen Wellenformdarstellung nur Zeit und Ampiltude gibt. und wäre nicht das berechnen der sinus und cosinus werte ein teil der erheblich zeit brauchen würde? Nein, den Sinus und Cosinus kann man bequem mit Konstantentabellen machen g gruss tobias
Du solltest dich mal nach den modularen Integer FFT's erhundigen. Diese FFT's arbeiten mit Primzahlen in modularen Ringen und ermöglichen es somit vollständig auf Fliekommazahlen zu verzichten. Desweiteren sind diese Abarten der FFT's die effizientesten die man auf Binärrechnern umsetzen kann. Durch die Anwendung von Integern und Modulararithmetik habe diese im Gegensatz zu Fließkommaberechnungen ein Fehler von Null, sie sind also exakte FFTs. Es gibt nun verschiedene solche FFTs, zB. Nussbaumer oder die Modulare Fermat FFT von Schönhage und Strassen. Bei all diesen FFTs müssen modulare Divisionen durchgeführt werden, also im Grunde langsamme Disvisionen. Aber beide vorhergenannte FFT's arbeiten mit Modularen Ringen die auf Primzahlen von spezieller Form aufsetzen. Zb. Fermat Zahlen wie 2^(2^m)+1 oder 2^(2^m)-1. Eine Modulare Division mit solchen Zahlen involvieren nur Bit-Shifts und Ausgleichsaddtionen bzw. Subtraktionen. Somit wurde die langsamme Disvision, vergleichbar mit den vielen Multiplikation bei Fließkomma FFTs, durch enorm schnelle Operationen ersetzt. Allgemein kann man sagen das modulare Integer FFTs ca. 5-10 mal schneller sind als die FFTs in komplexen Zahlen basierend auf Fließkomma/Festkomma Operationen. Gruß Hagen
//Hier meine für den Atmel optimierte FFT-Version
// Target : M32
// Crystal: 16.000Mhz
#include <iom32v.h>
#include <macros.h>
#define M 8
#define N (1<<M)
#define N_WAVE 1024 /* dimension of Sinewave[] */
#define LOG2_N_WAVE 10 /* log2(N_WAVE) */
#define N_LOUD 100 /* dimension of Loudampl[] */
#ifndef fixed
#define fixed short
#endif
#if N_WAVE != 1024
ERROR: N_WAVE != 1024
#endif
const fixed Sinewave[1024] = {
0, 201, 402, 603, 804, 1005, 1206, 1406,
1607, 1808, 2009, 2209, 2410, 2610, 2811, 3011,
3211, 3411, 3611, 3811, 4011, 4210, 4409, 4608,
4807, 5006, 5205, 5403, 5601, 5799, 5997, 6195,
6392, 6589, 6786, 6982, 7179, 7375, 7571, 7766,
7961, 8156, 8351, 8545, 8739, 8932, 9126, 9319,
9511, 9703, 9895, 10087, 10278, 10469, 10659, 10849,
11038, 11227, 11416, 11604, 11792, 11980, 12166, 12353,
12539, 12724, 12909, 13094, 13278, 13462, 13645, 13827,
14009, 14191, 14372, 14552, 14732, 14911, 15090, 15268,
15446, 15623, 15799, 15975, 16150, 16325, 16499, 16672,
16845, 17017, 17189, 17360, 17530, 17699, 17868, 18036,
18204, 18371, 18537, 18702, 18867, 19031, 19194, 19357,
19519, 19680, 19840, 20000, 20159, 20317, 20474, 20631,
20787, 20942, 21096, 21249, 21402, 21554, 21705, 21855,
22004, 22153, 22301, 22448, 22594, 22739, 22883, 23027,
23169, 23311, 23452, 23592, 23731, 23869, 24006, 24143,
24278, 24413, 24546, 24679, 24811, 24942, 25072, 25201,
25329, 25456, 25582, 25707, 25831, 25954, 26077, 26198,
26318, 26437, 26556, 26673, 26789, 26905, 27019, 27132,
27244, 27355, 27466, 27575, 27683, 27790, 27896, 28001,
28105, 28208, 28309, 28410, 28510, 28608, 28706, 28802,
28897, 28992, 29085, 29177, 29268, 29358, 29446, 29534,
29621, 29706, 29790, 29873, 29955, 30036, 30116, 30195,
30272, 30349, 30424, 30498, 30571, 30643, 30713, 30783,
30851, 30918, 30984, 31049,
31113, 31175, 31236, 31297,
31356, 31413, 31470, 31525, 31580, 31633, 31684, 31735,
31785, 31833, 31880, 31926, 31970, 32014, 32056, 32097,
32137, 32176, 32213, 32249, 32284, 32318, 32350, 32382,
32412, 32441, 32468, 32495, 32520, 32544, 32567, 32588,
32609, 32628, 32646, 32662, 32678, 32692, 32705, 32717,
32727, 32736, 32744, 32751, 32757, 32761, 32764, 32766,
32767, 32766, 32764, 32761, 32757, 32751, 32744, 32736,
32727, 32717, 32705, 32692, 32678, 32662, 32646, 32628,
32609, 32588, 32567, 32544, 32520, 32495, 32468, 32441,
32412, 32382, 32350, 32318, 32284, 32249, 32213, 32176,
32137, 32097, 32056, 32014, 31970, 31926, 31880, 31833,
31785, 31735, 31684, 31633, 31580, 31525, 31470, 31413,
31356, 31297, 31236, 31175, 31113, 31049, 30984, 30918,
30851, 30783, 30713, 30643, 30571, 30498, 30424, 30349,
30272, 30195, 30116, 30036, 29955, 29873, 29790, 29706,
29621, 29534, 29446, 29358, 29268, 29177, 29085, 28992,
28897, 28802, 28706, 28608, 28510, 28410, 28309, 28208,
28105, 28001, 27896, 27790, 27683, 27575, 27466, 27355,
27244, 27132, 27019, 26905, 26789, 26673, 26556, 26437,
26318, 26198, 26077, 25954, 25831, 25707, 25582, 25456,
25329, 25201, 25072, 24942, 24811, 24679, 24546, 24413,
24278, 24143, 24006, 23869, 23731, 23592, 23452, 23311,
23169, 23027, 22883, 22739, 22594, 22448, 22301, 22153,
22004, 21855, 21705, 21554, 21402, 21249, 21096, 20942,
20787, 20631, 20474, 20317, 20159, 20000, 19840, 19680,
19519, 19357, 19194, 19031, 18867, 18702, 18537, 18371,
18204, 18036, 17868, 17699, 17530, 17360, 17189, 17017,
16845, 16672, 16499, 16325, 16150, 15975, 15799, 15623,
15446, 15268, 15090, 14911, 14732, 14552, 14372, 14191,
14009, 13827, 13645, 13462, 13278, 13094, 12909, 12724,
12539, 12353, 12166, 11980, 11792, 11604, 11416, 11227,
11038, 10849, 10659, 10469, 10278, 10087, 9895, 9703,
9511, 9319, 9126, 8932, 8739, 8545, 8351, 8156,
7961, 7766, 7571, 7375, 7179, 6982, 6786, 6589,
6392, 6195, 5997, 5799, 5601, 5403, 5205, 5006,
4807, 4608, 4409, 4210, 4011, 3811, 3611, 3411,
3211, 3011, 2811, 2610, 2410, 2209, 2009, 1808,
1607, 1406, 1206, 1005, 804, 603, 402, 201,
0, -201, -402, -603, -804, -1005, -1206, -1406,
-1607, -1808, -2009, -2209, -2410, -2610, -2811, -3011,
-3211, -3411, -3611, -3811, -4011, -4210, -4409, -4608,
-4807, -5006, -5205, -5403, -5601, -5799, -5997, -6195,
-6392, -6589, -6786, -6982, -7179, -7375, -7571, -7766,
-7961, -8156, -8351, -8545, -8739, -8932, -9126, -9319,
-9511, -9703, -9895, -10087, -10278, -10469, -10659, -10849,
-11038, -11227, -11416, -11604, -11792, -11980, -12166, -12353,
-12539, -12724, -12909, -13094, -13278, -13462, -13645, -13827,
-14009, -14191, -14372, -14552, -14732, -14911, -15090, -15268,
-15446, -15623, -15799, -15975, -16150, -16325, -16499, -16672,
-16845, -17017, -17189, -17360, -17530, -17699, -17868, -18036,
-18204, -18371, -18537, -18702, -18867, -19031, -19194, -19357,
-19519, -19680, -19840, -20000, -20159, -20317, -20474, -20631,
-20787, -20942, -21096, -21249, -21402, -21554, -21705, -21855,
-22004, -22153, -22301, -22448, -22594, -22739, -22883, -23027,
-23169, -23311, -23452, -23592, -23731, -23869, -24006, -24143,
-24278, -24413, -24546, -24679, -24811, -24942, -25072, -25201,
-25329, -25456, -25582, -25707, -25831, -25954, -26077, -26198,
-26318, -26437, -26556, -26673, -26789, -26905, -27019, -27132,
-27244, -27355, -27466, -27575, -27683, -27790, -27896, -28001,
-28105, -28208, -28309, -28410, -28510, -28608, -28706, -28802,
-28897, -28992, -29085, -29177, -29268, -29358, -29446, -29534,
-29621, -29706, -29790, -29873, -29955, -30036, -30116, -30195,
-30272, -30349, -30424, -30498, -30571, -30643, -30713, -30783,
-30851, -30918, -30984, -31049, -31113, -31175, -31236, -31297,
-31356, -31413, -31470, -31525, -31580, -31633, -31684, -31735,
-31785, -31833, -31880, -31926, -31970, -32014, -32056, -32097,
-32137, -32176, -32213, -32249, -32284, -32318, -32350, -32382,
-32412, -32441, -32468, -32495, -32520, -32544, -32567, -32588,
-32609, -32628, -32646, -32662, -32678, -32692, -32705, -32717,
-32727, -32736, -32744, -32751, -32757, -32761, -32764, -32766,
-32767, -32766, -32764, -32761, -32757, -32751, -32744, -32736,
-32727, -32717, -32705, -32692, -32678, -32662, -32646, -32628,
-32609, -32588, -32567, -32544, -32520, -32495, -32468, -32441,
-32412, -32382, -32350, -32318, -32284, -32249, -32213, -32176,
-32137, -32097, -32056, -32014, -31970, -31926, -31880, -31833,
-31785, -31735, -31684, -31633, -31580, -31525, -31470, -31413,
-31356, -31297, -31236, -31175, -31113, -31049, -30984, -30918,
-30851, -30783, -30713, -30643, -30571, -30498, -30424, -30349,
-30272, -30195, -30116, -30036, -29955, -29873, -29790, -29706,
-29621, -29534, -29446, -29358, -29268, -29177, -29085, -28992,
-28897, -28802, -28706, -28608, -28510, -28410, -28309, -28208,
-28105, -28001, -27896, -27790, -27683, -27575, -27466, -27355,
-27244, -27132, -27019, -26905, -26789, -26673, -26556, -26437,
-26318, -26198, -26077, -25954, -25831, -25707, -25582, -25456,
-25329, -25201, -25072, -24942, -24811, -24679, -24546, -24413,
-24278, -24143, -24006, -23869, -23731, -23592, -23452, -23311,
-23169, -23027, -22883, -22739, -22594, -22448, -22301, -22153,
-22004, -21855, -21705, -21554, -21402, -21249, -21096, -20942,
-20787, -20631, -20474, -20317, -20159, -20000, -19840, -19680,
-19519, -19357, -19194, -19031, -18867, -18702, -18537, -18371,
-18204, -18036, -17868, -17699, -17530, -17360, -17189, -17017,
-16845, -16672, -16499, -16325, -16150, -15975, -15799, -15623,
-15446, -15268, -15090, -14911, -14732, -14552, -14372, -14191,
-14009, -13827, -13645, -13462, -13278, -13094, -12909, -12724,
-12539, -12353, -12166, -11980, -11792, -11604, -11416, -11227,
-11038, -10849, -10659, -10469, -10278, -10087, -9895, -9703,
-9511, -9319, -9126, -8932, -8739, -8545, -8351, -8156,
-7961, -7766, -7571, -7375, -7179, -6982, -6786, -6589,
-6392, -6195, -5997, -5799, -5601, -5403, -5205, -5006,
-4807, -4608, -4409, -4210, -4011, -3811, -3611, -3411,
-3211, -3011, -2811, -2610, -2410, -2209, -2009, -1808,
-1607, -1406, -1206, -1005, -804, -603, -402, -201,
};
/* placed at end of this file for clarity */
/*
fix_fft() - perform fast Fourier transform.
if n>0 FFT is done, if n<0 inverse FFT is done
fr[n],fi[n] are real,imaginary arrays, INPUT AND RESULT.
size of data = 2**m
set inverse to 0=dft, 1=idft
*/
fixed fix_fft(fixed fr[], fixed fi[], fixed m, char inverse)
{
short aus;
short v;
unsigned char *test;
unsigned char mr,nn,k,scale ;
fixed i,j,l,istep, n;
fixed t;
fixed subi,subr,tr,ti;
fixed wr,wi,qr,qi,shift;
n = 1<<m;
if(n > N_WAVE)
return -1;
mr = 0;
nn = n - 1;
scale = 0;
/* decimation in time - re-order data */
for(m=1; m<=nn; ++m) {
l = n;
do {
l >>= 1;
} while(mr+l > nn);
mr = (mr & (l-1)) + l;
if(mr <= m) continue;
tr = fr[m];
fr[m] = fr[mr];
fr[mr] = tr;
ti = fi[m];
fi[m] = fi[mr];
fi[mr] = ti;
}
l = 1;
k = LOG2_N_WAVE-1;
while(l < n) {
if(inverse) {
/* variable scaling, depending upon data */
shift = 0;
for(i=0; i<n; ++i) {
j = fr[i];
if(j < 0)
j = -j;
m = fi[i];
if(m < 0)
m = -m;
// if(j > 16383 || m > 16383) {
if(j > 16383 || m > 16383) {
shift = 1;
break;
}
}
if(shift)
++scale;
} else {
/* fixed scaling, for proper normalization -
there will be log2(n) passes, so this
results in an overall factor of 1/n,
distributed to maximize arithmetic accuracy.
*/
shift = 1;
}
/* it may not be obvious, but the shift will be
performed
on each data point exactly once, during this pass.
*/
istep = l << 1;
for(m=0; m<l; ++m) {
j = m << k;
/* 0 <= j < N_WAVE/2 */
wr = Sinewave[j+N_WAVE/4];
wi = -Sinewave[j] ;
if(inverse)
wi = -wi;
if(shift) {
wr >>= 1;
wi >>= 1;
}
for(i=m; i<n; i+=istep) {
j = i + l;
/* tr = fix_mpy(wr,fr[j]) -
fix_mpy(wi,fi[j]);
ti = fix_mpy(wr,fi[j]) +
fix_mpy(wi,fr[j]);
*/
subi=fi[j]; subr= fr[j];
//////// Beschleuniger Start
v = wr*subr;
test = (unsigned char *)&v +1;
if (*test >= 128)
{
*test = 255;
test--;
*test= 255;
}
else
{
*test=0;
test--;
*test=0;
}
tr = v;
v= wi*subi;
test = (unsigned char *)&v +1;
if (*test >= 128)
{
*test = 255;
test--;
*test= 255;
}
else
{
*test=0;
test--;
*test=0;
}
tr = tr - v;
/////////////Zeile 1 Ende beginn Zeile 2 ////////////////
v = (wr*subi);
test = (unsigned char *)&v +1;
if (*test >= 128)
{
*test = 255;
test--;
*test= 255;
}
else
{
*test=0;
test--;
*test=0;
}
tr = v;
v= wi*subr;
test = (unsigned char *)&v +1;
if (*test >= 128)
{
*test = 255;
test--;
*test= 255;
}
else
{
*test=0;
test--;
*test=0;
}
tr = tr + v;
////////// Beschleuniger Ende
// tr = ((wr*subr)>>15) - ((wi*subi)>>15);
// ti = ((wr*subi)>>15) + ((wi*subr)>>15);
//Mf(tr); Mf(ti);
qr = fr[i];
qi = fi[i];
if(shift) {
qr >>= 1;
qi >>= 1;
}
fr[j] = qr - tr;
fi[j] = qi - ti;
fr[i] = qr + tr;
fi[i] = qi + ti;
}
}
--k;
l = istep;
}
return scale;
}
Die wesendliche Änderung besteht in dem Programmteil "Beschleuniger". In der Ursprungsversion wurde der >>15 Befehl verwendet ,quasi ein Rechtsshift um 15 Stellen. Da es auf einer Atmel MCU keinen effektiven Assemblerbefehl dazu gibt, macht der C-Compiler nichts anderes ,als alle 15 shifts mit einer Schleife durchzulaufen und diese beinhaltet auch noch 17 Assenblerzeilen Code!! Ich habe einfach diesen Shift 15 durch eine einfache Fallunterscheidung ersetzt. Das braucht jetzt nur noch ca. 20 Assemblerzeilen ist aber mit einem Durchlauf beendet. Ich beschäftige mich gerade mit den Registeroptionen des Compilers und versuche nun das Effektiv mit Assembleroptionen in den Code einzubinden. //////// Beschleuniger Start
ok!! wer seine email noch nicht mal richtig schreiben kann sollte vieleicht was anderes machen huestel ;-}
Ich habe ehrlich gesagt nich soviel Ahnung von FFT usw. suche allerdings schon seit längerem nach einem schnellen FFT Code um einen Low Cost Spektum Analyser mit einem kleinen Grafik LCD zu bauen. Daher kam dieser optimierte Code gerade recht. Für den ersten Test verwende ich einen berechneten Sinus und lade 1024 Werte in das fr Array. fi lade ich mit Nullen. Der Sinus hat einen Wertebereich von +/-1000. Nachdem fix_fft gelaufen ist, enthalten alle Werte im Array (0..255) irgendwas im Bereich -2 bis 1, aber eigentlich müsste irgendwo eine deutliche Spitze sein... Einstellungen: m=8; inverse=0; Habe ich was falsch gemacht, oder muss ich noch irgendwas beachten ?
Jenachdem wie die Phase liegt, können die Zielwerte sowol im Real als auch im Imagteil liegen. Du mußt, um die Lautstärke zu ermitteln (abs(r[i]) +abs[i[i])) /2 rechnen. Außerdem kann eine solche FFT nur exakt einen Sinuston finden, wenn er ein vielfaches von der Niedrigsten Frequenz ist . Ansonsten fallen Werte zwichen 2 Frequenzen und man kann diese eine Frequenz nicht mehr exakt bestimmen. Abhilfe dafür schafft z.b. Zero-Padding. Aber bei einem einzigem Ton müßtest du trotzdem über 1-2 Frequnzen eine deutliche Spitze herausbekommen. Der Fehler leigt vermutlich woanders. Du mußt natürlich als ArrayLänge 8 und nicht 256 angeben. Villeicht hat du in deiner Sinusfunktion einen fehler. Um das zu testen nimm einfach mal Sinwave[0..n]. Oder wenn f Sinuston < f Grundfrequenz ist, dann krigt man natürlich auch kein ergebnis.
oh mein Fehler ...............
{
*test=0;
test--;
*test=0;
}
tr = tr + v; muß natürlich ti= tr + v heissen
////////// Beschleuniger Ende
// tr = ((wr*subr)>>15) - ((wi*subi)>>15);
// ti = ((wr*subi)>>15) + ((wi*subr)>>15);
//Mf(tr); Mf(ti);
Für den Blödian, der aber gern mitliest und es interessant findet(also mich): was macht man mit einer FFT denn genau? oder generell? ;)
Angehängte Dateien:
-
fft.gif
4,1 KB
Hab jetzt den Fehler behoben (und darüber auch noch den ti=tr-v) Die Sinuskurve ist auf jedenfall richtig im Array: fr[i]=1000*sin(i/2); Das kann ich auch im Debugger nachprüfen. Die Werte am Ende der FFT (mit zusammengefassten i und r Werten) liegen dann bei 0-6... Ich habe mal die Werte am Ende der FFT in den Anhang gepackt.
@Steril Damit wird ein Signal in die darin enthaltenen einzelnen Frequenzen und die entsprechende Stärke zerlegt. Speichert man nur die stärksten Frequenzen, hat man einen mp3 Encoder. Allerdings kann man mit FFT noch viel mehr machen wie z.B. Primzahlen berechnen oder sehr, sehr große Zahlen multiplizieren (frag mich aber bitte nicht wie...) Eiegntlich ist FFT (Fast Fourier Transformation) nur eine Spezialform von DFT (Discrete Fourier Transformation)
sieht bei mir ähnlich aus fi und fr jeweils länge 256 fi setze ich vorher komplett auf 0 fr enthält audio-samples (hab sowohl musik als auch reinen sinus probiert) m=8 und inverse=0 die ergebnisse liegen bei 0 bis 3 ich setze vor beginn der fft einen io-pin auf high und hintehrer wieder auf low. laut oszilloskop dauert also die komplette fft mit 256 punkten knappe 20ms, kommt mir etwas wenig vor (taktrate 18,432MHz)
Gute Idee mit dem Pin.... Muss ich bei mir auch mal machen. Ich habe das Programm allerdings nicht auf einem AVR sondern auf einem 16bit Controller M16C mit 24MHz laufen.
hallo thomas ich habe gerade ein bischen gegoogelt und folgende seite gefunden. http://www.jjj.de/fft/fftpage.html dort hat es ein txt file zum downloaden int fft.c, siehe anhang. ich weiss jetzt halt auch nicht ob das deine homepage ist. wenn ja hut ab, und gratulation zu der programmierung deiner fft. der code scheint mit deinem ziemlich identisch zu sein. nur wegen dem optimierungswettberb gruss tobias
jup die seite hab ich auch gefunden und mit der int_fft.c nen bissel rumgespielt es passiert mehr wie bei obigem code aber so ganz richtig ist das auch noch nich
Ich habe eine FFT Routine für QBASIC, aus einem simplen mp3 En/dekoder Programm. Diese geht einwandfrei, nur in C gehts nichtmehr. In QBASIC habe ich schon oft damit ein Oszilloskop mit Frequenzmessung programmiert. Ebenso ein Empfänger für den Bereich 100-1MHz. Da konnte ich mit einer einfachen Antenne, NE592 Videoopamp und einem TDA8703 über 100 MW Sender erkennen...
ich hab eine funktionierende FFT Funktion in C die auf dem AVR läuft nur benutzt die leider fließkommaoperationen und ist entsprechend langsam und invertieren kann sie auch nicht das brauch ich aber auch nicht
tobias hofer wrote..... dort hat es ein txt file zum downloaden int fft.c, siehe anhang. ich weiss jetzt halt auch nicht ob das deine homepage ist. wenn ja hut ab, und gratulation zu der programmierung deiner fft. der code scheint mit deinem ziemlich identisch zu sein. die int_fft.c Ursprungsversion stammt nicht von mir , sondern ich habe sie nur etwas abgeändert ,damit sie speziell auf Atmel Controllern schneller läuft.
so also hab jetzt den originalen sourcecode ohne die optimierungen genommen und siehe da es funktioniert - wenn auch nich ganz so schnell 50ms bei 18,432MHz mit 256 Punkten. außerdem hab ich die Sinus-Tabelle ins Flash getan das ist exakt genauso schnell und sparrt 2kb RAM... außerdem sollten die werte des eingangssignals den wertebereich des datentyps halbwegs gut ausnutzen also +/- dürfte wohl etwas wenig sein
Bei mir gehts immer noch nicht... Ich kann zwar eine Spitze erkennen, die sich auch verschiebt wenn ich die Frequenz ändere, aber da sind noch mehr SPitzen, dort wo keine hingehören....
Hallo, jetzt grab ich den alten Thread wieder aus ;) Ich verwende auch gerade diese FFT. Ich verstehe nicht was die m=8 bei dem Funktionsaufruf der FFT bewirkt. Kann mir einer weiterhelfen? Grüße Andreas
noch ne Frage :) was für Werte erhält man denn wenn man ein Feld mit 256 Stellen nimmt und diese von 0 - 255 füllt. sprich feld[20]=20,feld[21]=21 usw. Oder besser gefragt, wie könnte man die FFT gut testen? Mit konstanten Zahlen? Was erhalte ich hinter her? Oh je so viel Fragen ;) Grüße Andreas
Weißt du überhaupt, was eine FFT ist? http://www.dspguide.com/ Ich halte es für verkehrt, zu versuchen mit einer Sache rumzuexperimentieren, wenn ich nicht einmal ihre Grundlagen verstanden habe.
Hallo Alex, ich möchte ein Sprachsignal in den Frequenzbereich transformieren um Untersuchungen in bestimmten Frequenzen vorzunehmen und möchte dafür die FFT verwenden. Als Input in diesem Fall wäre, da der A/D Wandler mir ja nur int Werte liefert, wäre der Realteil (fr[] länge 256) die Daten vom A/D Wandler und der Imaginärteil 0 (fi[] länge 256) und die FFT vorwärts mit 0. Aber das m leuchtet mir nicht ein.... Naja ich les mal weiter... Gruß Andreas
Hmm ok, die Länge der Felder.... weil ja auch nun mal 1<<8 = 255 ist. Leuchtet ein :) Gruß Andreas
@Benedikt ....Speichert man nur die stärksten Frequenzen, hat man einen mp3 Encoder. .... AUTSCH :-)
Um die "Spitzen", die "nicht reinpassen" herauszubekommen, kann man
(wenn dir fft richtig funktioniert) noch ein sogenanntes "Windowing"
durchführen. Dabei wird einfach gesagt das Signal ein und ausgeblendet.
Damit werden die Signalsprünge am Anfang und Ende der Datenreihe
geglättet und somit diese hochfrequengen Anteile unterdrückt, die sonst
Aliasing Effekte erzeugen ("Spitzen, die nicht reinpassen").
Wen es interessiert googelt mal nach windowing fft, hanning window,
hamming window oder blackman window. Die Verschieden Arten wirken sich
auf Amplitudentreue oder Phasentreue aus.
Wäre auch interessant hier mal ne schnelle Lösung für nen MC zu haben
;)
@Andreas Siebel jo das sieht man schön wenn man z.B einen Sinus abtastet und der nicht 100% innerhalb der Window Zeit (tw) liegt. Dann bekommt man noch ne schöne si(x)-Funktion auf die Maximalwerte der eigentlichen Frequenz des Sinussignals gelegt. Da wären wir schon wieder beim Thema Faltung....
> Autor: Benedikt > Datum: 04.08.2004 07:42 > Bei mir gehts immer noch nicht... > Ich kann zwar eine Spitze erkennen, die sich auch verschiebt wenn ich > die Frequenz ändere, aber da sind noch mehr SPitzen, dort wo keine > hingehören.... Wenn Du ne Sinuswelle reinjagst, die aufm ersten und letzten Sample einen Nulldurchgang hat und es werden keine "fremden" Frequenzen angezeigt, dann liegt's wahrscheinlich am Window.
"Es gibt nun verschiedene solche FFTs, zB. Nussbaumer oder die Modulare Fermat FFT von Schönhage und Strassen. Allgemein kann man sagen das modulare Integer FFTs ca. 5-10 mal schneller sind als die FFTs in komplexen Zahlen basierend auf Fließkomma/Festkomma Operationen." Kann mir jemand mit einer Quelle helfen, wo diese Algorithmen beschrieben sind? vielen dank.
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.