c++ - 根据定义计算 DFT(C++ with )

Question

为了我个人对数学 Material 的理解，我尝试仅使用 C++ 及其标准库来实现离散傅里叶变换的“朴素”定义，尽管我的代码似乎直接翻译 DFT 的数学定义。

这是代码(经过编辑以便比原始代码更好地清理输出):

void DFT(std::complex<double>* outputs, int N, std::complex<double>* inputs)
{
  for (int k = 0; k < N; ++k) 
  {
    outputs[k] = std::complex<double>(0.0, 0.0);
    for (int t = 0; t < N; ++t) 
    {
       // tk2π/N
       double angle = t * k * TWOPI / double(N);
       // e^(-jtk2π/N)
       std::complex<double> dft_sino = std::polar(1.0, -angle);

      if(fabs(real(dft_sino)) < std::numeric_limits<float>::epsilon())
        dft_sino = std::complex<double>(0.0, imag(dft_sino));

      if(fabs(imag(dft_sino)) < std::numeric_limits<float>::epsilon())
        dft_sino = std::complex<double>(real(dft_sino), 0.0);

      std::cout << "DFT sinosoid (" << k << "), Sample " << t << ": " << dft_sino << std::endl;
      outputs[k] += inputs[t] * dft_sino;
    }
  }
}

输入集是:

 1+1i
-1+1i
 1-1i
-1-1i
-3-1i
 4-2i
 0-3i
 2-6i

我期望的(已验证)输出是:

 3-12i
 10.24+5.243i
 3+2i
 9.071+10.07i
-5+4i
 1.757-3.243i
-9+6i
-5.071-4.071i

程序的当前形式的输出是:

 3+2i
 3.293+6.364i
-2-1i
 6.121+6.95i
-5-4.91e-15i
 4.707-6.364i
-4+3i
 1.879-2.95i

我在这里明显遗漏了什么吗？

编辑:下面是相应 DFT 正弦样本的样本输出，这些样本在求和期间乘以输入。

DFT sinusoid (0):
Sample 0: 1+0i
Sample 1: 1+0i
Sample 2: 1+0i
Sample 3: 1+0i
Sample 4: 1+0i
Sample 5: 1+0i
Sample 6: 1+0i
Sample 7: 1+0i

DFT sinusoid (1):
Sample 0: 1+0i
Sample 1: 0.7071-0.7071i
Sample 2: 0-1i
Sample 3: -0.7071-0.7071i
Sample 4: -1+0i
Sample 5: -0.7071+0.7071i
Sample 6: 0+1i
Sample 7: 0.7071+0.7071i

DFT sinusoid (2):
Sample 0: 1+0i
Sample 1: 0-1i
Sample 2: -1+0i
Sample 3: 0+1i
Sample 4: 1+0i
Sample 5: 0-1i
Sample 6: -1+0i
Sample 7: 0+1i

DFT sinusoid (3):
Sample 0: 1+0i
Sample 1: -0.7071-0.7071i
Sample 2: 0+1i
Sample 3: 0.7071-0.7071i
Sample 4: -1+0i
Sample 5: 0.7071+0.7071i
Sample 6: 0-1i
Sample 7: -0.7071+0.7071i

DFT sinusoid (4):
Sample 0: 1+0i
Sample 1: -1+0i
Sample 2: 1+0i
Sample 3: -1+0i
Sample 4: 1+0i
Sample 5: -1+0i
Sample 6: 1+0i
Sample 7: -1+0i

DFT sinusoid (5):
Sample 0: 1+0i
Sample 1: -0.7071+0.7071i
Sample 2: 0-1i
Sample 3: 0.7071+0.7071i
Sample 4: -1+0i
Sample 5: 0.7071-0.7071i
Sample 6: 0+1i
Sample 7: -0.7071-0.7071i

DFT sinusoid (6):
Sample 0: 1+0i
Sample 1: 0+1i
Sample 2: -1+0i
Sample 3: 0-1i
Sample 4: 1+0i
Sample 5: 0+1i
Sample 6: -1+0i
Sample 7: 0-1i

DFT sinusoid (7):
Sample 0: 1+0i
Sample 1: 0.7071+0.7071i
Sample 2: 0+1i
Sample 3: -0.7071+0.7071i
Sample 4: -1+0i
Sample 5: -0.7071-0.7071i
Sample 6: 0-1i
Sample 7: 0.7071-0.7071i

Answer 1

好消息是您的 DFT 实现没有任何问题，而且我能够确认在正确输入的情况下，该函数会产生您期望的输出。这意味着它接收到的输入存在问题。以类似的方式实现逆变换表明​​以下输入实际上被馈送到 DFT 函数:

 1+1i
-1+1i
 1+0i
-1+0i
-3+0i
 4+0i
 0+0i
 2+0i

由此看来，您似乎缺少大多数输入的虚部(inputs[0] 和 inputs[1] 除外)。由于您没有提供 inputs 中的数据是如何生成并传递给 DFT 的，因此无法确切说明原因。但是，这里有一些可能导致此类问题的常见原因，您可以将其用作起点，同时调查为什么函数的 inputs 与您认为的不一样:

• 不小心(或没有)用零覆盖输入缓冲区的虚部。这可能是由于:
  • 为DFT 的inputs 和outputs 参数提供相同的数组(此实现要求它们是不同的数组)；
  • 使用小于转换大小 N 的输入和输出数组，然后在向这些数组写入值时写入越界；
• 居然忘记设置虚部；
• 从文件或程序的其他部分读取实部/虚部时错误地获取实部/虚部(例如，假设文件包含 8 个实部后跟 8 个虚部，但文件实际上仅包含 10 个值)。