fft -优化代码以消除Nyquist上的图像

Question

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

我的问题是:有没有一个简单的.不关心FFT的上半部分吗？如果我打算截断/丢弃它，我当然可以通过不计算它来节省时间？

​

Answer 1

您可以节省一点时间--转换后的输出的上半部分每个条目需要执行几次浮点操作。然而，与DIT和DIF策略的总Theta(n log n)运行时间相比，渐近节省的是Theta(n)。有关DIT策略的电路图，请参见下面的内容:计算X0..3需要所有E和O条目。DIF的情况与此类似。

​

​

"DIT-FFT-butterfly“by Virens --自己的作品。通过Wikimedia Commons在CC 3.0下获得许可。