第四章习题与答案

1、解: 直接计算: 复乘所需时间: 复加所需时间:用fft计算: 复乘所需时间: 复加所需时间:由（1）式可得的路径，如下表所示: k0 1 2 3 4 5 6 7 8 9 0.8 0.67 0.56 0.46 0.39 0.32 0.27 0.22 0.19 0.16arg 8. 请用c语言编写程序: (1) 按频率抽取的fft算法 (2) 分裂基fft算法基- 2 fft ( 频率抽取dif 法) 算法程序 /*free_copy*/ /* c语言编写的频率抽取fft算法(最大计算64点）*/ /* 输入: 序列点数、序列值 * / /* 输出: 序列fft变换后的数值及反变换(应与原序列相

2、同 ) */ #include "conio.h" #include "math.h" #include "stdio.h" #define n 64 #define pi 3.1415926 #define w0 (0.125*pi) #define cmul(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

3、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("nthis program is about fft by dif way. "); printf(&q

4、uot;nplease enter n : "); scanf("%d",&n1); n=n1; m1=log(n1)/log(2); m=log(n1)/log(2); if (m!=m1) n=pow(2,m+1); for(i=0;i<n;i+) ai.x=ai.y=0.0; printf("n"); for(i=0;i<n1;i+) printf("nplease enter data(%d)_re: ",i); scanf("%f",&ai.x); printf(&q

5、uot;nplease enter data(%d)_im: ",i); scanf("%f",&ai.y); for(z=0;z<=1;z+) flag=-1; for (m=(log(n)/log(2);m>=1;m-) le=pow(2,m); flag+; le1=le/2; for( j=0;j<le1;j+) for (i=j;i<=(n-1);i+=le) ip=i+le1; cequal(t,ai); cequal(t1,aip); f=(int) (i*pow(2,flag)%n; wn(w,f); cadd(ai

6、,t,t1); csub(aip,t,t1); a_ipx=aip.x; if (z=1) w.y*=-1; aip.x=aip.x*w.x-aip.y*w.y; aip.y=a_ipx*w.y+aip.y*w.x; nu2=n/2; nm1=n-2; j=0;i=0; while(i<=nm1) if (i<j) cequal(d,aj); cequal(aj,ai); cequal(ai,d); k=nu2; while(k<=j) j=j-k;k=k/2; j=j+k; i=i+1; if(z=0) printf("n序列的fft是:nn"); el

7、se printf("n用ifft计算出的原序列是:nn" ) ; for(i=0;i<n;i+) if(z=0) printf(" %7.3f",ai.x); if (ai.y>=0) printf(" + %7.3f j n",ai.y); else printf(" - %7.3f j n",fabs(ai.y); ai.y= -ai.y; else printf(" %7.3f",ai.x/n); ai.y=-ai.y/n; if (ai.y>=0) printf(&q

8、uot; + %7.3f j n",ai.y); else printf(" - %7.3f j n",fabs(ai.y); printf("n"); 分 裂 基 fft 算 法 程 序 /*free_copy*/ /*主程序:64点分裂基fft算法*/ /*输入: 64点任意序列*/ /*输出: 序列的fft变换*/ #include "conio.h" #include"math.h" #include"stdio.h" #define pi 3.1415926 #define

9、n 128 void main() float xn,yn,xt; float cc1,cc3,ss1,ss3; float r1,r2,r3,s1,s2,a,a3,e,m1; int n,n1,m,j,k,i; int is,id,i0,i1,i2,i3,n2,n4; printf("nthis program is about fft by speft way. "); printf("nplease enter n : "); scanf("%d",&n1); n=n1; m1=log(n1)/log(2); m=log

10、(n1)/log(2); if (m!=m1) n=pow(2,m+1); for(i=0;i<=n;i+) xi=yi=0.0; printf("n"); for(i=1;i<=n1;i+) printf("nplease enter data(%d)_re: ",i); scanf("%f",&xi); printf("nplease enter data(%d)_im: ",i); scanf("%f",&yi); j=1; for (i=1;i<=n-1

11、;i+) if (i<j) xt=xj; xj=xi; xi=xt; xt=yj; yj=yi; yi=xt; k=n/2; while (k<j) j=j-k; k=k/2; j=j+k; is=1; id=4; while (is<n) for (i0=is;i0<=n;i0+=id) i1=i0+1; r1=xi0; xi0=r1+xi1; xi1=r1-xi1; r1=yi0; yi0=r1+yi1; yi1=r1-yi1; is=2*id-1; id=4*id; n2=2; for (k=2;k<=m;k+) n2=n2*2; n4=n2/4; e=2.

12、0*pi/n2; a=0.0; for (j=1;j<=n4;j+) a3=3.0*a; cc1=cos(a); ss1=sin(a); cc3=cos(a3); ss3=sin(a3); a=j*e; is=j; id=2*n2; while (is<n) for (i0=is;i0<=n-1;i0+=id) i1=i0+n4; i2=i1+n4; i3=i2+n4; r1=xi2*cc1+yi2*ss1; s1=yi2*cc1-xi2*ss1; r2=xi3*cc3+yi3*ss3; s2=y i3*cc3-xi3*ss3; r3=r1+r2; r2=r1-r2; r1=

13、s1+s2; s2=s1-s2; xi2=xi0-r3; xi0=xi0+r3; xi3=xi1-s2; xi1=xi1+s2; yi2=yi0-r1; yi0=yi0+r1; yi3=yi1+r2; yi1=yi1-r2; is=2*id-n2+j; id=4*id; printf("n分裂基fft结果是： n "); for (i=1;i<=n;i+) printf("n %7.3f, %7.3fj",xi,yi); yi=-yi; getch(); printf("nn"); 9 我们希望利用一个单位抽样响应为n=50个抽

14、样的有限冲激响应滤波器来过滤一串很长的数据。要求利用重叠保留法通过快速傅立叶变换来实现这种滤波器，为了做到这一点 ,则:(1) 输入各段必须重叠p个抽样点 ；(2) 我们必须从每一段产生的输出中取出q个抽样点，使这些从每一段得到的抽样连接在一起时，得到的序列就是所要求的滤波输出。假设输入的各段长度为100个抽样点，而离散傅立叶变换的长度为128点。进一步假设，圆周卷积的输出序列标号是从n=0到n=127。则：(a)求p ； (b)求q； (c)求取出来的q个点之起点和终点的标号，即确定从圆周卷积的128点中要取出哪些点，去和前一段的点衔接起来。解：(a) 由于用重叠保留法，如果冲激响应h(n) 的点数为n点，则圆周卷积结果的前面的(n-1)个点不代表线性卷积结果。故每段重叠点数p为p=n 1 =50 1=49(b) 每段点数为 27 =128，但其中只有100个是有效输入数据，其余28个点为补充的零值点。因而各段的重叠而又有效的点数q为q=100 p=100 49 =51(c) 每段128 个数据点中，取出来的q个点的序号为 n=49 到 n=99。用这些点和前后段取出的相应点连接起来，即可得到原来的长输入序列。 另外，对于第一段数据不存在前一 段问题，故在数据之前必须加上p=n 1 =49个零值点，以免丢失数据。10. 当实现按时间抽取快