FFT Cooley Tukey算法 - 不能用於多個數字

Question

我正在嘗試爲FFT編寫Cooley Tukey算法。現在，算法運行良好，但是，只有2個數字 - 沒有別的。例如，我使用了在線FFT計算，輸入相同的數據並得到相同的結果。下面是算法的代碼：

#include <iostream> 
#include <math.h> 
#include <vector> 
#include <complex> 

using namespace std; 

#define pi 3.14159 

void ComplexFFT(vector<float> &realData, vector<float> &actualData, unsigned long sample_num, unsigned int sample_rate, int sign) 
{ 
    unsigned long n, mmax, m, j, istep, i; 
    double wtemp,wr,wpr,wpi,wi,theta,tempr,tempi; 

    // CHECK TO SEE IF VECTOR IS EMPTY; 

    actualData.resize(2*sample_num, 0); 

    for(n=0; (n < sample_rate); n++) 
    { 
     if(n < sample_num) 
     { 
      actualData[2*n] = realData[n]; 
     }else{ 
      actualData[2*n] = 0; 
      actualData[2*n+1] = 0; 
     } 
    } 

    // Binary Inversion 
    n = sample_rate << 1; 
    j = 0; 

    for(i=1; (i< n); i+=2) 
    { 
     if(j > i) 
     { 
      swap(actualData[j - 1], actualData[i - 1]); 
      swap(actualData[j], actualData[i]); 
     } 
     m = sample_rate; 
     while (m >= 2 && j > m) { 
      j -= m; 
      m >>= 1; 
     } 
     j += m; 
    } 
    mmax=2; 

    while(n > mmax) { 

     istep = mmax << 1; 
     theta = sign * (2*pi/mmax); 
     wtemp = sin(0.5*theta); 
     wpr = -2.0*wtemp*wtemp; 
     wpi = sin(theta); 
     wr = 1.0; 
     wi = 0.0; 

     for(m=1; (m < mmax); m+=2) { 
      for(i=m; (i <= n); i += istep) 
      { 
       j = i + mmax; 
       tempr = wr*actualData[j-1]-wi*actualData[j]; 
       tempi = wr*actualData[j]+wi*actualData[j-1]; 

       actualData[j-1] = actualData[i-1] - tempr; 
       actualData[j] = actualData[i]-tempi; 
       actualData[i-1] += tempr; 
       actualData[i] += tempi; 
      } 
      wr = (wtemp=wr)*wpr-wi*wpi+wr; 
      wi = wi*wpr+wtemp*wpi+wi; 
     } 
     mmax = istep; 
    } 

    // determine if the fundamental frequency 
    int fundemental_frequency = 0; 
    for(i=2; (i <= sample_rate); i+=2) 
    { 
     if((pow(actualData[i], 2)+pow(actualData[i+1], 2)) > pow(actualData[fundemental_frequency], 2)+pow(actualData[fundemental_frequency+1], 2)) { 
      fundemental_frequency = i; 
     } 

    } 
} 
int main(int argc, char *argv[]) { 

    vector<float> numbers; 
    vector<float> realNumbers; 

    numbers.push_back(50); 
    numbers.push_back(10); 
    numbers.push_back(50); 
    numbers.push_back(10); 
    ComplexFFT(numbers, realNumbers, 4, 8, -1); 

    for(int i=0; (i < realNumbers.size()); i++) 
    { 
     cout << realNumbers[i] << ' '; 
    } 
} 

如果我輸入：

50，10

那麼結果將是：在計算器

60.00, 0.0 
40.00, 0.0 

而且，確切的相同。

在哪裏，如果我進入：

60.00, 0.0 
40.00, 0.0 

計算器返回結果：

120.0, 0.0 
0.0, 0.0 
80.0, 0.0 
0.0, 0.0 

而且我的成績回報：

60, 60 
24.6446, -45.3553 
90, -10.0001 
4.64479, 45.3555 

有沒有人有什麼建議？

P.S.該算法僅適用於2位數值嗎？

謝謝:)

Answer 1

有在你的代碼中的一些錯誤：

  for(m=1; (m < mmax); m+=2) { 
      for(i=m; (i <= n); i += istep) 
      { 
       j = i + mmax;  // !!! Here, j will be bigger than actualData.size() - 1 
       tempr = wr*actualData[j-1]-wi*actualData[j]; 
       tempi = wr*actualData[j]+wi*actualData[j-1]; 

       actualData[j-1] = actualData[i-1] - tempr; 
       actualData[j] = actualData[i]-tempi; 
       actualData[i-1] += tempr; 
       actualData[i] += tempi; 
      } 
      wr = (wtemp=wr)*wpr-wi*wpi+wr; 
      wi = wi*wpr+wtemp*wpi+wi; 
     }