3FFT复习与习题解答

1、总结 1直接用dft计算运算量与用fft计算的运算量比较。 2.多种dft算法(时间抽取算法dit算法，频率抽取算法dif算法 3线性调频z变换即czt 4.fft的应用 重叠相加法 重叠保留法直接用dft计算的运算量与用fft计算的运算量比较，减少运算量的途径）分解法（）合并法（减少运算量的途径：次。复加次复乘计算的运算量：用）次。（次，复加复乘计算的运算量：直接用21log,log21222nnnnfftnnndft一个完整n=8的按dit时间抽取fft的运算流图 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38w28w18w08w08w08w08w08w08w08w2

2、8w28wx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)12/0nnnww其中旋转因子，共有m=0m=1m=2一个完整n=8的按dif频率抽取fft的运算流图 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)38w28w18w08w08w08w08w08w08w08w28w28wx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)12/0nnnww其中旋转因子，共有m=0m=1m=2czt公式1, 1 , 0),()()()()()(1, 1 , 0, )()()(11 , 0)(11 , 0,)()(,221022200222220mknhngz

3、xnhngzxzzmknkhngzxmnnhnnanxngeeaaazkkkkknnkknnnjjkk得到，即：的离散卷积值并乘与可以通过变换值点的由上式可知：令说明1（1）a为起始样点位置，表示在园内通常正可负，为角频率）：为起始样点相角（可：为起始样点半径，1,00000aaeaaj说明2（2）zk是z平面一段螺线上的等分角上某一采样点。上的一部分。，这段园弧则是单位园若的一段园弧，：表示半径弯曲（向原点盘旋）围线（螺线）盘旋向内的增加，随着盘旋向外弯曲的增加，围线（螺线）随着弯曲。旋是向内弯曲还是向外它的大小控制着围线盘：为螺线的伸展率。其中11:1:1;00000000)(00000a

4、akkeeaaeazjjkjkkk说明3的路径是逆时针旋转。为正时，表示当的路径是顺时针旋转。为负时，表示当它可以是正值或负值。（即之间角频率差。：表示两相邻kkkzzzzzzz0021100),)3(说明4变换）（线性调频此变换称为线性调频信号（号为在雷达系统中称这种信（列成线性增长的复指数序随时间可以想象为频率）序列（zcztsignalchirpenhnnhnjnn)()()(522022022重叠相加法 （1）x(n)为分段，每段长为p点，p选择与m数量组相同。用xi(n)表示x(n)的第i段.）点重叠。相邻两段输出序列有（点，长度为点，而长度为重叠部分相加起来：将各段点计算相乘：点计

5、算点）计算（11)()()()()()4()()()3()()()()2()()(),()(1010)()(1) 1(01) 1()()(10mmpnypnxnynynykyifftnyifftlkxkhkynhdftkhnxdftkxdftllnmmnnhnhlnpipinipnxnxdftliiiiiiiiiiii重叠保留法)()()()3()()()()(211) 1()()(1kxkhkynxdftkxnhdftkhfftnmmnllmmnnxnxiiiii相乘点）计算（个零值点。则需要在它前边填充前一段保留信号，而对第一段，由于没有，准备进行圆卷积。点短序列组成个输入序列值，的再补上

6、前一段保留下来段的前边这样分段后，应在每一为短序列的长度；点，每段长度为，分成几个短序列）先将（专题1.dft与fft计算量的比较p252页，2题)(13824. 0512)(02304. 05*9*5125*log)(1152. 050*9*25650*log2)(418.14512)(308. 15*) 1)(11.1350*),(512.5,502222sfftsnfftsnfftsdftsnndftsndftfftnxdftususnn点共需时间来计算用运算需要复加次数用运算需要复乘次数用共需要时间点直接计算（需要复加次数直接计算需要复乘次数直接计算解：运算需要多少时间。间，用问直接计

7、算需要多少时点的用它来计算每次复加需的速度为平均每次复乘、如果一台通用计算机专题2 fft算法 1.注意输入、输出、蝶形结、旋转因子 2.注意每 一级有多少蝶形单元 3.旋转因子求解时有何特殊方法 4.蝶形单元的输入与输出是在时域还是在频域？p252,第3题n=16点基2-按时间抽取的fft运算x(0)x(8)x(4)x(12)x(2)x(10)x(6)x(14)x(1)x(9)x(5)x(13)x(3)x(11)x(7)x(x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(8)x(9)x(10)x(11)x(12)x(13)x(14)x(15)016w016w016w016

8、w016w016w016w016w016w016w016w016w416w016w116w216w316w416w616w716w016w216w416w616w016w216w416w616w616w416w416w416w416w516w 试求出n=64时用dit共有多少级，每级有多少个蝶形单元，并写出每一级的旋转因子。个共，旋转因子为个共，旋转因子为个共，旋转因子为个共，旋转因子为个共，级，旋转因子为个为级，旋转因子为所以蝶形图共有六级解：32, 516,48,34, 221102643164264164064306446426406428648644640642464166486406

9、416640640166wwwwmwwwwmwwwwmwwwwmwwmwmn专题3 czt变换实现过程示意图。的路径及画出，平面路径为：已知点的复频谱法求其前试用其他点序列已知一个题页第cztzazzxcztnnnxnxpkk2022 . 138 . 0).(100701)()(8102530000312524102.10902.1)(3180702.18.0)(32),(),()2(32221711081)1(97,2.1)(70,2.18.0)()(20)32(2)32(202)203(252022)203(22222222222222nnenenhnnengnhnglmnlnenhnea

10、nxngnjnnjnnnjnnnjnnnnjnnnn点补零加长至将点，取由于采用基点解：)103(70702)2 . 1 ()8 . 0()()(90),()()6()()(,)5()()()()4()(),()3(2nknjnnknnnknkkkeanxzxcztkkqzxrqifftkqifftrhrgrqrhrg法求得以上求求出30.8202im(z)re(z)zk的路径示意图x(n)22nna22)(nnh22k)(kzx实现过程示意图专题4 fft的应用 p253页，第8题有一个fir滤波器处理机，用fft算法分段过滤信号，每段运算n=1024点，运算一遍需要0.2s,处理机具有两组1024个单元的复数存储器可供交替使用，一组供运算时，另一组可用来存储实时输入的信号序列。用该处理机并配以a/d变换器作连续信号的实时过滤，问：(1)抽样频率最高可达多少?(2)若作两路信号同时过滤时，抽样频率最高是多少?(3)在这两种情况下最高可以处理多高频率的信号