Einfache diskrete Fourier-In-Place-Transformation (DFT)

Question

Ich schreibe eine sehr einfache In-Place-DFT. Ich benutze die Formel, die hier gezeigt wird: http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Definition zusammen mit Eulers Formel, um zu vermeiden, eine komplexe Zahlklasse nur dafür zu verwenden. Bisher habe ich dies:

private void fft(double[] data) 
     { 
      double[] real = new double[256]; 
      double[] imag = new double[256]; 
      double pi_div_128 = -1 * Math.PI/128; 
      for (int k = 0; k < 256; k++) 
      { 
       for (int n = 0; n < 256; n++) 
       { 
        real[k] += data[k] * Math.Cos(pi_div_128 * k * n); 
        imag[k] += data[k] * Math.Sin(pi_div_128 * k * n); 
       } 
       data[k] = Math.Sqrt(real[k] * real[k] + imag[k] * imag[k]); 
      } 
     } 

Aber die Math.cos und Math.Sin Begriffe gehen schließlich sowohl positive als auch negative, so wie ich diese Begriffe Hinzufügen multipliziert mit Daten [k], löschen sie sich aus und ich Bekommen Sie nur einen obszön kleinen Wert. Ich sehe, wie es passiert, aber ich kann nicht verstehen, wie mein Code die Mathematik vielleicht falsch repräsentiert. Jede Hilfe wird geschätzt. FYI, ich muss meine eigene schreiben, ich merke, dass ich FFT von der Stange bekommen kann.

Answer 1

Ich glaube, Sie haben einen Fehler in diesem Abschnitt

for (int n = 0; n < 256; n++) 
{ 
    real[k] += data[k] * Math.Cos(pi_div_128 * k * n); 
    imag[k] += data[k] * Math.Sin(pi_div_128 * k * n); 
} 

Sie sollten Daten [k] mit Daten [n] ersetzen

EDIT:

Sie zerstören auch Ihre Daten in der Zeile:

data[k] = Math.Sqrt(real[k] * real[k] + imag[k] * imag[k]); 

Sie haben t o Speichere die Moduli deiner komplexen Zahlen irgendwo anders oder später. Wenn der Modulus alles ist, was Sie wollen und Sie ihn in Daten speichern wollen [] Sie müssen nach der Berechnung der Transformation eine weitere Schleife programmieren., Die gesamten Daten [] sind für die Berechnung jedes reellen [k] und imag [k] notwendig.

Answer 2

private double[] dft(double[] data) 
{ 
    int n = data.Length; 
    int m = n;// I use m = n/2d; 
    double[] real = new double[n]; 
    double[] imag = new double[n]; 
    double[] result = new double[m]; 
    double pi_div = 2.0 * Math.PI/n; 
    for (int w = 0; w < m; w++) 
    { 
     double a = w * pi_div; 
     for (int t = 0; t < n; t++) 
     { 
      real[w] += data[t] * Math.Cos(a * t); 
      imag[w] += data[t] * Math.Sin(a * t); 
     } 
     result[w] = Math.Sqrt(real[w] * real[w] + imag[w] * imag[w])/n; 
    } 
    return result; 
}