快速傅里叶变换是谁提出的 快速傅里叶变换的基本思想

快速傅里叶变换的简要介绍

有限长序列可以通过离散傅里叶变换(DFT）将其频域也离散化成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。

快速傅里叶变换是谁提出的 快速傅里叶变换的基本思想

快速傅里叶变换是谁提出的 快速傅里叶变换的基本思想

快速傅里叶变换——理论

离散信号傅里叶变换的公式如下所示：

离散傅里叶变换的原理是将原本非周期的信号扩展为周期信号，在实际的数字电路处理中，处理的信号是有限长的，取长度为N，即N为信号 的周期，对于有限长周期信号，其离散傅里叶变换有如下性质：

其中 为周期信号的傅里叶级数，而 表示当且仅当 时有 ，因此可以将傅里叶变换转为离散表达，如下所示：

考虑 以N为周期，因此仅需要计算k从0到N-1即可，取 此公式写成矩阵乘法模式如下所示：

W为一个 的方阵，该计算的复杂度为

对于系数矩阵中的元素 ，其公式如下所示：

考虑 ，推导公式如下所示：

再考虑 和 的情况：

再考虑 和 的情况：

考虑 且 或 的情况：

根据上述推导，可以得出系数W具有以下四条性质，这三条性质会在后续推导中用到：

基n快速傅里叶变换用于一个长度N为 的序列，例如基2快速傅里叶作用在 的序列上，基4快速傅里叶作用在 的序列上。现在考虑基2FFT的推导（硬件实现一般使用基4或基8FFT实现），首先写出有限长离散序列的傅里叶变换，记一个信号 的FFT变换为 ：

快速傅里叶变换的核心思想为 分而治之 ，即 分治法 ，该思想的核心是将一个长度为N的问题，分级为两个长度为 的问题，应用在这里即是需要将一个序列长度为N的FFT变换问题分解为两个序列长度为 的FFT变换。首先进行如下变换：

矩阵的形式如下所示：

根据W的性质 ，代入后有：

矩阵形式的表达如下所示，现在的矩阵为两个个高度为N，长度为N/2的矩阵。

代入 ，根据W的性质 有：

矩阵表达如下所示：

代入 ，根据W的性质 有：

矩阵表达如下所示：

根据上述推导，一个长度为N点的离散傅里叶变换被变为一个长度为 的离散傅里叶变换，取 公式如下所示：

根据频域抽取基2FFT的算法，除了按前后分类外，还可以直接按奇偶进行分类，公式如下所示：

对应的矩阵表示为：

取序列 ， 代入上述表达式，取 再代入W的变换性质可得：

其对应的矩阵为：

即将对F[k]的上半部分结果分解为两个FFT结果的和，即：

现在考虑F[k]的下半部分，公式如下所示：

取 ，代入有：

代入W的性质 和 ，有：

将变量i更换为k，其矩阵形式为：

最终可以将结果汇总为：

蝶形运算的公式如下，蝶形运算输入为 和 ，输出为 和 ，系数为 ：

其转换为矩阵表达为：

蝶形公式对应着2点FFT的计算，2点FFT的计算如下所示：

转换为矩阵表达为：

对应到蝶形运算有：

首先列出基2频域抽取FFT的分治公式：

以一个8点FFT为例，输入序列为：

进行次分治，分为两个4点FFT，序列为：

示意图如下所示，偶数标号的结果由个FFT生成，奇数标号的结果由第二个FFT生成：

随后进行第二次分治，将每个4点FFT分解为两个2点FFT，每个序列为：

示意图如下所示：

最终通过2点FFT计算出结果，但如上图所示，计算出的结果位置与标号并不对应，例如计算输出的标号为2的数据（Y10[1]）应当位于输出序列（X）的标号4（X[4]）。其变换规律为计算输出的标号为n的数据（第n+1个数据）对应到输出序列标号为m的数据，n为m的二进制反序。以计算输出标号为6（第七个数据）的数据Y13[0]为例，6的二进制为110，反序为011，对应十进制数为3，即有 。

首先列出时域抽取FFT的分治公式：

FFT变换是什么？

快速傅里叶变换(FFT) Fast Fourier Transform

是1965年由美国的库利—图基提出的计算离散傅里叶变换的方法，它大大地减少了运算量，缩短了运算时间，使实时分析成为可能。

傅里叶变换

傅里叶级数得名于法国数学家约瑟夫·傅里叶，他提出任何函数都可以展开为三角级数。

考虑一个在区间 上可积的函数 ，其傅里叶级数为

其中

由欧拉公式 得

代入（1）可得

令则可以得到傅里叶级数的复数形式

其中

傅里叶变换可以看作傅里叶级数的连续形式。

首先考虑定义在 上的函数的傅里叶级数展开：

其中

令记

则当 时， ， ， (14) 中的求和变为积分

相应地，(12) 变为

(16) 称为傅里叶变换，记作 ；(15) 称为傅里叶变换的逆变换，记作 。在信号分析中， 称为信号的时域表示， 称为信号的频域表示。

需要明确的是，不管是用时域还是用频域来表示一个信号，它们代表的都是同一个信号。可以从线性空间的角度理解这一点。同一个信号在不同的表象（或者说基向量）下具有不同的坐标。同一个向量在不同表象下的坐标可以通过一个线性变换联系起来。如果是有限维的空间，这个线性变换可以表示为一个矩阵。而傅里叶变换则是无限维空间不同表象之间的一种变换。举例来说，在量子力学中，一个波函数的坐标表象到动量表象间的变换就是一个傅里叶变换。

也可以将角频率 替换为自然频率 ，有 ，则

一般情况下，我们处理的信号都是离散的。取 在时间上的离散采样

是采样的时间间隔。傅里叶变换只能作用在连续函数上，为此我们引入

其中

为 Dirac 函数。 称为 Dirac 梳子，亦称 Shah 分布，是一个采样函数，常用在数字信号处理和离散时间信号分析中。

对 作傅里叶变换

这里利用了 Dirac 函数的性质 。(22) 即为离散时间傅里叶变换。

下面简单介绍一下采样定理。若原信号 不包含高于 的频率，即 ，则只要采样频率 ，时域采样就能完全重建原信号。

将 在 上展开为傅里叶级数

其中

注意到 时 ，而 ，故 时 ，因此 (24) 可改写为

代入 (23)，得

这里 。(26) 说明原信号的傅里叶变换可以由采样信号确定，进而可以利用傅里叶逆变换重建原信号。

此外，不难发现

是一个周期为 的周期函数。离散傅里叶变换 可以看作原信号连续傅里叶变换 的周期延拓，时域的离散化造成了频域的周期化。

离散时间傅里叶变换在频域上仍然是连续的。如果把频域也离散化，就得到了离散傅里叶变换。

也可以写成矩阵形式

其中 。

离散傅里叶变换的逆变换为

直接根据定义计算离散傅里叶变换的复杂度是 。快速傅里叶变换是快速计算离散傅里叶变换及其逆变换的一类数值算法。FFT 通过把 DFT 矩阵分解为稀疏矩阵之积，能够将复杂度降低到 。

在 Python 中可以利用 scipy.fftpack 进行快速傅里叶变换。

快速傅里叶变换公式

快速傅里叶变换公式如下：

公式描述：公式中F(ω)为f(t)的像函数，f(t)为F(ω)的像原函数。傅立叶变换在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。最初傅立叶分析是作为热过程的解析分析的工具被提出的。

：

因FFT是为时序电路而设计的，因此，控制信号要包括时序的控制信号及存储器的读写地址，并产生各种辅助的指示信号。同时在计算模块的内部，为保证高速，所有的乘法器都须始终保持较高的利用率。这意味着在每一个时钟来临时都要向这些单元输入新的作数。

而这一切都需要控制信号的紧密配合。为了实现FFT的流形运算，在运算的同时，存储器也要接收数据。这可以采用乒乓RAM的方法来完成。这种方式决定了实现FFT运算的时间。对于4k作，其接收时间为4096个数据周期,这样FFT的运算时间就是4096个数据周期。

另外，由于输入数据是以一定的时钟为周期依次输入的，故在进行内部运算时，可以用较高的内部时钟进行运算，然后再存入RAM依次输出。