您好，想请教一下快速傅里叶变换的理解。
大多数关于 FFT 的文章都描述了一个简单的 DFT 示例，其中 N=8 个样本。他们把它分成两半，平分和赔率。到那时，一切对我来说都很清楚（根据我已经实现了算法，并且我得到了整个频率范围的预期结果——在这种情况下从 1 到 8）。
但随后他们指示再次划分它，类似于第一次划分，然后再次划分。直到你最终得到 N/8。还有一些关于位反转的事情。但他们并没有表现出来，只是说“类似于第一次划分”。但在我看来，“类比”仍然不足以理解。对此感到抱歉。因此，对于接下来的划分，我得到了错误的结果。我做错了什么。不知道是什么。请帮我。
请让我通过一个简单的代码示例向您展示我的思维方式。首先我从 DFT 开始，这对我来说很清楚：
for(int freqBin=1; freqBin <= sampleRate; freqBin++)
{
_Sfx[0] = 0.0f; // I need to make it zero to perform _Sfx[0] += …
// in next coming for loop
for (int n=0; n<sampleRate; ++n)
{
complex<float> _Wnk_N = exp(-1i * 2.0 * M_PI * n * freqBin / sampleRate);
_Sfx[0] += inputSignal[n] * _Wnk_N;
}
output[freqBinK] = _Sfx[0];
}
然后我首先划分：
for(int freqBin=1; freqBin <= sampleRate/2; freqBin++)
{
for(int i=0; i<2; i++)
{
_Sfx[i] = 0.0f;
}
for (int n=0; n<sampleRate/2; ++n)
{
complex<float> _Wnk_N = exp(-1i * 2.0 * M_PI * n * freqBin / (sampleRate/2.0));
_Sfx[0] += inputSignal[2*n ] * _Wnk_N;
_Sfx[1] += inputSignal[2*n +1] * _Wnk_N;
}
complex<float> _Wk_N = exp(-1i * 2.0 * M_PI * freqBin / sampleRate);
_Sf_I_half = _Sfx[0] + _Wk_N * _Sfx[1];
_Sf_II_half = _Sfx[0] - _Wk_N * _Sfx[1];
output[freqBinK] = _Sf_I_half;
output[freqBinK + sampleRate /2] = _Sf_II_half;
}
这对我来说也很清楚 - 不确定，但我认为是这样，因为结果符合预期。
但后来我像这样进行下一个划分：
for(int freqBinK=1; freqBinK <= sampleRate/4; freqBinK++)
{
for(int i=0; i<4; i++)
{
_Sfx[i] = 0.0f;
}
for (int n=0; n<bufferSize/4; ++n)
{
complex<float> _Wnk_N = exp(-1i * 2.0 * M_PI * n * freqBin / (sampleRate/4.0));
_Sfx[0] += inputSignal[ 2*(2*n) ] * _Wnk_N ;
_Sfx[1] += inputSignal[ 2*(2*n) +1 ] * _Wnk_N ;
_Sfx[2] += inputSignal[ 2*(2*n +1) ] * _Wnk_N ;
_Sfx[3] += inputSignal[ 2*(2*n +1) +1] * _Wnk_N ;
}
complex<float> _Wk_N = exp(-1i * 2.0 * M_PI * freqBin / sampleRate);
complex<float> _Wk_N2 = exp(-1i * 2.0 * M_PI * freqBin / (sampleRate/2));
_Sf_I_quarter = (_Sfx[0] + _Wk * _Sfx[1]) +
_Wk_N2 * (_Sfx[2] + _Wk * _Sfx[3]);
_Sf_II_quarter = (_Sfx[0] - _Wk * _Sfx[1]) +
_Wk_N2 * (_Sfx[2] - _Wk * _Sfx[3]);
_Sf_III_quarter = (_Sfx[0] + _Wk * _Sfx[1]) -
_Wk_N2 * (_Sfx[2] + _Wk * _Sfx[3]);
_Sf_IV_quarter = (_Sfx[0] - _Wk * _Sfx[1]) -
_Wk_N2 * (_Sfx[2] - _Wk * _Sfx[3]);
output[freqBin] = _Sf_I_quarter;
output[freqBin + sampleRate /4] = _Sf_II_quarter;
output[freqBin + 2 * sampleRate /4] = _Sf_III_quarter;
output[freqBin + 3 * sampleRate /4] = _Sf_IV_quarter;
}
对于该代码，我只得到预期的一半范围，但在奈奎斯特（超过 N/2）之上有一些意想不到的值。为什么？在最后一个代码示例中我做错了什么？
你能帮我修改一下并按原样放置吗？请不要写关于 C++ 编程的文章。当我在 Stackoverflow 上问这个问题时，大多数答案都是关于代码的，但我问的是 FFT。并且请不要向我展示任何算法来完成 FFT，我只想了解下一步，在将 DFT 分成两半之后。如果我理解它，我希望我能够创建算法来计算整个范围的 FFT。
最后一件事：当然，我知道有很多 FFT 解决方案，免费，随时可用。但我的目标不是做 FFT，而是理解它。
提前非常感谢任何帮助。最好的祝福
编辑：当我说“预期”或“意外”时，我的意思是什么输出是有疑问的。
所以假设我有这样的输入信号：
for(int sample=0; sample<8; sample++)
{
inputSignal[sample] = sinf(1.0 * (float)sample * 2.0* M_Pi / 8.0);
}
当我通过 DFT 运行该信号时，我得到：
output[1] = 4.0;
output[2] = 0.0;
output[3] = 0.0;
output[4] = 0.0;
output[5] = 0.0;
output[6] = 0.0;
output[7] = 4.0;
output[8] = 0.0;
我需要评论它：
- 所有零都是近似值。实际上，更准确地说，所有零都类似于 8.52367e-07。但这不是重点，这就是我近似它的原因。
- 如您所见，我从 1 开始输出，而不是从零开始。问为什么？我也从 1 开始制作我的 DFT 频率环。因为我对 0 Hz 的频率不感兴趣。这些数字对应于
频率。因此，对于该问题的随机读者，我认为
输出 [1] 用于 1 Hz 会更清楚。但实际上这也不是重点。
但切中要害。现在你可以看到我的输出了。在我看来，它们是预期值。output[1]大于 0.0，因为我的输入信号有 1 Hz 正弦波。并且output[7]也大于 0.0，因为它是相对于奈奎斯特频率的镜像频率，即 4 Hz，只要我知道它是预期的。你同意？
在我的第二个代码示例中（我将 DFT 划分为偶数和赔率）给了我完全相同的输出值。这就是为什么我想我首先以适当的方式“分而治之”。
但是我的下一个“分而治之”（我的第三个代码示例）给了我不同的价值：
output[1] = 4.0;
output[2] = 0.0;
output[3] = 0.0;
output[4] = 0.0;
output[5] = 2.82843;
output[6] = 0.0;
output[7] = 2.82843;
output[8] = 0.0;
由于事实上它们是不同的价值观，我认为这些价值观是出乎意料的。这就是为什么我认为我做错了什么。但是找不到答案，究竟是什么问题？只能看到问题出在奈奎斯特以上的频率上，但为什么呢？请帮我。