山东理工大学：《数字信号处理》课程教学课件（讲稿）第4章 快速傅立叶变换（FFT，2/2）

第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）

第4章快速傅立叶变换(FFT) A(0) 4(0) 4(0) 4(0) x(0) X0) 4(1) A(1) A(1) x(4) W& X1) A(2) A(2) A(2) x(2) n X2) A(3) A3) A(3) x(6 w& 你 X3) A(4) A(4) A(4) x(1) X4) A(5) A(5) A(5) x(5) w& X5) A(6) A(6) A(6 x(3) wx X6) A(7) A(7) A(7) x(7) A7) w& wk X(T) 图4.2.4N点DT一FFT运算流图N=8)

图4.2.4 N点DIT―FFT运算流图(N=8) W N 0 W N 1 W N 2 W N 3 W N 0 W N 2 W N 0 W N 2 W N 0 W N 0 W N 0 W N 0 x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) 第4章 快速傅立叶变换（FFT）

第4章快速傅立叶变换(FFT) 4.2.3 DIT一FFT算法与直接计算DFT运算量的比较 )每一级运算都需要N/2次复数乘和N次复数加（每个蝶 形需要两次复数加法)。所以，M级运算总共需要的复 数乘次数为 N N CM= .M= 2 2 C4=N·M=Nlog2N 例如，N=210=1024时 N2 1048576 204.8 倍 (N/2)log,N 5120

4.2.3 DIT―FFT算法与直接计算DFT运算量的比较 ⚫ 每一级运算都需要N/2次复数乘和N次复数加(每个蝶 形需要两次复数加法)。所以，M级运算总共需要的复 数乘次数为 2 2 2 2 log log =  = =  = M A N N C M N C N M N N 复数加次数为 例如，N=2 10=1024时 2 2 1048576 204.8 ( / 2)log 5120 N N N = = 第4章 快速傅立叶变换（FFT） 倍

第4章 快速傅立叶变换(FFT) 1024 直接计算 (000江人)效大 512 256 FFT算法 128 64128256 512 1024 N(取样点数) 图4.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线

图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线 第4章 快速傅立叶变换（FFT）

L=1时 W状=WW4=W J=0 L=2时 WR-WN/2-W3 J=0,1 L=3时 W状-W入=W J=0,1,2,3 对N=2M的一般情况，第L级的旋转因子为 WW=W,J=0,1,2,24-1-1 2=2M×2-M=N.2-M W=W24w=W2w,J=0,2,21-1 p=J.2M-L

对N=2M的一般情况，第L级的旋转因子为 0, 1, 2, 3 3 0, 1 2 0 1 2 / 2 2 / 4 2 = = = = = = = = = = = = W W W J L W W W J L W W W J L J J N p N J J N p N J J N p N L L L 时 时 时 2 1 2 0 1 2 2 1 2 , , , , , M L L M P J J L N N N M L W W W J p J − −  −  − = = =  − =  1 2 , 0,1,2, ,2 1 2 2 2 2 − − − = =  − =  =  L p J L N L M L M L M W W J N

4.编程思想及程序框图 开后 送入x(n),M 三层循环的功能是： N=2 最外层（大）循环完成M次迭代过程即 L=1,2,M级，即每次循环为一级。 L=1M 中间（中）循环完成在一级中共有B个不 B←24-1 同因子WNk对应2ML个蝶形运算，同一个旋 J=0B-1 P=M-LJ 转因子对应着相隔2L点的2ML个蝶形。 k=J,N-1,2 最里层（小）循环完成同一个旋转因子 X(k)X(k)+(k+B)W X(k+B)(k)-X(k+B)W 不同蝶形的运算；其循环体为一个蝶形运 算。 输出 图4.2.6DIT一FFT运算和程序框图

4. 编程思想及程序框图 图4.2.6 DIT―FFT运算和程序框图 送 入x(n)，M N＝ 2 M L＝ 1 , M Ｊ＝ 0 , B－ 1 P＝ 2 M －L J k＝ J , N－ 1 , 2L p N p N X k B X k X k B W X k X k X k B W ( ) ( ) ( ) ( ) ( ) ( ) +  − +  + + 输 出 B 2 L－ 1 ◼三层循环的功能是： 最外层（大）循环完成M次迭代过程即 L=1,2, .,M 级，即每次循环为一级。 中间（中）循环完成在一级中共有B个不 同因子WN k对应2 M-L个蝶形运算，同一个旋 转因子对应着相隔2 L点的2 M-L个蝶形。 最里层（小）循环完成同一个旋转因子 不同蝶形的运算；其循环体为一个蝶形运 算