56-第四章FFT.ppt

1、1,第四章 快速傅里叶变换,FFT: Fast Fourier Transform 1965年，Cooley, Tukey 机器计算傅里叶级数的一种算法,2,一、直接计算DFT计算量,3,运算量,N (N 1),N 2,N个X(k) (N点DFT),N 1,N,一个X(k),复数加法,复数乘法,2N+2 (N 1)=2 (2N 1),4N,一个X (k),2N (2N 1),4N 2,N个X (k) (N点DFT),2,一次复加,2,4,一次复乘,实数加法,实数乘法,4,例:,5,改善DFT运算效率的基本途径,时间抽取法 DIT: Decimation-In-Time 频率抽取法 DIF: D

2、ecimation-In-Frequency,6,1. 算法原理,二、按时间抽取基-2 FFT算法,设序列点数 N = 2L，L 为整数，不满足则补零,将时域x(n)按n偶奇分两组：,基-2FFT算法：N为2的整数幂的FFT算法,DIT: Decimation-In-Time,长序列短序列？ 减少运算量? 分解之后还原？,7,则x(n)的DFT:,8,X(k)、W系数周期性，求后半部分,频域实现前/后分组,9,2. 蝶形信号流图,一个N点DFT分解为两个N/2点DFT 时域偶奇，频域前后分组,支路值支路起始节点支路系数 节点值所有输入支路值之和,结论,省,10,例：求 N=8点FFT,时域上：

3、x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(k)：X(0)X(3) X(k+N/2)：X(4)X(7),（1）先做N/2=4点DFT,11,N/2点DIT-FFT,两个N/2点DFT能重构N点DFT，即由短变为长序列,12,分解后的运算量：,N (N / 2 1),N 2 / 2,两个N / 2点DFT,N,N / 2,N / 2个蝶形,总计,2,1,一个蝶形,N / 2 (N / 2 1),(N / 2)2,一个N / 2点DFT,复数加法,复数乘法,运算量减少了近一半,13,进一步分解： N / 2 N / 4,14,其中

4、：,这样逐级分解，直到2点DFT ，当N = 8时 即分解到X3(k)，X4(k)，X5(k)，X6(k)，k = 0, 1,15,16,时间抽取法：每级输入时间序列按偶奇分为两更短序列,N=8 DIT-FFT蝶形图,17,当N = 2L时，共有L级蝶形，每级N / 2个蝶形，每个 蝶形有1次复数乘法2次复数加法。,复数乘法：,复数加法：,比较DFT,3. DIT-FFT与直接DFT运算量比较,18,1）原位运算（in-place),输入到存储器后的运算结果仍存放在同一存储器中,三、按时间抽取FFT算法的特点,单元A(0),单元A(1),暂存器R,第m级，k、j行,19,2）倒位序,000,0

5、,0,000,001,1,4,100,010,2,2,010,011,3,6,110,100,4,1,001,111,7,7,111,110,6,3,011,101,5,5,101,自然序,倒位序,N=8,20,整序重排,n 0 1 2 3 4 5 6 7,n 0 4 2 6 1 5 3 7,先自然顺序输入序列，再码位倒读变址： (1)n=n则数据不换 (2)nn则数据对调 (3)nn则调换，保证调换只进行一次,21,3）蝶形运算, 对N=2L点FFT，第m级运算，两节点距离：2m-1, 旋转因子,对于系数r：前一级取后一级序号的偶部分 最后一级r=0,1,N/2-1,22,内 容 小 结,D

6、IT-FFT算法原理、计算量、特点, 田,matlab关注：,fft 函数傅立叶变换,23,四、按频率抽取的基-2 FFT算法Decimation-in-Frequency(DIF-FFT),如何分解 如何重构 特点比较,24,时域x(n)按n前后分组，频域X(k)按k偶奇分组 前半子序列x(n),0nN/2-1; 后半子序列x(n+N/2),0nN/2-1; 例：N=8时，前半序列为：x(0),x(1),x(2),x(3); 后半序列为：x(4),x(5),x(6),x(7);,1、算法原理,设序列点数 N = 2L ，L为整数。,25,26,按k的奇偶将X(k)分成两部分：,27,令,X1

7、(2r)和X2(2r+1)分别是x1(n)和x2(n)的 N / 2点DFT， 记为,时域前后、频域偶奇分组,28,2、蝶形信号流图,支路值支路起始节点支路系数 节点值所有输入支路值之和,29,DIF-FFT一次分解,前半部分,后半部分,30,N /2仍为偶数，进一步分解：N /2 N /4,31,32,同理：,其中：,33,DIF-FFT二次分解,逐级分解，直到2点DFT,34,N=8 的 DIF-FFT 蝶形图,35,3、DIF-FFT的特点,1）原位计算,输入到存储器后的 运算结果仍存放在 同一存储器中,2）蝶形运算, 对N=2L点FFT，第m级运算，两节点距离：2L-m, 旋转因子,3

8、6,4、DIT与DIF的异同,基本蝶形不同,DIT: 先复乘后加减,DIF: 先减后复乘,运算量相同,都可原位运算,DIT和DIF的基本蝶形互为转置 比较图4-5和图4-18,DIT是时域不断奇偶，DIF是频域不断奇偶,37,内 容 小 结,DIT-FFT：时域偶奇、频域前后分组 DIF-FFT：时域前后、频域偶奇分组, 田,38,五、IFFT算法与FFT应用,39,1、利用FFT计算IFFT的思路,比较,40,(1) DIT-FFT改为IFFT时，输入由x(n)X(k),原来按 x(n)偶奇分组的时间抽取法FFT，现在就变成了按X(k) 偶奇抽取，所以称 DIF-IFFT (2) 同样，DI

9、F-FFT改为IFFT时，称 DIT-IFFT,命名规则,41,N=8 DIF-IFFT,42,N=8 DIT-IFFT,43,2、谱分析,定义如下与X(k)相关的序列,振幅谱,相位谱,功率谱,例：x(n)=1,0,2,1，进行谱分析,X(k)=4，-1+j，2，-1-j,44,1）. 线性卷积的FFT算法,需运算量：,若M点x(n)，N点h(n)，则线性卷积y(n),3、FFT应用,45,FFT法：以圆周卷积代替线性卷积,1) H(k)= FFTh(n) L/2*log2L,4) y(n)= IFFTY(k) L/2*log2L,3) Y(k)= H(k)X(k) L,2) X(k)= FF

10、Tx(n) L/2*log2L,L,46,2）. 频谱泄漏,改善方法：,时域截短，使频谱变宽拖尾,1）调整窗口形状,2）缓慢截短,P.136,47,4、N为合数的FFT算法,若 N 2L，两种方法处理：, 序列补零至2L，频谱取样点增加但不影响形状, 采用任意基数的FFT：设N=pq，可将N点DFT分解 为p个q点的DFT。,例：N=12=34，x(n)分成3组，每组4个值,x(0) x(3) x(6) x(9),x(1) x(4) x(7) x(10),x(2) x(5) x(8) x(11),p=3组,x(n)分为p组： x(pr)、x(pr+1)、x(pr+2) r=0,1,2,3,P.139,48,49,运算步骤,分解x(n)为p个q点序列：x(pr+l ) 求x(n)的p个q点DFT 若q能继续分解，则返回第1步，求更小的DFT 逐次分解并组合得到最后的N点DFT,50,频谱通