《从头到尾彻底理解傅里叶变换算法》由会员分享，可在线阅读，更多相关《从头到尾彻底理解傅里叶变换算法（23页珍藏版）》请在金锄头文库上搜索。
1、.从头到尾彻底理解傅里叶变换算法、上从头到尾彻底理解傅里叶变换算法、上前言第一部分、 DFT第一章、傅立叶变换的由来第二章、实数形式离散傅立叶变换Real DFT从头到尾彻底理解傅里叶变换算法、下第三章、复数第四章、复数形式离散傅立叶变换前言：关于傅立叶变换,无论是书本还是在网上可以很容易找到关于傅立叶变换的描述,但是大都是些故弄玄虚的文章,太过抽象,尽是一些让人看了就望而生畏的公式的罗列,让人很难能够从感性上得到理解-dznlong,那么,到底什么是傅里叶变换算法列?傅里叶变换所涉及到的公式具体有多复杂列?傅里叶变换Fourier transform是一种线性的积分变换。因其基本思想首先由法
2、国学者傅里叶系统地提出,所以以其名字来命名以示纪念。哦,傅里叶变换原来就是一种变换而已,只是这种变换是从时间转换为频率的变化。这下,你就知道了,傅里叶就是一种变换,一种什么变换列?就是一种从时间到频率的变化或其相互转化。ok,咱们再来总体了解下傅里叶变换,让各位对其有个总体大概的印象,也顺便看看傅里叶变换所涉及到的公式,究竟有多复杂：以下就是傅里叶变换的4种变体摘自,维基百科连续傅里叶变换一般情况下,若傅里叶变换一词不加任何限定语,则指的是连续傅里叶变换。连续傅里叶变换将平方可积的函数ft表示成复指数函数的积分或级数形式。这是将频率域的函数F表示为时间域的函数ft的积分形式。连续傅里叶变换的逆
3、变换 为：即将时间域的函数ft表示为频率域的函数F的积分。一般可称函数ft为原函数,而称函数F为傅里叶变换的像函数,原函数和像函数构成一个傅里叶变换对transform pair。除此之外,还有其它型式的变换对,以下两种型式亦常被使用。在通信或是信号处理方面,常以来代换,而形成新的变换对:或者是因系数重分配而得到新的变换对：一种对连续傅里叶变换的推广称为分数傅里叶变换Fractional Fourier Transform。分数傅里叶变换指的就是傅里叶变换的广义化。分数傅里叶变换的物理意义即做傅里叶变换 a 次,其中 a 不一定要为整数；而做了分数傅里叶变换之后,信号或输入函数便会出现在介于时
4、域与频域之间的分数域。当ft为偶函数或奇函数时,其正弦或余弦分量将消亡,而可以称这时的变换为余弦变换cosine transform或正弦变换sine transform.另一个值得注意的性质是,当ft为纯实函数时,F = F*成立.傅里叶级数连续形式的傅里叶变换其实是傅里叶级数 的推广,因为积分其实是一种极限形式的求和算子而已。对于周期函数,其傅里叶级数是存在的：其中Fn为复幅度。对于实值函数,函数的傅里叶级数可以写成：其中an和bn是实频率分量的幅度。离散时域傅里叶变换离散傅里叶变换是离散时间傅里叶变换DTFT的特例有时作为后者的近似。DTFT在时域上离散,在频域上则是周期的。DTFT可以
5、被看作是傅里叶级数的逆变换。离散傅里叶变换 离散傅里叶变换DFT,是连续傅里叶变换在时域和频域上都离散的形式,将时域信号的采样变换为在离散时间傅里叶变换DTFT频域的采样。在形式上,变换两端时域和频域上的序列是有限长的,而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT,也应当将其看作经过周期延拓成为周期信号再作变换。在实际应用中通常采用快速傅里叶变换以高效计算DFT。 为了在科学计算和数字信号处理等领域使用计算机进行傅里叶变换,必须将函数xn定义在离散点而非连续域内,且须满足有限性或周期性条件。这种情况下,使用离散傅里叶变换DFT,将函数xn表示为下面的求
6、和形式：其中Xk是傅里叶幅度。直接使用这个公式计算的计算复杂度为On*n,而快速傅里叶变换FFT可以将复杂度改进为On*lgn。后面会具体阐述FFT是如何将复杂度降为On*lgn的。计算复杂度的降低以及数字电路计算能力的发展使得DFT成为在信号处理领域十分实用且重要的方法。 下面,比较下上述傅立叶变换的4种变体,如上,容易发现：函数在时频域的离散对应于其像函数在频时域的周期性。反之连续则意味着在对应域的信号的非周期性。也就是说,时间上的离散性对应着频率上的周期性。同时,注意,离散时间傅里叶变换,时间离散,频率不离散,它在频域依然是连续的。 如果,读到此,你不甚明白,大没关系,不必纠结于以上4种
7、变体,继续往下看,你自会豁然开朗。有什么问题,也恳请提出,或者批评指正ok, 本文,接下来,由傅里叶变换入手,后重点阐述离散傅里叶变换、快速傅里叶算法,到最后彻底实现FFT算法,全篇力求通俗易懂、阅读顺畅,教你从头到尾彻底理解傅里叶变换算法。由于傅里叶变换,也称傅立叶变换,下文所称为傅立叶变换,同一个变换,不同叫法,读者不必感到奇怪。第一部分、DFT第一章、傅立叶变换的由来 要理解傅立叶变换,先得知道傅立叶变换是怎么变换的,当然,也需要一定的高等数学基础,最基本的是级数变换,其中傅立叶级数变换是傅立叶变换的基础公式。一、傅立叶变换的提出傅立叶是一位法国数学家和物理学家,原名是Jean Bapt
8、iste Joseph Fourier, Fourier于1807年在法国科学学会上发表了一篇论文,论文里描述运用正弦曲线来描述温度分布,论文里有个在当时具有争议性的决断：任何连续周期信号都可以由一组适当的正弦曲线组合而成。 当时审查这个论文拉格朗日坚决反对此论文的发表,而后在近50年的时间里,拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号,如在方波中出现非连续变化斜率。直到拉格朗日死后15年这个论文才被发表出来。 谁是对的呢？拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是,我们可以用正弦曲线来非常逼近地表示它,逼近到两种表示方法不存在能量差别,基于此,傅立叶是对的。 为什么我
9、们要用正弦曲线来代替原来的曲线呢？如我们也还可以用方波或三角波来代替呀,分解信号的方法是无穷多的,但分解信号的目的是为了更加简单地处理原来的信号。 用正余弦来表示原信号会更加简单,因为正余弦拥有原信号所不具有的性质：正弦曲线保真度。一个正余弦曲线信号输入后,输出的仍是正余弦曲线,只有幅度和相位可能发生变化,但是频率和波的形状仍是一样的。且只有正余弦曲线才拥有这样的性质,正因如此我们才不用方波或三角波来表示。二、傅立叶变换分类 根据原信号的不同类型,我们可以把傅立叶变换分为四种类别：1、非周期性连续信号 傅立叶变换Fourier Transform 2、周期性连续信号 傅立叶级数 3、非周期性离
10、散信号 离散时域傅立叶变换Discrete Time Fourier Transform 4、周期性离散信号 离散傅立叶变换 下图是四种原信号图例从上到下,依次是FT,FS,DTFT,DFT： 这四种傅立叶变换都是针对正无穷大和负无穷大的信号,即信号的的长度是无穷大的,我们知道这对于计算机处理来说是不可能的,那么有没有针对长度有限的傅立叶变换呢？没有。因为正余弦波被定义成从负无穷小到正无穷大,我们无法把一个长度无限的信号组合成长度有限的信号。 面对这种困难,方法是：把长度有限的信号表示成长度无限的信号。如,可以把信号无限地从左右进行延伸,延伸的部分用零来表示,这样,这个信号就可以被看成是非周期
11、性离散信号,我们可以用到离散时域傅立叶变换DTFT的方法。也可以把信号用复制的方法进行延伸,这样信号就变成了周期性离散信号,这时我们就可以用离散傅立叶变换方法DFT进行变换。本章我们要讲的是离散信号,对于连续信号我们不作讨论,因为计算机只能处理离散的数值信号,我们的最终目的是运用计算机来处理信号的。 但是对于非周期性的信号,我们需要用无穷多不同频率的正弦曲线来表示,这对于计算机来说是不可能实现的。所以对于离散信号的变换只有离散傅立叶变换DFT才能被适用,对于计算机来说只有离散的和有限长度的数据才能被处理,对于其它的变换类型只有在数学演算中才能用到,在计算机面前我们只能用DFT方法,后面我们要理
12、解的也正是DFT方法。 这里要理解的是我们使用周期性的信号目的是为了能够用数学方法来解决问题,至于考虑周期性信号是从哪里得到或怎样得到是无意义的。 每种傅立叶变换都分成实数和复数两种方法,对于实数方法是最好理解的,但是复数方法就相对复杂许多了,需要懂得有关复数的理论知识,不过,如果理解了实数离散傅立叶变换,再去理解复数傅立叶变换就更容易了,所以我们先把复数的傅立叶变换放到一边去,先来理解实数傅立叶变换,在后面我们会先讲讲关于复数的基本理论,然后在理解了实数傅立叶变换的基础上再来理解复数傅立叶变换。 还有,这里我们所要说的变换虽然是数学意义上的变换,但跟函数变换是不同的,函数变换是符合一一映射准
13、则的,对于离散数字信号处理DSP,有许多的变换：傅立叶变换、拉普拉斯变换、Z变换、希尔伯特变换、离散余弦变换等,这些都扩展了函数变换的定义,允许输入和输出有多种的值,简单地说变换就是把一堆的数据变成另一堆的数据的方法。三、一个关于实数离散傅立叶变换的例子 先来看一个变换实例,下图是一个原始信号图像： 这个信号的长度是16,于是可以把这个信号分解9个余弦波和9个正弦波一个长度为N的信号可以分解成N/2+1个正余弦信号,这是为什么呢？结合下面的18个正余弦图,我想从计算机处理精度上就不难理解,一个长度为N的信号,最多只能有N/2+1个不同频率,再多的频率就超过了计算机所能所处理的精度范围,如下图：
14、 9个余弦信号：9个正弦信号： 把以上所有信号相加即可得到原始信号,至于是怎么分别变换出9种不同频率信号的,我们先不急,先看看对于以上的变换结果,在程序中又是该怎么表示的,我们可以看看下面这个示例图： 上图中左边表示时域中的信号,右边是频域信号表示方法,从左向右,-,表示正向转换,从右向左,-,表示逆向转换,用小写x表示信号在每个时间点上的幅度值数组, 用大写X表示每种频率的副度值数组即时间x-频率X, 因为有N/2+1种频率,所以该数组长度为N/2+1, X数组又分两种,一种是表示余弦波的不同频率幅度值：Re X,另一种是表示正弦波的不同频率幅度值：Im X, Re是实数的意思,Im是虚数的意思,采用复数的表示方法把正余弦波组合起来进行表示,但这里我们不考虑复数的其它作用,只记住是一种组合方法而已,目的是为了便于表达在后面我们会知道,复数形式的傅立叶变换长度是N,而不是N/2+1。如此,再回过头去,看上面的正余弦各9种频率的变化,相信,问题不大了。第二章、实数形式离
