数字信号处理原理配套习题答案第5章快速傅利叶变换习题解答

5.1一台通用计算机的速度为：平均每次复数乘法需要100μs，每次复数加法需要20μs，今用来计算N=1024点的DFT[x(n)]。问直接运算需要多少时间？用FFT运算需要多少时间？解直接计算DFT需要N2次复数乘法、N(N-1)次复数加法；当N=1024=210复数乘法：N2=10242复数加法：N(N-1)=1024×(1024-1)≈10242=1048576所以直接运算需要的时间为1048576×100μs+1048576×20μs=125829120μs≈125.829s而如果用DIT-FFT算法，需要的运算量如下：复数乘法：mF复数加法：m所以采用DIT-FFT算法需要的时间为5120×100μs+10240×20μs=716800μs=0.7168s5.2一个线性非移变系统的单位取样响应为，已知输入信号为，请用FFT方法求，要求画出详细的运算流图，并写出计算步骤。解由题意y(n)=x(n)∗ℎ(n)，根据圆周卷积定理可知Y(k)=X(k)H(k)，又因为当N≥N1+N2−1=时，可用圆周卷积替代线性卷积。若用基-2FFT，N取4，先计算x(n)和ℎ(n)的FFT，再求X(k)和H(k)乘积得到Y(k)图5.6图5.7因此，Y(k)=X(k)H(k)={3,1求Y(k)的IFFT的方法有两种：方法一：因为y(n)=1NDFTY图5.8所以y(n)=方法二：可利用4点的DIF-IFFT计算y(n)结果，如图5.9所示。图5.9所以y(n)=1,5.3试画出为复合数时的FFT算法求的结果（采用基）。解依题意：，∴对于，有有，同样，令对于频率变量有，∴∴图5.105.4已知是一个点实序列的DFT，现在要用为求，为提高运算效率，试设计一个点IFFT运算一次完成。解将x(n)奇偶分组得{x1因为x(n)为实序列，因此构造一个复序列wn设{X{X(所以如果已知X(k)，可得令{WWk=也即wn5.5一个长度为的复序列与一个长度为的复序列卷积。(1)求直接进行卷积所需(复)乘法次数。(2)若用1024点基2按时间抽取FFT重叠相加法计算卷积，重做问题(1)。解(1)直接进行卷积所需(复)乘法次数为：K1=ML=512×8192=4194304。若用1024点按时间抽取的基-2FFT重叠相加法计算卷积，由于的长度为512点，可以将分段成16段长度为512的序列，这样与1024点的圆周卷积与线性卷积相等。根据快速卷积原理，需计算17次1024点的FFT和16次1024点的IFFT。N点的FFT的(复)乘法次数为mF=N2log2⁡NK5.6设是一个长度为的序列，且，，其中为偶数。(1)证明x(n)的N点DFT仅有奇次谐波，即X(k)=0，k为偶数(2)证明如何由一个经过适当调整的序列的N/2的DFT求得x(n)的N点DFT。证明(1)X=当k为偶数时，由于xn=−xn+N2(2)Xk因为WNXk=Xn/2(2k)表示序列的N2的DFT，从而得x5.7已知以1s为周期均匀采样得到。(1)试求频谱X(k)，并作出碟形图。(2)试进行谱分析，即求出振幅谱、相位谱和功率谱。解(1)采用图示法，4点的DIT-FFT运算蝶形图如图5.11所示。图5.11所以X(k)={5,2+j,-5,2-j}振幅谱Ak相位谱φ功率谱S(k)=A5.8用微处理机对实序列进行谱分析，要求谱分辨率F≤1Hz，信号的最高频率为，试确定以下各参数：(1)最小记录时间Tpmin；(2)最大的取样间隔Tmax；(3)最少采样点数Nmin解由F≤1Hz及Tp≥1F可得：而采样频率fsTN分辨率提高一倍，即，则5.9用重叠相加法计算一个长度为1000点的序列与长度为64点的序列的线性卷积时，共需要多少点DFT变换与DFT反变换？用重叠保留法呢？解由重叠相加法可知，需要把1000点的长序列分成每段分为L=128+1-64=65点共可得16段，这样每段65点序列与64点短序列的线性卷积恰好可以由128点的圆周卷积计算。由此可得需通过DFT转换16次，DFT转换1次，总共17次DFT，并运用DFT反变换16次就可以了。若采用重叠保留法，则分组的时候与重叠相加法有区别，第一段128点中包含64-1=63个零点，含有65个非零点，第二段中又重复第一段中最后63个点，然后依次排列后面的65个点，接着第三段依此类推，每段只有65个点是唯一的，因此100