张旭东（清华大学）数字信号处理：第3章 FFT.pptVIP

CZT在Z平面上的变换 路径是一条螺旋线 决定CZT的起点； 决定变换路径如何倾斜 决定变换的步长。 信号的点数 N 和变换路径的点数 M 可以不相等。 W0 φ0 θ0 A0 φ0 若：θ0=0，W0=A0=1， φ0= ， M=N 即是DFT。 3.利用Bluestein算法计算CZT： f(n) h(k-n) * 3.1 引言： 1. DFT运算量的估计 设x(n)为复序列，则计算每一X(k)需 N次复乘 （N-1）次复加 完成一次DFT计算需 （k=0,1,2??????N-1） 若用实数乘法统计：复乘运算：(a+jb)(c+jd)=(ac-bd)+j(ad+bc) =[(a-b)d+a(c-d)]+j[(a-b)d+b(c+d)] 完成一次DFT计算运算量为： 2. 提高DFT运算效率途径 利用 的性质：周期性、可约性、共轭对称性 把长序列化解成短序列进行计算，通过叠代运算来减少 DFT的运算量。 N2次复乘 N（N-1）次复加 ∝ N2 实乘：4N2 实加：2N(N-1)+2N2=4N2-2N (3次实乘，5次实加) 3. 基（Radix）的定义：在FFT运算中最小DFT单元序列的长 度称为基； 4. FFT按分解方法不同可分为： Radix—2 (N=2m) 时间抽选(DIT)—Decimation In Time 频率抽选(DIF)— Decimation In Frequency ?实质性乘法：指除去(±1), (±j)之外所需的乘法； 例：3点DFT（用于Radix—3） (Butterfly Computation) 三点信号流图： x(0) X(0) x(1) X(1) x(2) X(2) 5.高效算法标准： ? 乘、加次数最少； ? 算法结构的简单程度；（取指方便） ? 算法占用的存储量少； 3.2 时间抽选FFT算法(Radix 2—DIT—FFT) —N=2m 1.算法原理：时间抽选是把n序号按奇、偶分解 例：N=8=23 x(n)= （ 这一步骤也称为信号的多相分解） 0, 2, 4, 6=x(2r)=e(r) E((k))N/2 1, 3, 5, 7=x(2r+1)=f(r) F((k))N/2 (0≤r≤N/2) (0≤k≤N-1) ? 先做二个N/2点的DFT——需2×(N/2)2次乘法； ? 再做(N/2)个2点的DFT——勿需任何乘法； ? 级间需(N/2)个旋转因子(Twiddle—Factor FFT Algorithm)； ? 经第一次分解后，总共需复乘次数： mc= 2×(N/2)2+N/2=N/2(N+1) E(0) E(1) E(2) E(3) F(0) F(1) F(2) F(3) 再次分解如下图 完整的8点流图 x0 x1 x2 x3 2.