如何理解离散傅里叶变换（一）
——实数形式傅里叶变换
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本文作者：随煜而安 二零一五年五月二十三日
原创作者：July、dznlong
推荐阅读：
1.The Scientist and Engineer's Guide to Digital Signal Processing，By Steven W. Smith, Ph.D。http://www.dspguide.com/pdfbook.htm。
2.July大神博客 点击打开链接
3.dznlong大神博客 点击打开链接
4.高等数学/数学分析中关于傅里叶级数，三角函数正交系的部分内容
5.深入浅出的讲解傅里叶变换（个人感觉讲的一般，但是配图很形象帮助理解） 点击打开链接
说明：
I、本文中阐述的离散傅里叶变换方法是July、dznlong 两位根据此书：The Scientist and Engineer's Guide to Digital Signal Processing，By Steven W. Smith, Ph.D.而翻译而成的，此书地址：http://www.dspguide.com/pdfbook.htm。
II、同时，有相当一部分内容编辑整理自dznlong、July两位的博客，本文是根据两人文章的思路添加上一些个人的想法以及补充一些细节的成果。上面也贴出了其博客地址，向原创的作者表示致敬。
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
谈谈傅里叶变换
开始进入正题：
“关于傅立叶变换，无论是书本还是在网上可以很容易找到关于傅立叶变换的描述，但是大都是些故弄玄虚的文章，太过抽象，尽是一些让人看了就望而生畏的公式的罗列，让人很难能够从感性上得到理解”---dznlong，
那么，到底什么是傅里叶变换算法?傅里叶变换所涉及到的公式具体有多复杂列?这篇文章我借鉴两位大神的思路，并且先不列出一些复杂的公式，一步一步的引出我们要研究的东西，尽量做到通俗易懂。
傅里叶变换（Fourier transform）是一种线性的积分变换。因其基本思想首先由法国学者傅里叶系统地提出，所以以其名字来命名以示纪念。傅里叶变换就是一种变换而已，只是这种变换是从时间转换为频率的变化。
傅里叶变换的提出：
傅立叶是一位法国数学家和物理学家，原名是Jean Baptiste Joseph Fourier(1768-1830), Fourier于1807年在法国科学学会上发表了一篇论文，论文里描述运用正弦曲线来描述温度分布，论文里有个在当时具有争议性的决断：任何连续周期信号都可以由一组适当的正弦曲线组合而成。 当时审查这个论文拉格朗日坚决反对此论文的发表，而后在近50年的时间里，拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号，如在方波中出现非连续变化斜率。直到拉格朗日死后15年这个论文才被发表出来。
谁是对的呢？拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是，我们可以用正弦曲线来非常逼近地表示它，逼近到两种表示方法不存在能量差别，基于此，傅立叶是对的。
我们观察下图，直观的感受一下这个决断和傅里叶变换究竟在做怎样的一件事情。（图片来自：点击打开链接）
在这两几幅图中，分别代表了两个傅里叶变换。最前面黑色的线代表的就是要进行变换的时域上的函数f（t），它可以表示成后面所有彩色表示的正弦波叠加而成的总和。而后面依不同颜色排列而成的正弦波就是组合为f（t）的各个分量。这些正弦波按照频率从低到高从前向后排列开来，而每一个波的振幅都是不同的。一定有细心的读者发现了，在两个正弦波之间可能还有一条直线，那并不是分割线，而是振幅为0的正弦波！也就是说，为了组成特殊的曲线，有些正弦波成分是不需要的，或者说时域上的函数f（t）中不含有这种对应频率的分量。来看一个更为详细一些的图：
对于每个正弦波分量，如果我们只看它的频率和幅值。那么对于所有分量，就形成了一个以频率为自变量，幅值为因变量的频率域上的函数F（w），也就是频域图像。这时，一个时域——频域的映射就形成了。这个例子中我们可以看出，一个时域上的近似矩形波被分解成了不同频率分量的正弦波，反过来看，一些不同频率的正弦波叠加成了一个矩形波。要注意的是，在实际中通常是将时域的函数变换为不同频率的正弦波和余弦波的叠加，而不仅仅是一些正弦波的叠加，尽管这并没有什么不同，因为我们知道正余弦是可以互相表示的。
到此，在没有任何公式的情况下，我们也大概知晓了傅里叶变换在做怎样的一件事情。
傅立叶变换分类
根据原信号的不同类型，我们可以把傅立叶变换分为四种类别：
1、非周期性连续信号 傅立叶变换（Fourier Transform）
2、周期性连续信号 傅立叶级数(Fourier Series)
3、非周期性离散信号 离散时域傅立叶变换（Discrete Time Fourier Transform）
4、周期性离散信号 离散傅立叶变换(Discrete Fourier Transform)
现在我们要列出一些公式了，先观察即可，后面会做出详细的解释。
1.连续傅里叶变换
一般情况下，若“傅里叶变换”一词不加任何限定语，则指的是“连续傅里叶变换”。连续傅里叶变换将平方可积的函数f（t）表示成复指数函数的积分或级数形式。
这是将频率域的函数F(ω)表示为时间域的函数f（t）的积分形式。
连续傅里叶变换的逆变换 (inverse Fourier transform)为：
即将时间域的函数f（t）表示为频率域的函数F(ω)的积分。
2.傅里叶级数
连续形式的傅里叶变换其实是傅里叶级数 (Fourier series)的推广，因为积分其实是一种极限形式的求和算子而已。
对于周期函数，其傅里叶级数是存在的：
其中Fn为复幅度。对于实值函数，函数的傅里叶级数可以写成：
3.离散时域傅里叶变换
离散傅里叶变换是离散时间傅里叶变换（DTFT）的特例（有时作为后者的近似）。DTFT在时域上离散，在频域上则是周期的。DTFT可以被看作是傅里叶级数的逆变换。
4.离散傅里叶变换
离散傅里叶变换（DFT），是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再作变换。在实际应用中通常采用快速傅里叶变换以高效计算DFT。
为了在科学计算和数字信号处理等领域使用计算机进行傅里叶变换，必须将函数xn定义在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下，使用离散傅里叶变换（DFT），将函数xn表示为下面的求和形式：
其中Xk是傅里叶幅度。
现在我们已经把四种类型的傅里叶变换的公式给出了，直接看这些公式，就像很多教科书那样，我想大家跟我一样都是一头雾水。 下面是July、dznlong两位大神给出的一些更为直观的东西。
我们可以观察思考下上述傅立叶变换的4种变体的特点
下图是四种原信号图例（从上到下，依次是FT，FS，DTFT，DFT）：
对于计算机来说只有离散的和有限长度的数据才能被处理。所以首先可以肯定的是，对于计算机中的研究，我们的时域信号需要是离散的。对于我们要处理的输入信号，考虑如果是非周期性信号的普遍情况。我们需要用无穷多不同频率的正弦曲线来表示，这对于计算机来说也是不可能实现的。所以频率域上也要是离散的。所以基于上面的分析，我们下面重点讨论和理解的是离散傅立叶变换（DFT），因为只有它才能被计算机适用。
另外，每种傅立叶变换都分成实数和复数两种方法，对于实数方法是最好理解的，但是复数方法就相对复杂许多了，需要懂得有关复数的理论知识，不过，如果理解了实数离散傅立叶变换(real DFT)，再去理解复数傅立叶变换就更容易了，所以我们先把复数的傅立叶变换放到一边去，先来理解实数傅立叶变换，在后面我们会先讲讲关于复数的基本理论，然后在理解了实数傅立叶变换的基础上再来理解复数傅立叶变换。所以本文后面的重点是理解实数离散傅立叶变换(real DFT)。
截止到这里，我们简单阐述了傅里叶变换的一些基础知识和思想。后面，我们将从相对简单的实数傅里叶变换出发，试着去理解它。
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
实数离散傅立叶变换(real DFT)
首先，先来看一个关于实数离散傅立叶变换(Real DFT)的例子
通过这个例子，是想引出实数离散傅里叶变换在数学或者说程序中的表达方法，并且如果能理解实数离散傅里叶变换的原理就更好了
下图是一个实数原始离散信号图像：
这个信号的长度是16，于是可以把这个信号分解9个余弦波和9个正弦波（一个长度为N的信号可以分解成N/2+1个正余弦信号，这是为什么呢？我们稍后再讨论，也许结合下图你就能已经看出其中的原因。参看最后面的证明1）
结合下面的18个正余弦图,我想从计算机处理精度上就不难理解，一个长度为N的信号，最多只能有N/2+1个不同频率，再多的频率就超过了计算机所能所处理的精度范围），如下图：
9个余弦信号：
从左至右，从上到下，分别对应着频率k=0~8；
频率k=i就代表在长度为N的区间上存在着i个周期。k越大，周期越小。
9个正弦信号：
同样的，从左至右，从上到下，分别对应着频率k=0~8；
把以上所有信号相加即可得到原始信号，至于是怎么分别变换出9种不同频率信号的，我们也先不急，后面会说到，先看看对于以上的变换结果，在程序中又是该怎么表示的，我们可以看看下面这个示例图：
X[]数组又分两种，一种是表示余弦波的不同频率幅度值：Re X[]，另一种是表示正弦波的不同频率幅度值：Im X[]。
其中，Re是实数(Real)的意思，Im是虚数(Imagine)的意思，采用复数的表示方法把正余弦波组合起来进行表示，但这里我们不考虑复数的其它作用，只记住是一种组合方法而已，目的是为了便于表达（个人感觉这样表示是因为更为普遍和常用的复数形式傅里叶变换的存在，为了在形式上契合它）。还有，在后面我们会知道，复数形式的傅立叶变换频率域数组长度是N，而不是N/2+1。
到此，实数形式的离散傅里叶变换的表示方法及符号约定我们已经说清楚了，并且变换所做的实际工作我们也心里有数了。现在，补充上面欠着的关于“一个长度为N的信号可以分解成N/2+1个正余弦信号”的证明1。
这个问题解决了，不过到这里不知道有没有人和我有同样的疑问。为什么变换后的正弦余弦分量的频率取值都正好是整数？这个问题将在下面的学习中自然而然的明白。
实数形式离散傅里叶正变换（DFT）
由上面的讨论我们知道DFT是要将时域长度为N的离散序列x（n）变换为不同频率取值的正余弦分量，且频率K取值为0~N/2+1。其实我们正变换要做的是已知时域序列x（n），求频率域上的幅度值数组，也就是ReX[] 和ImX[]。
有三种完全不同的方法进行DFT：一种方法是通过联立方程进行求解, 从代数的角度看，要从N个已知值求N个未知值，需要N个联立方程，且N个联立方程必须是线性独立的，但这是这种方法计算量非常的大且极其复杂，所以很少被采用；第二种方法是利用信号的相关性（correlation）进行计算，这个是我们后面将要介绍的方法；第三种方法是快速傅立叶变换（FFT），这是一个非常具有创造性和革命性的的方法，因为它大大提高了运算速度，使得傅立叶变换能够在计算机中被广泛应用，但这种算法是根据复数形式的傅立叶变换来实现的，它把N个点的信号分解成长度为N的频域，这个跟我们现在所进行的实域DFT变换不一样，而且这种方法也较难理解，这里我们先不去理解，等先理解了复数DFT后，再来看一下FFT。有一点很重要，那就是这三种方法所得的变换结果是一样的，经过实践证明，当频域长度为32时，利用相关性方法进行计算效率最好，否则FFT算法效率较高。现在就让我们来看一下相关性算法。--July
利用第一种方法、信号的相关性(correlation)可以从噪声背景中检测出已知的信号，我们也可以利用这个方法检测信号波中是否含有某个频率的信号波：把一个待检测信号波乘以另一个信号波，得到一个新的信号波，再把这个新的信号波所有的点进行相加，从相加的结果就可以判断出这两个信号的相似程度。如下图：
上面a和 b两个图是待检测信号波，图a很明显可以看出是个3个周期的正弦信号波，图b的信号波则看不出是否含有正弦或余弦信号，图c和d都是个3个周期的正弦信号波，图e和f分别是a、b两图跟c、d两图相乘后的结果，图e所有点的平均值是0.5，说明信号a含有振幅为1的正弦信号c，但图f所有点的平均值是0，则说明信号b不含有信号d。这个就是通过信号相关性来检测是否含有某个信号的方法。
第二种方法：相应地，我也可以通过把输入信号和每一种频率的正余弦信号进行相乘（关联操作），从而得到原始信号与每种频率的关联程度（即总和大小），这个结果便是我们所要的傅立叶变换结果，下面两个等式便是我们所要的计算方法：
第二个式子中加了个负号，是为了保持复数形式的一致，前面我们知道在计算时又加了个负号，所以这只是个形式的问题，并没有实际意义，你也可以把负号去掉，并在计算
这里有一点必须明白一个正交的概念：两个函数相乘，如果结果中的每个点的总和为0，则可认为这两个函数为正交函数。要确保关联性算法是正确的，则必须使得跟原始信号相乘的信号的函数形式是正交的，我们知道所有的正弦或余弦函数是正交的，这一点我们可以通过简单的高数知识就可以证明它，所以我们可以通过关联的方法把原始信号分离出正余弦信号。也就是说，一个带有多个频率分量的时域函数f（t）乘以某个频率的正交基的积分，其实就等于函数中对应这个频率的分量与这个频率正交基的积分，也就求出了函数与这个频率的“关联度”。当然，其它的正交函数也是存在的，如：方波、三角波等形式的脉冲信号，所以原始信号也可被分解成这些信号，但这只是说可以这样做，却是没有用的。
实数形式离散傅里叶逆变换——合成运算方法(Real Inverse DFT)
DFT合成等式（合成原始时间信号，频率-->时间，逆向变换）：
如果有学过傅立叶级数，对这个等式就会有似曾相识的感觉，不错！这个等式跟傅立叶级数是非常相似的：
当然，差别是肯定是存在的，因为这两个等式是在两个不同条件下运用的，至于怎么证明DFT合成公式，这个我想需要非常强的高等数学理论知识了，这是研究数学的人的工作，对于普通应用者就不需要如此的追根究底了，但是傅立叶级数是好理解的，我们起码可以从傅立叶级数公式中看出DFT合成公式的合理性。
DFT合成等式中的Im X[k]和Re X[k]跟之前提到的Im X[k]和Re X[k]是不一样的，下面是转换方法（关于此公式的解释，见下文）:
但k等于0和N/2时,实数部分的计算要用下面的等式:
上面四个式中的N是时域中点的总数，k是从0到N/2的序号。
为什么要这样进行转换呢？这个可以从频谱密度(spectral density)得到理解，如下图就是个频谱图：
这是一个频谱图，横坐标表示频率大小，纵坐标表示振幅大小，原始信号长度为N（这里是32），经DFT转换后得到的17个频率的频谱，频谱密度表示每单位带宽中为多大的振幅，那么带宽是怎么计算出来的呢？看上图，除了头尾两个，其余点的所占的宽度是2/N，这个宽度便是每个点的带宽，头尾两个点的带宽是1/N,而Im X[k]和Re X[k]表示的是频谱密度，即每一个单位带宽的振幅大小，但
到此为止，我们对傅立叶变换便有了感性的认识了。但是，这只是在实域上的离散傅立叶变换，其中虽然也用到了复数的形式，但那只是个替代的形式，并无实际意义，现实中一般使用的是复数形式的离散傅立叶变换，且快速傅立叶变换是根据复数离散傅立叶变换来设计算法的。随着作者之后的学习，再总结出后面的博文。
联系客服
