第四章快速傅立叶变换(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算法