x()-DFT[Re((DF() -5F-明 因=Dr[ml-=DrTo-fa F)-Fw-奶 1-bW 对X(k)、Y(K)作DT得到： x(n）=aRw(n) y(n)=b"Rx (n) 注意： 根据DT的线性性质可以得到，当f(n)=x(n)+y(n)时，F(k)=X(k)+jY(k),其中 X(k)、Y(k)均为复序列。但并不是对于形如F(k)=X(k)+Y(K)进行DFT就一定形成 X(k)x(n),Y(k)y(n)的一一对应关系。如，我们将F(k)进行变形，使其虚部和实部分 开得到：F(k)=M(k)+N(k),对其进行DT变换，显然，IDFT[M(k)门≠x(n) IDFT[N(k)]≠y(n). 所以，直接由F(k)=X(k)+Y(k)得到IDFT X(k)]≠x(n),IDFT Y(k)】]≠y(n) 是不正确的。 2-18研究两个有限长序列x(n),y(n),此二序列当n<0皆为零，并且 x(n)=0,n28 y(n)=0,n≥20 各作其20点DFT,然后将两个DFT相乘，再计算乘积序列的DT得，试指出r()的哪些点对应于 x(n)与y(n)作线性卷积应得到的点 解答 这样计算相当于做了20点的圆周卷积m=7~19时，圆周卷积等于线性卷积可以通过画图得到. 6
( ) { } ( ) { } ( ) ( ) ( ) ( ) * * 1 Re 2 1 1 2 1 N k N X k DFT f n DFT f n f n a F k F N k aW ⎡ ⎤ = = ⎡ ⎤ + ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ − = + ⎡ ⎤ − = ⎣ ⎦ − ( ) { } ( ) { } ( ) ( ) ( ) ( ) * * 1 Im 2 1 1 2 1 N k N Y k DFT f n DFT f n f n j b F k F N k j bW ⎡ ⎤ = = ⎡ ⎤ − ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ − = − ⎡ ⎤ − = ⎣ ⎦ − 对 X k( ) 、Y k( ) 作 IDFT 得到： ( ) ( ) ( ) ( ) n N n N x n a R n y n b R n ⎧⎪ = ⎨ ⎪ = ⎩ 注意： 根据 DFT 的线性性质可以得到，当 f (n x ) = (n) + jy (n) 时， F (k X ) = (k ) + jY (k )，其中 X k( ) 、 Y k( ) 均为复序列。但并不是对于形如 F (k X ) = (k ) + jY (k ) 进行 IDFT 就一定形成 X k( ) ↔ x(n) ，Y k( ) ↔ y (n) 的一一对应关系。如，我们将 F (k ) 进行变形，使其虚部和实部分 开得到： F (k M ) = + (k ) jN (k ) ，对其进行 IDFT 变换，显然， IDFT ⎡ ⎤ M (k ) ≠ x (n) ⎣ ⎦ ， IDFT ⎡ ⎤ N (k ) ≠ y (n) ⎣ ⎦ 。 所以，直接由 F (k X ) = + (k ) jY (k )得到 IDFT ⎡ ⎤ X (k ) ≠ x (n) ⎣ ⎦ ，IDFTYk ⎡ ⎤ ( ) ≠ y (n) ⎣ ⎦ 是不正确的。 2-18 研究两个有限长序列 x n( ), y(n),此二序列当 n < 0 皆为零,并且 ( ) 0, 8 ( ) 0, 20 x n n y n n = ≥ = ≥ 各作其 20 点 DFT,然后将两个 DFT 相乘,再计算乘积序列的 IDFT 得,试指出 的哪些点对应于 与 作线性卷积应得到的点. r n( ) x n( ) y n( ) 解答: 这样计算相当于做了 20 点的圆周卷积 m = 7 ∼ 19 时,圆周卷积等于线性卷积.可以通过画图得到. 6
2-21试导出N=16时的基二按时间抽取算法和按频率抽取算法T,并分别画出它们的流图。 解答： 用基二按时间抽取： W6哈W哈W8 W66W店m 8哈W6W6 时间抽取系数除哈阳 gW话 哈W8W。 W。W落W哈用 很多同学在第二列W的位置写的是W阳 X=2mwg,k=0,115 按奇偶分组： X0W-立2rwg"+空2+gg -=2x2rw2+W22r+1w2*(因m=e0=e骨=g) =0 -立2rw+We空2r+Wr=6+wg G=∑x2r)im Hk)=∑x(2r+w G(k),H(k)都是只包含7点的DFT,Gk)只包含原序列中的偶数序列， 而H(k)则只包含奇数序列，另外它的周期都为8，所以有 G(k)=G(k+8)H(k)=H(k+8)哈=-W,所以有 X(k)=G(k)+WH(k),k=0l,27 X(k+8)=G(k)-WH(k),k=0,l27 一个16点序列的DFT可由两个8点序列的DFT得到，依此类推，G(k),H(k) 也可以这样得到. 用频率抽取法：
2-21 试导出 N =16时的基二按时间抽取算法和按频率抽取算法 FFT,并分别画出它们的流图. 解答: 用基二按时间抽取: 时间抽取系数 ， 0 0 0 0 16 16 16 16 0 4 2 16 16 16 16 0 0 4 16 16 16 16 0 4 16 16 16 16 0 0 0 16 16 16 16 0 4 2 16 16 16 16 0 0 4 16 16 16 16 0 16 6 W W W W W W W W W W W W W W W W W W W W W W W W W W W W W 4 7 16 16 16 6 W W W 1 2 3 4 5 6 很多同学在第二列W16 4 的位置写的是 2 W16 15 16 0 7 7 2 (2 1) 16 16 0 0 7 7 2 2 2 2 2 2 16 8 16 16 16 16 8 0 0 7 7 8 16 8 0 0 ( ) ( ) , 0,1,.,15 (2 ) (2 1) (2 ) (2 1) ( ) (2 ) (2 1) ( ) kn n rk r k r r j rk j rk rk k rk rk rk r r rk k rk r r X k x n W k x r W x r W x r W W x r W W e e W x r W W x r W G k W π π = + = = − − = = = = = = + + = + + = = = = + + = + ∑ ∑ ∑ ∑ ∑ ∑ ∑ 按奇偶分组: X(k)= 因 16 7 7 8 8 0 0 16 16 16 ( ) ( ) (2 ) ( ) (2 1) ( ), ( ) 7 , ( ) , ( ) ( ) ( ) ( ), 0,1,2,.7 ( 8) ( ) ( k rk rk r r k k k H k G k x r W H k x r W G k H k DFT G k H k W X k G k W H k k X k G k W H k = = = = + = − = + = + = − ∑ ∑ k+8 16 都是只包含 点的 只包含原序列中的偶数序列 而 则只包含奇数序列,另外它的周期都为8,所以有 G(k)=G(k+8) H(k)=H(k+8) W ,所以有 ), k = 0,1, 2,.7 一个16点序列的DFT可由两个8点序列的DFT得到,依此类推,G(k),H(k) 也可以这样得到. 用频率抽取法: 7
把序列按前后对半分开 x(n)=x(n),n=0,l,7 x3(m=x(n+8)n=0,1,7 X(k) -o -立xmg+立(mmg 现在按对频率序列抽取，把它分成偶部和奇部，偶数时令k=21,奇数时令 k=21+1,这里1=0,1，.7， X(21)=∑x(n)mg+∑，(m)W28n =0 =0 g=e=e雪= WWW 上式=∑x(m)+x(n)W 月=0 依此类推： X(21+1)=2x(m)-x(nW"Wg a(n）=x(n)+x(m) bm）=[x(m)-x3(n)jW8,n=0,l,7 这样又把16点的DFT化成了8点的DFT,向下不断细分得到下图： 2-25设x(n)是一个M点0≤n≤M-1的有限长序列，其Z变换为 M-1 X(e)=∑x(n)z" 今欲求X(白)在单位圆上N个等距离点的采样值X(仁人4=e户，k=0,L,N- (I)N≤M 间在(2)N>M两种情况下应如何用-个N点的T来计算全部的X(5,)值 解答 8
1 2 15 16 0 7 7 ( 8) 1 16 2 16 0 0 7 2 2( 1 16 2 16 0 ( ) ( ), 0,1,.,7 ( ) ( 8), 0,1,.,7 ( ) ( ) ( ) ( ) ( ) ( ) nk n nk n k n n nl n n x n x n n x n x n n X k x n W x n W x n W x n W x n W = + = = = = = = + = = = + + ∑ ∑ ∑ ∑ 把序列按前后对半分开 现在按对频率序列抽取,把它分成偶部和奇部,偶数时令k=2l,奇数时令 k=2l+1,这里l=0,1,.7, X(2l)= 7 8) 0 2 2 16 2 2 16 2 16 8 2( 8) ( 8) 16 8 8 7 1 2 8 0 7 1 2 8 16 0 1 2 1 2 16 [ ( ) ( )] [ ( ) ( )] ( ) ( ) ( ) ( ) [ ( ) ( )] , 0,1,.,7 l n j nl j nl nl nl n l n l nl nl n nl n n n W e e W W W W x n x n W x n x n W W a n x n x n b n x n x n W n π π + = − − + + = = = = = = = + − = + = − = ∑ ∑ ∑ 上式= 依此类推: X(2l+1)= 这样又把16点的DFT化成了8点的DFT,向下不断细分得到下图: 2-25 设 x(n) 是一个 M 点 0 ≤ ≤ n M −1的有限长序列,其 Z 变换为 1 0 ( ) ( ) M n n X z x n z − − = = ∑ 今欲求 X(z) 在单位圆上 N 个等距离点的采样值 2 ( ), , 0,1,., 1 j k N X zk k z e k N π = = − 问在 两种情况下,应如何用一个 N 点的 FFT 来计算全部的 值? (1) (2) N M N M ≤ > ( ) X zk 解答: 8
(2)N>M 将x(n)补零到N点，然后作FFT 形0 -0 =∑rmea」 N-1 DFT[x (n)] =0 (①)N≤M 将x(n)补零到LN,组成新序列 阳分 ne停 0 +∑me宗u N -艺nk宁丰艺n+N是n ee贤taw=e 月-0 -过+a+Wk京，空n+2Ngn 月=0 司 =2n+k0=Dn号n+ L-1 m-0-0 变成了N点的DFT 对于(1)还有另一种解法 现设有一序列y(m0≤n≤N-1,其中N点DFT与X(k)相同，即 x()=e片，k=0LN-1 于是有： w-容0]学-02 0 因为6 0I≠iN+n 所以：)-立N+)）其中P=:+1的整数部分，当M不够pN时，对 -0 序列补零。 9
1 1 2 2 1 2 ' ' 0 0 1 2 ' ' 0 1 1 222 0 0 (2) ( ) ( ) ( ) ( ) ( ) [ ( )] (1) ( ) , ( ) ( ) ( ) ( ) M M N j kn j kn j kn N N N n n n M N j kn N n M N j kn j kn j kn NNN n n N M x n N x n e x n e x n e x n e DFT x n N M x n LN X k x n e x n e x n e π π π π πππ − − − − − − = = = − − = − − −−− = = > = + = = ≤ = = + ∑ ∑ ∑ ∑ ∑ ∑ 将 补零到 点,然后作FFT X(k)= 将 补零到 组成新序列 1 1 1 2 2 2 ( ) ( ) 0 0 1 2 2 2 1 ( 2 ) 0 0 1 1 2 1 0 0 0 ( ) ( ) ( ) [() ( )] ( 2 ) [ ( )] [ ( )] M n N N M N j kn j k n N j k n N j kn N N N n n N M N j kn j k n N N N n n N L L j kn N n l l x n e x n N e e e x n x n N e x n N e x n lN e DFT x n lN N DFT π π π π π π − = − − − − − + − + = = − − − − − + = = − − − − = = = = + + = = + + + + = + = + ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∵ 变成了 点的 2 N π − 对于（1）还有另一种解法 现设有一序列 y n( ) 0 ≤ ≤ n N −1，其中 N 点 DFT 与 X k( )相同，即 ( ) ( ) 1 2 0 , 0,1, , N j kn N n X k y n e k N − π − = = = ∑ " −1 于是有： ( ) ( ) ( ) ( ) 1 1 2 2 1 1 2 0 0 0 0 1 1 N M M N j kl j kn j k l n N N N k l l k y n x l e e x l e N N − − π π − − π − − = = = = ⎡ ⎤ = = ⎢ ⎥ ⎣ ⎦ ∑ ∑ ∑ ∑ − 因为： ( ) 1 2 0 1 1 0 N j k l n N k l iN n e N l iN n − π − − = ⎧ = + = ⎨ ⎩ ≠ + ∑ 所以： ( ) ( ) 其中 0 p i y n x iN n = = ∑ + 1 M p N = + 的整数部分，当 M 不够 时，对 序列补零。 pN 9
227:我们希望利用一个长度为50的有限单位脉冲响应滤波器来过滤一串很长的数据，要求利用重叠 保留法并通过下T来实现这种滤波器。为做到这一点，(1)输入各段必须重叠N个样本：(2)必须从每 段产生的输出中取出M个样本，并将它们拼接在一起形成一长序列，即为滤波输出。设输入的各段长 度为100个样本，而T的长度为128，圆网卷积的输出序号为0127。 (1)求N: (2)求M: (3)求取出的M个点之起点与终点序号，即从圆周卷积的128点中取出哪些点去和前一段衔接起来？ 解：(1)输入各段必须重叠的样本数为滤波器长度减1：依题意有： ∴.N=N,-1=50-1=49 (2)输入段的长度Nm:滤波器长度N,=50,相邻输入段之间(N,-1)点发生重叠，圆周卷积 后每一段输出y,()的前(N,-)点发生混滑，去掉这一部分，把相邻段留下的点 (M=Nm-N+1)衔接构成最终的输入。设Nm=100,则有M=51。 (3)去掉混叠的前N(048)个点，和末尾补的28(100127)个零点，取出的M个点的序号为： 4999
2-27：我们希望利用一个长度为 50 的有限单位脉冲响应滤波器来过滤一串很长的数据，要求利用重叠 保留法并通过 FFT 来实现这种滤波器。为做到这一点，（1）输入各段必须重叠 N 个样本；（2）必须从每 一段产生的输出中取出 M 个样本，并将它们拼接在一起形成一长序列，即为滤波输出。设输入的各段长 度为 100 个样本，而 FFT 的长度为 128，圆周卷积的输出序号为 0~127。 （1） 求 N； （2） 求 M； （3） 求取出的M个点之起点与终点序号，即从圆周卷积的128点中取出哪些点去和前一段衔接起来？ 解：（1）输入各段必须重叠的样本数为滤波器长度减 1；依题意有：； ∴ 1 N N = −1 5 = 0 −1 = 49 （2）输入段的长度 Nin ；滤波器长度 1 N = 50，相邻输入段之间(N1 −1) 点发生重叠，圆周卷积 后每一段输出 y n i ( ) 的 前 (N1 −1) 点发生混淆，去掉这一部分，把相邻段留下的 点 ( ) 1 1 M N = − in N + 衔接构成最终的输入。设 100 Nin = ，则有 M = 51。 （3）去掉混叠的前 N（0~48）个点，和末尾补的 28（100~127）个零点，取出的 M 个点的序号为： 49~99。 10