快速傅里叶变换——理论

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

离散傅里叶变换的原理是将原本非周期的信号复制扩展为周期信号，在实际的数字电路处理中，处理的信号是有限长的，取长度为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的分治公式：

sinwt的傅里叶变换公式是cosωbai0t=[exp(jω0t)+exp(-jω0t)]/2。

傅立叶变换表示能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。

在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。最初傅立叶分析是作为热过程的解析分析的工具被提出的。

相关信息：

傅立叶变换是一种分析信号的方法，它可分析信号的成分，也可用这些成分合成信号。许多波形可作为信号的成分，比如正弦波、方波、锯齿波等，傅立叶变换用正弦波作为信号的成分。

根据欧拉公式，cosω0t=[exp(jω0t)+exp(-jω0t)]/2。

直流信号的傅里叶变换是2πδ(ω)。

根据频移性质可得exp(jω0t)的傅里叶变换是2πδ(ω-ω0)。

再根据线性性质，可得

cosω0t=[exp(jω0t)+exp(-jω0t)]/2的傅里叶变换是πδ(ω-ω0)+πδ(ω+ω0)。

扩展资料

计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。

它们都借助于的两个特点：一是周期性；二是对称性，这里符号代表其共轭。这样，便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。

时间抽取算法 　令信号序列的长度为N=2,其中M是正整数，可以将时域信号序列x(n)分解成两部分，一是偶数部分x（2n），另一是奇数部分x（2n+1），于是信号序列x(n）的离散傅里叶变换可以用两个N/2抽样点的离散傅里叶变换来表示和计算。考虑到和离散傅里叶变换的周期性，式⑴可以写成

⑶其中（4a）（4b）由此可见，式⑷是两个只含有N/2个点的离散傅里叶变换，G(k）仅包括原信号序列中的偶数点序列，H(k）则仅包括它的奇数点序列。虽然k=0，1，2，…，N-1，但是G(k）和H(k）的周期都是N/2，它们的数值以N/2周期重复。

傅里叶积分公式如下：

①在任一有限区间都连续或只有有限个第一类间断点，并且只有有限个极值。

②在(-∞，+∞)上绝对可积，即有限；则定义[f(x)→C(ω)]。

为 f(x)的（复）傅里叶变换；记C(ω) = F[ f (x)] = f (ω)，称 C(ω)为（复）傅里叶变换像函数。

傅里叶积分是一种积分在运算过程中的变换，它来源于函数的傅里叶积分表示。以傅里叶变换为工具，研究函数的许多性质，是傅里叶分析的主要内容。傅里叶变换在数学、物理以及工程技术中都有重要的应用。

当一个非常复杂的函数变成多个初等正弦函数相加时，它的积分比之前对复杂函数的积分变得简单多了。法国数学家傅里叶发现了周期函数可以用一系列正弦函数组成的级数表示。先把函数作傅里叶变换，然后再利用莱布尼茨公式即可求出结果。

定理：在上面定义的基础上，可以证明在间断点，右边的积分收敛到f(x)在该点左右极限的平均值。该积分为 f(x)的傅里叶复积分；f(x)为 C(ω)的（傅里叶逆变换 C(ω)→f(x)）原函数。

找一本数学手册，里面有各种傅里叶变换公式。高斯函数的傅里叶变换仍然是高斯函数，碰撞增宽的函数式洛伦兹线型，有现成的傅里叶变换公式。矩形函数的傅里叶变换是SinC函数，因为有频移所以傅里叶变换结果有一个关于位移的相位。

在上一篇中 通俗易懂的傅里叶级数和傅里叶变换(一) 中简单介绍了什么是傅里叶级数，最后得到了在周期为 的傅里叶级数的系数解，那么如何得到任意周期的傅里叶级数呢？

我们先看在周期为 的函数傅里叶级数表达:

其对应的解为：

如何将其变为任意周期的函数呢？

其实这里只需要简单的换元操作即可。

举个栗子:

其周期为 , 。我们令 ,则 ,整理下:

所以在对于t来说就变换成了周期为 的函数。

so对于周期为 （方便计算）的函数f(t) 只需令 带入原周期为 的函数即可：

同样的可以得到：

最后我们得到:

过程很简单，我就省略了，毕竟人生苦短。

我们在写一下傅里叶级数的公式：

其中T代表函数的周期，也就是上面的2L，对应的解就是:

想要得到傅里叶级数的复数形式，需要先了解下欧拉公式。

关于欧拉公式，网上有很多的博客，这里就不细说了，只是简单说下欧拉公式的本质。

我们先看下公式：

可以看作是复平面上的一个向量，其到实轴的投影是 ，到虚轴的投影是 ，其中 便是向量与实轴的夹角。

而欧拉公式的直观理解就是在复平面上做圆周运动

随着 变化， 就变成圆周运动了。而前面的系数a则是圆的半径，当a=1的时候就是在单位圆上做圆周运动。

而且通过欧拉公式，我们可以得到三角函数的复数形式：

将上面的复变三角函数替换傅里叶级数中的三角函数得到:

我们令 中的n为-n

则得到：

所以可以看到n的范围变成了 到 ，并且每一项都有 ，于是我们可以得到一个漂亮的形式：

其中 分为3中情况：

我们将傅里叶级数之前的解带入上边

这里因为cos是偶函数，sin是奇函数所以：

可以惊奇的发现，三种情况的解是一样的。所以对于任意周期函数，我们都可以写成:

但其中的每一项是什么意思呢？

还记得之前说的 的本质吗？在圆上做圆周运动，那么 也是在做周期运动了。那 又是什么呢？

我们知道 ，所以我们可以把 看成是以 为单位的频率(正常来讲频率是 )。而系数 是就可以看成是几倍的基频，正数是逆时针运动，负数就是顺时针运动。在图形上的反应就是，频率越高，转的越快了

，但其最小公共周期是一样的。

1倍基频

那么系数 怎么理解呢？前面说过 的系数a是代表 运动的圆半径，这里 是复数是不是也能这样理解呢？其实粗糙来讲是可以这样理解的。

看个图，只管的理解下把

上图中红色的向量相对于蓝色的向量只是多了系数 ,所以红色向量运动的半径就是2刚好是复数 的模长乘以1，当然除此之外，红色向量的幅角也变大了些。这些都是因为复数的乘法性质---复数相乘表现为幅角相加，模长相乘。

这下，当有人和你说傅里叶变换是把时域变换到频域上，你应该就很容易理解是什么意思了。频域就是1倍，2倍，3倍的 ,而每个 都有自己的幅长 ,当把这些所有的 相加，就得到时域中的图像。

更加生动有趣的介绍可以参见 傅里叶分析之掐死教程 ，我这里是从数学的角度来介绍傅里叶变换。

目前该证明的都差不多了，还有最后一个任务，就是推广到非周期函数上。对于非周期函数，我们可以看成是周期无限远的函数，那也就是周期T变成 的时候傅里叶级数。随则T的变大 也就不断的减小，当T趋近于 的时候， 也由 变成了 ，那么很自然就需要对 做积分。

我们先看下

当T趋近于 的时候 我们可以得到：

将这些带入 傅里叶级数,并且T趋近于 ，就得到:

其中画红圈的地方就是傅里叶变换

而整个公式就是傅里叶逆变换，写成：

以上就是傅里叶变换的全部内容，如果你喜欢的话就点个赞。有时间的话，我会写些傅里叶变换的应用。

虽然是通信专业的学生，但是研究生阶段一直做着与通信不那么相关的图像视频的东西。工作后开始进入无线通信的领域，一边看协议的同时一边恶补已经还给老师的通信基础知识。

OFDM技术是4G和5G中都很重要的一个知识点。我们都知道OFDM是通过FFT来是实现的。那么FFT的基础又是DFT。DFT，FFT是令很多通信专业本科生头疼的课程DSP中的重要内容。从网上搜刮了一些相关资料，觉得李永乐老师的视频是最清晰明了的。这里记录一下。

1, 变换与反变换

在直角坐标系中有两个向量A和B，单看上去，这两个向量是两个图。我们也可以用数字的形式来表示这两个图。A对应（2，1），B对应（1，2）。这种使用图和数字两种形式来表示向量的方法就可以看作是一种简单的变换与反变换。见图1

2 标准正交基

同样我们还是直角坐标系中的两个向量，ex和ey 我们知道这两个向量有个特点就是他们之间相互内积为0，而他们对自己做内积则值为1我们就说ex和ey是标准正交基。见图2

3傅里叶级数

我们在大学的高等数学里面学过傅里叶级数。他是法国数学家傅里叶发现的。他发现任何周期函数都可以表示成正弦和余弦的级数和的形式。见图3那么我们就可以将一个周期函数分解成无数个正弦（余弦）和的形式。我们把这些和在三维中画出来。从不同的角度，看到的东西是不一样的。见图4从y轴的方向上看，它是一个周期函数，从z轴看过去，它是各个频率分量上的值（值的大小就是振幅的大小），这就是频域表达。再细心看会发现，每个频率上的起始点是不一样的，这就是相位的不同。这里面不仅引入了时域，频域的概念，而且引入了频率，振幅和相位的概念。

4欧拉公式

5傅里叶变换

傅里叶级数提出来之后，有好学的同学就要问了，那不是周期的函数我们怎么提取它的频率分量呢？这里我们就会用到标准正交基的概念了。根据正交基的定义，我们知道1，sinwt和coswt也是正交基。那么如果我们把这个非周期函数与正弦函数做积分将会得到什么样的结果呢？结果就会是含有w的项不为零，不含w的项为零。从而就得到了傅里叶变换。

6 DFT

学过DSP课程我们知道，时域和频域上的信号有这样的关系：

那么在实际应用中我没办法准确的表示出连续信号，但是可以准确的表示出离散信号。一对发送端和接收端都喜欢离散的信号，因为能够用数字准确的表示出来。但是我们日常生活中的信号一般并不是周期信号，聪明的人就会想到，我们可以把它离散化，再周期化，不就可以了吗。是的，就这么干。而实际上DFT也就是这么干的。

DFT的变换与反变换公式：这里不做详细推导，网上有很多推导过程。

但是当n很大时，计算量很大，这就引入了FFT。1965年,库利(cooley)和图基(Tukey)首先提出FFT算法对于N点DFT,仅需(N/2)log2N 次复数乘法运算例如N=1024=2的10次幂时，需要(1024/2)log2 2的10次幂 =51210=5120次。5120/1048576=488% ,速度提高20倍。