我正在编写一个音频分析程序，需要对数据帧进行一些 FFT。我有一些代码（相当冗长，所以我将省略细节），通过索引的位反转，根据Danielson-Lanczos 引理成功地执行数据的洗牌。例如，数据序列0,1,2,3,4,5,6,7变为0,2,4,6,1,3,5,7（尽管我使用的窗口大于 8 个样本！）
问题是我对如何处理结果向量有点困惑。我完全迷路了。我读过一些关于对数据点对进行转换然后将它们组合起来的内容。那么我会将 DFT 应用于0and 2，然后将结果向量与4and的 DFT 的向量相加6（使用上面的示例数据点）并将其添加到(DFT(1,3) + DFT(5,7))？
如果重要的话，我正在处理 wav 文件的正确通道，因此信号没有虚部。
（我正在使用 C# 在 Unity 中进行开发，j 可以找到的唯一库是 .Net 4.0，而 Unity 目前仅支持 3.5。另外，我认为这很有趣，如果不是令人困惑的话！）
我不太确定您要问什么，但我会尝试告诉您有关您问题的这一点的一些信息：
问题是我对如何处理结果向量有点困惑。
您没有合成向量，您有两个向量 [0,2,4,6], [1,3,5,7] 并且通过 DL 引理，您可以将原始向量的 DFT 计算为这两个向量的 DFT。
考虑到两个较短的 DFT 是周期性的，并且后半部分的组合系数是前半部分使用的系数的负数，我们要么导致 FFT 算法的非常简单的递归实现，要么导致更复杂的实现不使用递归。让我们保持简单...
在 pythonesque 伪代码中，递归实现可以简单地写成
def fft(x,n,e):
if n==1:
X = x # the DFT of a scalar is the scalar itself
return X
else:
X0, X1 = fft(x[0::2],n/2,e[0::2]), fft(x[1::2],n/2,e[0::2])
X0, X1 = X0 + e*X1, X0-e*X1
X = concatenate(X0,X1)
return X
在哪里
x是我们要计算 DFT 的向量n是它的长度e是一个具有所谓的 _twiddle_factors_ 的向量，即n第 - 个单位根的一半（对于正向 DFT，从单位圆的下部开始，否则从上部开始）并且[start:stop:step]符号代表向量元素的选择，到末尾stop缺少含义。
要打电话fft，您必须提供旋转因子的初始向量
X = fft( x, n, exp(-2*pi*1j*(0..n/2-1)/n)) # forward
x = fft(X/n, n, exp(+2*pi*1j*(0..n/2-1)/n)) # inverse
其中1jid 是虚数单位，表示从到(0..n/2-1)的算术级数，包括极端情况。0n/2-1