资源描述
快速傅里叶变换快速傅里叶变换（FFT）引言引言qFFT:FFT:Fast Fourier TransformFast Fourier Transformq19651965年年，Cooley-Cooley-TukeyTukey 发发表表文文章章机机器器计计算算傅傅里里叶叶级级数数的的一一种种算算法法，提提出出FFTFFT算算法法，解解决决DFTDFT运算量太大，在实际使用中受限制的问题。运算量太大，在实际使用中受限制的问题。qFFTFFT的的应应用用。频频谱谱分分析析、滤滤波波器器实实现现、实实时时信信号号处理等。处理等。qDSPDSP芯片实现。芯片实现。一、直接计算一、直接计算DFT的问题及改进途径的问题及改进途径1.运算量运算量复数乘法复数乘法复数加法复数加法一个一个X(k)NN 1N个个X(k)(N点点DFT)N 2N(N 1)实数乘法实数乘法实数加法实数加法一次复乘一次复乘42一次复加一次复加2一个一个X(k)4N2N+2(N 1)=2(2N 1)N个个X(k)(N点点DFT)4N 22N(2N 1)2、减少、减少DFT运算量的途径运算量的途径FFT FFT 算法分类算法分类:q时间抽抽选法法DIT:Decimation-In-Timeq频率抽率抽选法法DIF:Decimation-In-Frequency二二、按时间抽选的基、按时间抽选的基-2FFT算法算法1、算法原理、算法原理设序列点数设序列点数 N=2M，M 为整数。为整数。若不满足，则补零若不满足，则补零将序列将序列x(n)按按n的奇偶性分成两的奇偶性分成两组：N为2的整数的整数幂的的FFT算法称算法称基基-2FFT算法算法。将将N点点DFT定义式分解为两个长度为定义式分解为两个长度为N/2的的DFT记：记：（1 1）（这一步利用：（这一步利用：）其中其中X1(k)和和X2(k)分别为分别为x1(r)和和x2(r)的的N/2点点DFT，即即:由于由于X1(k)和和X2(k)均以均以N/2为周期，且为周期，且 ，所以，所以X(k)又可表示为又可表示为将上式表达的运算用一个专用将上式表达的运算用一个专用“蝶形蝶形”信号流图表示。信号流图表示。注：注：a.上支路为加法，下支路为减法；上支路为加法，下支路为减法；b.乘法运算的支路标箭头和系数。乘法运算的支路标箭头和系数。N点点DFT的一次时域抽取分解图的一次时域抽取分解图(N=8)那么，那么，X1(k)又可表示为又可表示为:由于由于 ，仍为偶数，因此，两个仍为偶数，因此，两个 点点DFTDFT又可按奇偶性进一步分解为又可按奇偶性进一步分解为4 4个个 点的点的DFTDFT。式中式中 同同理理，由由X3(k)和和X4(k)的的周周期期性性和和WN/2m的对称性的对称性 WN/2k+N/4=-WN/2k，最后得到：，最后得到：“蝶形蝶形”信号流图表示信号流图表示 q 用同样的方法可计算出用同样的方法可计算出其中其中 N点点DFT的第二次时域抽取分解图的第二次时域抽取分解图(N=8)q类似的分解一直继续下去，直到分解为最后的两类似的分解一直继续下去，直到分解为最后的两类蝶形运算为止类蝶形运算为止(2(2点点DFT).DFT).q如上述如上述N=8=2N=8=23 3，N/4=2N/4=2点：点：类似进一步分解类似进一步分解1点点DFTx(0)1点点DFTx(4)X3(0)X3(1)进一步简化为蝶形流图：进一步简化为蝶形流图：X3(0)X3(1)x(0)x(4)N点点DIT-FFT运算流图运算流图(N=8)2 2、运算量、运算量当当N=2L时，共有时，共有L级蝶形，每级级蝶形，每级N/2个蝶形，个蝶形，每个蝶形有每个蝶形有1次复数乘法次复数乘法2次复数加法。次复数加法。复数乘法：复数加法：比较DFT DIT算法的其他形式流图算法的其他形式流图q输入倒位序输出自然序输入倒位序输出自然序q输入自然序输出倒位序输入自然序输出倒位序q输入输出均自然序输入输出均自然序q相同几何形状相同几何形状q输入倒位序输出自然序输入倒位序输出自然序q输入自然序输出倒位序输入自然序输出倒位序 1.1.算法原理算法原理 设设序序列列x(n)长长度度为为N=2M，首首先先将将x(n)前前后后对对半半分分开开，得得到到两两个个子子序序列列，其其DFT可可表表示示为为如下形式：如下形式：三、频域抽取法三、频域抽取法FFT(DIF-FFT)偶数偶数 奇数奇数 将将X(k)分解成偶数组与奇数组，当分解成偶数组与奇数组，当k取取偶数偶数(k=2r,r=0,1,N/2-1)时时 当当k取奇数取奇数(k=2r+1,r=0,1,N/2-1)时时令：令：将将x1(n)和和x2(n)分别代入前两式，可得：分别代入前两式，可得：用蝶型结构图表示为：用蝶型结构图表示为：DIF-FFT一次分解运算流图一次分解运算流图(N=8)N/2仍仍为偶数，偶数，进一步分解：一步分解：N/2 N/4DIF-FFT二次分解运算流图二次分解运算流图(N=8)DIF-FFT运算流图运算流图(N=8)DIT-FFT的一种变形运算流图的一种变形运算流图2.按频率抽取按频率抽取FFT蝶形运算特点蝶形运算特点1）原位计算）原位计算-1M级蝶形运算，每级级蝶形运算，每级N/2个蝶形，每个蝶形结构：个蝶形，每个蝶形结构：m表示第表示第m级迭代，级迭代，k、j表示数据所在的行数表示数据所在的行数2）蝶形运算两）蝶形运算两节点点间的的“距离距离”对N=2M点点FFT，输入自然序，入自然序，输出倒位序，出倒位序，第第m级两两节点距离：点距离：2M-m=N/2m第第m级运算：级运算：q蝶形运算两蝶形运算两节点的第一个点的第一个节点点为k值，表示成，表示成M位二位二进制数，左移制数，左移m-1位，把右位，把右边空出的位空出的位置置补零，零，结果果为r的二的二进制数。制数。存存储单元元输入序列入序列x(n):N个存个存储单元元 系数系数 ：N/2个存个存储单元元3.DIT与与DIF的异同的异同q基本蝶形不同基本蝶形不同DIT:先复乘后加减先复乘后加减DIF:先减后复乘先减后复乘q运算量相同运算量相同q都可原位运算都可原位运算qDIT和和DIF的基本蝶形互为转置的基本蝶形互为转置四、四、IDFT的的FFT算法算法（FFT应用一）应用一）一、从定义比较分析一、从定义比较分析与与DFT的比的比较：1）旋）旋转因子因子WN-kn 的不同；的不同；2）结果果还要乘要乘 1/N。二、实现算法二、实现算法直接使用直接使用FFT程序的算法程序的算法共轭共轭FFT共轭共轭乘乘1/N直接调用直接调用FFT子程序计算子程序计算IFFT的方法：的方法：3.8 模拟信号的频谱分析模拟信号的频谱分析信号的频谱分析：计算信号的傅里叶变换信号的频谱分析：计算信号的傅里叶变换对连续时间非周期信号的对连续时间非周期信号的DFT逼近过程逼近过程1）时域抽样）时域抽样2）时域截断）时域截断3）频域抽样）频域抽样近似逼近：近似逼近：1.对连续时间非周期信号的对连续时间非周期信号的DFT逼近逼近2.对连续时间周期信号的对连续时间周期信号的DFS逼近逼近近似逼近：近似逼近：频率响应的混叠失真及参数的选择频率响应的混叠失真及参数的选择同时提高信号最高频率和频率分辨率，需增加采同时提高信号最高频率和频率分辨率，需增加采样点数样点数N。信号最高频率与频率分辨率之间的矛盾信号最高频率与频率分辨率之间的矛盾频率分辨率频率分辨率提高频率分辨率方法：提高频率分辨率方法：增加信号实际记录长度增加信号实际记录长度 补零并不能提高频率分辨率补零并不能提高频率分辨率 DFT(实实际际中中用用FFT计计算算)可可用用来来对对连连续续信信号和数字信号进行谱分析。号和数字信号进行谱分析。(1)混叠现象混叠现象混叠现象混叠现象 (2)截断效应截断效应截断效应截断效应。3.用用DFT进行谱分析的误差问题进行谱分析的误差问题（3 3）栅栏效应）栅栏效应改善方法：改善方法：增加频域抽样点数增加频域抽样点数N（时域补零），使谱线更密时域补零），使谱线更密DFT只计算离散点（基频只计算离散点（基频F0的整数倍处）的频谱，的整数倍处）的频谱，而不是连续函数而不是连续函数【本章知识点小结本章知识点小结】1.1.周期序列的离散傅里叶级数（周期序列的离散傅里叶级数（DFSDFS）及性质）及性质;2.2.离散傅里叶变换（离散傅里叶变换（DFTDFT）定义、物理意义；）定义、物理意义；3.3.离散傅里叶变换的性质：圆周移位、圆周卷积离散傅里叶变换的性质：圆周移位、圆周卷积等；等；4.4.频域采样定理；频域采样定理；5.5.快速傅里叶变换（快速傅里叶变换（FFTFFT）:DIT-FFT:DIT-FFT、DIF-FFTDIF-FFT；6.6.模拟信号的频谱分析。模拟信号的频谱分析。本章结束本章结束
展开阅读全文