How exactly do you compute the Fast Fourier Transform?

Question

I've been reading a lot about Fast Fourier Transform and am trying to understand the low-level aspect of it. Unfortunately, Google and Wikipedia are not helping much at all.. and I have like 5 different algorithm books open that aren't helping much either.

我试图找到像矢量[1,0,0,0]那样简单的FFT.当然我可以将其插入Matlab,但这无助于我理解底层正在发生的事情.另外,当我说我想找到一个向量的FFT时,就像说我想用一个更有效的算法找到一个向量的DFT一样吗？

Answer 1

你是对的,"快速傅立叶变换只是在O(n log n)时间内计算离散傅里叶变换的任何算法的名称,并且有几种这样的算法.

这是我想到的最简单的DFT和FFT解释,也是小N的例子,这可能会有所帮助.(请注意,有其他解释和其他算法.)

离散傅立叶变换

给定N数字f ₀,f ₁,f ₂,...,f _N-1,DFT给出不同的N数字组.

具体做法是:让ω是基元Ñ第1(或者在复数或在一些有限域)根,这意味着ω ^Ñ = 1,但没有较小的功率是1.可以想到的f- _ķ的作为多项式P的系数(X)=ΣF _ķ X ^ķ.DFT给出的N个新数F ₀,F ₁,...,F _N-1是在ω 的幂处评估多项式的结果.也就是说,对于每个Ñ从0到N-1时,新数F _Ñ是P(ω ^Ñ)=Σ _0≤k≤N-1 ˚F _ķ ω ^NK.

[选择ω的原因是逆DFT具有很好的形式,与DFT本身非常相似.

注意,找到这些F是天真地进行O(N ²)操作.但是我们可以利用来自我们选择的ω的特殊结构,这允许我们在O(N log N)中进行.任何这样的算法都称为快速傅立叶变换.

快速傅立叶变换

所以这是进行FFT的一种方法.我将用2N替换N以简化符号.我们F ₀,F ₁,F ₂,...,F _2N-1 ,我们要计算P(ω ⁰),P(ω ¹),... P(ω ^2N-1 ),我们可以写

P(X)= Q(x)的+ω ^Ñ R(x)的有

Q(x)= f ₀ + f ₁ x + ... + f _N-1 x ^N-1

R(x)= f _N + f _{N + 1} x + ... + f _2N-1 x ^2N-1

现在这里是美丽的东西.观察到,在ω的值^{ķ+ N}被非常简单地与在ω的值^ķ:
P(ω ^{ķ+ N})=ω ^Ñ(Q(ω ^ķ)+ω ^Ñ R(ω ^ķ))= R(ω ^ķ)+ω ^ñ Q(ω ^ķ).所以Q和R中的ω评价⁰至ω ^N-1就足够了.

这意味着原来的问题-评估在2N-术语多项式P的2N点ω ⁰到ω ^2N-1 -已经降低到评估在N点ω的N项多项式Q和R的两个问题⁰至ωN ^-1.因此运行时间T(2N)= 2T(N)+ O(N)以及所有这些,其给出T(N)= O(N log N).

DFT的例子

请注意,其他定义将因子设为1/N或1 /√N.

对于N = 2,ω= -1,(a,b)的傅立叶变换是(a + b,ab).

对于N = 3,ω是1的复杂立方根,并傅里叶变换的(A,B,C)是(A + B + C,A +Bω+Cω ²,一个+Bω ² +Cω).(由于ω ⁴ =ω.)

对于N = 4和ω= i,(a,b,c,d)的傅里叶变换是(a + b + c + d,a + bi-c-di,a-b + cd,a-bi) -c + DI).特别是你问题中的例子:(1,0,0,0)上的DFT给出(1,1,1,1),也许不是很有启发性.

Answer 2

FFT只是DFT的有效实现.两者的结果应该相同,但通常FFT会快得多.确保您首先了解DFT的工作原理,因为它更简单,更容易掌握.

了解DFT后,继续进行FFT.注意,尽管一般原理是相同的,但FFT有许多不同的实现和变化,例如抽取时间v抽取频率,基数2 v其他基数和混合基数,复数到复数v real到复杂等

关于这一主题的一本很好的实用书籍是E. Brigham的快速傅立叶变换及其应用.

Answer 3

是的，FFT 只是一种高效的 DFT 算法。理解 FFT 本身可能需要一些时间，除非您已经研究过复数和连续傅立叶变换；但它基本上是对从周期函数导出的基数的基数变化。

（如果你想了解更多关于傅里叶分析的知识，我推荐Gerald B. Folland 的《傅里叶分析及其应用》一书）