什么是快速傅立叶变换？

Question

我被问到一个面试问题，我需要在哪里使用它，但我不知道它是什么。

那么，在简单的英语中，什么是Fast Fourier Transform，我如何使用它来求函数的导数，给定它的(x，y)值作为输入？

您将如何实现它？

编辑：

我之所以这样问，是因为给定一系列(x，y)值，我需要计算函数的外观，推导它并找到它不断变化的次数(即，(0，1)，(1，2)被算作1)或根本不变(0，5)，(1，5)也被算作一次变化)。

Answer 1

至于问题的第一部分，前物理学教授Bartosz Milewski有一个非常好的explanation，什么是快速傅立叶变换以及它是如何工作的。

此外，Mastering The Fourier Transform in One Day也值得一读。

在英语中(?)

假设你有一个声音从扬声器中传来。

然后你设置，让我们在这里得到一个很好的整数，1024个谐振器，它们在特定的频率范围内共振。

播放声音，比如说，一秒钟。

振荡器开始对扬声器发出的声音产生共鸣。在这一秒之后，你可以读出每个振荡器有多大的共振度。结果，你得到了离散傅立叶变换，这意味着你得到了一个图表，显示每个频率范围对扬声器发出的声音的贡献程度。

不是将声音可视化为波形引起的气压量，而是在时隙中变化，而是将其可视化为一系列频率范围的强度。

当然，在解释DFT时，扬声器部分并不是真正合适的，因为您必须处理采样输入。因此，在这种情况下，假设音频以44 the的速率采样，1024个数字“振荡器”实际上应该在1/44秒后进行测量。

快速傅立叶变换是一种执行离散傅立叶变换的算法，对于计算机来说，在输入信号上运行非常容易。它施加了一些你在实现中必须处理的约束(例如，样本数量必须是2的幂)，因为它使用了一些聪明的技巧来大幅减少在sample buffer上执行的计算量。

真的没有必要更深入，因为我给出的两个链接提供了一个相当清晰的解释。请注意，在不了解背后的数学知识的情况下，不可能从理论到实现。

我希望这篇介绍能有一些意义！

Answer 2

傅立叶分析是一系列数学技术，都是基于将信号分解成正弦信号。离散傅立叶变换(DFT)是用于数字化信号的家族成员。

来自Wolfram，

快速傅立叶变换(

)是一种离散傅立叶变换算法，它将N个点所需的计算量从2N^2减少到2NlgN，其中lg是以2为底的对数。如果要转换的函数与采样频率不是谐波相关的，则FFT的响应看起来像一个正弦函数(尽管积分功率仍然正确)。混叠(也称为泄漏)可以通过使用变迹函数的变迹来减少。然而，混叠的减少是以扩大频谱响应为代价的。

它通常作为信号处理课程的一部分来教授。因此，您一定需要进行一些图像/声音处理。:)

请参阅斯坦福工程学院的这些讲座：here

基本上，DFT是

​

​

Cooley-Tukey FFT算法的伪代码如下：

Y0,...,N−1 ← ditfft2(X, N, s):             DFT of (X0, Xs, X2s, ..., X(N-1)s):
    if N = 1 then
        Y0 ← X0                                      trivial size-1 DFT base case
    else
        Y0,...,N/2−1 ← ditfft2(X, N/2, 2s)             DFT of (X0, X2s, X4s, ...)
        YN/2,...,N−1 ← ditfft2(X+s, N/2, 2s)           DFT of (Xs, Xs+2s, Xs+4s, ...)
        for k = 0 to N/2−1                           combine DFTs of two halves into full DFT:
            t ← Yk
            Yk ← t + exp(−2πi k/N) Yk+N/2
            Yk+N/2 ← t − exp(−2πi k/N) Yk+N/2
        endfor
    endif

(无耻地抄袭自http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm)

此外，您可能想要查看

1. http://www.fftw.org/download.html
2. http://www.developer.com/java/other/article.php/3457251
3. http://www.dspguide.com/pdfbook.htm

Answer 3

快速傅立叶变换是一种计算离散傅立叶变换( discrete Fourier transform )的算法。您可以将DFT看作是将采样信号表示为正弦和的一种方式。由于正弦的导数很简单，因此可以通过找到其DFT的导数来估计信号样本的导数。

这是signal processing中的一个很大的主题，我建议您购买一本介绍性书籍或参加一个课程来了解更多信息。

更新：在简单的英语中，它是一种将数字序列视为波的和的方式。