《快速傅里叶变换(经典实用).ppt》由会员分享,可在线阅读,更多相关《快速傅里叶变换(经典实用).ppt(58页珍藏版)》请在三一文库上搜索。
1、快速傅里叶变换,第四章 快速傅立叶变换 Fast Fourier Transform,快速傅里叶变换,第一节 直接计算DFT的问题及改进途径,1、问题的提出,设有限长序列x(n),非零值长度为N,若对x(n)进行一次DFT运算,共需多大的运算工作量?,计算成本? 计算速度?,快速傅里叶变换,2. DFT的运算量,回忆DFT和IDFT的变换式:,快速傅里叶变换,计算机运算时(编程实现):,以DFT为例:,快速傅里叶变换,运算量,(a+jb)(c+jd)=(ac-bd)+j(bc+ad),快速傅里叶变换,例:计算一个 N点DFT ,共需N2次复乘。以做一次 复乘1s计,若N =4096,所需时间为
2、,例:石油勘探,有24个通道的记录,每通道波形记 录长度为5秒,若每秒抽样500点/秒, 1)每道总抽样点数:500*5=2500点 2)24道总抽样点数:24*2500=6万点 3)DFT复乘运算时间:N2=(60000)2=36*108次,快速傅里叶变换,由于计算量大,且要求相当大的内存,难以实现实时处理,限制了DFT的应用。长期以来,人们一直在寻求一种能提高DFT运算速度的方法。,FFT便是 Cooley 当n=奇数时,令n=2r+1;,分组,变量置换,2、算法步骤,得到:,快速傅里叶变换,带入DFT中,快速傅里叶变换,所以,由于,?,快速傅里叶变换,X1(k)、X2(k)只有N/2个点
3、,以N/2为周期;而X (k)却有N个点,以N为周期。要用X1(k)、X2(k)表达全部的X (k) 值,还必须利用WN系数的周期特性。,快速傅里叶变换,又考虑到 的对称性:,有:,快速傅里叶变换,蝶形运算流图符号,说明: (1) 左边两路为输入 (2) 右边两路为输出 (3) 中间以一个小圆表示加、 减运算(右上路为相加 输出、右下路为相减输 出),1个蝶形运算需要1次复乘,2次复加,快速傅里叶变换,运算量减少了近一半,分解后的运算量:,快速傅里叶变换,先将N=8点的DFT分解成2个4点DFT: 可知:时域上:x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x
4、(7)为奇子序列 频域上:X(0)X(3),由X(k)给出 X(4)X(7),由X(k+N/2)给出,例子:求 N=23=8点FFT变换 按N=8N/2=4,做4点的DFT:,快速傅里叶变换,N=8点的直接DFT的计算量为: 复乘:N2次 = 64次 复加:N(N-1)次 = 87=56次,此外,还有4个蝶形结,每个蝶形结需要1次复乘,2次复加。 一共是:复乘4次,复加8次。,得到X1(k)和X2(k)需要: 复乘:(N/2)2+ (N/2)2次 = 32次 复加:N/2(N/2-1)+N/2(N/2-1) =12+12 =24次,用分解的方法得到X (k)需要: 复乘:32+4 = 36次
5、复加:24+8 = 32次,快速傅里叶变换,N点DFT的一次时域抽取分解图(N=8),快速傅里叶变换,因为4点DFT还是比较麻烦,所以再继续分解。,若将N/2(4点)子序列按奇/偶分解成两个N/4点(2点)子序列。即对将x1(r)和x2(r)分解成奇、偶两个N/4点(2点)点的子序列。,快速傅里叶变换,那么,X1(k)又可表示为,快速傅里叶变换,X2(k)也可以进行相同的分解:,注意:通常我们会把 写成 。,快速傅里叶变换,N点DFT的第二次时域抽取分解图(N=8),快速傅里叶变换,8,8,快速傅里叶变换,N点DITFFT运算流图(N=8),快速傅里叶变换,3、DITFFT算法与直接计算DFT
6、运算量的比较,1)、N=2M的DFT运算可分成M级,每一级有N/2个蝶形 ,每个蝶形有一次复乘两次复加。,2)、所以M级共有 次复乘和 次复加。,3)、若直接计算DFT,需N2次复乘和N(N-1)次复加。,显然,当N较大时,有:,快速傅里叶变换,FFT算法与直接计算DFT所需乘法次数的比较曲线,快速傅里叶变换,4、DITFFT的运算规律及编程思想,FFT的每级(列)计算都是由N个复数数据(输入)两两构成一个蝶型(共N/2个蝶形)运算而得到另外N个复数数据(输出)。,当数据输入到存储器以后,每一组运算的结果,仍然存放在这同一组存储器中直到最后输出。,例:将x(0)放在单元A(0)中,将x(4)放
7、在单元A(1)中,W80 放在一个暂存器中。,将x(0) + W80 x(4) 送回A(0)单元,将x(0) - W80 x(4) 送回A(1)单元,1) 原位运算 (亦称同址计算),快速傅里叶变换,回顾:N点DITFFT运算流图(N=8),快速傅里叶变换,如上所述,N点DITFFT运算流图中,每级都有N/2个蝶形。每个蝶形都要乘以因子WNP,称其为旋转因子,p称为旋转因子的指数。,2)旋转因子的变化规律,观察FFT运算流图发现,第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下:,L=1时,WNp=WN/4J, N/4 =21 =2L, J=0 L=2时, WNp =W
8、N/2J, N/2 =22 =2L, J=0,1 L=3时, WNp =WNJ, N =23 =2L, J=0,1,2,3,快速傅里叶变换,对N=2M的一般情况,第L级的旋转因子为:,快速傅里叶变换,设序列x(n)经时域抽选(倒序)后,存入数组X中。如果蝶形运算的两个输入数据相距B个点(B=2L-1),应用原位计算,则蝶形运算可表示成如下形式:,下标L表示第L级运算,XL(J)则表示第L级运算后数组元素X(J)的值。,快速傅里叶变换,3) 编程思想及流程图,快速傅里叶变换,4)码位倒序,由N=8蝶形图看出:原位计算时,FFT输出的X(k)的次序正好是顺序排列的,即X(0)X(7),但输入x(n
9、)都不能按自然顺序存入到存储单元中,而是按x(0),x(4),x(2),x(6) ,x(1),x(5),x(3),x(7)的顺序存入存储单元,即为乱序输入,顺序输出。 这种顺序看起来相当杂乱,然而它是有规律的。即码位倒读规则。,快速傅里叶变换,以N=8为例:,看出:码位倒读后的顺序刚好是数据送入计算机内的顺序。,快速傅里叶变换,倒序规律,快速傅里叶变换,对于数N,在其二进制最高位加1,等于加N/2。,若已知某个反序号为J,为求下一个反序号,可先判J的最高位: 1) 若为0,则把该位变成1(即加N/2)就得到下 一个反序号, 2) 若为1,则需判断次高位: 若次高位为0,则把最高位变0(相当减去
10、 N/2)后,再把次高位变1(即加N/4)。 若次高位为1,则需判断次次高位,分析:,快速傅里叶变换,倒 序 排 列 算 法 的 流 程 图,快速傅里叶变换,第四节 按频率抽选的基2-FFT算法,在基2快速算法中,频域抽取法FFT也是一种常用的快速算法,简称DIFFFT。,设序列x(n)长度为N=2M,首先将x(n)前后对半分开,得到两个子序列,其DFT可表示为如下形式,快速傅里叶变换,DIFFFT一次分解运算流图(N=8),快速傅里叶变换,DIFFFT二次分解运算流图(N=8),快速傅里叶变换,DIFFFT运算流图(N=8),快速傅里叶变换,时间抽取算法与频率抽取算法的比较,1) 频率抽选法
11、和时间抽选法总的计算量是相同的,2) 频率抽取法和时间抽取法一样,都适用于原位运 算, 即蝶形的输入和输出占用同一个存储单元。,3) 均存在码位倒序问题。,4) 频率抽选法和时间抽选法一样,基本运算也是蝶形 运算。但两者的蝶形形式略有不同。,快速傅里叶变换,第五节 IDFT的快速算法IFFT,上述FFT算法流图也可以用于离散傅里叶逆变换(Inverse Discrete Fourier Transform,简称IDFT)。,比较DFT和IDFT的运算公式:,1) 旋转因子:,2) 系数:,快速傅里叶变换,DITIFFT运算流图,快速傅里叶变换,DITIFFT运算流图(防止溢出),快速傅里叶变换
12、,如果希望直接调用FFT子程序计算IFFT,则可用下面的方法:,对上式两边同时取共轭,得:,快速傅里叶变换,例1、如果通用计算机的速度为平均每次复乘需要 5s,每次复加需要0.5s,用它来计算512点 的DFTx(n),问:,1)直接计算需要多少时间? 2)用FFT需要多少时间?,解:1)用DFT进行运算:,复乘:T1=N2510-6=1.31072秒,复加:T2=N(N-1)0.510-6=0.130816秒,总共:T=T1+T2=1.441536秒,快速傅里叶变换,2)用FFT进行运算:,复乘:T1=(N/2)log2N510-6=0.01152秒,复加:T2= Nlog2N 0.510-
13、6=0.002304秒,总共:T=T1+T2=0.013824秒,快速傅里叶变换,例2、对一个连续时间信号xa(t)采样1秒得到4096个采 样点的序列,求:,1)若采样后没有发生混叠现象,xa(t)的最高频率是 多少?,解:1秒内采样4096个点,说明采样频率是4096Hz。,快速傅里叶变换,2)若计算采样信号的4096点DFT,DFT系数之间 的频率间隔是多少?,解:(要求解的是频谱分辨的间隔F),快速傅里叶变换,例3、长度为240点的序列x(n)与长度为N点的h(n)卷 积。当N=10和240时,直接进行卷积 x(n)*h(n) 和用 IFFTX(K)H(K) 的方法相比,那种方法求 解y(n)的效率更高?,LN1+N2-1,快速傅里叶变换,直接进行卷积(N=10):,乘法次数:24010 = 2400次,用FFT的方法(N=10):添零到256点,L=256,乘法次数:,3(L/2)log2LL = 31288256 = 3328次,快速傅里叶变换,直接进行卷积(N=240):,乘法次数:240240 = 57600次,用FFT的方法(N=240):添零到512点,L=512,乘法次数:,3(L/2)log2LL = 32569512 = 7424次,此课件下载可自行编辑修改,供参考! 感谢你的支持,我们会努力做得更好!,