离散傅里叶变换-FFT的实现

我正在尝试做一个声音处理项目，需要将频率放入另一个域。现在，我试图实现一个FFT，但进行得并不顺利。我试图理解z-转换，但也不太顺利。我读了一遍，发现DFT要简单得多，特别是算法。所以我用例子编写了算法，但是我不知道或者不认为输出是正确的。(我这里没有安装Matlab，也找不到任何资源来测试它)，我想知道你们是否知道我的方向是否正确。到目前为止，我的代码如下：

#include <iostream>
#include <complex>
#include <vector>

using namespace std;

const double PI = 3.141592;

vector< complex<double> > DFT(vector< complex<double> >& theData)
{
// Define the Size of the read in vector
const int S = theData.size();

// Initalise new vector with size of S
vector< complex<double> > out(S, 0);
for(unsigned i=0; (i < S); i++)
{
    out[i] = complex<double>(0.0, 0.0);
    for(unsigned j=0; (j < S); j++)
    {
        out[i] += theData[j] * polar<double>(1.0, - 2 * PI * i * j / S);
    }
}

return out;
}

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

vector< complex<double> > numbers;

numbers.push_back(102023);
numbers.push_back(102023);
numbers.push_back(102023);
numbers.push_back(102023);

vector< complex<double> > testing = DFT(numbers);

for(unsigned i=0; (i < testing.size()); i++)
{
    cout << testing[i] << endl;

}
}

输入为：

102023               102023

102023               102023

结果：

(408092,       0)

(-0.0666812,  -0.0666812)

(1.30764e-07, -0.133362)

(0.200044,    -0.200043)

任何帮助或建议都是很棒的，我并不期待太多，但是，任何事情都是很棒的。谢谢您：)

---

解决方案

您的代码看起来没有问题。out[0]应代表输入波形的"DC"分量。在您的情况下，它比输入波形大4倍，因为您的归一化系数是1。

其他系数应代表输入波形的幅度和相位。系数被镜像，即OUT[i]==OUT[N-I]。您可以使用以下代码对其进行测试：

double frequency = 1; /* use other values like 2, 3, 4 etc. */
for (int i = 0; i < 16; i++)
    numbers.push_back(sin((double)i / 16 * frequency * 2 * PI));

对于frequency = 1，这将提供：

(6.53592e-07,0)
(6.53592e-07,-8)
(6.53592e-07,1.75661e-07)
(6.53591e-07,2.70728e-07)
(6.5359e-07,3.75466e-07)
(6.5359e-07,4.95006e-07)
(6.53588e-07,6.36767e-07)
(6.53587e-07,8.12183e-07)
(6.53584e-07,1.04006e-06)
(6.53581e-07,1.35364e-06)
(6.53576e-07,1.81691e-06)
(6.53568e-07,2.56792e-06)
(6.53553e-07,3.95615e-06)
(6.53519e-07,7.1238e-06)
(6.53402e-07,1.82855e-05)
(-8.30058e-05,7.99999)

在我看来这似乎是正确的：直流可以忽略不计，第一次谐波的振幅为8，其他谐波的振幅可以忽略不计。