数字信号处理参考试题4.

第四章 快速傅里叶变换1 如果一台通用计算机的速度为平均每次复乘5s，每次复加0.5s，用它来计算512点的的DFTx(n)，问直接计算需要多少时间，用FFT运算需要多少时间。解：（1）直接计算复乘所需时间 复加所需时间所以 （2）用FFT计算复乘所需时间 复加所需时间所以 2 已知，是两个N点实序列，的DFT值，仅需要从，求，的值，为了提高运算效率，试用一个N点IFFT运算一次完成。解：依据题意 ，取序列 对作N点IFFT可得序列。 又根据DFT性质由原题可知，都是实序列。再根据，可得 3 N16时，画出基-2按时间抽取法及按频率抽取法的FFT流图（时间抽取采用输入倒位序，输出自然数顺序，频率抽取采用输入自然顺序，输出倒位序）。解：（1）按时间抽取，见图P4-3(a)。图 P4-3（a）（2）按频率抽取，见图P4-3(b)。图 P4-3（b）4 N=16时，导出基-4FFT公式、画出流图，并就运算量与基-2的FFT相比较（不计乘±1及乘±j的运算量）。解：依题意 N4×4r1r2对于n<N，有 同样令N=r1r2，对于频率变量k(k<N)有可得 根据上式 令 则 而 所以 计算量比较：基-4：只在乘旋转因子时有复乘，复乘8次；复加64次。基-2：复乘10次，复加64次。基-4流图如图P4-4所示。图 P4-45 试用N的组合数时的FFT算法求N=12的结果（采用基-3×4），并画出流图。解：依题意 对于，有 同样 令，对于频率变量有 可得 根据上式，得 流图如图P4-5所示。最后输出为，是倒位序的，按可算出其相应的k值，在整序后，即可得正常顺序的输出。图 P4-56 同上题。导出的结果，并画出流图。解：依题意 对于n<N，有 同样，令，对于频率变量有 可得 根据上式得 令 则 所以 流图如图P4-6所示。图 P4-67 研究一个长度为M点的有限长序列。我们希望计算求z变换在单位圆上N个等间隔点上的抽样，即在上的抽样。试对下列情况，找出只用一个N点DFT就能计算的N个抽样的方法，并证明之。（1） （2）解：（1）依题意 设，则 因为 且令 所以 由此可见，对于，可先计算，然后对它求一次N点DFT，即可计算在单位圆上的N点抽样。（2）若，可将补零到N点，即 则 8 已知一个8点序列试用CZT法求其前10点的复频率。已知z平面路径为，画出zk的路径及CZT实现过程示意图。解：依题意 则 所以 而 把代入,可得 令 则 由（1）式可得的路径（模和相角），如表4-8所示。其CZT实现过程和的路径见图P4-8(a)，P4-8(b)。表 P4-8 k0 1 2 3 4 5 6 789|zk|0.80.670.560.460.390.320.270.220.190.16Agrzk/313/3016/3019/3022/3025/3028/3031/3034/3037/30图 P4-8（a）图 P4-8（b）9 在下列说法中选择正确的结论。线性调频z变换（CZT）可以用来计算一个M点有限长序列在z平面的实轴上各点的z变换，使（1）。（2）。（3）（1）和（2）两者都行。（4）（1）和（2）两者都不行。即线性调频z变换不能计算在z为实数时的抽样。解：（1） 是正确的。因为 其中 都是任意实数。所以若求有限长序列在z平面实轴上各点的z变换，只需取此时 式中 为了用FFT计算，式中取 计算时可先求出 则 10.当实现按时间抽取快速傅里叶变换算法时，基本的碟形计算利用定点算术运算实现该蝶形计算时，通常假设所有数字都按一定比例因子化为小于1。因此在蝶形计算的过程中还必须关心溢出问题。 （1）证明如果我们要求和，则在蝶形计算中不可能出现溢出，即 （2） 实际上要求： 试乎更容易些，也更适合些。问这些条件是否足以保证在蝶形计算中不会出现溢出？请证明你的回答。证明（1）由题意 ，可求得 即 因此 所以 同理可证 （2）因为 所以 即 或 因此不一定小于12，故利用（1）的结果可以得出，及不一定小于1。同理可得出，及不一定小于1。所以上述条件不足以保证在蝶形运算中不出现溢出。11. 表示长度为10的有限长序列的傅里叶变换。我们希望计算在频率时的10个抽样。计算抽样。计算时不能采用先算出比要求数多的抽样然后在丢掉一些的办法。讨论采用下列各方法的可能性：（1） 直接利用10点快速傅里叶变换算法。（2） 利用线性调频z变换算法。解：（1） 若直接利用10点快速傅里叶变换算法，则 式中 对于每个k值，计算要求8+816次实数乘法（s=0时没有乘法）。对于每个k值，计算要求2×16+436次实数乘法。因此对10点傅里叶变换，总共需要360次实数乘法。（2） 如考虑利用线性调频z变换算法，则在应用这种算法时，W必须不是k的函数，因为这里W是k的函数，所以不能利用线性调频z变换算法。12.我们希望利用一个单位抽样响应点数N=50的有限冲激响应滤波器来过滤一串很长的数据。要求利用重叠保留法通过快速傅里叶变换来实现这种滤波器，为了做到这一点，则：（1） 输入各段必须重叠P个抽样点；（2） 我们必须从每一段产生的输出中取出Q个抽样点，使这些从每一段得到的抽样连接在一起时，得到的序列就是所要求的滤波输出。假设输入的各段长度为100个抽样点，而离散傅里叶变换的长度为128点。进一步假设，圆周卷积的输出序列标号是从n=0到n=127。则：（a）求P； （b）求Q；（c）求取出来的Q个点的起点和终点的标号，即确定从圆周卷积的128点中要取出哪些点，去和前一段的点衔接起来。图 P4-12解：（a）由于用重叠保留法，如果冲激响应的点数为N点，则圆周卷积结果的前面的N-1个点不代表线性卷积结果，故每段重叠点数P为 P=N-1=50-1=49（b）每段点数为27128，但其中只有100个是有效输入数据，其余28个点为补充的零值点。因而各段的重叠而又有效的点数Q为 （c）每段128个数据点中，取出来的Q个点的序号从n=49到n=99。用这些点和前后段取出的相应点连接起来。即可得到原来的长输入序列。另外，对于第一段数据没有前一段，故在数据之前必须加上P=N-1=49个零值点，以免丢失数据。13.请用C语言编写程序：（1） 按频率抽取的FFT算法；（2） 分裂基FFT算法。程序如下：基-2 FFT（频率抽取DIF法）算法程序/*Free_Copy*/*C语言编写的频率抽取FFT算法（最大计算64点）*/*输入：序列点数、序列值*/*输出：序列FFT变换后的数值及反变换（应与原序列相同）*/#include “conio.h”#include “math.h”#include “stdio.h”#define N 64#define PI 3.1415926#define w0 (0.125*PI)#define Cmula(a,b,c) a.x=b.x*c.x-b.y*c.y;a.y=b.x*c.y+b.y*c.x;#define Cequal(a,b) a.x=b.x;a.y=b.y;#define Cadd(a,b,c) a.x=b.x+c.x;a.y=b.y+c.y;#define Csub(a,b,c) a.x=b.x-c.x;a.y=b.y-c.y;#define Wn(w,r) w.x=cos(2.0*PI*r/n);w.y=-sin(2.0*PI*r/n);struct comp float x; float y;void main() int I,j,nu2,nm1,n,m,le,le1,k,ip,z; int flag,f,n1;struct comp aN,t,t1,w,d;float a_ipx,m1;printf(“n This program is about FFT by DIF way.”);printf(“