algorithm - fft - 优化代码以消除高于 Nyquist 的图像

Question

我的理解是:如果我对(例如)2048 个数据点进行 FFT，我将获得前 1024 个点的数据，代表高达采样频率 1/2 的频率。我已经看到时间抽取 (DIT) 和频率抽取 (DIF) 作为更快计算 FFT 的方法。

我的问题:有没有一个程序可以简单地......不打扰 FFT 的上半部分？如果我要截断/丢弃它，我肯定可以通过不计算它来节省时间吗？

Answer 1

您可以节省一点时间——转换输出的上半部分每个条目都需要进行几个浮点运算。不过，与 DIT 和 DIF 策略的总 Theta(n log n) 运行时间相比，渐近节省的是 Theta(n)。请参见下面的 DIT 策略电路图:计算 X[0..3] 需要所有 E 和 O 条目。 DIF 的情况类似。

Virens 的“DIT-FFT-butterfly” - 自己的作品。通过 Wikimedia Commons 获得 CC BY 3.0 许可.