c - Roberts-Slaney-Bouras 整数 FFT 实现问题

Question

我已经使用 np.fft 在 Python 中实现了信号处理 FFT 算法(太简单了)。现在我正在使用整数算法在 C 中完成此操作。经过一番研究，我发现互联网上最流行的 C 整数 FFT 库之一是 Roberts、Slaney 和 Bouras 的库，可以在很多地方找到，包括第二个条目 here。 .fft，

有几个概念不太明白，希望指导。具体来说，上面链接的库中包含的示例脚本通过将信号的所有偶数索引放入信号的前半部分并将奇数索引放入信号的后半部分，将输入信号分为实部和虚部两个容器。

for (i=0; i<N; i++){
    x[i] = AMPLITUDE*cos(i*FREQUENCY*(2*3.1415926535)/N);
    if (i & 0x01)            // only odd index
        fx[(N+i)>>1] = x[i]; // N+i >> 1 is len(input)+i/2
    else                     // only even index
        fx[i>>1] = x[i];
}
fix_fftr(fx, log2N, 0);

信号数组的长度没有改变，但现在包含两个几乎相同的信号。然后FFT驱动函数(fix_fftr)将整个输入信号作为参数并执行完全相同的操作

if (inverse)
    scale = fix_fft(fr, fi, m-1, inverse);
for (int i=1; i<n; i+=2) {
    tt = f[n+i-1];      // even index
    f[n+i-1] = f[i];    // odd index into the second half
    f[i] = tt;          // even index into the first half
}
if (!inverse)
    scale = fix_fft(fr, fi, m-1, inverse);
return scale;

这是什么原因？

Answer 1

第一部分是计算旋转因子，它是给定长度 FFT 的常数，并且与数据无关。

第二部分似乎是基于递归位反转寻址的数据混洗的一部分，这是就地 FFT 中的一个组件。