为什么FFT会加速卷积中涉及的计算？ [英] Why does FFT accelerate the calculation involved in convolution?

问题描述

我看到很多文献中他们说通过使用fft可以达到更快的卷积。我知道一个人需要获得fft然后从结果中获取，但我真的不明白为什么使用fft可以使卷积更快？

I am seeing a lot of literature in which they say that by using the fft one can reach a faster convolution. I know that one needs to get fft and and then ifft from the results, but I really do not understand why using the fft can make the convolution faster?

推荐答案

FFT加速卷积以获得足够大的滤波器，因为卷积需要为每个输出样本添加N次乘法（和N-1）相反，（2）N个样本块的N ^ 2个运算。

FFT speeds up convolution for large enough filters, because convolution requires N multiplications (and N-1) additions for each output sample and conversely (2)N^2 operations for a block of N samples.

考虑到，通过添加零，每个必须将FFT处理的块大小加倍，每个块需要（2）*（2N）* log（2N）运算来执行FFT，2N运算再乘以4N * log（2N）运算再执行逆FFT，有一个收支平衡点，其中8Nlog2N <= 2N ^ 2。

Taking account, that one has to double the block size for FFT processing by adding zeroes, each block requires (2)*(2N)*log(2N) operations to perform FFT, 2N operations to multiply and again 4N*log(2N) operations to perform inverse FFT, there is a break even point, where 8Nlog2N <= 2N^2.

基本原因是：

1）离散时域信号可表示为一个频率之和。

2）时域卷积（O（N ^ 2））等于频域中的频率倍增（O（N））
3）转换是可逆的< br>
4）存在一种在少于N ^ 2次操作中将信号从时域转换到频域的方法（这是第一个F）在'快速傅里叶变换'）。

1) a discrete time-domain signal can be represented as a sum of frequencies.
2) convolution in time domain (O(N^2)) equals multiplication of frequencies in frequency domain (O(N)) 3) the transformation is invertible
4) there exists a method to convert a signal from time domain to frequency domain in less than N^2 operations (that's the first F in 'Fast Fourier Transform').

直接FT为O（N ^ 2），其中每个频域元素F（i）= Sigma f（i）* exp（i * pi / N然而，FFT基于exp（i * pi / N）具有某些对称性的观察结果，允许计算在奇数/偶数向量中分割。）

The straight forward FT is O(N^2), where each Frequency domain element F(i) = Sigma f(i) * exp(i*pi/N).

偶数矢量可以以O（N）为代价来计算，而奇数矢量需要一半大小的完整FT。由于这可以重复直到N = 2，因此总体复杂度将与（Nlog（N））成比例。

However the FFT is based on an observation that exp(i*pi/N) has certain symmetries, allowing the calculation to be split in odd/even vectors. The even vectors can be calculated at the expense of O(N) while the odd vectors require a full FT of half the size. As this can be repeated until N=2, the overall complexity will be (proportional to) Nlog(N).

这篇关于为什么FFT会加速卷积中涉及的计算？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！