完整版教程下载地址：http://www.armbbs.cn/forum.php?mod=viewthread&tid=94547
第24章 DSP变换运算-傅里叶变换
本章节开始进入此教程最重要的知识点之一傅里叶变换。关于傅里叶变换，本章主要是把傅里叶相关的基础知识进行必要的介绍，没有这些基础知识的话，后面学习FFT（快速傅里叶变换）时会比较困难。本章节的内容主要来自百度百科，wiki百科以及网络和书籍中整理的一些资料。
24.1 初学者重要提示
24.2 傅里叶人物简介
24.3 傅里叶变换概念
24.4 傅里叶的特殊形式
24.5 傅里叶变换相关知识
24.6 总结
24.1 初学者重要提示
- 为大家推荐西电的*精品课程信号与系统，含课堂视频，书籍和课堂PPThttp://www.armbbs.cn/forum.php?mod=viewthread&tid=94886 。
- 非常好的DSP基础知识普及书籍：http://www.armbbs.cn/forum.php?mod=viewthread&tid=97312 。
- 通过本章学习要搞清楚为什么计算机要选择DFT作为运算基础，而不是DTFT或其它。
- 通过傅里叶的学习，我们知道任何波形都可以使用正弦波无限逼近，但是为什么选择的是正弦波，而不是三角波或者方波，本章也进行了解释。
24.2 傅里叶人物简介
学习傅里叶变换前，一定要对傅里叶这个人有所了解，这样更加有利于学习他提出的理论。
让·巴普蒂斯·约瑟夫·傅立叶（Jean Baptiste Joseph Fourier，1768 –1830），法国著名数学家、物理学家，1817年当选为科学院院士，1822年任该院终身秘书，后又任法兰西学院终身秘书和理工科大学校务委员会主席，主要贡献是在研究热的传播时创立了一套数学理论。
傅立叶生于法国中部欧塞尔（Auxerre）一个裁缝家庭，8岁时沦为孤儿，就读于地方军校，1795年任巴黎综合工科大学助教，1798年随拿破仑军队远征埃及，受到拿破仑器重，回国后被任命为格伦诺布尔省省长。
傅立叶早在1807年就写成关于热传导的基本论文《热的传播》，向巴黎科学院呈交，但经拉格朗日、拉普拉斯和勒让德审阅后被科学院拒绝，1811年又提交了经修改的论文，该文获科学院大奖，却未正式发表。傅立叶在论文中推导出著名的热传导方程 ，并在求解该方程时发现解函数可以由三角函数构成的级数形式表示，从而提出任一函数都可以展成三角函数的无穷级数。傅立叶级数（即三角级数）、傅立叶分析等理论均由此创始。
傅立叶由于对传热理论的贡献于1817年当选为巴黎科学院院士。
1822年，傅立叶终于出版了专著《热的解析理论》（Theorieanalytique de la Chaleur ，Didot ，Paris，1822）。这部经典著作将欧拉、伯努利等人在一些特殊情形下应用的三角级数方法发展成内容丰富的一般理论，三角级数后来就以傅立叶的名字命名。傅立叶应用三角级数求解热传导方程，为了处理无穷区域的热传导问题又导出了当前所称的“傅立叶积分”，这一切都极大地推动了偏微分方程边值问题的研究。然而傅立叶的工作意义远不止此，它迫使人们对函数概念作修正、推广，特别是引起了对不连续函数的探讨；三角级数收敛性问题更刺激了集合论的诞生。因此，《热的解析理论》影响了整个19世纪分析严格化的进程。傅立叶1822年成为科学院终身秘书。
24.3 傅里叶变换概念
关于傅里叶变换的概念和公式方面的内容需要大家重新拿起当年的《信号与系统》课本温习下，不过在温习课本之前强烈建议看下这个帖子：http://zhuanlan.zhihu.com/wille/19763358（傅里叶分析之掐死教程（完整版））。这个帖子非常适合没有傅里叶变换方面知识的同学看，如果有傅里叶方面的基础认识的话，看完这个帖子，你的认识会更加的深刻。
这里我只把傅里叶简单的定义贴上进行说明。傅立叶变换是一种分析信号的方法，它可分析信号的成分，也可用这些成分合成信号。许多波形可作为信号的成分，比如正弦波、方波、锯齿波等，傅立叶变换用正弦波作为信号的成分。
假设f(t)是t的周期函数，如果t满足狄里赫莱条件：在一个周期内具有有限个间断点，且在这些间断点上，函数是有限值；在一个周期内具有有限个极值点；绝对可积。则有下图①式成立。称为积分运算f(t)的傅立叶变换，②式的积分运算叫做F(ω)的傅立叶逆变换。F(ω)叫做f(t)的像函数，f(t)叫做F(ω)的像原函数。F(ω)是f(t)的像。f(t)是F(ω)原像。
24.4 傅里叶的特殊变换形式
下面要讲到的这几种概念很重要，初学时不要搞混淆了。
上图做的非常好，从上到下依次是：
24.4.1 连续傅里叶变换（Fourier Transform）
一般情况下，若“傅里叶变换”一词的前面未加任何限定语，则指的是连续傅里叶变换。连续傅里叶变换将平方可积的函数表示成复指数函数的积分形式：
上式其实表示的是连续傅里叶变换的逆变换，即将时间域的函数表示为频率域的函数F(ω)的积分。反过来，其正变换恰好是将频率域的函数F(ω)表示为时间域的函数f(t)的积分形式。一般可称函数f(t)为原函数，而称函数F(ω)为傅里叶变换的像函数，原函数和像函数构成一个傅里叶变换对（transform pair）。
当f(t)为奇函数（或偶函数）时，其余弦（或正弦）分量为零，而可以称这时的变换为余弦变换（或正弦变换）。
24.4.2 傅里叶级数（Fourier series）
连续形式的傅里叶变换其实是傅里叶级数的推广，因为积分其实是一种极限形式的求和算子而已。对于周期函数，它的傅里叶级数（Fourier series）表示被定义为：
其中T为函数的周期，Fn为傅里叶展开系数，它们等于
对于实值函数，函数的傅里叶级数可以写成：
其中an和bn是实频率分量的振幅。
24.4.3 离散时间傅里叶变换（Discrete-time Fourier transform）
离散时间傅里叶变换（discrete-time Fourier transform, DTFT）针对的是定义域为Z的数列。设为某一数列，则其DTFT被定义为
相应的逆变换为
DTFT在时域上离散，在频域上则是周期的，它一般用来对离散时间信号进行频谱分析。DTFT可以被看作是傅里叶级数的逆。
24.4.4 离散傅里叶变换（Discrete Fourier transform）
为了在科学计算和数字信号处理等领域使用计算机进行傅里叶变换，必须将函数定义在离散点上而非连续域内，且须满足有限性或周期性条件。这种情况下，序列的离散傅里叶变换（discrete Fourier transform, DFT）为
其逆变换为
直接使用DFT的定义计算的复杂度为，而快速傅里叶变换（fast Fourier transform, FFT）可以将复杂度改进为
。计算复杂度的降低以及数字电路计算能力的发展使得DFT成为在信号处理领域十分实用且重要的方法。
24.4.5 傅里叶变换家族
下表列出了傅里叶变换家族的成员。容易发现，函数在时（频）域的离散对应于其像函数在频（时）域的周期性，反之连续则意味着在对应域的信号的非周期性
24.5 傅里叶变换相关知识（重要）
24.5.1 傅里叶变换的提出
傅里叶是一位法国数学家和物理学家的名字，英语原名是Jean Baptiste Joseph Fourier(1768-1830), Fourier对热传递很感兴趣，于1807年在法国科学学会上发表了一篇论文，运用正弦曲线来描述温度分布，论文里有个在当时具有争议性的决断：任何连续周期信号可以由一组适当的正弦曲线组合而成。当时审查这个论文的人，其中有两位是历史上著名的数学家拉格朗日(Joseph Louis Lagrange, 1736-1813)和拉普拉斯(Pierre Simon de Laplace, 1749-1827)，当拉普拉斯和其它审查者投票通过并要发表这个论文时，拉格朗日坚决反对，在他此后生命的六年中，拉格朗日坚持认为傅里叶的方法无法表示带有棱角的信号，如在方波中出现非连续变化斜率。法国科学学会屈服于拉格朗日的威望，拒绝了傅里叶的工作，幸运的是，傅里叶还有其它事情可忙，他参加了政治运动，随拿破仑远征埃及，法国大革命后因会被推上断头台而一直在逃避。直到拉格朗日死后15年这个论文才被发表出来。
拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是，我们可以用正弦曲线来非常逼近地表示它，逼近到两种表示方法不存在能量差别，基于此，傅里叶是对的。
用正弦曲线来代替原来的曲线而不用方波或三角波来表示的原因在于，分解信号的方法是无穷的，但分解信号的目的是为了更加简单地处理原来的信号。用正余弦来表示原信号会更加简单，因为正余弦拥有原信号所不具有的性质：正弦曲线保真度。一个正弦曲线信号输入后，输出的仍是正弦曲线，只有幅度和相位可能发生变化，但是频率和波的形状仍是一样的。且只有正弦曲线才拥有这样的性质，正因如此我们才不用方波或三角波来表示。
24.5.2 傅里叶变换分类
根据原信号的不同类型，我们可以把傅里叶变换分为四种类别：
这四种傅里叶变换都是针对正无穷大和负无穷大的信号，即信号的的长度是无穷大的，我们知道这对于计算机处理来说是不可能的，那么有没有针对长度有限的傅里叶变换呢？没有。因为正余弦波被定义成从负无穷大到正无穷大，我们无法把一个长度无限的信号组合成长度有限的信号。面对这种困难，方法是把长度有限的信号表示成长度无限的信号，可以把信号无限地从左右进行延伸，延伸的部分用零来表示，这样，这个信号就可以被看成是非周期性离解信号，我们就可以用到离散时间傅里叶变换的方法。还有，也可以把信号用复制的方法进行延伸，这样信号就变成了周期性离散信号，这时我们就可以用离散傅里叶变换方法进行变换。这里我们要学的是离散信号，对于连续信号我们不作讨论，因为计算机只能处理离散的数值信号，我们的最终目的是运用计算机来处理信号的。
但是对于非周期性的信号，我们需要用无穷多不同频率的正弦曲线来表示，这对于计算机来说是不可能实现的。所以对于离散信号的变换只有离散傅里叶变换（DFT）才能被适用，对于计算机来说只有离散的和有限长度的数据才能被处理，对于其它的变换类型只有在数学演算中才能用到，在计算机面前我们只能用DFT方法，后面我们要理解的也正是DFT方法。这里要理解的是我们使用周期性的信号目的是为了能够用数学方法来解决问题，至于考虑周期性信号是从哪里得到或怎样得到是无意义的。
每种傅里叶变换都分成实数和复数两种方法，对于实数方法是最好理解的，但是复数方法就相对复杂许多了，需要懂得有关复数的理论知识，不过，如果理解了实数离散傅里叶变换(real DFT)，再去理解复数傅里叶就更容易了。
还有，这里我们所要说的变换(transform)虽然是数学意义上的变换，但跟函数变换是不同的，函数变换是符合一 一映射准则的，对于离散数字信号处理（DSP），有许多的变换：傅里叶变换、拉普拉斯变换、Z变换、希尔伯特变换、离散余弦变换等，这些都扩展了函数变换的定义，允许输入和输出有多种的值，简单地说变换就是把一堆的数据变成另一堆数据的方法。
24.5.3 傅里叶变换的意义
傅里叶变换是数字信号处理领域一种很重要的算法。要知道傅里叶变换算法的意义，首先要了解傅里叶原理的意义。傅里叶原理表明：任何连续测量的时序或信号，都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅里叶变换算法利用直接测量到的原始信号，以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。
和傅里叶变换算法对应的是傅里叶逆变换算法。该逆变换从本质上说也是一种累加处理，这样就可以将单独改变的正弦波信号转换成一个信号。因此，可以说，傅里叶变换将原来难以处理的时域信号转换成了易于分析的频域信号（信号的频谱），可以利用一些工具对这些频域信号进行处理、加工。最后还可以利用傅里叶逆变换将这些频域信号转换成时域信号。
从现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。
在数学领域，尽管最初傅里叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。"任意"的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式。
傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。
24.6 总结
通过本章节，一定要搞明白傅里叶变换，傅里叶级数，离散时间傅里叶变换和离散傅里叶变换直接的关系，特别是24.4.2小节的知识点。