我一直在阅读关于快速傅里叶变换的内容，试图理解其中的底层。不幸的是，谷歌和维基百科并没有提供太多帮助，而我打开的五本不同的算法书也没有什么帮助。
我试图找到类似向量[1，0，0，0]这样简单的东西的FFT。当然，我可以直接将其放入Matlab中，但那不会帮助我理解底层发生了什么。此外，当我说我想要找到一个向量的FFT时，是否意味着我想要使用更高效的算法来找到一个向量的DFT？
你如何准确计算快速傅里叶变换？
16
- Parth
3
虽然这可能不会帮助理解，但这是一个很好的实现：http://www.fftw.org/。它有相当完善的文档。 - Adam Shiemke
请注意，这是一个两部分的问题：1. 我如何直观地想象或甚至预测离散傅里叶变换（正如答案中提到的，FFT实际上是执行DFT的算法）对我的输入所做的事情？2. 我该如何实现FFT？ - Domi
那么它有什么用呢？傅里叶变换将输入信号转换为频率空间，告诉您不同频率在信号中出现的频率。这为您提供了许多关于信号的信息，您可以使用这些信息来查找、消除或放大某些频率甚至是信号的其他属性。这是可能的，因为傅里叶变换具有反演，允许您将更改后的频率空间转换回信号空间。 - Domi
5个回答
28
你说得对，“快速傅里叶变换”只是一个在 O(n log n) 时间内计算离散傅里叶变换的算法的名称，而且有许多这样的算法。
以下是我能想到的 DFT 和 FFT 的最简单解释，以及一些小 N 的示例可能会有所帮助。（请注意，还有其他解释和算法。）
离散傅里叶变换
给定 N 个数字 f0、f1、f2、…、fN-1，DFT 给出了一个不同的 N 个数字集合。
具体来说：令 ω 是一个原根为 N（可以是复数或某个有限域中的原根），这意味着 ωN=1，但没有更小的幂等于 1。您可以将 fk 视为多项式 P(x) = ∑fkxk 的系数。DFT 给出的 N 个新数字 F0、F1、…、FN-1 是在 ω 的幂次下对该多项式进行 求值的结果。也就是说，对于每个从 0 到 N-1 的 n，新数字 Fn 是 P(ωn) = ∑0≤k≤N-1 fkωnk。
[之所以选择 ω 是因为逆 DFT 具有很好的形式，非常类似于 DFT 本身。]
请注意，朴素地找到这些 F 需要 O(N2) 次操作。但我们可以利用我们选择的 ω 所带来的特殊结构，使我们能够在 O(N log N) 内执行它。任何这样的算法都称为快速傅里叶变换。
快速傅里叶变换
下面是一种执行 FFT 的方法。我将用 2N 替换 N 来简化符号。我们有 f0、f1、f2、…、f2N-1，我们想要计算 P(ω0)、P(ω1)、…P(ω2N-1)，其中
P(x) = Q(x) + ωNR(x)，其中
Q(x) = f0 + f1x + … + fN-1xN-1
R(x) = fN + fN+1x + … + f2N-1x2N-1
观察这个式子。注意到在 ωk+N 的值可以很简单地与 ωk 的值相关联：
P(ωk+N) = ωN(Q(ωk) + ωNR(ωk)) = R(ωk) + ωNQ(ωk)。所以 Q 和 R 在 ω0 到 ωN-1 处的计算足够了。
这意味着你最初的问题——在 2N 个点 ω0 到 ω2N-1 上评估 2N 项多项式 P——已经被转化为评估 N 个点 ω0 到 ωN-1 的两个问题：N 项多项式 Q 和 R。因此，运行时间 T(2N) = 2T(N) + O(N)，这给出了 T(N) = O(N log N)。
DFT 的例子
注意到其他的定义会放置一个 1/N 或 1/√N 的系数。
对于 N=2，ω=-1，(a,b) 的 Fourier 变换是 (a+b, a-b)。
对于 N=3，ω 是 1 的复立方根，(a,b,c) 的 Fourier 变换是 (a+b+c, a+bω+cω2, a+bω2+cω)。（由于 ω4=ω。）
对于 N=4 和 ω=i，(a,b,c,d) 的 Fourier 变换是 (a+b+c+d, a+bi-c-di, a-b+c-d, a-bi-c+di)。特别地，在你问题中的例子中：(1,0,0,0) 的 DFT 是 (1,1,1,1)，可能并不很清晰。
- ShreevatsaR
1
这个答案非常清晰明了，点赞！ - jmishra
7
FFT只是DFT的高效实现。两者的结果应该是相同的，但通常FFT会更快。请确保您先了解DFT的工作原理，因为它更简单且更易于理解。
当您了解了DFT之后，再学习FFT。请注意，虽然一般原则相同，但FFT有许多不同的实现和变体，例如时间抽取与频率抽取，基数2与其他基数以及混合基数，复杂到复杂与实到复杂等。
关于这个主题，可以阅读E. Brigham的《快速傅里叶变换及其应用》这本实用书。
当您了解了DFT之后，再学习FFT。请注意，虽然一般原则相同，但FFT有许多不同的实现和变体，例如时间抽取与频率抽取，基数2与其他基数以及混合基数，复杂到复杂与实到复杂等。
关于这个主题，可以阅读E. Brigham的《快速傅里叶变换及其应用》这本实用书。
- Paul R
2
1对于参考Brigham点赞。这是我读过的最好的解释。 - andand
@andand：谢谢，是的，这本书很棒，尽管它现在已经相当老了：应用章节也很好，而且仍然相关。 - Paul R
2
我也是对傅里叶变换比较陌生，但我发现这本在线书籍非常有帮助：
《科学家和工程师数字信号处理指南》。
该链接将带您到离散傅里叶变换章节。该章节解释了所有傅里叶变换之间的区别，以及在哪种情况下使用哪种傅里叶变换，并提供伪代码，展示如何计算离散傅里叶变换。
该链接将带您到离散傅里叶变换章节。该章节解释了所有傅里叶变换之间的区别，以及在哪种情况下使用哪种傅里叶变换，并提供伪代码，展示如何计算离散傅里叶变换。
- Garg Unzola
2
是的，FFT只是一种高效的DFT算法。如果您之前已经学过复数和连续傅里叶变换，则理解FFT本身可能需要一些时间；但它基本上是从周期函数派生出的基础变换。
（如果您想了解更多傅里叶分析知识，我推荐Gerald B. Folland的书《傅里叶分析及其应用》）
- You
2
如果您想要了解DFT和FFT的简单易懂的英文解释，而不是学术术语的混杂，那么您一定需要阅读这篇文章：http://blogs.zynaptiq.com/bernsee/dft-a-pied/。我自己也不能更好地解释它了。
- Rob Vermeulen
1
很遗憾没有对实际FFT算法进行解释。无论如何，非常感谢这个链接！ - macbirdie
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接