Transformée de Fourier discrète simple en place (DFT)

Question

J'écris une DFT en place très simple. J'utilise la formule montrée ici: http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Definition avec la formule d'Euler pour éviter d'avoir à utiliser une classe de nombre complexe juste pour cela. Jusqu'à présent, j'ai ceci:

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]); 
      } 
     } 

Mais les termes Math.cos et Math.sin vont finalement à la fois positifs et négatifs, de sorte que je suis d'ajouter ces termes multiplié par des données [k], ils annulent et je juste obtenir une valeur obscène. Je vois comment cela se passe, mais je ne comprends pas comment mon code est peut-être mal représenter les mathématiques. Toute aide est appréciée. Pour info, je dois écrire le mien, je me rends compte que je peux obtenir des FFT sur étagère.

Answer 1

Je crois que vous avez une erreur dans cette section

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); 
} 

Vous devez remplacer les données [k] avec des données [n]

EDIT:

Vous détruisez également vos données dans la ligne:

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

Vous avez t o stocker les modules de vos nombres complexes ailleurs ou plus tard. Si le module est tout ce que vous voulez, et vous voulez le stocker dans les données [] Vous devez coder une autre boucle après avoir calculé la transformation., Toute la donnée [] est nécessaire pour calculer tout réel [k] et imag [k].

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; 
}