psi*_*lia 6 c math audio signal-processing fft
实现低通FIR滤波器,什么时候应该使用FFT和IFFT而不是时域卷积？
目标是实现实时计算所需的最短CPU时间.据我所知,FFT具有大约O(n log n)的复杂度,但时域中的卷积具有O(n 2)复杂度.要在频域中实现低通滤波器,应使用FFT,然后将每个值乘以滤波系数(将其转换为频域),然后进行IFFT.
那么,问题是何时使用基于频率的(FFT + IFFT)滤波而不是使用基于直接卷积的FIR滤波器是合理的？比方说,如果有一个32个定点系数,是否应该使用FFT + IFFT？128个系数怎么样？等等...
试图优化现有的源代码(基于卷积的FIR滤波器),我完全感到困惑,要么我应该使用FFT,要么只是优化它来使用SSE.
Pet*_*ans 10
卷积实际上是O(m*n),其中m是有限脉冲响应的宽度,N是样本窗口.
因此,更改为FFT + IFFT有用的m的临界点与样本窗口的log(N)有关.
在实时操作中,FFT是面向批处理的这一事实可能比时钟周期的相对量更重要,因为如果应用程序处于调节循环中,则在过滤之前等待1024个采样点可能是不可接受的.
现在已经进行了很多开发,这个领域和大量代码可用,所以尝试几个解决方案和基准测试是关键.
这取决于你正在使用的架构和其他各种因素,但一维DSP的一般"经验法则"是,如果滤波器尺寸很小,比如说小于100个术语,你可能最好使用直接卷积,但对于较大的滤波器尺寸,可能值得在频域中进行快速卷积.
当然,您需要确定过滤首先是性能瓶颈,因为如果您的时域实现已经足够快,那么进行快速卷积就没有必要付出额外的努力.
底线:先从简单直接卷积,然后切换到快速卷积以后,如果你需要它.(您需要保留第一个用于验证第二个实现的实现,因此无论如何都不会浪费精力.)