第四章习题与答案

运算需要多少时间。计算需要多少时间，用，问直拉点的，用它来计算每次复加速度为平均每次复乘需如果一台通用计算机的FFTDFT[x(n)]512s5s50.1解:⑴直接计算:复乘所需时间:复加所需时间:⑵用FFT计算:复乘所需时间:复加所需时间:运算一次完成。点试用一个为了提高运算效率值求今需要从值的点实序列是两个已知IFFTNnynxkYkXDFTnynxNkYkX,,)(),()(),(,)(),()(),(.2sTTTsNNT441536.1130816.0)1512(512105.0)1(105.021662sNT31072.151210510526261sNTN01152.0512log105log1052251262261sTTTsNNT013824.0002304.0512log512105.0log105.02126262值的过程。）（），（完成计算点）可用一次（）（）（综上所述，构造序列）（）（）（）（可得：）（）（）（再根据都是实序列，）（），（由原题可知：）（）（）（）（（）（）（性质：又根据可得序列点作对取序列依据题意解]Im[]Re[][][][).()()()()()()();()(::nynxIFFTNkjYkXkZnznynznxnjynxnznynxnjynxkYjIDFTkXIDFTkjYkXIDFTDFTnzIFFTNkZkjYkXkZkYnykXnx。的运算量及乘不计乘相比较的基并就运算量与公式并画出流图基导出时)(2,4,16.3jjFFTFFTN),()4()()(),()4()()(3,2,1,03,2,1,0,)(,3,2,1,03,2,1,0;,440101011010102101011120102121kkXkkXkrkXkXnnxnnxnrnxnxkkkrkkNkkrrNnnnrnnNnrrN有对于频率变量同样令有对于解：依题意：303016416416013030)4)(4(16011501601001001010101)4()4()()(nnknknknnnkknnnnk并画出流图。采用基的结果算法求为组合数时的试用,)43(12.4NFFTN1201021213,2,1,02,1,0,,0,43rrNnnnrnnNnrrN令同样：有对于解：依题意：3020)3)(4(1201110120101011010102101011010101),()()(),()3()()(),()4()()(2,1,03,2,1,0,)0(nnkknnnnkWnnxWnxkXkkXkkXkrkXkXnnxnnxnrnxnxkkkrkkNkk有对于频率变量MNbMNaNzXDFTNNkezNznxzXznnxnxnxMkNjMnn)(;)(:)(,,1,,1,0,,)()(0,1-Mn0),()(,)(.5210之个抽样的方法，并证明的就能计算点找出用一个情况试对下列上的抽样即在上的抽样个等间隔点在单位圆上变换我们希望计算求其他点的有限长序列研究一个长度为1220121122220(1)1122()00(),()()(1)()()()()()()[(MjkjnkNNnNNMjkjnkjnkjnkNNNNnnNnlNNNjnkjnNkNNnnaNMXexnelNMlNXexnexnexnexnexnNexnl解：若依意(1)12[(1)]01)]MlNjnlNkNnNe10,)()(1010)()(,)()()(,)()]([)()1)1(0(])1([)()10(])2([)(),()(),()(,1020201010102212102)(2NkenxeXNnMMnnxnxNnxMNbNzXDFTNnyMNenyeXNlMnNlnxnyNnNlnxnyNnxnynxnyeeNnknNjkNjlmmNnlmknNjmkNjllknNjklNnNj则：即点到补零，可将若：点抽样在单位圆上的即可计算点，然后对它求一次，可先计算由此可见，对于且令：实现过程示意图。的路径及画出平面路径为。已知的复频谱点法求其前面试用其他点序列已知一个CZTzAzzXCZTnxkk;20/2,2.1W,3/,8.0)(10n,07n0,1)(8.600009,,1,0,)]()([)(7,,1,0)(7,,1,0;)()(:)(}2.12.18.0{)2.1()(])([90,)2.1()8.0()()((1)90,)2.1(8.02.1;8.02222227022)(222270]32)(20220[2)(21222202222221)310(7070)310(20203000kkhkgWzXnWnhnWAnxngWWAnxWeezXnkknnkkeznxzXkeAWzeeWWeeAAkknnnnnknnknnnknjnknnkjkknkjnnknnnkkkjkkkjjjj则：令则解：依题意：由（1）式可得kz的路径，如下表所示:k0123456789kz0.80.670.560.460.390.320.270.220.190.16arg[kz]3301330163019302230253028303130343037时的抽样。为实数在变换不能计算即线性调频两者都不行两者都行和为实数为实数使变换的的实轴上各点平面在点有限长序列计算一个可以用来变换线性调频的结论在下列说法中选择正确zH(z)z,(b)(b)(a)(c)0a,a1,-N,1,0,k,z(b)1a,a1,-N,1,0,k,)(:),()()(..7kakazazHzzzznhMCZTzkkk11,,010,)()()(1,,1,0,)()()()()()1(0,0,,1,)(,,,1,,1,0)()()(2/)1(2/2/102/2/)(102/2/10001000000)(0010222222200LnMLamLnNNnanpanhngNknkpngaaanhaanhzHaazaWAzznhWANkeWAAWzznhzHanNMnnMnknkMnnkMnnkkkkkjkkkMnnkk式中此时即可只需取变换各点的上平面实轴在若求有限长序列都是任意实数其中：是正确的。解：10,)()(,)]([)()()()(,)]([)(,)]([)(122/2NkkrazHLkRIFFTnrkpkGkRLnpFFTkpLngFFTkGMNLFFTkkJ则点点点计算时可先求出计算，式中取为了用8.请用C语言编写程序:(1)按频率抽取的FFT算法(2)分裂基FFT算法基-2FFT(频率抽取DIF法)算法程序/*Free_Copy*//*C语言编写的频率抽取FFT算法(最大计算64点）*//*输入:序列点数、序列值*//*输出:序列FFT变换后的数值及反变换(应与原序列相同)*/#includeconio.h#includemath.h#includestdio.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;in;i++){a[i].x=a[i].y=0.0;}printf(\n);for(i=0;in1;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;jle1;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(ij){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);}elseprintf(\n用ifft计算出的原序列是:\n\n);for(i=0;in;i++)if(z==0){printf(%7.3f,a[i].x);if(a[i].y=0)printf(+%7.3fj\n,a[i].y);elseprintf(-%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);elseprintf(-%7.3fj\n,fabs(a[i].y));}}printf(\n);}分裂基FFT算法程序/*Free_Copy*//*主程序:64点分裂基FFT算法*//*输入:64点任意序列*//*输出:序列的FF