ifft結果不同於原始信號

Question

FFT工作正常，但是當我想採用IFFT時，我總是從其結果中看到相同的圖形。無論原始信號如何，結果都很複雜，圖形總是相同的。

在實部圖表

是與虛部段=幀大小

一個-sin它與同期

在哪裏可以是一個問題一個-cos？

原始信號：

IFFT真正的價值（在照片是唯一的幀的一半）：

FFT算法，我使用。

double** FFT(double** f, int s, bool inverse) { 
    if (s == 1) return f; 
    int sH = s/2; 

    double** fOdd = new double*[sH]; 
    double** fEven = new double*[sH]; 
    for (int i = 0; i < sH; i++) { 
     int j = 2 * i; 
     fOdd[i] = f[j]; 
     fEven[i] = f[j + 1]; 
    } 

    double** sOdd = FFT(fOdd, sH, inverse); 
    double** sEven = FFT(fEven, sH, inverse); 

    double**spectr = new double*[s]; 

    double arg = inverse ? DoublePI/s : -DoublePI/s; 
    double*oBase = new double[2]{ cos(arg),sin(arg) }; 
    double*o = new double[2]{ 1,0 }; 

    for (int i = 0; i < sH; i++) { 
     double* sO1 = Mul(o, sOdd[i]); 

     spectr[i] = Sum(sEven[i], sO1); 
     spectr[i + sH] = Dif(sEven[i], sO1); 

     o = Mul(o, oBase); 
    } 

    return spectr; 
} 

Answer 1

的 「蝴蝶」 部分錯誤地應用係數：

for (int i = 0; i < sH; i++) { 
    double* sO1 = sOdd[i]; 
    double* sE1 = Mul(o, sEven[i]); 

    spectr[i] = Sum(sO1, sE1); 
    spectr[i + sH] = Dif(sO1, sE1); 

    o = Mul(o, oBase); 
} 

側面說明：

我一直在你的格式，但它使事情混亂：

fOdd有索引0，2，4，6，...所以它應該是fEven

fEven具有索引1，3，5，7，...所以它應該是fOdd

真sOdd應該是sLower和sEven應sUpper，因爲它們分別對應於頻譜的0:s/2和s/2:s-1元素：

sLower = FFT(fEven, sH, inverse); // fEven is 0, 2, 4, ... 
sUpper = FFT(fOdd, sH, inverse); // fOdd is 1, 3, 5, ... 

然後蝶形變爲：

for (int i = 0; i < sH; i++) { 
    double* sL1 = sLower[i]; 
    double* sU1 = Mul(o, sUpper[i]); 

    spectr[i] = Sum(sL1, sU1); 
    spectr[i + sH] = Dif(sL1, sU1); 

    o = Mul(o, oBase); 
} 

當這樣寫時，比較容易與pseudocode example on wikipedia比較。

而且@Dai是正確的你會泄漏大量的內存

Answer 2

關於內存，你可以使用std::vector封裝動態分配的數組，並確保在執行離開範圍他們釋放。您可以使用unique_ptr<double[]>，但性能提升不值得IMO和您失去at()方法的安全性。

（基於@羅布的回答）

一些其他提示：

• 避免含義模糊的標識 - 程序應該是可讀的，名稱，如「f」和「s」使你的程序更難閱讀和維護。
• 由於現代編輯器自動顯示類型信息，因此基於類型的匈牙利符號被忽視，因此它爲標識符名稱添加了不必要的複雜性。
• 使用size_t索引，而不是int
• STL是你的朋友，使用它！
• 使用const預防性地防止錯誤以防止只讀數據的意外突變。

像這樣：

#include <vector> 

using namespace std; 

vector<double> fastFourierTransform(const vector<double> signal, const bool inverse) { 

    if(signal.size() < 2) return signal; 
    const size_t half = signal.size()/2; 

    vector<double> lower; lower.reserve(half); 
    vector<double> upper; upper.reserve(half); 

    bool isEven = true; 
    for(size_t i = 0; i < signal.size(); i++) { 
     if(isEven) lower.push_back(signal.at(i)); 
     else   upper.push_back(signal.at(i)); 

     isEven = !isEven; 
    } 

    vector<double> lowerFft = fastFourierTransform(lower, inverse); 
    vector<double> upperFft = fastFourierTransform(upper, inverse); 

    vector<double> result; 
    result.reserve(signal.size()); 

    double arg = (inverse ? 1 : -1) * (DoublePI/signal.size()); 

    // Ideally these should be local `double` values passed directly into `Mul`. 
    unique_ptr<double[]> oBase = make_unique<double[]>(2); 
    oBase[0] = cos(arg); 
    oBase[1] = sin(arg); 

    unique_ptr<double[]> o = make_unique<double[]>(2); 
    o[0] = 0; 
    o[1] = 0; 

    for(size_t i = 0; i < half; i++) { 

     double* lower1 = lower.at(i); 
     double* upper1 = Mul(o, upper.at(i)); 

     result.at(i  ) = Sum(lower1, upper1); 
     result.at(i + half) = Dif(lower1, upper1); 

     o = Mul(o, oBase); 
    } 

    // My knowledge of move-semantics of STL containers is a bit rusty - so there's probably a better way to return the output 'result' vector. 
    return result; 
}