数 理 着考处 由式(64.3)知道,一个N点序列X(k)=X(k)R(k)的IDFT为 x(n n=0,1,2,…,N-1 (72.3) 由式(723)可知,IDFT正是将频域的N点映射成时域的N点 的一种映射关系,即 (0) X(0) X(1) (72.4) x(N-1) WW(N-D)..WN-1(N-D LX(N-1) 由式(722)可知,计算一个(k)值需要N次复数乘法及(N-1) 次复数加法,而一共有N个点,所以完成N个X(k)的运算,总共需要 N2次复数乘法及N(N-1)次复数加法
1 0 00 0 0 1 ( 1) 0 ( 1) ( 6.4.3 ( ) ( ) ( ) 1 ( ) ( ) , 0,1,2, , 1 (7.2.3) 7.2.3 (0) (1) 1 ( 1) N N nk N k N N N N NN N N N N N N N Xk XkR k xn X kW n N N N N x WW W x WW W N x N WW W − − = − −− −− − = = =− ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ − ∑ IDFT IDFT " " " # # #% # " 由式（ ）知道，一个 点序列 的 为 由式（ ）可知， 正是将频域的 点映射成时域的 点 的一种映射关系，即 1)( 1) 2 (0) (1) (7.2.4) ( 1) 7.2.2 ( ) ( 1) ( ) ( 1) N X X X N Xk N N N N X k N N N − − ⎡ ⎤⎡ ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦ − ⎣ ⎦ − − # 由式（ ）可知，计算一个 值需要 次复数乘法及 次复数加法，而一共有 个点，所以完成 个 的运算，总共需要 次复数乘法及 次复数加法
数 理 着考处 考虑到 (1)计算一次复数乘法,需要用四次实数乘法及二次实数加法 (2)计算一次复数加法,需要用二次实数加法。 (3)计算单个X(k)值,需要4N次实数乘法及2N+2(N-1)=2(2N-1) 实数加法。则完成N个Y(k)的运算,总共需要的实数乘法次数M和 实数加法次数M分别为 (1)M=4N2; (2)Mn=2N(2N-1) 因此,直接计算DFT,随着N的增加,其计算量是惊人的
2 1 2 3 ( ) 4 2 2( 1) 2(2 1) ( ) 1 4 2 2 (2 1) c a c a Xk N N N N N Xk M M M N M NN N + −= − = = − DFT 考虑到 （）计算一次复数乘法，需要用四次实数乘法及二次实数加法。 （ ）计算一次复数加法，需要用二次实数加法。 （ ）计算单个 值，需要 次实数乘法及 实数加法。则完成 个 的运算，总共需要的实数乘法次数 和 实数加法次数 分别为 （） ； （ ） 。 因此，直接计算 ，随着 的增加，其计算量是惊人的
F压数 理 22、改进的途径 着考处 利用DFT中W的下述性质,可以减小DFT的运算量 (1)W的对称性:(Ww)=W 2)W的周期性:Wm=W(+Nk=形mk+N) (3)W的可约性:W=Wm,W=WWm 显然有:WmN-8)=W(N-m)=W,WN2=-1,W(+N2)=-Wk 综上所述 (1)利用W的上述特性,可使DFT运算中的有些项可以合并; 2)利用W的对称性、周期性和可约性,可以将长序列的DFT 分解成短序列的DFT。 快速傅里叶变换(FFT)算法正是基于这样的基本思路发展 起来的。快速傅里叶变换的基本算法可以分为两类,即按时间 抽选(DT)法,按频率抽选(DIF)法
() () () () 2 ( 2) 1 ( ) 2 3 , 1 1 nk N nk nk nk N N N nk nk n N k n k N N N N N nk nk nmk nk nk m N N mN N N m n N k N n k nk N k N k N N NN N N nk N W W WW W WW W W WW WW W W WW W W W ∗ − + + − −− + = = = = = = = =− =− DFT DFT DFT 利用 中 的下述性质，可以减小 的运算量。 （） 的对称性： （ ） 的周期性： （ ） 的可约性： 显然有： ， ， 综上所述 （）利用 的上述特性，可使 运算中的有 2 ) nk WN DFT DFT FFT DIT DIF 些项可以合并； （ ）利用 的对称性、周期性和可约性，可以将长序列的 分解成短序列的 。 快速傅里叶变换（ 算法正是基于这样的基本思路发展 起来的。快速傅里叶变换的基本算法可以分为两类，即按时间 抽选（ ）法，按频率抽选（ ）法。 2、改进的途径
数 理 2473 Goertzel算法 着考处 利用W因子的周期性,1958年 Goertzel提出了一种 DFT的快速算法,我们称为 Goertz算法 1、将DFT运算化为线性卷和运算 考虑到x(n)=x(n)R(n)及W=(e12mN)M=e2 若定义 ys(n)=x(n)*WN u(n)=2x(m)R(mW(n-m u(n-m) ∑x(m)R、(mWx(m (73.1)
7.3 Goertzel算法 1958 nk WN Goertzel DFT Goertzel 利用 因子的周期性， 年 提出了一种 的快速算法，我们称为 算法。 2 2 ( ) ( ) () () () ( ) 1 () () () ( ) ( ) ( ) ( ) ( ) (7.3.1) Nk j N Nk j k N N nk n m k kN N N m n n mk N N m xn xnR n W e e y n x n W u n x m R mW u n m x m R mW − −− π π +∞ − − − =−∞ − − =−∞ = == = =∗ = − = ∑ ∑ 考虑到 及 若定义 1、将DFT运算化为线性卷和运算
数 理 着考处 由式(7.3.1)可得 y(N)=∑x(m)R(Om)Wm=∑x(m)R(mW n=-00 n=-0 ∑x(mWW=∑x(nx"=X(k) m=0 即X(k)=y(n)N 73.2) 由式(732)可知,Y(k)正是有限长序列x(m)=x(m)R(n)作用 于单位冲激响应为h(n)=W"u(m的线性位不变系统时,其系统零 状态响应y(n)在n=N位的输出值 考虑到h(n)=W"u(mn),则描述线性位不变系统的转移函数为 H(二) 1-Wx=,1<=|s (73.3) 因此,完成X(k的一阶复递推计算的信流图,如图7.3.所示
( ) 1 1 0 0 7.3.1 () () () () () ( ) () () ( ) ( ) (7.3.2) 7.3.2 ( ) N N N mk mk k N N N N m m N N mk nk N N m n k nN y N x m R mW x m R mW x mW x nW X k Xk y n X k − − =−∞ =−∞ − − = = = = = = == = ∑ ∑ ∑ ∑ 由式（ ）可得 即 由式（ ）可知， 正是有限长序列 1 () () () () () ( ) () () 1 ( ) , 1 (7.3.3) 1 ( ) 7.3.1 N nk N k nk N k N xn xnR n hn W un yn n N hn W un Hz z W z X k − − − − = = = = = < ≤∞ − 作用 于单位冲激响应为 的线性位不变系统时，其系统零 状态响应 在 位的输出值。 考虑到 ，则描述线性位不变系统的转移函数为 因此，完成 的一阶复递推计算的信流图，如图 所示