李洁《数字信号处理》20058 数字信号处理 Digital Signal processing 第四章快速 Fourier变换(FFT 主讲教师:李洁 形影x去 首先,FFT并不是一种新的 Fourier变换,只是DFT的一种快速算法 X(k)=DFx(m=2∑xmHk=01…,N-1,we 直接计算D由W如的周期性和对 称性,会使计算过程出现许多冗余 直接计算DFT总共需要N次 复数乘法和N(N-1)次复数o 加法! FTRadix-2 FT∝N FFT o Nlog2N 1281638448 102410485765120 李洁一《数字信号处理 2|30 Digital Signal processing Jie Li 2005
李洁《数字信号处理》2005® Digital Signal Processing__Jie Li 2005® 1 数字信号处理 第四章 快速Fourier变换(FFT) Digital Signal Processing 主讲教师：李洁 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 2 / 30 0 500 1000 1500 2000 0 10 20 30 40 Number of samples, N Number of Operations DFT ∝ N2 FFT ∝ N log2N 直接计算DFT DFT 由于WN kn 的周期性和对 称性，会使计算过程出现许多冗余 直接计算DFT总共需要N2次 复数乘法和N（N-1）次复数 加法！ VERY BAD VERY BAD ! 首先，FFT并不是一种新的Fourier变换，只是DFT的一种快速算法。 ( ) [ ( )] ( ) 0,1, , 1 1 0 = = ∑ = − − = X k DFT x n x n W k N N n kn N L W8 0 W8 4 W8 2 W8 5 W8 6 W8 3 W8 7 W8 1 1024 1048576 5120 128 16384 448 32 1024 80 4 16 4 N DFT Radix-2
李洁《数字信号处理》20058 如果一台通用计算机的速度为平均每次复乘5s,每次复加0.5s,用它来计算 的DFTx(n)],问直接计算需要多少时间,用FFT运算需要多少时间 ①直接利用DFT计算:复乘次数为N2复加次数为N(N-1) ②利用FFT计算:复乘次数为 复加次数为Nog:N (1)直接计算 T=5×10×N=5x104×5122=1.31072s 复加所需时间 =0.5×10×N×(N-1)=0.5×10×512×(512 T-T1+T2=1.441536s 复乘所需时间 T=5×10×2N-5×10+×2912-0.012 复加所需时间 所T1=0.5×10×NogN=0.5×10×512512=0.00304 T=T+T:=0.013824s 李洁一《数字信号处理 3/ 影x去 4.2基2FF算法当当当N-2时,?? 1.H的特性怎神少D的计算量 周期性Wm+=e -(m+IN 对称性W=W"(W")=WW=-W果 可约性W=WmW=Wm 李洁一《数字信号处理 4l30 Digital Signal processing Jie Li 2005
李洁《数字信号处理》2005® Digital Signal Processing__Jie Li 2005® 2 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 3 / 30 例 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 4 / 30 §4.2 基2FFT算法 1. m 的特性 WN 周期性 2 2 j m lN j m ( ) m lN m N N We e W N N π π −+ − + = == 对称性 W8 0 W8 4 W8 2 W8 5 W8 6 W8 3 W8 7 W8 1 W160 W168 W164 W1610 W1612 W166 W1614 W162 W161 W16 W 3 165 W167 W169 W1611 W1613 W1615 怎样减少DFT的计算量？ W W W W W W m N N m N m N N m N N m N m N = = = − − − − + ( )* 2 可约性 W W W W nk m N m nk N mnk mN nk N / / = = 当 当 当N=2M时，？？？
李洁《数字信号处理》20058 2.时域抽取法基2FF基本原理 X(k)=DFx(m)=∑x(n)W如k=01…N-1 012345678910 x(r)=x(2r),r=0,2,3x1(k)=∑x)4,k=012,3 x4k)=∑x(r)H+, X(k)=∑xn)W=x0)W“+x(2)W+x(4W+x16)1+x(DW+x(3)W+x5)H1+x7W =(x(0)H“+x02)2+x(4)W“+x(6)W4)+W(x()W"+x(3)W+x5W+x7)W =(x(0)W“+x(2)W+x4)W“+x(6)W“)+“(x(D)W“+x3)W“+x(5H:+x7)W2 x(k)=x1(k)+W:(x3(k),k=0123 X(+4)=x1(k+4)+W(x2(k+4)=X1(k)-H,(x2(k),k=0123 5 影x去 蝶形 Butterfly 李洁一《数字信号处理 630 Digital Signal processing Jie Li 2005
李洁《数字信号处理》2005® Digital Signal Processing__Jie Li 2005® 3 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 5 / 30 2. 时域抽取法基2FFT基本原理 ( ) [ ( )] ( ) 0,1, , 1 1 0 = = ∑ = − − = X k DFT x n x n W k N N n kn N L W8 0 W8 4 W8 2 W8 5 W8 6 W8 3 W8 7 W8 1 0 1 2 3 4 5 6 7 8 9 10 n 0 N x(n) 1 ( ) (2 ), 0,1,2,3 x1 r = x r r = ( ) (2 1), 0,1,2,3 x2 r = x r + r = ( ) ( ) , 0,1,2,3 3 0 1 1 4 = ∑ = = X k x r k n kn W ( ) ( ) , 0,1,2,3 3 0 2 2 4 = ∑ = = X k x r k n kn W W W W W W W W W W k k k k k k k k n kn X k x n x x x x x x x x 7 8 5 8 3 8 1 8 6 8 4 8 2 8 0 8 7 0 8 ( ) = ∑ ( ) = (0) + (2) + (4) + (6) + (1) + (3) + (5) + (7) = W W kn j kn j kn kn e e 2 8 2 8 2 4 2 4 = = = − − π π ( ) ( ( )) ( (0) (2) (4) (6) ) ( (1) (3) (5) (7) ) ( (0) (2) (4) (6) ) ( (1) (3) (5) (7) ) 1 8 2 3 4 2 4 1 4 0 4 1 8 3 4 2 4 1 4 0 4 6 8 4 8 2 8 0 8 1 8 6 8 4 8 2 8 0 8 X k X k x x x x x x x x x x x x x x x x W W W W W W W W W W W W W W W W W W W k k k k k k k k k k k k k k k k k k k = + = + + + + + + + = + + + + + + + ( 4) ( 4) ( ( 4)) ( ) ( ( )), 0,1,2,3 ( ) ( ) ( ( )), 0,1,2,3 2 1 8 2 4 1 8 1 8 2 + = + + + = − = = + = + X k X k X k X k X k k X k X k X k k W W W k k k 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 6 / 30 蝶形 WN k X1(k) X1(k)+WN k X2(k) X1(k)-WN k X2(k) X2(k) Butterfly
李洁《数字信号处理》20058 X(0) N2点x1(1) X1(2) X(2) x(6) X1(3) X(3) x(1) 2点x2(1) X2(2) x(5) DFTX (3)wN 71 影x去 X X1(1) x(2) DFT X(① X2(0) X, (1 (3) 李洁一《数字信号处理 8|30 Digital Signal processing Jie Li 2005
李洁《数字信号处理》2005® Digital Signal Processing__Jie Li 2005® 4 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 7 / 30 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 8 / 30
李洁《数字信号处理》20058 李洁一《数字信号处理 9 影x去 4.DIT-FFT的运算规律及编程思想 I)原位计算 X(3) 李洁一《数字信号处理 10/30 Digital Signal processing Jie Li 2005 5
李洁《数字信号处理》2005® Digital Signal Processing__Jie Li 2005® 5 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 9 / 30 李洁 -- 《数字信号处理》 -- 第四章 快速Fourier Fourier变换 10 / 30 4. DIT-FFT的运算规律及编程思想 Ⅰ）原位计算