数 理 着考处 k 2 图733X(N-k)的二阶递推计算流图 由式(7.3.7)和式(7.3.16)可知,两个辅助系统的转移函数 H(=)相同,使得式(7.36)和式(7.3.15)描述的两个线性位不系 统转移函数H(=)极点相同,而零点互为共轭复数关系,因此 可以依据信流图7.32,利用(N-1)及(N)计算出X(k,即 X(K)=y M)=Y(M)WNJK(N-1) 7.3.17)
7.3.7 7.3.16 ˆ ( ) 7.3.6 7.3.15 ( ) 7.3.2 ( 1) ( ) ( ) ˆ ˆ ( ) ( ) ( ) ( 1) (7.3.17) ˆ ˆ k k k k k Nk H z H z y N y N Xk Xk y N y N Wy N − ==− − 由式（ ）和式（ ）可知，两个辅助系统的转移函数 相同，使得式（ ）和式（ ）描述的两个线性位不系 统转移函数 的极点相同，而零点互为共轭复数关系，因此， 可以依据信流图 ，利用 及 计算出 ，即
数 理 着考处 也可以依据信流图73.3,利用(N-1)及(N)计算出 Y(N-k,即 X(N-k)=(N)=j(N)-W(N-1) (73.18 式(7317)和式(73.18)表明,利用(N-1)及(N) 可同时计算出X(k)及X(N-k)两个值,因此,所需要实数乘 法次数M和实数加法次数M将减半,即 (1)M=N(N+2) 2)M=2N2 与直接计算DFT的方法相比,虽然 Goertzel算法完成DFT 运算时,其运算量减少较多,但是其运算量仍然正比于M2
7.3.3 ( 1) ( ) ˆ ˆ ( ), ( ) ( ) ( ) ( 1) (7.3.18) ˆ ˆ 7.3.17 7.3.18 ˆ ( 1) ( ) ˆ () ( ) 1 ( 2) 2 k k k k k Nk k k c a c yN yN XN k XN k r N y N W y N yN yN Xk XN k M M M NN − − − −= = − − − − = + 也可以依据信流图 ，利用 及 计算出 即 式（ ）和式（ ）表明，利用 及 可同时计算出 及 两个值，因此，所需要实数乘 法次数 和实数加法次数 将减半，即 （） （ ） 2 2 2 Goertzel M N a N = 与直接计算 的方法相比，虽然 算法完成 DFT DFT 运算时，其运算量减少较多，但是其运算量仍然正比于
数 理 着考处 无论直接完成DFT的运算,还是利用 Goertzel算法完成DFT运算, 我们并不需要计算出N个的X(k)值,而计算出N/2个值就可得到N个 X(k)值。在图732所示的递推系统中,利用(N-1)及(N)可以同 时计算出X(k)值及X(N-k)值,因此,我们可以计算任意L≥N/2个 的X(k),利用每一个X(k)及X(N-k),便可以完成N个X(k的计算。 在这种情况下,总计算量正比于LN。当L较小时,直接完成DFT的运 算和利用 Goertzel算法完成DFT运算都是可取的,当N为2的整数次幂 时,还有计算量正比于Nlog,N的算法。因此,当L<log,N时,直接 完成DFT的运算和利用 goertzel算法完成DFT运算都是最有效的方法, 但是,当需要计算全部N个Y(k)值时,下面将要讨论的按时间抽取的 算法或按频率抽取的算法又是最有效的算法
Goertzel () 2 ( ) 7.3.2 ˆ ˆ ( 1) ( ) () ( ) 2 ( ) () ( ) ( ) k k N Xk N N X k yN yN Xk XN k L N X k Xk XN k N Xk LN L − − ≥ − 无论直接完成 的运算，还是利用 算法完成 运算， DFT DFT 我们并不需要计算出 个的 值，而计算出 个值就可得到 个 值。在图 所示的递推系统中，利用 及 可以同 时计算出 值及 值，因此，我们可以计算任意 个 的 ，利用每一个 及 ，便可以完成 个 的计算。 在这种情况下，总计算量正比于 。当 2 2 Goertzel 2 log log Goertzel ( ) N N N L N N Xk < DFT DFT DFT DFT 较小时，直接完成 的运 算和利用 算法完成 运算都是可取的，当 为 的整数次幂 时，还有计算量正比于 的算法。因此，当 时，直接 完成 的运算和利用 算法完成 运算都是最有效的方法， 但是，当需要计算全部 个 值时，下面将要讨论的按时间抽取的 算法或按频率抽取的算法又是最有效的算法
数 理 着考处 274按时间抽取(D)的基2FFT算法 对长度是N为2的整数次幂的序列,不断地进行奇偶分组, 将长序列的DFT运算,最终变成2点序列的DFT运算。 1、算法的推导 设序列长度为N=2M,M为整数。若不满足这一条件, 可以人为加上若干个零值点,使这一条件得以满足。这种 N为2的整数次幂的FFT,称为基2-FFT 设序列x(n)=x(m)R(n),可按序号m的奇偶将序列分成 两组,即令n=2r及n=2r+,r=0,1,2,,N/2-1,于是有
7.4 按时间抽取(DIT)的基2 FFT算法 2 2 N DFT DFT 对长度是 为 的整数次幂的序列，不断地进行奇偶分组， 将长序列的 运算，最终变成 点序列的 运算。 1、算法的推导 2 2 - () () () 2 2 1 0,1, 2 2 1 M N N M N xn xnR n n n rn r r N = = = =+ = − FFT 2 FFT " 设序列长度为 ， 为整数。若不满足这一条件， 可以人为加上若干个零值点，使这一条件得以满足。这种 为 的整数次幂的 ，称为基 。 设序列 ，可按序号 的奇偶将序列分成 两组，即令 及 ， ， ， ，于是有
数 理 着考处 X(k)=DFIx(m)=∑x(m)W ∑x2)+2x2x+1m ∑x2)2+W∑x(2+1)2 (74.1) 式中,WM2=eM2 令4k)=∑x(2m)WM,k=01,2,…,N2-1 742) B(k)=∑x2r+1WM,k=0,2,…N/2-1 (74.3) 那么X(k)=A(k)+WB(k),k=0,1,2,…,N/2-1(744)
1 0 2 1 2 1 2 (2 1) 0 0 2 1 2 1 2 2 0 0 2 2 2 2 2 2 ( ) [ ( )] ( ) (2 ) (2 1) (2 ) (2 1) (7.4.1) ( ) (2 ) N nk N n N N rk r k N N r r N N rk k rk N N N r r j j N N N N X k x n x nW x rW x r W x rW W x r W We e W Ak x rW π π − = − − + = = − − = = − − = = = ++ = ++ === = ∑ ∑ ∑ ∑ ∑ DFT 式中， 令 2 1 2 0 2 1 2 0 , 0,1, 2, , 2 1 (7.4.2) ( ) (2 1) , 0,1, 2, , 2 1 (7.4.3) ( ) ( ) ( ) , 0,1,2, , 2 1 (7.4.4) N rk N r N rk N r k N k N Bk x r W k N X k Ak W Bk k N − = − = = − =+ = − =+ = − ∑ ∑ " " 那么