第四章习题与答案.docx
《第四章习题与答案.docx》由会员分享，可在线阅读，更多相关《第四章习题与答案.docx（18页珍藏版）》请在冰点文库上搜索。
第四章习题与答案
解:
⑴直接计算:
复乘所需时间:
复加所需时间:
⑵用FFT计算:
复乘所需时间:
复加所需时间:
由
（1）式可得
的路径，如下表所示:
k
0123456789
0.80.670.560.460.390.320.270.220.190.16
arg[
]
8.请用C语言编写程序:
（1）按频率抽取的FFT算法
（2）分裂基FFT算法
基-2FFT（频率抽取DIF法）算法程序
/*Free_Copy*/
/*C语言编写的频率抽取FFT算法（最大计算64点）*/
/*输入:
序列点数、序列值*/
/*输出:
序列FFT变换后的数值及反变换（应与原序列相同）*/
#include"conio.h"
#include"math.h"
#include"stdio.h"
#defineN64
#definePI3.1415926
#definew0（0.125*PI）
#defineCmul（a,b,c）a.x=b.x*c.x-b.y*c.y;a.y=b.x*c.y+b.y*c.x;
#defineCequal（a,b）a.x=b.x;a.y=b.y;
#defineCadd（a,b,c）a.x=b.x+c.x;a.y=b.y+c.y;
#defineCsub（a,b,c）a.x=b.x-c.x;a.y=b.y-c.y;
#defineWn（w,r）w.x=cos（2.0*PI*r/n）;w.y=-sin（2.0*PI*r/n）;
structcomp
{
floatx;
floaty;
};
voidmain（）
{
inti,j,nu2,nm1,n,m,le,le1,k,ip,z;
intflag,f,n1;
structcompa[N],t,t1,w,d;
floata_ipx,m1;
printf（"\nThisprogramisaboutFFTbyDIFway."）;
printf（"\npleaseenterN:
"）;
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;iprintf（"\n"）;
for（i=0;i{
printf（"\npleaseenterdata（%d）_[Re]:
",i）;
scanf（"%f",&a[i].x）;
printf（"\npleaseenterdata（%d）_[Im]:
",i）;
scanf（"%f",&a[i].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{
for（i=j;i<=（n-1）;i+=le）
{
ip=i+le1;
Cequal（t,a[i]）;
Cequal（t1,a[ip]）;
f=（int）（i*pow（2,flag））%n;
Wn（w,f）;
Cadd（a[i],t,t1）;
Csub（a[ip],t,t1）;
a_ipx=a[ip].x;
if（z==1）
{
w.y*=-1;
}
a[ip].x=a[ip].x*w.x-a[ip].y*w.y;
a[ip].y=a_ipx*w.y+a[ip].y*w.x;
}
}
}
nu2=n/2;
nm1=n-2;
j=0;i=0;
while（i<=nm1）
{
if（i{
Cequal（d,a[j]）;
Cequal（a[j],a[i]）;
Cequal（a[i],d）;
}
k=nu2;
while（k<=j）
{
j=j-k;k=k/2;
}
j=j+k;
i=i+1;
}
if（z==0）
{
printf（"\n序列的fft是:
\n\n"）;
}
else
printf（"\n用ifft计算出的原序列是:
\n\n"）;
for（i=0;iif（z==0）
{
printf（"%7.3f",a[i].x）;
if（a[i].y>=0）
printf（"+%7.3fj\n",a[i].y）;
else
printf（"-%7.3fj\n",fabs（a[i].y））;
a[i].y=-a[i].y;
}
else
{
printf（"%7.3f",a[i].x/n）;
a[i].y=-a[i].y/n;
if（a[i].y>=0）
printf（"+%7.3fj\n",a[i].y）;
else
printf（"-%7.3fj\n",fabs（a[i].y））;
}
}
printf（"\n"）;
}
分裂基FFT算法程序
/*Free_Copy*/
/*主程序:
64点分裂基FFT算法*/
/*输入:
64点任意序列*/
/*输出:
序列的FFT变换*/
#include"conio.h";
#include"math.h"
#include"stdio.h"
#definePI3.1415926
#defineN128
voidmain（）
{
floatx[N],y[N],xt;
floatcc1,cc3,ss1,ss3;
floatr1,r2,r3,s1,s2,a,a3,e,m1;
intn,n1,m,j,k,i;
intis,id,i0,i1,i2,i3,n2,n4;
printf（"\nThisprogramisaboutFFTbySPEFTway."）;
printf（"\npleaseentern:
"）;
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++）
{
x[i]=y[i]=0.0;
}
printf（"\n"）;
for（i=1;i<=n1;i++）
{
printf（"\npleaseenterdata（%d）_[Re]:
",i）;
scanf（"%f",&x[i]）;
printf（"\npleaseenterdata（%d）_[Im]:
",i）;
scanf（"%f",&y[i]）;
}
j=1;
for（i=1;i<=n-1;i++）
{
if（i{
xt=x[j];
x[j]=x[i];
x[i]=xt;
xt=y[j];
y[j]=y[i];
y[i]=xt;
}
k=n/2;
while（k{
j=j-k;
k=k/2;
}
j=j+k;
}
is=1;
id=4;
while（is{
for（i0=is;i0<=n;i0+=id）
{
i1=i0+1;
r1=x[i0];
x[i0]=r1+x[i1];
x[i1]=r1-x[i1];
r1=y[i0];
y[i0]=r1+y[i1];
y[i1]=r1-y[i1];
}
is=2*id-1;
id=4*id;
}
n2=2;
for（k=2;k<=m;k++）
{
n2=n2*2;
n4=n2/4;
e=2.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{
for（i0=is;i0<=n-1;i0+=id）
{
i1=i0+n4;
i2=i1+n4;
i3=i2+n4;
r1=x[i2]*cc1+y[i2]*ss1;
s1=y[i2]*cc1-x[i2]*ss1;
r2=x[i3]*cc3+y[i3]*ss3;
s2=y[i3]*cc3-x[i3]*ss3;
r3=r1+r2;
r2=r1-r2;
r1=s1+s2;
s2=s1-s2;
x[i2]=x[i0]-r3;
x[i0]=x[i0]+r3;
x[i3]=x[i1]-s2;
x[i1]=x[i1]+s2;
y[i2]=y[i0]-r1;
y[i0]=y[i0]+r1;
y[i3]=y[i1]+r2;
y[i1]=y[i1]-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",x[i],y[i]）;
y[i]=-y[i];
}
getch（）;
printf（"\n\n"）;
}
9我们希望利用一个单位抽样响应为N=50个抽样的有限冲激响应滤波器来过滤一串很长的数据。
要求利用重叠保留法通过快速傅立叶变换来实现这种滤波器，为了做到这一点,则:
（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.当实现按时间抽取快速傅立叶变换算法时，基本的蝶形计算
利用定点算术运算实现该蝶形计算时，通常假设所有数字都已按一定比例因子化为小于1。
因此在蝶形计算的过程中还必须关心溢出问题。
（a）证明如果我们要求
则在蝶形计算中不可能出现溢出，即
（b）实际上要求：
似乎更容易些，也更适合些。
问这些条件是否足以保证在蝶形计算中不会出现溢出？
请证明你的回答。
证明：
（a）
解：
（a）
若直接利用10点快速傅立叶变换算法，则：
将n为偶数与n为奇数的部分分开，可得：
（b）
如考虑利用线性调频z变换算法，
则
升级会员 