[工学]离散时间信号处理课件第1章DFT的快速算法.pdf

第1章 DFT的快速算法 1. 1 FFT算法（基于抽选） 1．1．1 基2FFT：DIT和DIF 1．1．2 混合基（包括任意基）FFT 1．1．3 分裂基（组合基，SRFFT ） 1．2 GOERTZEL （戈泽尔）算法 适用于计算部分X[k] ，是直接法的一半运算量 1．3 CHIRPZ （线性调频）变换算法（CTA，CZT） 适用于任意个X[k] ，任意频率点开始，任意频域取样间隔 第1章 DFT的快速算法 N −1 X [k ] ∑x [n ]W kn 0 ≤k ≤N −1 N n 0 1 N −1 −kn ≤ ≤ − x[n ] ∑X [k ]WN 0 n N 1 N k 0 kn −j 2πkn / N −jωn W e e | , k 0,..., N −1 N ω 2πk / N W−kn ej 2πkn / N ejωn | , k 0,..., N −1 N ω 2πk / N 直接计算运算量： 复数乘法：N2 （4实乘+2实加） 复数加法：N （N-1） （2实加） 实数乘法：4N2 2 实数加法：4N -2N 1.1 FFT算法（基于抽选） 1.1.1 基2FFT：DIT和DIF N 2m 1.1.1 1.DIT 第一次分解 N −1 X [k ] ∑x [n ]W kn 0 ≤k ≤N −1 N n 0 N / 2 −1 N / 2 −1 ∑ x [2m ]W k 2 m =+ ∑ x [2m +1]W k (2 m +1) N N m 0 m 0 令 g [m ] x [2m ] 0 =≤m ≤N / 2 −1 h[m] x[2 m 1] 0 m N / 2 1 + ≤ ≤ − N / 2 −1 N / 2 −1 则 X [k ] ∑ g [m ]W km