Das e hoch i*p ist die Eulersche Formel, auch Eulersche Identität
genannt. Das heißt: schreibt man z = e^(i*p) und z ist eine komplexe
Zahlen (was ja im Grunde zwei reelle Zahlen sind->reelle und imaginäre),
dann ist der reelle Teil = cos(p) und der imaginäre = sin(p).
Du übergibst der Fourier-Transformation ein Array aus komplexen Zahlen,
wobei im Realteil alle Abtastwerte vom deinem AD-Wandler gespeichert
sind und alle imaginären Teile des Arrays auf 0 gesetzt werden. Wenn du
das Spektrum suchst benötigst von den transformierten Werten nur die
Hälfte + 1. Hast du z.B. der FFT 32 komplexe Zahlen übergeben, brauchst
du zum Schluss die ersten 17, die anderen Werte sind Spiegelungen mit
negativer imaginären Teil. Jetzt brauchst du nur noch die Auslenkung der
ersten 17 komplexen Zahlen ermitteln indem du jeweils r = Wurzel((real +
real) + (imag * imag)) rechnet und dann hast du dein Spektrum.
Aus dem Pseudocode von Wikipedia hatte ich folgende C++ Routinen
geschrieben, wurden aber auf wiki wieder entfernt:
vector<complex<double> > DFT(vector<complex<double> >f)
{
int n = f.size();
vector<complex<double> > r(n);
complex<double> temp;
for(int k = 0; k != n; k++)
{
for(int j = 0; j != n; j++)
{
double x = (-2.0 M_PI k * j) / n;
temp = complex<double>(cos(x), sin(x));
r[k] = r[k] + (f[j] * temp);
}
}
return r;
}
vector<complex<double> > FFT(vector<complex<double> >f)
{
int n = f.size();
if((n & n - 1) != 0)
{
cout << "n ist keine Zweierpotenz." << endl;
vector<complex<double> > r(0); return r;
}
else if(n == 1)
{
return f;
}
vector<complex<double> > gPar(n / 2);
vector<complex<double> > uPar(n / 2);
for(int k = 0; k != n / 2; k++)
{
gPar[k] = f[k * 2];
uPar[k] = f[k * 2 + 1];
}
vector<complex<double> > g = FFT(gPar);
vector<complex<double> > u = FFT(uPar);
complex<double> temp;
vector<complex<double> > r(n);
for(k = 0; k != n / 2; k++)
{
double x = (-2.0 PI k) / n;
temp = complex<double>(cos(x), sin(x));
r[k] = g[k] + (u[k] * temp);
r[k + (n / 2)] = g[k]- (u[k] * temp);
}
return r;
}
Ich hab die dft in Excel nachgebildet mit 8 Abtastwerten, dadurch hab
ich die Transformation besser verstanden.
Auf
http://manfred.informatik.hu-berlin.de/php/fftw.php
kannst du die Werte der fft überprüfen.
