数字信号处理：第4章1快速付里叶变换FFT

1、第四章第四章快速付里叶变换快速付里叶变换(FFT)Fast FourierTransforming第一节第一节 引引 言言一、快速付里叶变换一、快速付里叶变换FFT 有限长序列通过离散傅里叶变换有限长序列通过离散傅里叶变换 (DFT)将其频将其频 域离散化成有限长序列域离散化成有限长序列.但其但其计算量太大计算量太大(与与N的平方成正比）的平方成正比）, 很难很难 实时地处理问题实时地处理问题 , 因因 此此 引引 出出 了了 快快 速速 傅傅 里里 叶叶 变变 换换(FFT) . FFT 并并 不不 是是 一一 种种 新新 的的 变变 换换 形形 式式 ,它它 只只 是是 DFT 的的 一一

2、 种种 快快 速速 算算 法法 . 并并 且且 根根 据据 对对 序序 列列 分分 解解 与与 选选 取取 方方 法法 的的 不不 同同 而而 产产 生生 了了 FFT 的的 多多 种种 算算 法法 . FFT 在在 离离 散散 傅傅 里里 叶叶 反反 变变 换换 、 线线 性性 卷卷 积积 和和 线线 性性 相相 关关 等等 方方 面面 也也 有有 重重 要要 应应 用用.。二、FFT产生故事 当时加文当时加文(Garwin)在自已的研究中极需要一个计算在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基付里叶变换的快速方法。他注意到图基(J.W.Turkey)正正在写有关付里叶变

3、换的文章，因此详细询问了图基关在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。在加文的迫切要求下，库利很图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。快设计出一个计算机程序。1965年年库利库利-图基在图基在、Mathematic of Computation 杂志上发表了著杂志上发表了著名的名的“机器计算付里级数的一种算法机器计算付里级数的一种算法”文章，提出一文章，提出一

4、种快速计算种快速计算DFT的方法和计算机程序的方法和计算机程序-揭开了揭开了FFT发展发展史上的第一页，促使史上的第一页，促使FFT算法产生原因还有算法产生原因还有1967年至年至1968年间年间FFT的数字硬件制成的数字硬件制成，电子数字计算机的条，电子数字计算机的条件，件， 使使DFT的运算大简化了。的运算大简化了。三、本章主要内容 1.直接计算直接计算DFT算法存在的问题及改进途径。算法存在的问题及改进途径。 2.多种多种DFT算法算法(时间抽取算法时间抽取算法DIT算法，频率算法，频率抽取算法抽取算法DIF算法，线性调频算法，线性调频Z变换即变换即CZT法法) 3.FFT的应用的应用第

5、二节第二节直接计算直接计算DFT算算法存在的问题及法存在的问题及改进途径改进途径一、直接计算一、直接计算DFT计算量计算量 问题提出：问题提出： 设有限长序列设有限长序列x(n),非零非零值值长度为长度为N,计算对计算对x(n)进行一次进行一次DFT运算，共需多大的运算，共需多大的运算工作量运算工作量?1.比较比较DFT与与IDFT之间的运算量之间的运算量10)()()(NnknNDFTWnxkXnx1, 1 , 0Nk101( )( )( )NIDFTknNkX kx nX k WN 1, 1 , 0Nn其中其中x(n)为为复数复数， 也为也为复数复数所以所以DFT与与IDFT二者二者计算量

6、相同计算量相同。knNjknNeW22.以以DFT为例，计算为例，计算DFT复数运算量复数运算量 计算一个计算一个X(k)(一个频率成分一个频率成分)值，运算量为值，运算量为例例k=1则则要进行要进行N次复数乘法次复数乘法+(N-1)次复数加法次复数加法所以，要完成整个所以，要完成整个DFT运算，其计算量为：运算，其计算量为：N*N次复数相乘和次复数相乘和N*(N-1)次复数加法次复数加法10)() 1 (NnnNWnxX3.一次一次复数乘法换算成实数运算量复数乘法换算成实数运算量 复数运算要比实数运算复杂，需要的运算时复数运算要比实数运算复杂，需要的运算时间长。间长。 一个复数乘法一个复数乘

7、法包括包括4个实数乘法个实数乘法和和2个实数相个实数相法法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad) 4次实数乘法次实数乘法2次实数加法次实数加法4.计算计算DFT需要的实数运算量需要的实数运算量 每运算一个每运算一个X(k)的值，需要进行的值，需要进行4N次实数相乘次实数相乘和和 2N+2(N-1)=2(2N-1)次实数相加次实数相加.整个整个DFT运算量为：运算量为：4N2次实数相乘和次实数相乘和2N(2N-1)次次实数相加实数相加.由此看出：直接计算由此看出：直接计算DFT时，时，乘法次数与加法次乘法次数与加法次数都是和数都是和N2成比例成比例的。当的。当N很大时，所需

8、工作量很大时，所需工作量非常可观。非常可观。)Re)(ImIm)(Re) Im)(ImRe)(Re)(10knNknNNnknNknNWnxWnxjWnxWnxkX例子例子 例例1:当当N=1024点时，直接计算点时，直接计算DFT需要：需要： N2=220=1048576次，即一百多万次的复乘运次，即一百多万次的复乘运算，这对实时性很强的信号处理算，这对实时性很强的信号处理(如雷达信号如雷达信号处理处理)来讲，它对计算速度有十分苛刻的要求来讲，它对计算速度有十分苛刻的要求-迫切需要改进迫切需要改进DFT的计算方法，以减少总的计算方法，以减少总的运算次数。的运算次数。 例例2：石油勘探，石油勘

9、探，24道记录，每道波形记录长道记录，每道波形记录长度度5秒，若每秒抽样秒，若每秒抽样500点点/秒，秒， 每道总抽样点数每道总抽样点数=500*5=2500点点 24道总抽样点数道总抽样点数=24*2500=6万点万点 DFT运算时间运算时间=N2=(60000)2=36*108次次作业作业 P194页，第页，第1题题二、改善二、改善DFT运算效率的基本途径运算效率的基本途径利用利用DFT运算的系数运算的系数 的固有对称性和的固有对称性和周期性，改善周期性，改善DFT的运算效率。的运算效率。1.合并法合并法：合并：合并DFT运算中的某些项。运算中的某些项。2.分解法分解法：将长序列：将长序列

10、DFT利用对称性和周利用对称性和周期性，分解为短序列期性，分解为短序列DFT。knNW利用利用DFT运算的系数运算的系数 的固有对的固有对称性和周期性，改善称性和周期性，改善DFT的运算效的运算效率率knNWknNW的的对称性：对称性：nkNknNWW*)(knNW的的周期性：周期性：)()(kNnNkNnNknNWWW1)()(22kjkNNjkNNeeW因为：因为：1, 1 , 0Nk1)()(22njNnNjNnNeeW1, 1 , 0Nn由此可得出由此可得出：nkNknNNkNnNWWW)()()(1sincos)(222/jeWNNjNNkNNkNWW)(2例子例子 例例:1454)

11、54(494WWWW1898178258WWWW利用以上特性利用以上特性,得到改进得到改进DFT直接算法的方法直接算法的方法.(1) 合并法：步骤合并法：步骤1分解成虚实部分解成虚实部 合并合并DFT运算中的有些项运算中的有些项 对对虚实部而言虚实部而言 所以带入所以带入DFT中：中：*()()knk NnNNWWknNnNkNWWReRe)(knNnNkNWWImIm)(1) 合并法：步骤合并法：步骤2代入代入DFT中中1010Re)(ImIm)(ReIm)(ImRe)(Re)(NnnkNnkNNnnkNnkNWnxWnxjWnxWnxkX展开：展开：1010Im)Re(Im)(Re)()(

12、NnnkNnkNNnnkNWjWnxjnxWnxkX(1) 合并法：步骤合并法：步骤3合并有些项合并有些项nkNnNkNnkNWnNxnxWnNxWnxRe)(Re)(ReRe)(ReRe)(Re)(nkNnNkNnkNWnNxnxWnNxWnxIm)(Im)(ImIm)(ImIm)(Im)()ReRek NnknNNWW()ImImk NnknNNWW 根据：根据：有：有：(1) 合并法：步骤合并法：步骤4结论结论 由此找出其它各项的类似归并方法：由此找出其它各项的类似归并方法：乘法次数可以减少一半。乘法次数可以减少一半。例：例：1545) 15(515Re)4(Re) 1 (ReRe)4(

13、Re) 1 (Re) 15 (ReRe) 1 (ReWxxWxxWxWx2、将长序列、将长序列DFT利用对称性和利用对称性和周期性分解为短序列周期性分解为短序列DFT-思路思路 因为因为DFT的运算量与的运算量与N2成正比的成正比的 如果一个大点数如果一个大点数N的的DFT能能分解为若干小点分解为若干小点数数DFT的组合的组合，则显然可以达到减少运算工，则显然可以达到减少运算工作量的效果。作量的效果。2、将长序列、将长序列DFT利用对称性和利用对称性和周期性分解为短序列周期性分解为短序列DFT-方法方法22)()()(NNNkXkXkX把把N点数据分成二半：点数据分成二半：其运算量为：其运算量

14、为：2)2(N2)2(N2N再分二半：再分二半：44)()(NNkXkX44)()(NNkXkX+=22N2)4(N2)4(N2)4(N2)4(N+=24N这样一直分下去，剩下这样一直分下去，剩下两点的变换两点的变换。2、将长序列、将长序列DFT利用对称性和利用对称性和周期性分解为短序列周期性分解为短序列DFT-结论结论 快速付里时变换快速付里时变换(FFT)就是在此特性基础上就是在此特性基础上发展起来的，并产生了多种发展起来的，并产生了多种FFT算法，其算法，其基本上可分成两大类：基本上可分成两大类： 按抽取方法分：按抽取方法分： 时间抽取法时间抽取法(DIT);频率抽取法频率抽取法(DIF

15、) 按按“基数基数”分：分：基基-2FFT算法；基算法；基-4FFT算算法；混合基法；混合基FFT算法；分裂基算法；分裂基FFT算法算法 其它方法：其它方法：线性调频线性调频Z变换变换(CZT法法)第三节第三节基基-2按时间抽取的按时间抽取的FFT算法算法Decimation-in-Time(DIT)(Coolkey-Tukey)一、算法原理一、算法原理 设输入序列设输入序列长度为长度为N=2M(M为正整数，将该序为正整数，将该序列列按时间顺序的奇偶分解按时间顺序的奇偶分解为越来越短的子序列，为越来越短的子序列，称为称为基基2按时间抽取的按时间抽取的FFT算法算法。也称为。也称为Coolkey

16、-Tukey算法。算法。 其中基数其中基数2-N=2M，M为整数为整数.若不满足这个若不满足这个条件，可以人为地加上若干零值（加零补长）条件，可以人为地加上若干零值（加零补长）使其达到使其达到 N=2M例子例子 设一序列设一序列x(n)的长度为的长度为L=9,应加零补长为应加零补长为 N=24=16 应补应补7个零值。个零值。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 nx(n)二、算法步骤二、算法步骤1.分组，变量置换分组，变量置换DFT变换：变换：10)()(NnknNWnxkX1,0Nk先将先将x(n)按按n的奇偶分为两的奇偶分为两 组，作变量置换组，作

17、变量置换:当当n=偶数时，令偶数时，令n=2r;当当n=奇数时，令奇数时，令n=2r+1;得到：得到：x(2r)=x1(r); x(2r+1)=x2(r);r=0N/2-1; 则可得其则可得其DFT为两部分：为两部分：前半部分前半部分：后半部分后半部分：)()()(21kXWkXkXkN12/, 0Nk)()()2/(21kXWkXNkXkN2.代入代入DFT中中)()() 12()2()()21rxDFTrxDFTrxDFTrxDFTnxDFTkX（生成两个子序列生成两个子序列x(0),x(2)x(2r)偶数点偶数点x(1),x(3)x(2r+1)奇数点奇数点12/, 0Nr代入代入DFT变

18、换式：变换式：/2 1/2 12(21)00/2 1/2 1221200222/222/( )(2 )(21)( )()( )()NNrkrkNNrrNNrkrkkNNNrrjjNNNNX kxr WxrWx r Wxr WWeeWW3.求出子序列的求出子序列的DFT上式得：上式得：/2 1/2 11/22/200/2 1/2 111/2/200/2 1/2 122/012/202)( )( )( )( )(2 )( )( )( )( )0,211()/21NNrkrkkNNNrrNNrkrkNNrrNNrkrkNrNrkNX kx r Wxr WWXkx r Wxr WXkxr WXkW X

19、kkxrWN（其其中中：12/, 0Nk4.结论结论1 一个一个N点的点的DFT被分解为被分解为两个两个N/2点点DFT。X1(k),X2(k)这两个这两个N/2点的点的DFT按照：按照：12)( )0,1/21( )kNNDFTX kkkNXW Xk又又合合成成 点点中中的的前前半半部部分分（ 再应用再应用W系数的周期性系数的周期性，求出用，求出用X1(k),X2(k)表达的后半部的表达的后半部的X(k+N/2)的值。的值。5.求出后半部的表示式求出后半部的表示式12/012/022/2)2/(2/2212/012/012/1)2/(2/11)2/(2/2/)()()()2()()()()2

20、(NrNrrkNkNrNNrNrrkNkNrNNkrNrkNkXWrxWrxkNXkXWrxWrxkNXWW看出：后半部的看出：后半部的k值所对应的值所对应的X1(k),X2(k)则完全重复了前半部分则完全重复了前半部分的的k值所对应的值所对应的X1(k),X2(k)的值。的值。2/2)1/2(/2)( )( )NkNkkNkNNNNX kNX kW X kWWWW（又又后后半半部部分分：6.结论结论2频域中的频域中的N个点频率成分个点频率成分为：为：1212( )( )( )(/2)( )( )kNkNX kX kW XkX kNX kW Xk前前半半部部分分：后后半半部部分分：结论：结论：

21、只要求出（只要求出（0N/2-1）区间内的各个整区间内的各个整数数k值所对应的值所对应的X1(k),X2(k)值，值，即可以求出即可以求出(0N-1)整个区间内全部整个区间内全部X(k)值，这就是值，这就是FFT能能大量节省计算的关键。大量节省计算的关键。7.结论结论3由于由于N=2M，因此因此N/2仍为偶数仍为偶数，可以，可以依依照上面方法进一步把每个照上面方法进一步把每个N/2点子序列点子序列，再按输入再按输入n的奇偶分解为两个的奇偶分解为两个N/4点的子点的子序列，按这种方法不断划分下去，直到序列，按这种方法不断划分下去，直到最后剩下的是最后剩下的是2点点DFT，两点，两点DFT实际上实

22、际上只是只是加减运算加减运算。) 1 ()0() 1 () 1 ()0()0(2,)()(10 xxXxxXNWnxkXNnknN时三、蝶形结三、蝶形结即蝶式计算结构也即为蝶式信号流图即蝶式计算结构也即为蝶式信号流图上面上面频域频域中前中前/后半部分表示式可以用蝶形信号后半部分表示式可以用蝶形信号流图表示。流图表示。作图要素：作图要素：(1)左边两路为输入左边两路为输入(2)右边两路为输出右边两路为输出(3)中间以一个小圆表示加、中间以一个小圆表示加、减运算（右上路为相加输出、减运算（右上路为相加输出、右下路为相减输出右下路为相减输出)(4)如果在某一支路上信号需要进行如果在某一支路上信号需要

23、进行相乘运算，则在该支路上标以箭头，相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。将相乘的系数标在箭头旁。(5)当支路上没有箭头及系当支路上没有箭头及系数时，则该支路的传输比数时，则该支路的传输比为为1。X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN蝶形结描述的另一种方法蝶形结描述的另一种方法X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN1 例子：求例子：求 N=23=8点点FFT变换变换 （1）先按）先按N=8-N/2=4，做做4点的点的DFT：)()() 2/()()()(2121kXWkXNkXkXWkXkXkNk

24、N12/, 0Nk先将先将N=8DFT分解成分解成2个个4点点DFT：可知：可知：时域上时域上：x(0),x(2),x(4),x(6)为偶子序列为偶子序列 x(1),x(3),x(5),x(7)为奇子序列为奇子序列 频域上频域上：X(0)X(3)，由，由X(k)给出给出 X(4)X(7),由由X(k+N/2)给出给出(a)比较比较N=8点直接点直接DFT与分解与分解2个个4点点DFT的的FFT运算量运算量N=8点的点的直接直接DFT的计算量为：的计算量为：N2次次(64次）次）复数相乘复数相乘,N(N-1)次次(8(8-1)=56次次)复数相复数相加加.共计共计120次。次。（b)求求 一个蝶

25、形结需要的运算量一个蝶形结需要的运算量要运算一个蝶形结，需要要运算一个蝶形结，需要一次乘法一次乘法 ， 两次加法两次加法。)(2kXWkN)()() 2/()()()(2121kXWkXNkXkXWkXkXkNkN（c）分解为两个分解为两个N/2=4点的点的DFT的运算的运算量量分解分解2个个N/2点（点（4点）的点）的DFT：)(2 )(21)X kDFT x rDFT x r（偶数偶数其其复数相乘复数相乘为为复数相加复数相加为为奇数奇数其其复数相乘复数相乘为为复数相加复数相加为为22）（N）（122NN22）（N）（122NN次。共计为次，（次，复数相加为复数相乘为5624) 123222

26、NNN(d)用用2个个4点来求点来求N=8点的点的FFT所需的运算量所需的运算量再将再将N/2点（点（4点）合成点）合成N点点(8点点)DFT时，时，需要进行需要进行N/2个蝶形运算个蝶形运算)()() 2/()()()(2121kXWkXNkXkXWkXkXkNkN12/, 0Nk还需还需N/2次（次（4次）乘法次）乘法 及及 次次(8次）加法次）加法运算运算。22N)(2kXWkN2222(1)(18( )36,232,6822N NFFTX kNNNNNN）所所以以 点点求求共共需需次次复复数数乘乘法法次次复复数数加加法法 共共计计为为次次。看看出出仅仅做做一一次次分分解解就就可可以以节

27、节省省约约一一半半计计算算量量。(e)将将N=8点分解成点分解成2个个4点的点的DFT的信号流图的信号流图 4点点DFTx(0)x(2)x(4)x(6)4点点DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶偶数数序序列列奇奇数数序序列列3821282118210821) 3 () 3 (3) 2() 2(2) 1 () 1 (1) 0() 0(0WXXXWXXXWXXXWXXX）（）（）（）（如：X(4)X(7)同学们自已写同学们自已写

28、x1(r)x2(r)(2)N/2(4点点)-N/4(2点点)FFT(a)先将先将4点分解成点分解成2点的点的DFT： 因为因为4点点DFT还是比较麻烦，所以再继续分解。还是比较麻烦，所以再继续分解。 若将若将N/2(4点点)子序列按奇子序列按奇/偶分解成两个偶分解成两个N/4点（点（2点）点）子序列。子序列。即对将即对将x1(r)和和x2(r)分解成奇、偶两个分解成奇、偶两个N/4点点（2点）点的子序列。点）点的子序列。1(0)(4)( ):(2)(6)xxx rxx偶偶序序奇奇序序列列、列列、2(1)(5)( ):(3)(7)xxx rxx偶偶序序列列奇奇序序同同、列列、理理：1314(2

29、)( )01014(21xLx LxLx LNLL偶偶序序列列若若设设：（），在在此此，奇奇序序列列） （ ）2526(2 )( )01014(21xLx LxLx LNLL偶序列同理：（），在此，奇序列） （ ）(b)求求2点的点的DFT11/4 1/4 12(21)113/2413/2425/2625/21/20022/6( )( )(2 )(21)01( )( )( )(/4)( )( )( )( )( )(/4)( )kNkNkNkNDFTNNLkLkNNLLx rX kXL WXLWLx rX kXLWXLX kNXLWXLXkXLWXLXkNXLWXL 可分解为：其中，同理：同样，

30、也）可分解为：（c)一个一个2点的点的DFT蝶形流图蝶形流图2点点DFT2点点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W) 1 () 1 () 3 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(41431404314143140431XWXXXWXXXWXXXWXX其中（d)另一个另一个2点的点的DFT蝶形流图蝶形流图2点点DFT2点点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W) 1 (

31、) 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(61452604526145260452XWXXXWXXXWXXXWXX其中同理：同理：(3)将将N/4（2点）点）DFT再分解成再分解成2个个1点的点的DFT(a)求求2个一点的个一点的DFT21200022012200322003221220 1022(0)(0)(4)(1)(0)( )( )(0)(4)(0)(4)0,1;0,1(4)NnnknnknkknkNNXxWxWXxWxWX kx n WxWxWxWxWWWnkWWWW 代代入入上上面面流流图图可可知知：这这是是一一蝶蝶形形结结这这

32、里里用用到到对对称称性性，则则，其其中中 最后剩下两点最后剩下两点DFT,它可分解成两个一点它可分解成两个一点DFT，但一点但一点DFT就等就等于输入信号本身，所以于输入信号本身，所以两点两点DFT可用一个蝶形结表示可用一个蝶形结表示。取。取x(0)、x(4)为例。为例。(b)2个个1点的点的DFT蝶形流图蝶形流图 1点点DFTx(0)1点点DFTx(4)X3(0)X3(1)02W进一步简化为蝶形流图：进一步简化为蝶形流图：02WX3(0)X3(1)x(0)x(4)4()0()4()0() 1 ()4()0()4()0()0(023023xxxWxXxxxWxX其中：(4)一个完整一个完整N=

33、8的按时间抽取的按时间抽取FFT的运算流图的运算流图 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)0/ 2 1NNNWW其其 中中 旋旋 转转 因因 子子 ， 共共 有有m=0m=1m=2四、四、FFT算法中一些概念算法中一些概念 （1）“级级”概念概念 将将N 点点DFT先分成两个先分成两个N/2点点DFT，再是四个再是四个N/4点点DFT直至直至N/2个两点个两点DFT.每分一次称每分一次称为为“一一”级运算级运算。 因为因为N=2M所

34、以所以N点点DFT可可分成分成M级级 如上图所示依次如上图所示依次m=0,m=1.M-1共共M级级（2）“组组”概念概念 每一级都有每一级都有N/2个蝶形单元个蝶形单元，例如：，例如：N=8,则每级则每级都有都有4个蝶形单元。个蝶形单元。每一级的每一级的N/2个蝶形单元可以分个蝶形单元可以分成若干组，成若干组，每一组具有相同的结构每一组具有相同的结构，相同的，相同的 因因子分布，子分布，第第m级的组数为：级的组数为：rNW12mN例：例：N=8=23，分分3级。级。m=0级级,分成四组分成四组,每组系数为每组系数为m=1级级,分成二组分成二组,每组系数为每组系数为m=2级级,分成一组分成一组,

35、每组系数为每组系数为080204/WWWN28082012/02/,WWWWWWNNNN382818083210,WWWWWWWWNNNN(3) 因子的分布因子的分布rNW121 , 0,3 , 2 , 102101001238281808828081404408022mkkkkkWmWWWWkWmWWWWkWmWWkWmm级的系数为看出：第，级，级，级，由上可知：结论：结论：每由后向前（每由后向前（m由由M-1-0级）推进一级）推进一级，则此级系数取后级系数中偶数序号的那一级，则此级系数取后级系数中偶数序号的那一半。半。（4）按时间抽取法）按时间抽取法2点点DFT2点点DFT2点点DFT2点

36、点DFT2点点DFT2点点DFT2点点DFT2点点DFT两个两个2点点DFT两个两个2点点DFT两个两个2点点DFT两个两个2点点DFT两个两个4点点DFT两个两个4点点DFT两个两个N/2点点DFTX1(k).X2(k)X(k) 由于每一步分解都是由于每一步分解都是基于在每级按输入时间序列的基于在每级按输入时间序列的次序是属于偶数还是奇数来分解次序是属于偶数还是奇数来分解为两个更短的序列，为两个更短的序列，所以称为所以称为“按时间抽取法按时间抽取法”.x(n)五、按时间抽取的五、按时间抽取的FFT算法与直算法与直接计算接计算DFT运算量的比较运算量的比较 由前面介绍的按时间抽取的由前面介绍的

37、按时间抽取的FFT运算流图可见：运算流图可见： 每级都由每级都由N/2个蝶形单元构成个蝶形单元构成，因此每一级运算都，因此每一级运算都需要需要N/2次复乘和次复乘和N次复加次复加（每个结加减各一次）。这（每个结加减各一次）。这样（样（N=2M)M级运算共需要：级运算共需要： 复乘次数复乘次数： 复加次数复加次数： 可以得出如下结论：可以得出如下结论：按时间抽取法所需的按时间抽取法所需的复乘数和复加数都是与复乘数和复加数都是与成正比成正比。而直接计算。而直接计算DFT时所需的复乘数与复加数则都时所需的复乘数与复加数则都是与是与N2成正比成正比.(复乘数复乘数md=N2,复加数复加数ad=N(N-

38、1)N2)NFNMNm2log22NFNMNa2log2logNN例子例子 看看N=8点和点和N=1024点时直接计算点时直接计算DFT与用与用基基2-按时间抽取法按时间抽取法FFT的运算量。的运算量。4.102102227.224648loglog1020102222NNNNNNN看出：看出：当当N较大时，按时间抽取法将比直接法快一、较大时，按时间抽取法将比直接法快一、二个数量级之多。二个数量级之多。作业 P194，2及3中的DIT部分六、按时间抽取六、按时间抽取FFT算法的特点算法的特点 根据根据DIT基基2-FFT算法原理，能得出任何算法原理，能得出任何N=2m点点的的FFT信号流图，并

39、进而得出信号流图，并进而得出FFT计算程序流程计算程序流程图。最后总结出按时间抽取法解过程的规律。图。最后总结出按时间抽取法解过程的规律。 1.原位运算（原位运算（in-place) 2.码位倒读规则码位倒读规则1.原位运算（原位运算（in-place) 原位运算的结构，可以节省存储单元，降低设原位运算的结构，可以节省存储单元，降低设备成本。备成本。 定义：当数据输入到存储器以后，每一组定义：当数据输入到存储器以后，每一组运算运算的结果的结果，仍仍然存然存放放在这在这同一组存储器同一组存储器中直到最中直到最后输出。后输出。02Wx(0)x(4)X3(0)X3(1)中放在一个暂存器中放在单元中，

40、将放在单元例：将RWAxAx08) 1 ()4()0()0(单元送回单元送回将) 1 ()4()0()0()4()0(0808AxWxAxWx例子例子 例：例：N=8 FFT运算运算,输入输入:x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=X(0)A(1)=X(1)A(2)=X(2)A(3)=X(3)A(4)=X(4)A(5)=X(5)A(6)=X(6)A(7)=X(7)012

41、388881,23,4RWRW RWRW暂存器R1R1R1R1R1R3R1R1R3R2R3R4看出：用原位运算结构运算后，看出：用原位运算结构运算后，A(0)A(7)正好顺序存放正好顺序存放X(0)X(7),可以直接顺序输出。可以直接顺序输出。2.码位倒读规则码位倒读规则 我们从输入序列的序号及整序规律得到我们从输入序列的序号及整序规律得到码位码位倒读规则倒读规则。由。由N=8蝶形图看出：原位计算时，蝶形图看出：原位计算时，FFT输出的输出的X(k)的次序正好是顺序排列的，的次序正好是顺序排列的，即即X(0)X(7),但输入但输入x(n)都不能按自然顺序都不能按自然顺序存入到存储单元中，而是按

42、存入到存储单元中，而是按x(0),x(4),x(2), x(6).的顺序存入存储单元即为的顺序存入存储单元即为乱序输入乱序输入，顺序输出顺序输出。这种顺序看起来相当杂乱，然而。这种顺序看起来相当杂乱，然而它是有规律的。即它是有规律的。即码位倒读规则码位倒读规则。例子例子以以N=8为例：为例：01234567000001010011100101110111自然顺序自然顺序n二进制码表示二进制码表示码位倒读码位倒读码位倒置顺序码位倒置顺序n00010001011000110101111104261537看出：看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。码位倒读后的顺序刚好是数据送入计算机内的顺序。整序重排子程序整序重排子程序具体执行时，只须将具体执行时，只须将1与与4对调送入，对调送入，3与与6对调送入，而对调送入，而0，2，5，7不变，仅需要一个中间存储单元。不变，仅需要一个中间