《讲_数字信号处理-频率抽取FFT-IFFT课件》由会员分享,可在线阅读,更多相关《讲_数字信号处理-频率抽取FFT-IFFT课件(22页珍藏版)》请在金锄头文库上搜索。
1、第2章 DFT及其快速算法,2-1 周期序列2-2 离散傅立叶级数2-3 离散傅立叶变换2-4 频率采样理论2-5 快速傅立叶变换2-6 离散傅立叶反变换(IDFT) 的运算,一个完整N=8的按时间抽取FFT的 运算流图,x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7),X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7),m=0,m=1,m=2,2.5.3 频率抽取基2 FFT 算法(DIF),将x(n)按前后分为两组:,前,后,将N=8点分解成2个4点的DFT的信号流图,4点 DFT,x(0) x(1) x(2) x(3),4点 DF
2、T,x(4) x(5) x(6) x(7),X(0) X(2) X(4) X(6),X(1) X(3) X(5) X(7),X1(k),前半部分序列,后半部分序列,x1(n),x2(n),X2(k),完整N=8的按频率抽取FFT的运算流图,x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7),X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7),m=0,m=1,m=2,DIF与DIT比较,不同之处: (1)DIF与DIT两种算法结构倒过来。 DIF为输入顺序,输出乱序。运算完毕再运行“二进制倒读”程序。 DIT为输入乱序,输出顺序。先运行“二
3、进制倒读”程序,再进行求DFT。 (2)DIF与DIT根本区别:在于蝶形结不同。 DIT的复数相乘出现在减法之前。 DIF的复数相乘出现在减法之后。,DIT,DIF,2-6 计算IFFT,将下列两式进行比较,一、改变FFT流图系数的方法 1.思路,在IFFT的运算中,常常把1/N分解为(1/2)m,并且在M级运算中每一级运算都分别乘以1/2因子,就可得到IFFT的两种基本蝶形运算结构。(并不常用此方法),2.IFFT的基本蝶形运算,A,B,A,B,(a)频率抽取IFFT的蝶形运算,(b)时间抽取IFFT的蝶形运算,时间抽取和频率抽取的概念要倒一下,四.直接利用FFT流图的方法 1.思路,前面的
4、两种IFFT算法,排程序很方便,但要改变FFT的程序和参数才能实现。 现介绍第三种IFFT算法,则可以完全不必改动FFT程序。,2.直接利用FFT流图方法的推导,实序列的FFT 运算, FFT算法为同址运算,且 X(k)一般为复数,,存放的数组应该是复数数组,但输入序列 x(n),通常为实序列,存放到复数数组中时,造成存储空,间及运算时间的浪费,为提高存储空间利用率及提,高运算速度:,1. 通过一个N 点FFT运算 ,同时求出两个,独立的N 点实序列的DFT,设,x(n)与y(n)为实,序列。,令,N点FFT,由傅立叶变换的奇偶虚实性,2. 用一个N点FFT运算,求一个2N点实序列,的DFT,设x(n)为2N点实序列,令g(m)=x(2m) , h(m)=x(2m+1),且,N点FFT,再由时间抽取基2 FFT算法,补0,IDFT,线性 卷积,用FFT实现线性卷积,任意基数的FFT算法,N点分解为p个q点DFT或q个p点DFT,任意基数的FFT算法,N点分解为p个q点DFT或q个p点DFT,