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