实现低通FIR滤波器,什么时候应该使用FFT和IFFT而不是时域卷积？
目标是实现实时计算所需的最短CPU时间.据我所知,FFT具有大约O(n log n)的复杂度,但时域中的卷积具有O(n 2)复杂度.要在频域中实现低通滤波器,应使用FFT,然后将每个值乘以滤波系数(将其转换为频域),然后进行IFFT.
那么,问题是何时使用基于频率的(FFT + IFFT)滤波而不是使用基于直接卷积的FIR滤波器是合理的？比方说,如果有一个32个定点系数,是否应该使用FFT + IFFT？128个系数怎么样？等等...
试图优化现有的源代码(基于卷积的FIR滤波器),我完全感到困惑,要么我应该使用FFT,要么只是优化它来使用SSE.
我想用离散滤波器对离散信号进行卷积.信号和滤波器是F#中的浮点序列.
我可以弄清楚如何做的唯一方法是使用两个嵌套的for循环和一个可变数组来存储结果,但它感觉不是很有用.
这是我如何做到非功能性:
conv = double[len(signal) + len(filter) - 1]
for i = 1 to len(signal)
for j = 1 to len(filter)
conv[i + j] = conv[i + j] + signal(i) * filter(len(filter) - j)