《傅里叶变换算法详细介绍要点.pdf》由会员分享，可在线阅读，更多相关《傅里叶变换算法详细介绍要点.pdf（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、从头到尾彻底理解傅里叶变换算法、上 前言 第一部分、DFT 第一章、傅立叶变换的由来 第二章、实数形式离散傅立叶变换(Real DFT)从头到尾彻底理解傅里叶变换算法、下 第三章、复数 第四章、复数形式离散傅立叶变换/*/这一片的傅里叶变换算法，讲解透彻，希望对大家会有所帮助。感谢原作者们（July、dznlong）的精心编写。未*前言：关于傅立叶变换，无论是书本还是在网上可以很容易找到关于傅立叶变换的描述，但是大 都是些故弄玄虚的文章，太过抽象，尽是一些让人看了就望而生畏的公式的罗列，让人很难 能够从感性上得到理解”-dznlong，那么，到底什么是傅里叶变换算法列？傅里叶变换所涉及到的公式
2、具体有多复杂列？傅里叶变换(Fourier transform)是一种线性的积分变换。因其基本思想首先由法国学者傅 里叶系统地提出，所以以其名字来命名以示纪念。哦，傅里叶变换原来就是一种变换而已，只是这种变换是从时间转换为频率的变化。这下,你就知道了，傅里叶就是一种变换，一种什么变换列？就是一种从时间到频率的变化或其相 互转化。ok，咱们再来总体了解下傅里叶变换，让各位对其有个总体大概的印象，也顺便看看傅里 叶变换所涉及到的公式，究竟有多复杂：以下就是傅里叶变换的 4种变体(摘自，维基百科)连续傅里叶变换 一般情况下，若 傅里叶变换”一词不加任何限定语，则指的是 连续傅里叶变换”。连续傅 里叶
3、变换将平方可积的函数 f(t)表示成复指数函数的积分或级数形式。OO 00 这是将频率域的函数 F(3表示为时间域的函数 f(t)的积分形式。连续傅里叶变换的逆变换(inverse Fourier transform)为：即将时间域的函数f(t)表示为频率域的函数 F(3)的积分。一般可称函数f(t)为原函数，而称函数 F(3为傅里叶变换的像函数，原函数和像函数构 成一个傅里叶变换对(transform pair)。除此之外，还有其它型式的变换对，以下两种型式亦常被使用。在通信或是信号处理方面，f=二 常以 2 7T来代换，而形成新的变换对：3C X(f)=/x(t)3C C=/X(刀严胡 o
4、c 或者是因系数重分配而得到新的变换对:oc F()=3C-g f(皆刃F3)=命 f F(w)严 ds oo f()=TF(s)=/oo 一种对连续傅里叶变换的推广称为分数傅里叶变换(Fractional Fourier Transform)。分数 傅里叶变换(fractional Fourier transform,FRFT)指的就是傅里叶变换(Fourier transform,FT)的广义化。分数傅里叶变换的物理意义即做傅里叶变换 a次，其中a不一定要为整数；而做了分数 傅里叶变换之后，信号或输入函数便会出现在介于时域(time domain)与频域(frequency domain)
5、之间的分数域(fractional domain)。当f(t)为偶函数(或奇函数)时，其正弦(或余弦)分量将消亡，而可以称这时的变换为 余弦变换(cosine transform)或正弦变换(sine transform).另一个值得注意的性质是，当 f(t)为纯实函数时，F(-3)=F*(3成立 傅里叶级数 连续形式的傅里叶变换其实是傅里叶级数(Fourier series)的推广，因为积分其实是一种 极限形式的求和算子而已。对于周期函数，其傅里叶级数是存在的：他)=凡严 并=X 其中Fn为复幅度。对于实值函数，函数的傅里叶级数可以写成：f(龙)=血+”%cos(nx)+bn sin(nT)
6、其中an和bn是实频率分量的幅度。离散时域傅里叶变换 离散傅里叶变换是离散时间傅里叶变换(DTFT)的特例(有时作为后者的近似)。DTFT 在时域上离散，在频域上则是周期的。DTFT可以被看作是傅里叶级数的逆变换。离散傅里叶变换 离散傅里叶变换（DFT），是连续傅里叶变换在时域和频域上都离散的形式，将时域信号 的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。在形式上，变换两端（时域和 频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作 DFT，也应当将其看作经过周期延拓成为周期信号再作变换。在实际应用中通常采用快速傅里叶变换以高效
7、计算 DFT o 为了在科学计算和数字信号处理等领域使用计算机进行傅里叶变换，必须将函数 xn定义 在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下，使用离散傅里叶变换（DFT）,将函数xn表示为下面的求和形式：xn 丫；甘kt，zi=0、丁 N 1 fc=O 其中Xk是傅里叶幅度。直接使用这个公式计算的计算复杂度为 O（n*n）,而快速傅里叶 变换（FFT）可以将复杂度改进为 O（n*lgn）。（后面会具体阐述 FFT是如何将复杂度降 为O（n*lgn）的。）计算复杂度的降低以及数字电路计算能力的发展使得 DFT成为在信号 处理领域十分实用且重要的方法。下面，比较下上述傅立叶变换
8、的 4种变体，变换 时间 频率 连续傅里叶变换 逹续，非周期性 连续，非周期性 傅里叶级数 连续，周期性 离散，非周期性 离散时间傅里叶变换 离散.非周期性 妙，周期性 离散傅里叶变换 离散，周期性 离散，周期性 如上，容易发现：函数在时（频）域的离散对应于其像函数在频（时）域的周期性。反之 连续则意味着在对应域的信号的非周期性。也就是说，时间上的离散性对应着频率上的周期 性。同时，注意，离散时间傅里叶变换，时间离散，频率不离散，它在频域依然是连续的。如果，读到此，你不甚明白，大没关系，不必纠结于以上 4种变体，继续往下看，你自 会豁然开朗。（有什么问题，也恳请提出，或者批评指正）ok,本文，
9、接下来，由傅里叶变换入手，后重点阐述离散傅里叶变换、快速傅里叶算法，到最后彻底实现 FFT算法，全篇力求通俗易懂、阅读顺畅，教你从头到尾彻底理解傅里叶 变换算法。由于傅里叶变换，也称傅立叶变换，下文所称为 傅立叶变换，同一个变换，不同 叫法，读者不必感到奇怪。第一部分、DFT 第一章、傅立叶变换的由来 要理解傅立叶变换，先得知道傅立叶变换是怎么变换的，当然，也需要一定的高等数学 基础，最基本的是级数变换，其中傅立叶级数变换是傅立叶变换的基础公式。一、傅立叶变换的提出 傅立叶是一位法国数学家和物理学家，原名是Jean Baptiste Joseph Fourier(1768-1830),Four
10、ier于1807年在法国科学学会上发表了一篇论文，论文里描述运用正弦曲线来描述温 度分布，论文里有个在当时具有争议性的决断：任何连续周期信号都可以由一组适当的正弦 曲线组合而成。当时审查这个论文拉格朗日坚决反对此论文的发表，而后在近50年的时间里，拉格朗日 坚持认为傅立叶的方法无法表示带有棱角的信号，如在方波中出现非连续变化斜率。直到拉 格朗日死后15年这个论文才被发表出来。谁是对的呢？拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是，我们 可以用正弦曲线来非常逼近地表示它，逼近到两种表示方法不存在能量差别，基于此，傅立 叶是对的。为什么我们要用正弦曲线来代替原来的曲线呢？如我们也还
11、可以用方波或三角波来代替 呀，分解信号的方法是无穷多的，但分解信号的目的是为了更加简单地处理原来的信号。用正余弦来表示原信号会更加简单，因为正余弦拥有原信号所不具有的性质：正弦曲线 保真度。一个正余弦曲线信号输入后，输出的仍是正余弦曲线，只有幅度和相位可能发生变 化，但是频率和波的形状仍是一样的。且只有正余弦曲线才拥有这样的性质，正因如此我们 才不用方波或三角波来表示。二、傅立叶变换分类 根据原信号的不同类型，我们可以把傅立叶变换分为四种类别：1、非周期性连续信号 傅立叶变换(Fourier Transform)2、周期性连续信号 傅立叶级数(Fourier Series)3、非周期性离散信号
12、 离散时域傅立叶变换(Discrete Time Fourier Transform)4、周期性离散信号 离散傅立叶变换（Discrete Fourier Transform）下图是四种原信号图例（从上到下，依次是 FT,FS,DTFT,DFT）这四种傅立叶变换都是针对正无穷大和负无穷大的信号，即信号的的长度是无穷大的，我们知道这对于计算机处理来说是不可能的，那么有没有针对长度有限的傅立叶变换呢？没有。因为正余弦波被定义成从负无穷小到正无穷大，我们无法把一个长度无限的信号组合 成长度有限的信号。面对这种困难，方法是：把长度有限的信号表示成长度无限的信号。如，可以把信号无 限地从左右进行延伸，延
13、伸的部分用零来表示，这样，这个信号就可以被看成是 非周期性 离 散信号，我们可以用到离散时域傅立叶变换（DTFT）的方法。也可以把信号用复制的方法 进行延伸，这样信号就变成了 周期性离散信号，这时我们就可以用 离散傅立叶变换方法（DFT）进行变换。本章我们要讲的是 离散信号，对于连续信号我们不作讨论，因为计算机 只能处理离散的数值信号，我们的最终目的是运用计算机来处理信号的。但是对于非周期性的信号，我们需要用无穷多不同频率的正弦曲线来表示，这对于计算 机来说是不可能实现的。所以对于离散信号的变换只有 离散傅立叶变换(DFT)才能被适用，对于计算机来说只有离散的和有限长度的数据才能被处理，对于其
14、它的变换类型只有在数学 演算中才能用到，在计算机面前我们只能用 DFT方法，后面我们要理解的也正是 DFT方法。这里要理解的是我们使用周期性的信号目的是为了能够用数学方法来解决问题，至于考 虑周期性信号是从哪里得到或怎样得到是无意义的。每种傅立叶变换都分成实数和复数两种方法，对于实数方法是最好理解的，但是复数方 法就相对复杂许多了，需要懂得有关复数的理论知识，不过，如果理解了实数离散傅立叶变 换(real DFT)，再去理解复数傅立叶变换就更容易了，所以我们先把复数的傅立叶变换放到 一边去，先来理解实数傅立叶变换，在后面我们会先讲讲关于复数的基本理论，然后在理解 了实数傅立叶变换的基础上再来理
15、解复数傅立叶变换。还有，这里我们所要说的变换(transform)虽然是数学意义上的变换，但跟函数变换是不 同的，函数变换是符合一一映射准则的，对于离散数字信号处理(DSP)，有许多的变换:傅立叶变换、拉普拉斯变换、Z变换、希尔伯特变换、离散余弦变换等，这些都扩展了函数 变换的定义，允许输入和输出有多种的值，简单地说变换就是把一堆的数据变成另一堆的数 据的方法。三、一个关于实数离散傅立叶变换(Real DFT)的例子 先来看一个变换实例，下图是一个原始信号图像：SO 60 40-0 I-二M-H-M 0 4 S 12 L6 S ample xnunbei 这个信号的长度是16，于是可以把这个信
16、号分解 9个余弦波和9个正弦波(一个长度 为N的信号可以分解成 N/2+1个正余弦信号，这是为什么呢？结合下面的 18个正余弦图 我想从计算机处理精度上就不难理解，一个长度为 N的信号，最多只能有 N/2+1个不同频 率，再多的频率就超过了计算机所能所处理的精度范围），如下图：9个余弦信号：(osine Waves 9个正弦信号 i 1 丁 t 1 i:T 4：t l 2 f i i 1 T rT 1 I *-4 a FT i 审 i 1 1 1 1 H i f 1 耳 ir1f:9 T 1 f i 1 1 4-I H i 1 1 I：1 I 1 1-h h i -1 r -r r 1-T *
17、1-I-业 h I t *i d m i T I J V *汪 rT Pl L.1 F T I i I j 1 b h I 1 r*r*f*1 屮 t|1 d II i I 1 Er o 把以上所有信号相加即可得到原始信号，至于是怎么分别变换出 9种不同频率信号的,我们先不急，先看看对于以上的变换结果，在程序中又是该怎么表示的，我们可以看看下面 这个示例图：2 上图中左边表示时域中的信号，右边是频域信号表示方法，从左向右，-,表示正向转换(Forward DFT),从右向左，-,表示逆向转换(In verse DFT),用小写x表示信号在每个时间点上的幅度值数组，用大写X表示每种频率的副度值数
18、组(即时间x-频率X),因为有N/2+1种频率，所以该数组长度为 N/2+1,X数组又分两种，一种是表示余弦波的不同频率幅度值：Re X，另一种是表示正弦波的不同频率幅度值：Im X，Re是实数(Real)的意思，Im是虚数(Imagine)的意思，采用复数的表示方法把正余弦波 组合起来进行表示，但这里我们不考虑复数的其它作用，只记住是一种组合方法而已，目的 是为了便于表达(在后面我们会知道，复数形式的傅立叶变换长度是 N，而不是N/2+1)。如此，再回过头去，看上面的正余弦各 9种频率的变化，相信，问题不大了。第二章、实数形式离散傅立叶变换(Real DFT)上一章，我们看到了一个实数形式离
19、散傅立叶变换的例子，通过这个例子能够让我们 先对傅立叶变换有一个较为形象的感性认识，现在就让我们来看看实数形式离散傅立叶变换 的正向和逆向是怎么进行变换的。在此，我们先来看一下频率的多种表示方法。inie Domain 4 rm N samples Frequency Domain ReX IniX II I I I I ITH 0 SI N 2-1 samples i i【i i rm 0 N/2 N?2+1 samples die(iri:p?-nifles t z collectively referred to as X 频域中关于频率的四种表示方法2 1、序号表示方法，根据时域中信号
20、的样本数取 0 N/2，用这种方法在程序中使用起来可 以更直接地取得每种频率的幅度值，因为频率值跟数组的序号是一一对应的：Xk，取值范 围是0 N/2；2、分数表示方法，根据时域中信号的样本数的比例值取 0 0.5:X?，?=k/N，取值范围 是 0 1/2;3、用弧度值来表示，把？乘以一个2 n得到一个弧度值，这种表示方法叫做自然频率(natural frequency):X w w=2 n?=2 n k/N取值范围是 0 n 4、以赫兹(Hz)为单位来表示，这个一般是应用于一些特殊应用，如取样率为 10 kHz表示 每秒有10,000个样本数：取值范围是 0到取样率的一半。DFT基本函数
21、cki=cos(2 n ki/N)n ki/N)ski=si n(2 其中k表示每个正余弦波的频率，如为2表示在0到 N长度中存在两个完整的周期，10 即有10个周期，如下图:Sainplr lllliliber 上图中至于每个波的振幅(amplitude)值(Re Xk,lm Xk)是怎么算出来的,这个是DFT 的核心，也是最难理解的部分，我们先来看看如何把分解出来的正余弦波合成原始信号(Inverse DFT)。三、合成运算方法(Real In verse DFT)DFT合成等式(合成原始 时间信号，频率-时间，逆向变换)：N/2 _ N/2 _ x门=ReXk cc 舟+工加丘门 51(
22、2北肝/N)k=0 A-=0 当然，差别是肯定是存在的，因为这两个等式是在两个不同条件下运用的，至于怎 么证明DFT合成公式，这个我想需要非常强的高等数学理论知识了，这是研究数学的人的 工作，对于普通应用者就不需要如此的追根究底了，但是傅立叶级数是好理解的，我们起码 可以从傅立叶级数公式中看出 DFT合成公式的合理性。DFT合成等式中的Im Xk和Re Xk跟之前提到的Im Xk和Re Xk是不一样的，下 面是转换方法(关于此公式的解释，见下文)：ImX fr ReX k ReX k N/2 2 N/2290 但k等于0和N/2时,实数部分的计算要用下面的等式 ReXO=N 曲M2=吟N/2
23、N 上面四个式中的 N是时域中点的总数，k是从0到N/2的序号。为什么要这样进行转换呢？这个可以从频谱密度（spectral density）得到理解，如下图就 是个频谱图：这是一个频谱图，横坐标表示频率大小，纵坐标表示振幅大小，原始信号长度为 N（这 里是32），经DFT转换后得到的17个频率的频谱，频谱密度表示每单位带宽中为多大的 振幅，那么带宽是怎么计算出来的呢？看上图，除了头尾两个，其余点的所占的宽度是 2/N，这个宽度便是每个点的带宽，头尾两个点的带宽是1/N,而Im Xk和Re Xk表示的是频谱密 度，即每一个单位带宽的振幅大小，但 2 艾尺 三丄表示 2/N（或1/N）带宽的振幅
24、 大小，所以 也 H丄X川分别应当是Im Xk和Re Xk的2/N（或1/N）。频谱密度就象物理中物质密度，原始信号中的每一个点就象是一个混合物，这个混合物是由 不同密度的物质组成的，混合物中含有的每种物质的质量是一样的，除了最大和最小两个密 弓 度的物质外，这样我们只要把每种物质的密度加起来就可以得到该混合物的密度了，又该混 合物的质量是单位质量，所以得到的密度值跟该混合物的质量值是一样的。至于为什么虚数部分是负数，这是为了跟复数 DFT保持一致，这个我们将在后面会知 道这是数学计算上的需要（Im Xk在计算时就已经加上了一个负号（稍后，由下文，便可 知），再加上负号，结果便是正的，等于没有
25、变化）。如果已经得到了 DFT结果，这时要进行逆转换，即合成原始信号，则可按如下步骤进 行转换：1、先根据上面四个式子计算得出 二；王川的值；2、再根据DFT合成等式得到原始信号数据。下面是用BASIC语言来实现的转换源代码：100 DF逆转换方法 110/XX数组存储计算结果（时域中的原始信号）120/REX数组存储频域中的实数分量，IMX为虚分量 130 140 DIM XX511 150 DIM REX256 160 DIM IMX256 170 180 PI=3.14159265 190 N%=512 200 210 GOSUB XXXX 转到子函数去获取 REX和IMX数据 220
26、230 240 250 FOR K%=0 TO 256 260 REXK%=REXK%/（N%/2）270 IMXK%=-IMXK%/（N%/2）290 280 NEXT k%300 REX0=REX0/N 310 REX256=REX256/N 320 330 初始化XX数组 340 FOR 1%=0 TO 511 350 XXI%=0 360 NEXT I%370 380 390 400 410 420 FOR K%=0 TO 256 430 FOR I%=0 TO 511 440 450 XXI%=XXI%+REXK%*COS(2*PI*K%*I%/N%)460 XXI%=XXI%+IM
27、XK%*SIN(2*PI*K%*I%/N%)470 480 NEXT I%490 NEXT K%500 510 END 上面代码中420至490换成如下形式也许更好理解，但结果都是一样的:420 FOR I%=0 TO 511 430 FOR K%=0 TO 256 440 450 XXI%=XXI%+REXK%*COS(2*PI*K%*I%/N%)460 XXI%=XXI%+IMXK%*SIN(2*PI*K%*I%/N%)470 480 NEXT I%490 NEXT K%四、分解运算方法(DFT)有三种完全不同的方法进行 DFT:种方法是通过联立方程进行求解，从代数的角度 看，要从N个已知
28、值求N个未知值，需要N个联立方程，且N个联立方程必须是线性独立 的，但这是这种方法计算量非常的大且极其复杂，所以很少被采用；第二种方法是利用信号 的相关性(correlation)进行计算，这个是我们后面将要介绍的方法；第三种方法是快速傅 立叶变换(FFT),这是一个非常具有创造性和革命性的的方法，因为它大大提高了运算速 度，使得傅立叶变换能够在计算机中被广泛应用，但这种算法是根据复数形式的傅立叶变换 来实现的，它把 N个点的信号分解成长度为 N的频域，这个跟我们现在所进行的实域 DFT 变换不一样，而且这种方法也较难理解，这里我们先不去理解，等先理解了复数 DFT后，再来看一下FFT。有一点
29、很重要，那就是这三种方法所得的变换结果是一样的，经过实践 证明，当频域长度为 32时，利用相关性方法进行计算效率最好，否则 FFT算法效率较高。现在就让我们来看一下相关性算法。利用第一种方法、信号的相关性(correlation)可以从噪声背景中检测出已知的信号，我们也 可以利用这个方法检测信号波中是否含有某个频率的信号波：把一个待检测信号波乘以另一 个信号波，得到一个新的信号波，再把这个新的信号波所有的点进行相加，从相加的结果就 可以判断出这两个信号的相似程度。如下图：Example 1 HGURh S-$Tut?example sigiuh.(a)an：；：JK Mud-Ded for c
30、onuuung tbe vpecvhc fUnttKm ihoun in(c)And(4,Figures(e)and(f)sbmr ih#result of nmliiplying eadiexan4)k 灯五by the basis ftmcuon-Figure(e)ba$aa average Of0.5,luduatuip thar J(1 Jcouuins th haw nuicticn with m amplitude of 1.0.Cgverscly*(!)hai zeio aterage OPT j does nor conm:he basis-fiincnou 上面a和b两个图是
31、待检测信号波，图a很明显可以看出是个 3个周期的正弦信号波，图b的信号波则看不出是否含有正弦或余弦信号，图c和d都是个3个周期的正弦信号波，图e和f分别是a、b两图跟c、d两图相乘后的结果，图 e所有点的平均值是 0.5，说明信 号a含有振幅为1的正弦信号c,但图f所有点的平均值是 0,则说明信号b不含有信号d。这个就是通过信号相关性来检测是否含有某个信号的方法。)sl(.$igiul aaalyzed b x：Tii/i 1 ten?aafll-ied r T Example 电总=孑 Dilxubei:：.-T.：-ri nc-q bring 9 T ie 13 4 64$anip min
32、jber 32 d.fun nuatT 第二种方法：相应地，我也可以通过把输入信号和每一种频率的正余弦信号进行相乘（关 联操作），从而得到原始信号与每种频率的关联程度（即总和大小），这个结果便是我们所 要的傅立叶变换结果，下面两个等式便是我们所要的计算方法：1 RwX伙=cos（2nki/N）r-0 ImXk-52,v/sin（2兀斤 f/N）第二个式子中加了个负号，是为了保持复数形式的一致，前面我们知道在计算此凭曲时 又加了个负号，所以这只是个形式的问题，并没有实际意义，你也可以把负号去掉，并在计 算 r-时也不加负号。这里有一点必须明白一个正交的概念：两个函数相乘，如果结果中的每个点的总和
33、为 0，则可认为这两个函数为正交函数。要确保关联性算法是正确的，则必须使得跟原始信号相乘 的信号的函数形式是正交的，我们知道所有的正弦或余弦函数是正交的，这一点我们可以通 过简单的高数知识就可以证明它，所以我们可以通过关联的方法把原始信号分离出正余弦信 号。当然，其它的正交函数也是存在的，如：方波、三角波等形式的脉冲信号，所以原始信 号也可被分解成这些信号，但这只是说可以这样做，却是没有用的。F面是实域傅立叶变换的 BASIC语言代码:J 100 THE DISCRETE FOURIER TRANSFORM 110 The frequency domain signals,held in RE
34、X and IMX,are calculated from 120 the time domain signal,held in XX.130r 140 DMXX511 150 DIM REX256 160 DM IMX256 170(180 PI=3.14159265 190 N%=512 200 r 210GOSUB XXXX 220 230 f 240 FOR K%=0 TO 256 Zero REX&IMX so thev can be used as accumulators 250 REXK%J=0 260 IMXK%j 270 NEXT Ko 280 290 300 310 FO
35、R=0 TO 256 320 330 340 350 360 370 XX holds the time domain signal rREX J holds the real pail of the frequency domain rIMX j holds the imaginary pail of the fiequencv do mam Set the constant PI N%is the number of points in XX Mythical subroutine to load data into XX oirelate XX with the cosine and s
36、ine waves.Eq S-4 K%loops through each sample in REX and IMX FOR I o=0 TO 511 1%loop through 便ach sample in XX REXKb=REXK%+XXI%+COS(2*PI*K%*I%/N%)=I2VIXK%XXI%+SIN(2o*I%X%)NEXT Pb 380 NEXT K%390 400 END 到此为止，我们对傅立叶变换便有了感性的认识了吧。但要记住，这只是在实域上的 离散傅立叶变换，其中虽然也用到了复数的形式，但那只是个替代的形式，并无实际意义，现实中一般使用的是复数形式的离散傅立叶变换
37、，且快速傅立叶变换是根据复数离散傅立叶 变换来设计算法的，在后面我们先来复习一下有关复数的内容，然后再在理解实域离散傅立 叶变换的基础上来理解复数形式的离散傅立叶变换。第三章、复数 复数扩展了我们一般所能理解的数的概念，复数包含了实数和虚数两部分，利用复数 的形式可以把由两个变量表示的表达式变成由一个变量（复变量）来表达，使得处理起来更加 自然和方便。我们知道傅立叶变换的结果是由两部分组成的，使用复数形式可以缩短变换表达式，使得我们可以单独处理一个变量(这个在后面的描述中我们就可以更加确切地知道)，而且 快速傅立叶变换正是基于复数形式的，所以几乎所有描述的傅立叶变换形式都是复数的形 式。但是复
38、数的概念超过了我们日常生活中所能理解的概念，要理解复数是较难的，所以 我们在理解复数傅立叶变换之前，先来专门复习一下有关复数的知识，这对后面的理解非常 重要。一、复数的提出 在此，先让我们看一个物理实验：把一个球从某点向上抛出，然后根据初速度和时间来 计算球所在高度，这个方法可以根据下面的式子计算得出：2 其中h表示高度，g表示重力加速度(9.8m/s2),v表示初速度，t表示时间。现在反过来，假如知道了高度，要求计算到这个高度所需要的时间，这时我们又可以通过下式来计算：r 二 1 士(多谢JERRY_PRI提出：1、根据公式h=-(gt2/2)+Vt(gt后面的2表示t的平方)，我们可以讨论
39、最终情况，也就 是说小球运动到最高点时，v=gt，所以，可以得到t=sqt(2h/g)且在您给的公式中，根号下为 1-(2h)/g，化成分数形式为(g-2h)/g，g和h不能直接做加减 运算。2、g是重力加速度，单位是m/s2，h的单位是m,他们两个相减的话在物理上没有意义，而且使用您给的那个公式反向回去的话推出的是 h=-(gt2/2)+gt啊(gt后面的2表示t的平 方)。3、直接推到可以得出 t=v/g qt(v2-2hg)/g2)(v和g后面的2都表示平方)，那么也就 是说当v22hg时会产生复数，但是如果从实际的 v2是不可能小于2hg的，所以我感觉复 数不能从实际出发去推到，只能从
40、抽象的角度说明一下。)经过计算我们可以知道，当高度是 3米时，有两个时间点到达该高度：球向上运动时的 时间是0.38秒，球向下运动时的时间是 1.62秒。但是如果高度等于 10时，结果又是什么 呢？根据上面的式子可以发现存在对负数进行开平方运算，我们知道这肯定是不现实的。第一次使用这个不一般的式子的人是意大利数学家 Girolamo Cardano(1501-1576)，两个世纪后，德国伟大数学家 Carl Friedrich Gause(1777-1855)提出了复数的概念，为 后来的应用铺平了道路，他对复数进行这样表示：复数由实数(real)和虚数(imaginary)两 部分组成，虚数中
41、的根号负 1用i来表示(在这里我们用 j来表示，因为i在电力学中表示 电流的意思)。我们可以把横坐标表示成实数，纵坐标表示成虚数，则坐标中的每个点的向量就可以 用复数来表示，如下图：上图中的ABC三个向量可以表示成如下的式子:ASM 5三 Y I l|l I I h I l|p di It b 11 kl Ilf I 1 I it f li til|I I d d I li li|l-2-1012345 A=2+6j B=-4 T.5j C=3-7j 这样子来表达方便之处在于运用一个符号就能把两个原来难以联系起来的数组合起来 了，不方便的是我们要分辨哪个是实数和哪个是虚数，我们一般是用 Re(
42、)和Im()来表示实 数和虚数两部分，如：Re A=2 Im A:6 Re B=-4 Im B=-1.5 Re C=3 Im C:=-7 复数之间也可以进行加减乘除运算:这里有个特殊的地方是 j2等于-1，上面第四个式子的计算方法是把分子和分母同时乘 以c-dj，这样就可消去分母中的 j 了。复数也符合代数运算中的交换律、结合律、分配律：A B=B A (A+B)+C=A+(B+C)A(B+C)=AB+AC 二、复数的极坐标表示形式 前面提到的是运用直角坐标来表示复数，其实更为普遍应用的是极坐标的表示方法,如下图：上图中的M即是数量积(magnitude)，表示从原点到坐标点的距离，B是相位角
43、(phase angle)，表示从X轴正方向到某个向量的夹角，下面四个式子是计算方法：(=三孑三*4*15J M=.18.25*3j-|吗十 0=arctan I 4 V iip R M=.5B 0=arctati(-7/3)Real axis I I-i I 4 I J R 4 I f l F I I I 4 I M-A)2 Im A)2 aictan 我们还可以通过下面的式子进行极坐标到直角坐标的转换:a+jb=M(cos 0+j sin 0)上面这个等式中左边是直角坐标表达式，右边是极坐标表达式。欧拉等式（欧拉，瑞士的著名数学家，Leonhard Euler,1707-1783)：ejx
44、=cos x+j sin x 这个等式可以从下面的级数变换中得到证明:E(T)#冃0 上面中右边的两个式子分别是 cos（x）和sin（x）的泰勒（Taylor）级数。Re A Mcos(6)Tin A M sin(6)还有一个更为重要的等式(2E)!.这样子我们又可以把复数的表达式表示成指数的形式了:a+jb=M ej（这便是复数的两个表达式）指数形式是数字信号处理中数学方法的支柱，也许是因为用指数形式进行复数的乘除运 算极为简单的缘故吧：三、复数是数学分析中的一个工具 为什么要使用复数呢？其实它只是个工具而已，就如钉子和锤子的关系，复数就象那 锤子，作为一种使用的工具。我们把要解决的问题表
45、达成复数的形式(因为有些问题用复数 的形式进行运算更加方便)，然后对复数进行运算，最后再转换回来得到我们所需要的结果。有两种方法使用复数，一种是用复数进行简单的替换，如前面所说的向量表达式方法 和前一节中我们所讨论的实域 DFT，另一种是更高级的方法：数学等价(mathematical equivale nee)，复数形式的傅立叶变换用的便是数学等价的方法，但在这里我们先不讨论这 种方法，这里我们先来看一下用复数进行替换中的问题。用复数进行替换的基本思想是：把所要分析的物理问题转换成复数的形式，其中只是 简单地添加一个复数的符号 j，当返回到原来的物理问题时，则只是把符号 j去掉就可以了。有一
46、点要明白的是并不是所有问题都可以用复数来表示，必须看用复数进行分析是否 适用，有个例子可以看出用复数来替换原来问题的表达方式明显是谬误的：假设一箱的苹果 是5美元，一箱的桔子是 10美元，于是我们把它表示成 5+10j，有一个星期你买了 6箱 苹果和2箱桔子，我们又把它表示成 6+2j，最后计算总共花的钱是(5+10j)(6+2j)=10+70j，结果是买苹果花了 10美元的，买桔子花了 70美元，这样的结果明显是错了，所以复 数的形式不适合运用于对这种问题的解决。四、用复数来表示正余弦函数表达式 对于象M cos(3 t+和)cos(3 t)+B sin(表达式，用复数来表示，可以变得非常
47、简洁，对于直角坐标形式可以按如下形式进行转换：A cos(3f)+B sill(oof)门 a+Jb conventional representatiofif(complex rmnibei)上式中余弦幅值 A经变换生成a,正弦幅值B的相反数经变换生成 b:A a,B-b，但要注意的是，这不是个等式，只是个替换形式而已。对于极坐标形式可以按如下形式进行转换：M cos(o)r+()壬(eoveniiounl represemarion)(complex member)上式中，M M,0 这里虚数部分采用负数的形式主要是为了跟复数傅立叶变换表达式保持一致，对于这种 替换的方法来表示正余弦，符号
48、的变换没有什么好处，但替换时总会被改变掉符号以跟更高 级的等价变换保持形式上的一致。在离散信号处理中，运用复数形式来表示正余弦波是个常用的技术，这是因为利用复 数进行各种运算得到的结果跟原来的正余弦运算结果是一致的，但是，我们要小心使用复数 操作，如加、减、乘、除，有些操作是不能用的，如两个正弦信号相加，采用复数形式进行 相加，得到的结果跟替换前的直接相加的结果是一样的，但是如果两个正弦信号相乘，则采 用复数形式来相乘结果是不一样的。幸运的是，我们已严格定义了正余弦复数形式的运算操 作条件：1、参加运算的所有正余弦的频率必须是一样的；2、运算操作必须是线性的，如两个正弦信号可以进行相加减，但不
49、能进行乘除，象信号的 放大、衰减、高低通滤波等系统都是线性的，象平方、缩短、取限等则不是线性的。要记住 的是卷积和傅立叶分析也只有线性操作才可以进行。下图是一个相量变换（我们把正弦或余弦波变成复数的形式称为相量变换，Phasor transform）的例子，一个连续信号波经过一个线性处理系统生成另一个信号波，从计算过程 我们可以看出采用复数的形式使得计算变化十分的简洁：在第二章中我们描述的实数形式傅立叶变换也是一种替换形式的复数变换，但要注意的 是那还不是复数傅立叶变换，只是一种代替方式而已。下一章、即，第四章，我们就会知道 复数傅立叶变换是一种更高级的变换，而不是这种简单的替换形式。第四章、
50、复数形式离散傅立叶变换 复数形式的离散傅立叶变换非常巧妙地运用了复数的方法，使得傅立叶变换变换更加自 然和简洁，它并不是只是简单地运用替换的方法来运用复数，而是完全从复数的角度来分析 问题，这一点跟实数 DFT是完全不一样的。把正余弦函数表示成复数的形式 3cO5(3f-7/4)or 2 12L3cos(W)-1.5cos(0f-TU8or 13858cos(wr)-0.5743訂呦 or 2,1213-/2,1213 Of 0.1913-)04619 l.W or L3858-;05741 npa亠一 VP3二 4 3 2 1 O-1J 巧-4 通过欧拉等式可以把正余弦函数表示成复数的形式：