西安电子科技大学：《数字信号处理》课程教学资源（PPT课件）第四章 快速傅立叶变换（FFT）

第四章快速傅立叶变换(FT 主要内容 DFT的问题及解决途径 FFT的原理和复杂性 按时间抽取的FFT算法 按频率抽取的FFT算法 烹散傅立叶反变换的快速算法 ·线性调频z变换( chirp-z变换)算法 线性卷积的FFT算法

第四章 快速傅立叶变换(FFT) 主要内容： •DFT的问题及解决途径 •FFT的原理和复杂性 •按时间抽取的FFT算法 •按频率抽取的FFT算法 •离散傅立叶反变换的快速算法 •线性调频z变换（chirp－z 变换）算法 •线性卷积的FFT算法

DFT算法存在的问题 >DFT直接计算存在的问题: 设x(n)为N点有限长序列,正反变换计算量相同 X(k)=DFTIx(n]=>x(n)Wnk, 0≤k≤N-1 x(n)=DDF7[X(k)=∑X(kN,0≤n≤N-1 例N=4:X(k)=∑x(nW4=2x0)W+x(4+x(2W24+2x3)W X(0)=x(0)W40+x(1)W。+x(2)W40+x(3)W4 X(1)=x(0)W4+x(1)W4+x(2)W42+x(3)W4 X(2)=x(0)W+x(1)W42+x(2)W4+x(3)W 一X(3)=x(0W4+x(1)4+x(2)40+x(3)4

DFT算法存在的问题 ➢DFT直接计算存在的问题： 设x(n)为N点有限长序列，正反变换计算量相同       − = − − = = =   = =   1 0 1 0 ( ) 0 n N -1 1 ( ) ( ) ( ) ( ) ( ) 0 k N -1 N k n k N N n n k N X k W N x n IDFT X k X k DFT x n x n W ， ， ( ) ( ) (0) (1) (2) (3) 3 4 2 4 4 0 4 3 0 4 k k k k n n k X k x n W x W x W x W x W    = = = + + + (3) (0) (1) (2) (3) (2) (0) (1) (2) (3) (1) (0) (1) (2) (3) (0) (0) (1) (2) (3) 9 4 6 4 3 4 0 4 6 4 4 4 2 4 0 4 3 4 2 4 1 4 0 4 0 4 0 4 0 4 0 4 X x W x W x W x W X x W x W x W x W X x W x W x W x W X x W x W x W x W = + + + = + + + = + + +  = + + + 例N＝4：

DFT算法存在的问题 >N点DFT的直接计算量 1.乘法次数: 对每一个k:N次复数乘法【4N次实乘和2N次实加】 1个复乘等于4四个实乘和2个实加;(+c+1=c-M+b+m 了N个k 次复数乘法 2.加法次数: ·对每一个k:N-1次复加【2(N-1)次实加】 N个k:N(N-1)次复加 即和N成正比 例N=1024,则有1048576次复乘(约400万次实乘),假 定运算器的指令速度为100MIPS,则计算时间大约为4秒

➢N点DFT的直接计算量: DFT算法存在的问题 1. 乘法次数： 对每一个k：N次复数乘法【4N次实乘和2N次实加】 1个复乘 等于 4 四个实乘和 2 个实加； N个k： 次复数乘法 2. 加法次数： • 对每一个k： N－1次复加【2（N－1）次实加】 • N个k： N（N－1）次复加 即和 成正比。 2 N 例N＝1024，则有1048576次复乘（约400万次实乘），假 定运算器的指令速度为100MIPS，则计算时间大约为4秒。 2 N (a + jb)(c + jd) = ac − bd + j(cb + ad)

DFT算法存在的问题 改进办法: 1.旋转因子WW的对称性和周期性 (1)对称性:W+N2)=-W (2)周期性:W+Nn=W=W(+N (3)可约性:W=Wm=WWm 例:求当N=4时,X(2)的值 X(2)=∑x(m)W2n=xOW4+x(1)42+x(2)W4+x(3)W [x(O)+x(2W4+[x(1)+x(3)J2(周期性) [x(O)+x(2)[x(1)+x(3)}W4(对称性) 通过合并,使乘法次数由4次减少到1次,运算量减少

DFT算法存在的问题 ➢改进办法： 1. 旋转因子 WN m 的对称性和周期性 例：求当N＝4时，X(2)的值 （1) 对称性： （2) 周期性： k N k N WN = −W ( + / 2) n N k N kn N k N n WN W W ( + ) ( + ) = = {[ (0) (2)] [ (1) (3)]} ( ) [ (0) (2)] [ (1) (3)] ( ) (2) ( ) (0) (1) (2) (3) 0 4 2 4 0 4 6 4 4 4 2 4 0 4 3 0 2 4 ＝ － 对称性 周期性 x x x x W x x W x x W X x n W x W x W x W x W n n + + = + + + =  = + + + = 通过合并，使乘法次数由4次减少到1次，运算量减少。 kn m N m mkn mN kn WN W W / （3)可约性: = = / • • • • 0 WN 2 N WN k WN k −WN k N 2 0

DFT算法存在的问题 N点DFT的复乘次数与N的平方成比例,显然N较小时 乘法次数大大减少。利用上述旋转因子的特性,可以 将有些项合并,并将DFT分解为短序列,从而降低运 算次数,提高运算速度。 1965年,库利(ooey)和图基( Tukey)首先提出FT算 法。对于N点DFT,仅需(N②2)og2N次复数乘法运算。 例如N=1024=210时,需要(1024/2)og2210 =512*10=5120次。5120/1048576=488%,速度 提高20倍。 ·分为时域抽取(DIT)和频域抽取(DIF)两大类

DFT算法存在的问题 • N点DFT的复乘次数与N的平方成比例，显然N较小时 乘法次数大大减少。利用上述旋转因子的特性，可以 将有些项合并，并将DFT分解为短序列，从而降低运 算次数，提高运算速度。 • 1965年，库利(cooley)和图基(Tukey)首先提出FFT算 法。对于N点DFT，仅需(N/2)log2N 次复数乘法运算。 例 如 N=1024=2 10 时 ， 需 要 (1024/2)log2 2 10 =512*10=5120次。5120/1048576=4.88% ，速度 提高20倍。 • 分为时域抽取（DIT）和频域抽取（DIF）两大类

按时间抽取的基一2FFT算法 以N=4为例 X()=x0)+x(1)+x2)+x(3)=x(0)A(2)+[x()Bx(3 X)0x0)+x(wy-x(2)-2x3w=x0)c(2)+Wx()x(3 N2)=x00)+2301 X(3)=3(0)-=x()1-x2)+x(3)4=x(0)c(2)-W{()Dx(3) 运算流图x(O X(0 x(2) ACB X(1 X(2) D w x(3) X(3) 1 王

按时间抽取的基－2 FFT算法 以 N＝4为例       (3) (0) (1) (2) (3) (0) (2)  (1) (3) (2) (0) (1) (2) (3) (0) (2) (1) (3) (1) (0) (1) (2) (3) (0) (2) (1) (3) (0) (0) (1) (2) (3) (0) (2) (1) (3) 1 4 1 4 1 4 1 4 1 4 1 4 X x x W x x W x x W x x X x x x x x x x x X x x W x x W x x W x x X x x x x x x x x = − − + = − − − = − + − = + − + = + − − = − + − = + + + = + A + + B A B C D C D 运算流图 x(0) x(2) x(1) x(3) A -1 C -1 B D 1 W4 X (0) X (2) -1 X (1) X (3) -1

按时间抽取的基=2FFT算法 算法原理 (一)N2点DFT 1.先将ⅹ(η)按n的奇偶分为两组作DFT设N=24(L大于 等于2),不足时,可补些零,这样一个N点的DFT分 解为两个N/2点的DFT。 X(k)=∑x(m)W=∑x(mW+∑x(n)W n为偶数 n为奇数 ∑x(2r)+∑x(2r+1)W +1)k O ∑x(21)形+形∑x(2r+ = E(+wFc

按时间抽取的基－2 FFT算法 一、算法原理 1. 先将x(n)按n的奇偶分为两组作DFT,设N=2 L （L大于 等于2），不足时，可补些零，这样一个N点的DFT分 解为两个N/2点的DFT。 ( ) ( ) (2 ) (2 1) (2 ) (2 1) 1 0 2 1 0 2 1 0 (2 1) 1 0 2 2 2 2 2 E k W F k x r W W x r W x r W x r W k N r r k N k N r r k N r r k N r r k N N N N N = + = + + = + +     − = − = − = + − =    − = − = − = = = + 1 0 1 0 1 0 ( ) ( ) ( ) ( ) N n n N n n kn N kn N N n kn X k x n WN x n W x n W 为偶数 为奇数 (一)N/2点DFT

按时间抽取的基一2FFT算法 2.分解说明 E(k)=∑x(2)W0≤k≤ N F()=∑x(2n+1)W0≤k≤ E(k)和F(k)均为N2点的DFT,均以M2为周期; 因W是以N为周期,故X(k)是以N为周期 X(k)=E(k)+WF(k)只能确定出X(k)的k￡,…,个1 值,即前一半的结果

2. 分解说明： 1 2 ( ) (2 ) 0 1 0 2 2 =   − − = N E k x r W k N r r k N 1 2 ( ) (2 1) 0 1 0 2 2 =  +   − − = N F k x r W k N r r k N • E(k)和F(k)均为N/2点的DFT，均以N/2为周期； • 因W 是以N为周期，故X(k)是以N为周期； • X(k)=E(k)+W F(k)只能确定出X(k)的k= 个 值，即前一半的结果。 0,1, , 1 2 − k  N N k N 按时间抽取的基－2 FFT算法

按时间抽取的基-2FFT算法 3.Xk)后一丰的确定 由旋转因子的周期性(k+y)mmk E(2+k)=x(2)”=∑x(2)Wy=E(k) 同理:F( n+k)=F(k) 2 这就是说,E(k)和F(k)的后一半分别等于其前一半的值。 W(+k)=WWk=一Wk X(k+)=Ek+)+WF(k+)=E(k)-WF(k)0≤k≤-1 可见X(k)的后一半,也完全由E(k和F(k)的前一半确定。 即N点的DFT可由两个N/2点的DFT来计算

按时间抽取的基－2 FFT算法 3. X(k)后一半的确定 由旋转因子的周期性： r k rk N N WN W 2 2 2 ( ) = + ) (2 ) (2 ) ( ) 2 ( 1 0 ( ) 1 0 2 2 2 2 2 k x r W x r W E k N E N N N N N r r k r k r + = = = − = + − = 这就是说，E(k)和F(k)的后一半分别等于其前一半的值。 同理： ) ( ) 2 ( k F k N F + = k N k N N k WN W W W N N = = − +2 2 ( )  1 2 ) ( ) ( ) 0 2 ) ( 2 ) ( 2 ( 2  + = + + + = −   − + N E k W F k k N W F k N E k N X k k N k N N 可见,X(k)的后一半，也完全由E(k)和F(k)的前一半确定。 即N点的DFT可由两个N/2点的DFT来计算

。按时间抽取的基一2FFT算法 4.蝶形运算一一流图表示 由E(K)、F扆示)的运算是一种特殊的运算-碟形运算 X(K=E(k)+WNF(k) X(k+)=E(k)-WF(k)(k=01…,-1 2 蝶形运算流图(N2个蝶形) E(k) X(k FlK)wk X￥(-+k

4. 蝶形运算－－流图表示 蝶形运算流图（N/2个蝶形): -1 X (k) ) 2 ( k N X + E(k) F(k) k WN ) ( ) ( ) 2 ( ( ) ( ) ( ) E k W F k N X k X k E k W F k k N k N + = − = + ( 0,1, , 1) ( 0,1, , 1) 2 2 = − = − N N k k   由E(k)、F(k)表示X(k)的运算是一种特殊的运算-碟形运算 按时间抽取的基－2 FFT算法