《南京大学dsp_c04 fft》由会员分享，可在线阅读，更多相关《南京大学dsp_c04 fft（71页珍藏版）》请在金锄头文库上搜索。
1、第四章FFTInternal Use Only24.1引言 DFT和卷积是信号处理中两个最基本最常用的运算 卷积可化为DFT来实现，其它许多算法如相关，滤波 和谱估计也都可用DFT来实现 DFT的运算量大，无法达到实时 快速傅氏变换（FFT）是DFT的快速算法 1965年库利和图基发表了FFT算法，使DFT运算缩短了 12个数量级，DSP发展的一个里程碑 FFT的其它算法(基2及N不等于2的整数次幂的算法， 素因子算法、WFTA算法)Internal Use Only34.2直接DFT的运算1、DFT运算量1010( )N( )( ),(0,1,.,1)1( )( ),(0,1,.,1)1DF
2、TIDFT1(2)DFTIDFTN nk N nN nk N knknk NNx nX kx n WkNx nX k WnNNWWN= =设的长度为 ，与类似（ ）因子运算程序同样适用于Internal Use Only41023102421024N56648N) 1()(1NN)()()(202，复加，复乘 ，复加，复乘例如：次复加次复乘，运算需全部次复加次复乘，运算需一个NNNkXkXkXWnxnk N复数Internal Use Only52、改善DFT运算的途径 WNnk的对称性 WNnk的周期性 WNnk的可约性 FFT将长序列的DFT分解为短序列的DFT1.2 =NNjN NeW
3、)()(Nkn NkNn Nnk NWWW+=12 *=NNjNWeWnk Nnk NWW=*)(NNjmmNjm mNWeeW=2.2 nk Nmnk mNWW=Internal Use Only64.3按时间抽取（DIT）的基2 FFT（库利图基）1、算法原理12,.,1 , 0) 12()()2()() 10)(FFT2FFT2N,2N21L= +=NrrxrxrxrxnNnnxL的奇偶分成下面两组：按算法的：基的整数次幂的为为整数设序列的点数Internal Use Only7)()()()()()() 12()2()()()()()(211202/21202/11202 21202
4、1120) 12(1202101010kXWkXWrxWWrxWrxWWrxWrxWrxWnxWnxWnxnxDFTkXk NNrrk Nk NNrrk NNrrk Nk NNrrk NNrkr NNrrk NNnnnk NNnnnk NNnnk N+=+=+=+=+=+=奇数偶数一个N点DFT分解为 两个N/2点DFTInternal Use Only8)()()2()2()2()()2()()()()2(2122 12211202/1120)2(2/11kXWkXkNXWkNXkNXkXkNXkXWrxWrxkNXk NNkNNrrk NNrkNrN=+=+=+=+=+同理：蝶形算符后半部
5、分X(k)Internal Use Only9N=8分解为两个4点DFTInternal Use Only10少一半运算量相对于直接运算，可减复加复乘，运算量为：点复加复乘，个蝶结，此外还有复加复乘，的运算量为点两个复加复乘，）有（点每个，点分解为两个点乘，二次复加每个蝶形运算：次复2N 2N 2NDFTNN2N 2N) 12(N2NDFT2N) 12(22NDFT2NDFT2NDFTN2222+NNNInternal Use Only11=+=+=+=+=+= =+=1404441404334 2314 2314044 214043140)12(2114022114131)()( ,)()(
6、)()()4(14,.,2 , 1 , 0 )()( )()( ) 12()2()(14,.,2 , 1 , 0)() 12()()2(4N 2NNk NNk Nk Nk NNk Nk NNk NNk NNk NWxkXWxkXkXWkXkNXNkkXWkXWxWWxWxWxkXN xxxxlllllllllllllllllllllll点序列解为两个还为偶数，可进一步分由于Internal Use Only12)()()4()()()(DFT4N)(6 2526 2522kXWkXkNXkXWkXkXkXk Nk N=+=点分解为两个同样也可将N=8N/2点DFTN/4点DFTN/4点DFTN
7、/4点DFTN/4点DFTN/2点DFT（4点） （2点）Internal Use Only13两个N/4DFT构成一个N/2点DFTInternal Use Only14N8按时间抽取Internal Use Only15也可用一个蝶结表示因而两点两点DFT1)4()0()4()0() 1 ()0() 1 ()4()0()4()0() 1 ()0()0() 1 , 0()()()()(),(),(),(:DFT022 1 201 231 23300 230 23310431404336543NjjNNk NNk NWeeWxWxxWxxWxXxWxxWxxWxXkWxWxkXkXkXkXkX
8、=+=+=+=+=+= llllInternal Use Only16N8按时间抽取Internal Use Only172、运算量 N2L时，共有L级蝶形，每级有N/2个蝶结复加 复乘 直接级 次复加次复乘 个蝶 二次复加一个蝶 一次复乘) 1(NNN2NNLL2NLN2N 2N222NDFTNLogNLogInternal Use Only18Internal Use Only19Internal Use Only203、算法特点 原位运算 每一级运算均由N/2个蝶结构成，且某一列的N 个数据经蝶形运算，其结果为另一列N个数据， 可存储在同一组存储器中=+= )()()()()()(111
9、1 jXWkXjXjXWkXkXmr Nmmmr NmmInternal Use Only21 倒位序规律 输入倒位序，输出自然序 倒位序x(n)偶奇不断分组Internal Use Only22 倒位序的实现 变址运算（n2n1n0)- - - - (n0n1n2)(nx) (nxInternal Use Only23倒位序的变址处理nn=不交换YNnn=Q形成 点序列，偶对称，如则只需求出区间 点序列与上类似，采用递归方法，需次复乘共需三次 点，需次复乘需 次复乘需次复乘总的复乘次数为：223log3N2NLMlog5NLM22 ()NMkLLLLX z 而直接计算需次乘法CZT的输入点数
10、N及输出点数M没有限制，各zk间的角度可以任意 因而频率分辨率可调整，计算ZT的周线可以不是圆而是螺线，起始 点可任意选定。便于作窄带高分辨率分析。Internal Use Only524.7 线性卷积的FFT算法1、直接算法2/FIR1)()()()()()(10LMLMMLnymnxmhnyMnhLnxMm减一半滤波器中，可将运算量在线性相位次复乘点，其运算量为为点序列点序列，设+=( )(1)h nh Mn= Internal Use Only532、圆周卷积计算线卷积Nlog23log21),()()4),()()()3log21),()()2log21),()(1)()()()(10
11、10)()(,1010)()(N0)(,N0)(2222总的运算量为：）的步骤如下：计算点至补点至补NNNNkYIDFTnyNkHkXkYNNnxDFTkXNNnhDFTkHnyFFTnhnxnyNnMMnnhnhNnLLnnxnxnhnx= = =Internal Use Only54MMMNMLnhnxMLMLLMNNNLM222log6102,)()() 1)1(log231)1(2/log232/+= +效率比点数差不多，与效率比采用分段卷积的方法太大时，效率下降，需 效率比的点数很多时LLLMLNMLnx2log32M1,)()2+=Internal Use Only55124- 2
12、( )0,1L( )01L1001L150x nx n例：设为在区间上均匀分布的 点随机序列，是均值为 ，方差为 的 点高斯分布随机序列，通过计算次随机序列的卷积，确定时的卷积计算平均时间Internal Use Only56 重叠相加法)()()(,21MLN0)()()(*)()(*)()(*)()()()(,.1 , 0, 01) 1(),()(L)()(M)(00nhnxnynhnxnhnxnhnxnhnxnynxnxinLiniLnxnxnxnxnhiimiiiiiii= +=至补及，对可用圆卷积的方法实现其它点的多段分为为很长的序列，将，的点数为Internal Use Only5
13、7=+0)()()()5)()(,IFFTN)4)()()()3)()(,FFTN)2)()(,FFTN1)1M1M11)(L)(iiiiiiiiiiinynynykYIDFTnykHkXkYnxDFTkXnhDFTkHMMLnynx相加，包括重叠部分将各段点计算相乘，点计算点计算：重叠相加法的步骤如下点重叠点与后一段的前即前一段的后点重叠点，相邻两段输出有为点，为Internal Use Only58Internal Use Only59Internal Use Only60 重叠保留法10(1) ( )1,M1( )(2)( )( )( )( ) ()( )(3)M1(4)iNiiiNN
14、mx nLNMNx ny nx nh nx m h nmRn=+=分段，每段再在每一段的前面补上前一段保留下来的 个输入值，组成 点序列将每一段圆卷积结果的前 个值去掉将输出序列重新组合相加Internal Use Only61重叠保留法示意图Internal Use Only62重叠保留法示意图Internal Use Only63点应去除每一段圆周卷积前时，而不同于线性卷积的结果此时值，围的末端出现非范在时，点圆周移位时后作点，补为象：重叠保留法中的混叠现1-M)()()()(1N1-M)()()( 0 10)()(20N0M)()()()()()()(10=mnhnRmnhmxnnRmn
15、hmxNmnRmnhMnmhnRmnhmxnhnxnyNNiNNiNNNmNNiiiQInternal Use Only64重叠保留法中的混叠现象Internal Use Only65重叠保留法中的混叠现象Internal Use Only66 MatLab实现10y(x,h,N)0( ),10 ( )0,0.,0, ( ),01, ( )( );1,0,012 1,( )( )( )( )( )Mkx xkkkfunctionhsolpsavnx nM x nx nnLNMk x nx m kLmkLNknNNMKNx nL y nx nh ny n= =+ =+=+=14 2 43 个时给定在分段之前，先将前个样本置设则第 段为：所分的段数为：为的长度最后丢弃每一个1M 中的
