Moin.

Eine FFT mit bit-reverse Shifting u. Butterfly-Algorithmus usw. ist aber zunächst mal viel aufwendiger zu implementieren. Die Grundformel zur DFT hatte ich ja schon im alten Thread genannt. Erläuterung in vielen Büchern (und Websites?) zur Digitalen Signalverarbeitung. Aber wenn es doch FFT sein soll: von der libfftw abgucken oder sie gleich ganz verwenden.

D.

Moin.

Ich habe mal ein Beispielprogramm zur DFT gemacht und mit FFT verglichen. Dies ist das Programm:

Code :

#include <complex.h> #include <math.h> #include <stdio.h> #include <sys/time.h> #define NN 256 #define FNAME "dft_test.out" void create_time_function (complex in[], int N) { int k; for (k = 0; k < N; k++) { if ((0 <= k) && (k < N/8)) creal(in[k]) = 0.0; if ((N/8 <= k) && (k < N/4)) creal(in[k]) = 8.0/N * k - 1.0; if ((N/4 <= k) && (k < 3*N/8)) creal(in[k]) = -8.0/N * k + 3.0; if ((3*N/8 <= k) && (k < N/2)) creal(in[k]) = 0.0; if ((N/2 <= k) && (k < 5*N/8)) creal(in[k]) = 0.0; if ((5*N/8 <= k) && (k < 3*N/4)) creal(in[k]) = 8.0/N * k - 5.0; if ((3*N/4 <= k) && (k < 7*N/8)) creal(in[k]) = -8.0/N * k + 7.0; if ((7*N/8 <= k) && (k < N)) creal(in[k]) = 0.0; cimag(in[k]) = 0.0; } } void dft (complex tim[], complex frq[], int N) { int n, j; complex sum; for (n = 0; n < N; n++) { creal(sum) = cimag(sum) = 0.0; for (j = 0; j < N; j++) { sum += tim[j] * cexp(-I*2.0*M_PI*n*j/N); } frq[n] = /* 1.0 / (double) N * */ sum; } } int main (void) { complex in[NN], out[NN]; double power_spectrum[NN/2+1]; int k; FILE *fp; struct timeval start, end, run; create_time_function (in, NN); gettimeofday (&start, NULL); dft (in, out, NN); gettimeofday (&end, NULL); timersub (&end, &start, &run); printf ("Running %ld usecs\n", 1000000L*run.tv_sec + run.tv_usec); power_spectrum[0] = creal(out[0])*creal(out[0]); for (k = 1; k < (NN+1)/2; ++k) power_spectrum[k] = creal(out[k])*creal(out[k]) + cimag(out[k])*cimag(out[k]); if (NN % 2 == 0) power_spectrum[NN/2] = creal(out[NN/2])*creal(out[NN/2]); fp = fopen (FNAME, "w"); for (k = 0; k < NN; k++) { double f1; if (k <= NN/2) f1 = power_spectrum[k]; else f1 = 0.0; fprintf (fp, "%03d %f %f\n", k, creal(in[k]), f1); } fclose (fp); return 0; }

Die erzeugte Datei mit den Zahlenwerten ist zur Darstellung mittels gnuplot o.ä. gedacht. Die FFT-Variante ist bis auf den Aufruf der Funktion dft() weitestgehend gleich; sie benutzt Funktionen aus der librfftw (http://www.fftw.org).

Ergebnis:
1. Die berechneten Zahlenwerte sind identisch! Jedenfalls bei der Anzeigegenauigkeit, die der gcc beim Format-Argument "%f" standardmäßig auswählt, nämlich "%.6f".
2. Ich muss anerkennen, der Geschwindigkeitsvorteil von FFT ist atemberaubend. Die DFT-Routine verbraucht ca. 55 Millisekunden; die Zeiten schwanken etwas von Aufruf zu Aufruf. Die FFT-Berechnung, die wie gesagt auf dasselbe Zahlenresultat führt, benötigt ca. 490 Mikro(!)sekunden.

D.

hmmm leider kann ich mit den tipps nicht viel anfangen! Leider!

hab mir jedoch mal gedacht ich versuchs selbst zu programmieren. Anbei habe ich mal den source code beigefügt! wäre unter umständen fein wenn mir jemand bei der fehlersuche helfen könnte!

#include <18F4550.h>
#fuses HS,NOWDT,NOPROTECT,NOLVP,NOBROWNOUT
//#fuses HSPLL,CPUDIV2,NOWDT,NOPROTECT,NOLVP,NOBROWNOUT
#device ADC=10
#use delay(clock= 20000000)
#use RS232(baud=9600, xmit=pin_c6, rcv=pin_c7)
#include <math.h>


float sinWert[451];

float pee=3.14159;
int kf_re[32];
int kf_im[32];
int kf_abs[32];
int k,p;

int in[64];
int out;
long n=1000;
long a,x,w;
int f=1;


void main(){

//----- Setup PWM -----
setup_ccp1(CCP_PWM);
setup_timer_2(t2_div_by_1,255,1);

//----- Setup ADC -----
setup_adc_ports(AN0_TO_AN2);
SETUP_ADC(ADC_CLOCK_INTERNAL);



sinWert[0]=0.0000;
sinWert[1]= 0.01745;
sinWert[2]= 0.03490;
sinWert[3]= 0.05234;
sinWert[4]= 0.06976;
sinWert[5]= 0.08716;
sinWert[6]= 0.10453;
sinWert[7]= 0.12187;
sinWert[8]= 0.13917;
sinWert[9]= 0.15643;
sinWert[10]= 0.17365;
sinWert[11]= 0.19081;
sinWert[12]= 0.20791;
sinWert[13]= 0.22495;
sinWert[14]= 0.24192;
sinWert[15]= 0.25882;
sinWert[16]= 0.27564;
sinWert[17]= 0.29237;
sinWert[18]= 0.30902;
sinWert[19]= 0.32557;
sinWert[20]= 0.34202;
sinWert[21]= 0.35837;
sinWert[22]= 0.37461;
sinWert[23]= 0.39073;
sinWert[24]= 0.40674;
sinWert[25]= 0.42262;
sinWert[26]= 0.43837;
sinWert[27]= 0.45399;
sinWert[28]= 0.46947;
sinWert[29]= 0.48481;
sinWert[30]= 0.50000;
sinWert[31]= 0.51504;
sinWert[32]= 0.52992;
sinWert[33]= 0.54464;
sinWert[34]= 0.55919;
sinWert[35]= 0.57358;
sinWert[36]= 0.58778;
sinWert[37]= 0.60181;
sinWert[38]= 0.61566;
sinWert[39]= 0.62932;
sinWert[40]= 0.64279;
sinWert[41]= 0.65606;
sinWert[42]= 0.66913;
sinWert[43]= 0.68200;
sinWert[44]= 0.69466;
sinWert[45]= 0.70711;
sinWert[46]= 0.71934;
sinWert[47]= 0.73135;
sinWert[48]= 0.74314;
sinWert[49]= 0.75471;
sinWert[50]= 0.76604;
sinWert[51]= 0.77715;
sinWert[52]= 0.78801;
sinWert[53]= 0.79864;
sinWert[54]= 0.80902;
sinWert[55]= 0.81915;
sinWert[56]= 0.82904;
sinWert[57]= 0.83867;
sinWert[58]= 0.84805;
sinWert[59]= 0.85717;
sinWert[60]= 0.86602;
sinWert[61]= 0.87462;
sinWert[62]= 0.88295;
sinWert[63]= 0.89101;
sinWert[64]= 0.89879;
sinWert[65]= 0.90631;
sinWert[66]= 0.91355;
sinWert[67]= 0.92050;
sinWert[68]= 0.92718;
sinWert[69]= 0.93358;
sinWert[70]= 0.93969;
sinWert[71]= 0.94552;
sinWert[72]= 0.95106;
sinWert[73]= 0.95630;
sinWert[74]= 0.96126;
sinWert[75]= 0.96593;
sinWert[76]= 0.97030;
sinWert[77]= 0.97437;
sinWert[78]= 0.97815;
sinWert[79]= 0.98163;
sinWert[80]= 0.98481;
sinWert[81]= 0.98769;
sinWert[82]= 0.99027;
sinWert[83]= 0.99255;
sinWert[84]= 0.99452;
sinWert[85]= 0.99619;
sinWert[86]= 0.99756;
sinWert[87]= 0.99863;
sinWert[88]= 0.99939;
sinWert[89]= 0.99985;
sinWert[90]= 1.00000;

.
.
.
.
und so weiter bis 451 des tua i jetzt aber nit eine




//###########################################################################

while(1){

if(a==n){
a=0;
}


out = 0;
for(k=0;k<=f;k++){
x=360*k*a/n;

//for(x=360*k*a/n;x>=361;x=x-360){
//Hallo;
//}

if(x>=91){
if(x<=180){
x=180-x;
}
}
if(x>=181){
if(x<=270){
x=x-180;
sinWert[x]=-sinWert[x];

}
}
if(x>=271){
if(x<=360){
x=360-x;
sinWert[x]=-sinWert[x];
}
}


out = out + kf_abs[k]*sinWert[x];
}
set_PWM1_duty(out);

//------------------------------------------------------------------------------

for(p=0;p<=f;p++){
w=360*p*a/n;

//for(w=360*p*a/n;w>=361;w=w-360){
//Hallo;
//}

if(w>=91){
if(w<=180){
w=180-w;
}
}
if(w>=181){
if(w<=270){
w=w-180;
sinWert[w]=-sinWert[w];

}
}
if(w>=271){
if(w<=360){
w=360-w;
sinWert[w]=-sinWert[w];

}
}

kf_im[p]=kf_im[p]+in[a]*sinWert[w];
kf_re[p]=kf_re[p]+in[a]*sinWert[w+90];
if(a==n-1){
kf_abs[p]=sqrt(kf_re[p] * kf_re[p] + kf_im[a] * kf_im[p]);
}
}

//------------------------------------------------------------------------------

in[a]=read_adc();


a++;

}

//##########################################################################


}




das ganze hab ich mit einem PIC 18F450

Danke Dombrowski für deine unterstützung! wie ich meins heute nachmittag reingeschrieben hab war deins bei mir noch nicht online! also den ersten satz mit "Leider!" bitte vergessen!
werd dein programm grad mal durchstudieren. mal schaun ob ich es auch zum laufen bring!

LG

Moin.

Wenn der µC eine PC-Schnittstelle hat, würde ich die Abtastwerte zunächst mal zum PC schicken und dort per FT auswerten. Dort kann man grafisch darstellen und schnell beurteilen, ob das alles Sinn macht, usw. Die Werte müssen aber mit einer Abtastfrequenz ermittelt werden, die nicht total von der endgültigen Frequenz abweicht.

Aber ich weiß nicht, was du bisher schon an Vorarbeit durchlaufen hast. Vielleicht erzählst du ein bisschen zur Aufgabenstellung. Es geht also darum, ein Signal regelmäßig abzutasten und aus dessen Spektrum eine Stellgröße für eine PWM-Steuerung zu ermitteln. Soweit richtig? Was für Eigenschaften sind über das abzutastende Signal bekannt?

D.

Also zur Aufgabenstellung:

Wir bauen sowas wie ein Lasermikrophon. Um dies genauer zu erklären: man leuchtet mit einem Laserpunkt auf eine scheibe und nimmt das reflektierte signal von der fensterscheibe mit einer photodiodenmatrix auf.

d.h. wir haben uns eine photodiodenmatrix gebaut (SMD) welche in form einer antiparallelschaltung aufgebaut ist. Man kann sich das sowie ein schachbrettmuster vorstellen. diese photodiodenmatrix liefert uns je nach auslenkung des empfangenen laserpunkts werte von 0.5-4.5V welche der PIC nun berechnen soll mittels FFT,DFT oder was auch immer. Anschließend soll dieses berechnete signal über den PWM ausgegeben werden und dann über eine audiostufe hörbar gemacht werden. Prinzipiell funktioniert das alles auch schon bis auf die Programmierung des PIC.

Klar werden sich manche jetzt sagen bau einen Bandpass rein. Doch das ist eben genau das was wir nicht machen wollen,dürfen....naja!

soviel mal zu den hintergrundinformationen wofür wir den PIC brauchen.

GLG