第四章快速傅立叶变换(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）两大类