Transformada de Fourier discreta simple en el lugar (DFT)

Question

Escribo un DFT en el lugar muy simple. Estoy usando la fórmula que se muestra aquí: http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Definition junto con la fórmula de Euler para evitar tener que usar una clase de números complejos solo para esto. Hasta ahora tengo esto:

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

Pero los términos Math.cos y finalmente van Math.sin tanto positivos como negativos, de modo que estoy añadiendo esos términos se multiplica con los datos [k], se cancelan y yo acaba de obtener un valor obscenamente pequeño. Veo cómo está sucediendo, pero no puedo entender cómo mi código quizás esté representando erróneamente las matemáticas. Cualquier ayuda es apreciada. Para tu información, tengo que escribir la mía, me doy cuenta de que puedo conseguir FFT de venta libre.

Answer 1

Creo que usted tiene un error en esta sección

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

Debe reemplazar los datos [k] con datos [n]

EDIT:

También se destruya sus datos en la línea:

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

Usted tiene t o almacenar los módulos de sus números complejos en otro lugar o más tarde. Si el módulo es todo lo que desea y desea almacenarlo en datos [], debe codificar otro ciclo después de calcular la transformación. Todos los datos [] son ​​necesarios para calcular cada [k] real e 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; 
}