第四章 快速傅立叶变换运算需要多少时间。

计算需要多少时间，用，问直拉点的，用它来计算每次复加速度为平均每次复乘需如果一台通用计算机的FFT DFT[x (n)]512s 5 s 50.1μμ 解: 解: ⑴ 直接计算: 复乘所需时间:复加所需时间: ⑵用FFT 计算:复乘所需时间: 复加所需时间:运算一次完成。

点试用一个为了提高运算效率值求今需要从值的点实序列是两个已知IFFT N n y n x k Y k X DFT n y n x N k Y k X ,,)(),()(),(,)(),()(),(.2sN T N 01152.0 512log 105 log 105 2251262261=⨯⨯⨯=⨯⨯=--s T T T sN N T 013824.0 002304.0 512log 512105.0 log 105.0 2126262=+=∴=⨯⨯⨯=⨯⨯⨯=--sT T T sN N T 441536.1 130816.0 )1512(512105.0 )1(105.0 21662=+=∴=-⨯⨯⨯=-⨯⨯⨯=--s N T 31072.1 512105 105 26261=⨯⨯=⨯⨯=--值的过程。

）（），（完成计算点）可用一次（）（）（综上所述，构造序列）（）（）（）（可得：）（）（）（再根据都是实序列，）（），（由原题可知：）（）（）（）（（）（）（性质：又根据可得序列点作对取序列依据题意解 ]Im[ ]Re[ ][][ ][ ).()( )()()( )()();()( ::n y n x IFFT N k jY k X k Z n z n y n z n x n jy n x n z n y n x n jy n x k Y jIDFT k X IDFT k jY k X IDFT DFT n z IFFT N k Z k jY k X k Z k Y n y k X n x +===+=+=+=++=⇔⇔。

输出倒位序顺序频率抽取采用输入自然输出自然数顺序序时间抽取采用输入倒位流图抽取法的按时间抽取法及按频率画出基时), ,,( 2,16.3FFT N -=。

的运算量及乘不计乘相比较的基并就运算量与公式并画出流图基导出时)(2,4,16.4j j FFT FFT N ±±--=),( )4()()(),( )4()()(3,2,1,03,2,1,0,)( ,3,2,1,03,2,1,0;, 440101011010102101011120102121k k X k k X k r k X k X n n x n n x n r n x n x k k k r k k N k k r r N n n n r n n N n r r N =+=+==+=+=∴⎩⎨⎧==+=<=⎩⎨⎧==+=<∴=⨯=有对于频率变量同样令有对于解：依题意：∑∑∑∑∑====++=+=+==∴30316416416013030)4)(4(160115016010010******** )4( )4()()(n n k n k n k n n n k k n n n nkW W W n nx W n n x W n x k X并画出流图。

采用基的结果算法求为组合数时的试用,)43(12.5⨯-=NFFTN1 20 10 21213,2,1,02,1,0 ,,,43rrNnnnrn nNnr r N=⎩⎨⎧== +=<≤∴=⨯=令同样：有对于解：依题意：∑∑∑==++===∴=+=+==+=+=∴⎩⎨⎧==+=<≤32)3)(4(1211112111111211110111),()()(),()3()()(),()4()()(2,1,03,2,1,0,)0(n nkknnnnkWnnxWnxkXkkXkkXkrkXkXnnxnnxnrnxnxkkkrkkNkk有对于频率变量并画出流图。

的结果同上题导出,52330.6⨯⨯==N∑∑∑∑==+===∴=++==++=∴++===∴========2903001201201201201232103012245010'22103)3(300102010'21121'1010*********'1023120101)()(),,()36()(),,()510()()36( ),,( ),,()(4,3,2,1,0,),,(),,( ),,(),,(1,0,),,(),,(),,(),,(2,1,0,),,(),,(02000111101202n nkn k n n k k n k n k n n k n W n x k X k k k X k k k X k X n n n x n n n x n x k k k X k k k X k k k X k X k W n k k Xk k k X W n k k X n k k X k Wn n k X n k k X W n n k X n n k X k Wn n n x n n k X 则令⎪⎩⎪⎨⎧===++=++=<≤=⎪⎩⎪⎨⎧===++=++=<∴=⨯⨯=2,1,01,04,3,2,1,0;36)300(,4,3,2,1,01,02,1,0 ;510 ,5230120120*********12012031322321k k k k k k k r k r r k k k k r r r N n n n n n n n r n r r n n N n r r r N 有对于频率变量令同样：有对于解：依题意：流图如下图所示:MN b M N a N z X DFT N N k e z N zn x z X z nn x n x n x M k Nj M n n>≤-===⎩⎨⎧≤≤=∙∙∙∑-=- )(;)(:)(,,1,,1,0,,)()( 0,1-M n 0 ),()(,)(.721之个抽样的方法，并证明的就能计算点找出用一个情况试对下列上的抽样即在上的抽样个等间隔点在单位圆上变换我们希望计算求其他点的有限长序列研究一个长度为π{}200011110102200010200111210202101201205)3(302106301220403033063053015302010103001242010)36)(510(301240 ),,( ),,(),,(k n n k k k n n k n k n n n k n k n k n k n k n n n k n n n n k k k n n n n W W W W W n n n x W W W W W Wn n n x Wn n n x +========++++=⨯⎥⎥⎦⎤⎢⎢⎣⎡⎥⎥⎦⎤⎢⎢⎣⎡⎪⎪⎭⎫ ⎝⎛=⨯==∑∑∑∑∑∑∑∑∑∑∑∑∑--=--=--=--=-+++=<≤-=≤∙∙∙1)1( 212 2122122)()()()()1()()( , )(M Nl n kn Nj N N n kn Nj N n kn Nj k Nj M n kn Nj kNj en x en x en x eX lN M N l en x eX M N a ππππππ设依题意若解：10,)()(1010)()(,)()()(, )( )]([)()1)1(0(])1([)()10( ])2([)(),()(),()(,])1([)()(1020201101221210 2 )(21)1(0])1([21)(212-≤≤=⎩⎨⎧-≤≤-≤≤=>≤=∴---≤≤-+=-≤≤-+=+===-+++++=∑∑∑∑∑∑∑-=--=-=-=----+----=-+--=+--=-∙∙∙∙∙∙∙∙∙N k e n xeX N n M M n n x n x N n x M N b N z X DFT N n yM N en yeX N l M n N l n x n y N n N l n x n y N n x n y n x n y eeeN l n x eN n x en x N n kn Nj k Nj l m mN n l m kn Nj mk Nj l l kn Nj klN n Nj N l M n kN l n j N n kN n Nj N n kn Nj πππππππππ则：即点到补零，可将若：点抽样在单位圆上的即可计算点，然后对它求一次，可先计算由此可见，对于且令：实现过程示意图。

的路径及画出平面路径为。

已知的复频谱点法求其前面试用其他点序列已知一个CZT z A z z X CZT n x k k ; 20/2 ,2.1W ,3/ ,8.0)( 10 n,07n 0 ,1)( 8.80000πφπθ====⎩⎨⎧≤≤=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.0 2.1;8.022 22722)(222270]32)(20220[2)(21222202222221)310(707)310(2020300=*======⨯⨯⨯=∴--+=≤≤⨯==∴≤≤⨯======--=---=+-------+-=-=-+----∑∑∑∑k k h k g Wz X nWn h n W A n x n g W WA n x We e z X n k k n nk k e z n x z X k e AW z e eW W e e A A k k n n n n n k n n k n n n k n j n k n n k j k k nk j n nk nn nkk k j kkk j j j j 则：令则解：依题意：πππππππππϕπθ由（1）式可得k z 的路径，如下表所示:{}时的抽样。

为实数在变换不能计算即线性调频两者都不行两者都行和为实数为实数使变换的的实轴上各点平面在点有限长序列计算一个可以用来变换线性调频的结论在下列说法中选择正确z H(z)z ,(b)(b)(a) (c)0a ,a 1,-N ,1,0,k ,z (b)1a ,a 1,-N ,1, 0,k ,)(:),( )()(..9k ≠==±≠==∙∙∙∙∙∙ak a z a z H z z z z n h M CZT z k k k1,,1,0 , )()()()()()1( 0 ,0 , , 1 , )(,,,1,,1,0)()()(102/2/)(102/2/10001000000)(0010222200-=-===±≠=====∴-====∙∙∙∙∙∙∙∙∙∑∑∑∑-=---=---=--+---=-N k n k p n g a a a n h aa n h z H a a z a W A z z n h W A N k e W A AW z zn h z H a M n k n k M n nk M n nk k kk k j k k k M n n kk 此时即可只需取变换各点的上平面实轴在若求有限长序列都是任意实数其中：是正确的。