第4章快速傅立叶变换(FFT) 4.1引言 4.2基2FFT算法 4.3进一步减少运算量的措施 4.4其他快速算法简介 Back
第4章 快速傅立叶变换（FFT） 4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 其他快速算法简介
第4章快速傅里叶疫换FT) 时域抽取法基2FFT基本原理(DIT-FFT) 1.先将x(n)按n的奇偶分为两组作DFT,设N=2M,这样 有： x2）=x6r=0,1,-1 n为偶数时： x2r+10=xr=0,1,-1 n内熟时DFxm=∑m)W n-0N-1 X(k)=Σx(n)wW+Σx(n)W n=0(n为偶数) n=0(n为奇数) N=】 X(k)=∑xr)W+W∑x,r)W=X(k)+WX,(k) X(k+)=x,()-x() k=0,1,.,岁-1
第4章 快速傅里叶变换(FFT) (2 1) ( ), 0,1, , 1 (2 ) ( ), 0,1, , 1 2 2 1 2 + = = − = = − N N x r x r r x r x r r 1.先将x(n) 按n的奇偶分为两组作DFT,设N=2M , 这样 有: n为偶数时: n为奇数时: 时域抽取法基2FFT基本原理（DIT-FFT） − − = = 1 0 ( ) [ ( )] ( ) N n nk n WN X k DFT x n x X(k) x (r)W W x (r)W X (k) W X (k) k N r k r k N r r k N N N N 1 2 1 0 2 1 0 1 2 2 2 2 = + = + − = − = − = − = = + 1 0 1 0 ( ) ( ) ( ) N n N n nk N nk X k x n WN x n W (n为偶数) (n为奇数) ) ( ) ( ) 0,1, , 1 2 (k 1 2 2 = − = − k N X k WN X k k N X ＋
第4章快速傅立叶变换 (FFT) 4.蝶形运算 1次复乘2次复加 X(k)=X1(k)+W2(k)前一半k=0,1,2. X(k)=X1(k)-WX2(k)后一半k=0,1,2. 实现上式运算的流图称作堞形运算 (N/2个蝶形) X(k) Xk)=X()+WX(k)(前一半) X2(k) W X+)=X,()-WX,()(后一半)
实现上式运算的流图称作蝶形运算（N/2个蝶形) 4.蝶形运算 1 2 ( ) ( ) ( ) k 0,1,2 1 2 ( ) ( ) ( k 0,1,2 1 2 1 2 = − = − = + = − N X k X k W X k N X k X k W X k k N k N 后一半 ）前一半 X(k) X (k) W X (k) (前一半) k = 1 + N 2 ) ( ) ( )(后一半) 2 ( 1 2 k X k W X k N X k + = − N 1 1 1 1 -1 ( ) 1 X k ( ) 2 X k k WN 1次 复乘2次复加 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换 (FFT) 4+BC D A-BC 图4.2.1蝶形运算符号
图4.2.1 蝶形运算符号 C A B A＋ BC A－ BC 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) X(0) X(0) 6(0)=x1(0)=x(04 点 ,(四)=x(2)=x48 DFT 四 X(1) x(0)=x(四=x(2)分 X四 X(2 七0=付=6时 X山旺 X③ 00n漪 -1 x0)=0)=10 X(0 X,0W型 点 X5()=x2(2)=x(⑤)w X四 X,1 x60)=x2)=x3) &,0咽 甜狗 HN X四 x6()=x23)=x(7) ,③)W
(0) (0) (1) 5 5 x = x = x (1) (2) (5) 5 2 x = x = x (0) (1) (3) 6 2 x = x = x (1) (3) (7) 6 2 x = x = x (0) (0) (0) 3 1 x = x = x (1) (2) (4) 3 1 x = x = x (0) (1) (2) 4 1 x = x = x (1) (3) (6) 4 1 x = x = x (3) (2) (1) (0) 1 1 1 1 X X X X (3) (2) (1) (0) 2 2 2 2 X X X X X(0) X(4) 0 WN X(1) X(5) 1 WN X(2) X(6) 2 WN X(3) X(7) 3 WN -1 -1 -1 -1 (1) (0) 3 3 X X (1) (0) 4 4 X X 0 WN 2 WN -1 -1 (1) (0) 5 5 X X (1) (0) 6 6 X X 0 WN 2 WN -1 -1 0 WN -1 点 DFT 4 N 点 DFT 4 N 点 DFT 4 N 点 DFT 4 N 0 WN -1 0 WN -1 0 WN -1 第4章 快速傅立叶变换（FFT）