4-快速傅里葉變換解析

1、第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 1第第4章章 快速傅里葉變換快速傅里葉變換 4.1 引言引言 4.2 直接計(jì)算直接計(jì)算DFT的問題及改進(jìn)的途徑的問題及改進(jìn)的途徑 4.3 按時(shí)間抽取（按時(shí)間抽?。―IT）的基）的基2-FFT算法算法4.4 按頻率抽取（按頻率抽?。―IF）的基）的基2-FFT算法算法4.5 離散傅里葉反變換（離散傅里葉反變換（IDFT）的快速計(jì)算方法）的快速計(jì)算方法 4.10 線性卷積的線性卷積的FFT算法算法 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 24.1 引引 言言 快速傅里葉變換（快速傅里葉變換（FFT）并不是一種新的變換，并不是一種新的變

2、換， 而是而是離散傅里葉變換離散傅里葉變換（DFT）的一種快速算法）的一種快速算法。 由于有限長(zhǎng)序列在其頻域也可離散化為有限長(zhǎng)序列（由于有限長(zhǎng)序列在其頻域也可離散化為有限長(zhǎng)序列（DFT），因此離散），因此離散傅里葉變換（傅里葉變換（DFT）在數(shù)字信號(hào)處理中是非常有用的。例如，在信號(hào)的頻譜）在數(shù)字信號(hào)處理中是非常有用的。例如，在信號(hào)的頻譜分析、分析、 系統(tǒng)的分析、系統(tǒng)的分析、 設(shè)計(jì)和實(shí)現(xiàn)中都會(huì)用到設(shè)計(jì)和實(shí)現(xiàn)中都會(huì)用到DFT的計(jì)算。的計(jì)算。 但是，在相當(dāng)長(zhǎng)但是，在相當(dāng)長(zhǎng)的時(shí)間里，的時(shí)間里， 由于由于DFT的計(jì)算量太大的計(jì)算量太大，即使采用計(jì)算機(jī)也很難對(duì)問題進(jìn)行實(shí)時(shí)，即使采用計(jì)算機(jī)也很難對(duì)問題進(jìn)行實(shí)

3、時(shí)處理，所以并沒有得到真正的運(yùn)用。處理，所以并沒有得到真正的運(yùn)用。 直到直到1965年首次發(fā)現(xiàn)了年首次發(fā)現(xiàn)了DFT運(yùn)算的一種運(yùn)算的一種快速算法以后，情況才發(fā)生了根本的變化。人們開始認(rèn)識(shí)到快速算法以后，情況才發(fā)生了根本的變化。人們開始認(rèn)識(shí)到DFT運(yùn)算的一些運(yùn)算的一些內(nèi)在規(guī)律，從而很快地發(fā)展和完善了一套高速有效的運(yùn)算方法，內(nèi)在規(guī)律，從而很快地發(fā)展和完善了一套高速有效的運(yùn)算方法， 這就是現(xiàn)在這就是現(xiàn)在人們普遍稱之為快速傅里葉變換（人們普遍稱之為快速傅里葉變換（FFT）的算法。）的算法。 FFT出現(xiàn)后使出現(xiàn)后使DFT的運(yùn)算的運(yùn)算大大簡(jiǎn)化，運(yùn)算時(shí)間一般可縮短一二個(gè)數(shù)量級(jí)之多，從而使大大簡(jiǎn)化，運(yùn)算時(shí)間一般

4、可縮短一二個(gè)數(shù)量級(jí)之多，從而使DFT的運(yùn)算在實(shí)的運(yùn)算在實(shí)際中真正得到了廣泛的應(yīng)用。際中真正得到了廣泛的應(yīng)用。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 34.2 直接計(jì)算直接計(jì)算DFT的問題及改進(jìn)的途徑的問題及改進(jìn)的途徑 一、直接計(jì)算一、直接計(jì)算DFT的運(yùn)算量的運(yùn)算量 設(shè)設(shè)x(n)為為N點(diǎn)有限長(zhǎng)序列，其點(diǎn)有限長(zhǎng)序列，其DFT為為 10)()(NnnkNWnxkXk=0, 1, , N-1 （4-1） 反變換（反變換（IDFT）為）為 101( )( )NnkNkx nX k WNn=0, 1, , N-1 （4-2） 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4 二者的差別

5、只在于二者的差別只在于WN的指數(shù)符號(hào)不同，以及差一個(gè)常數(shù)乘的指數(shù)符號(hào)不同，以及差一個(gè)常數(shù)乘因子因子1/N，所以，所以IDFT與與DFT具有相同的運(yùn)算工作量。具有相同的運(yùn)算工作量。 下面我們下面我們只討論只討論DFT的運(yùn)算量。的運(yùn)算量。 一般來說，一般來說，x(n)和和WNnk都是復(fù)數(shù)，都是復(fù)數(shù)，X(k)也是復(fù)數(shù)，因此每也是復(fù)數(shù)，因此每計(jì)算一個(gè)計(jì)算一個(gè)X(k)值值，需要，需要N次復(fù)數(shù)乘法次復(fù)數(shù)乘法和和N-1次復(fù)數(shù)加法次復(fù)數(shù)加法。而。而X(k)一共有一共有N個(gè)點(diǎn)（個(gè)點(diǎn)（k從從0取到取到N-1），所以），所以完成整個(gè)完成整個(gè)DFT運(yùn)算運(yùn)算總共需總共需要要N2次復(fù)數(shù)乘法次復(fù)數(shù)乘法及及N(N-1)次復(fù)數(shù)

6、加法次復(fù)數(shù)加法。 在這些運(yùn)算中乘法運(yùn)算在這些運(yùn)算中乘法運(yùn)算要比加法運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間也多一些。因?yàn)閺?fù)數(shù)運(yùn)算要比加法運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間也多一些。因?yàn)閺?fù)數(shù)運(yùn)算實(shí)際上是由實(shí)數(shù)運(yùn)算來完成的，實(shí)際上是由實(shí)數(shù)運(yùn)算來完成的， 這時(shí)這時(shí)DFT運(yùn)算式可寫成運(yùn)算式可寫成 10)()(NnnkNWnxkX101( )( )NnkNkx nX k WN反變換：反變換：正變換：正變換：第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 5)Re)(ImIm)(ReIm)(ImRe)(ReIm)Re(Im)(Re)()(101010nkNnkNnkNNnnkNNnnkNnkNNnnkNWnxWnxjWnxWn

7、xWjWnxjnxWnxkX（4-3） 由此可見，由此可見，一次復(fù)數(shù)乘法一次復(fù)數(shù)乘法需用需用四次實(shí)數(shù)乘法四次實(shí)數(shù)乘法和和二次實(shí)數(shù)加法二次實(shí)數(shù)加法；一次復(fù)數(shù)加法需二次實(shí)數(shù)加法。一次復(fù)數(shù)加法需二次實(shí)數(shù)加法。 因而每因而每運(yùn)算一個(gè)運(yùn)算一個(gè)X(k)需需4N次實(shí)次實(shí)數(shù)乘法數(shù)乘法和和2N+2(N-1)=2(2N-1)次實(shí)數(shù)加法次實(shí)數(shù)加法。 所以，所以，整個(gè)整個(gè)DFT運(yùn)算運(yùn)算總共需要總共需要4N2次實(shí)數(shù)乘法次實(shí)數(shù)乘法和和2N(2N-1)次實(shí)數(shù)加法次實(shí)數(shù)加法。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 6 當(dāng)然，上述統(tǒng)計(jì)與實(shí)際需要的運(yùn)算次數(shù)稍有出入，因?yàn)槟钞?dāng)然，上述統(tǒng)計(jì)與實(shí)際需要的運(yùn)算次數(shù)稍有出入，

8、因?yàn)槟承┬￤Nnk可能是可能是1或或j，就不必相乘了，例如，就不必相乘了，例如W0N=1，W N=-1， WNN/4=-j等就不需乘法。等就不需乘法。 但是為了便于和其他運(yùn)算方法作比較，但是為了便于和其他運(yùn)算方法作比較， 一般都不考慮這些特殊情況，而是把一般都不考慮這些特殊情況，而是把WNnk都看成復(fù)數(shù)，當(dāng)都看成復(fù)數(shù)，當(dāng)N很很大時(shí)，這種特例的影響很小。大時(shí)，這種特例的影響很小。 從上面的統(tǒng)計(jì)可以看到，從上面的統(tǒng)計(jì)可以看到，直接計(jì)算直接計(jì)算DFT，乘法次數(shù)和加法，乘法次數(shù)和加法次數(shù)都是和次數(shù)都是和N2成正比的成正比的，當(dāng)當(dāng)N很大時(shí)，運(yùn)算量是很可觀的，有很大時(shí)，運(yùn)算量是很可觀的，有時(shí)是無法忍受的。

9、時(shí)是無法忍受的。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 7 例例3-1 根據(jù)式（根據(jù)式（3-1），對(duì)一幅），對(duì)一幅NN點(diǎn)的二維圖像進(jìn)行點(diǎn)的二維圖像進(jìn)行DFT變換，如用每秒可做變換，如用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？ 解解 直接計(jì)算直接計(jì)算DFT所需復(fù)乘次數(shù)為（所需復(fù)乘次數(shù)為（N2)21012次，因此用每次，因此用每秒可做秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，則需要近萬次復(fù)數(shù)乘法的計(jì)算機(jī)，則需要近3000小時(shí)。小時(shí)。 這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理來說，要么提高計(jì)算速度

10、，而這這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理來說，要么提高計(jì)算速度，而這樣，對(duì)計(jì)算速度的要求太高了。另外，只能通過改進(jìn)對(duì)樣，對(duì)計(jì)算速度的要求太高了。另外，只能通過改進(jìn)對(duì)DFT的計(jì)的計(jì)算方法，以大大減少運(yùn)算次數(shù)。算方法，以大大減少運(yùn)算次數(shù)。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 8二、二、 改善途徑改善途徑 能否減少運(yùn)算量，從而縮短計(jì)算時(shí)間呢？仔細(xì)觀察能否減少運(yùn)算量，從而縮短計(jì)算時(shí)間呢？仔細(xì)觀察DFT的運(yùn)算就可看出，的運(yùn)算就可看出， 利用系數(shù)利用系數(shù)Wnk的以下固有特性，就可減少運(yùn)的以下固有特性，就可減少運(yùn)算量：算量： （1） WNnk的共軛對(duì)稱性的共軛對(duì)稱性 nkNnkNWW*)(（2） WN

11、nk的周期性的周期性 )()(NknNkNnNnkNWWW（3） WNnk的可約性的可約性 mnkmNnkNnmkmNnkNWWWW/,第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 9另外另外 kNNkNNNnkNknNNkNnNWWWWWW)2/(2/)()(, 1, 這樣，利用這些特性，使這樣，利用這些特性，使DFT運(yùn)算中有些項(xiàng)可以合并，運(yùn)算中有些項(xiàng)可以合并，并能使并能使DFT分解為更少點(diǎn)數(shù)的分解為更少點(diǎn)數(shù)的DFT運(yùn)算。由于運(yùn)算。由于DFT的運(yùn)算的運(yùn)算量是與量是與N2成正比的，所以成正比的，所以N越小越有利，因而小點(diǎn)數(shù)序列越小越有利，因而小點(diǎn)數(shù)序列的的DFT比大點(diǎn)數(shù)序列的比大點(diǎn)數(shù)序列

12、的DFT的運(yùn)算量要小。的運(yùn)算量要小。 快速傅里葉變換算法正是基于這樣的基本思想而發(fā)展快速傅里葉變換算法正是基于這樣的基本思想而發(fā)展起來的。它的算法形式有很多種，但基本上可以分成兩大起來的。它的算法形式有很多種，但基本上可以分成兩大類：類： 按時(shí)間抽取按時(shí)間抽取(ecimation inTime，縮寫為，縮寫為DIT)法法 按頻率抽取按頻率抽取(Decimationin Frequency，縮寫為，縮寫為DIF)法法第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 104.3 按時(shí)間抽取按時(shí)間抽取(DIT)的的基基-2 FFT算法算法 (庫利庫利-圖基算法圖基算法)一、一、 算法原理算法原理

13、設(shè)序列設(shè)序列x(n)長(zhǎng)度為長(zhǎng)度為N，且滿足，且滿足N=2L，L為正整數(shù)。按為正整數(shù)。按n的奇的奇偶把偶把x(n)分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的子序列：點(diǎn)的子序列： 12, 1 , 0)() 12()()2(21Nrrxrxrxrx（4-4） 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 11則可將則可將DFT化為化為 111000( ) ( )( )( )( )NNNnknknkNNNnnnnnX kDFT x nx n Wx n Wx n W為偶數(shù)為奇數(shù)由于由于 ， 則上式可表示成則上式可表示成 2222/2/2jjNNNNWeeW111221/22/2200( )( )( )( )(

14、 )NNkNrkkrkNNNrrX kxX kr WW XWkx r W（4-5） 11222(21)001122221200(2 )(21)( )()( )()NNrkrkNNrrNNrkkrkNNNrrxr WxrWx r WWx r W第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 12式中，式中，X1(k)與與X2(k)分別是分別是x1(r)及及x2(r)的的N/2點(diǎn)點(diǎn)DFT： rkNNrrkNNrrkNNrrkNNrWrxWrxkXWrxWrxkX2/1202/212022/1202/11201)12()()()2()()(（4-6） （4-7） X1(k)，X2(k)只有只有N

15、/2個(gè)點(diǎn)，即個(gè)點(diǎn)，即k=0, 1, , N/2-1。而而X(k)卻有卻有N個(gè)點(diǎn)，即個(gè)點(diǎn)，即k=0, 1, , N-1， 故用故用式（式（4-5）計(jì)算得到的只是計(jì)算得到的只是X(k)的前一半的結(jié)果的前一半的結(jié)果:11221/22/21200( )( )( )( )( ),NNrkkrkkNNNNrrX kx r WWx r WX kW Xk12, 1 , 0Nk第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 13rkNNkrNWW2/22/（周期性）（周期性）由于由于1122()()()2221/2/200()( )(21),2NNNNNr kkr kNNNrrNX kx r WWxrW再考

16、慮到再考慮到WkN 的以下性質(zhì)的以下性質(zhì): kNkNNNkNNWWWW2/211221/22/20012()( )( )2( )( ),NNrkkrkNNNrrkNNX kx r WWx r WX kW Xk所以所以X(k)的后一半結(jié)果為的后一半結(jié)果為:12, 1 , 0Nk12, 1 , 0Nk第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 1412,( )( )( )0,1,12kNNX kX kW Xkk21212222( )( ),NkNkNNNNX kXkWXkX kW Xk12, 1 , 0Nk（4-11） （4-12） 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 15

17、圖圖 4-1 時(shí)間抽選法蝶形運(yùn)算流圖符號(hào)時(shí)間抽選法蝶形運(yùn)算流圖符號(hào) X2(k)X1(k)kNW1X1(k)kNWX2(k)X1(k)kNWX2(k)12, 1 , 0)()()(21NkkXWkXkXkN12( )( )0,1,122kNNNXkX kW Xkk.蝶形運(yùn)算蝶形運(yùn)算這樣，就可將這樣，就可將X(k)表達(dá)為前后兩部分：表達(dá)為前后兩部分： 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 16圖圖 4-2 按時(shí)間抽選將一個(gè)按時(shí)間抽選將一個(gè)N點(diǎn)點(diǎn)DFT分解分解 為兩個(gè)為兩個(gè)N/2點(diǎn)點(diǎn)DFT（N=8） X1(0)X1(1)x1(0) x(0)X(0)X(1)X1(2)X1(3)110NW

18、DFT2點(diǎn)Nx1(1) x(2)x1(2) x(4)x1(3) x(6)X(2)X(3)X2(0)X2(1)x2(0) x(1)X(4)X(5)X2(2)X2(3)DFT2點(diǎn)Nx2(1) x(3)x2(2) x(5)x2(3) x(7)X(6)X(7)1NW2NW3NW1112, 1 ,0)()()(21NkkXWkXkXkN12( )( )0,1,122kNNNXkXkWXkk12(2 )( )(21)( )0,1,12xrx rxrx rNr第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 17(1)N/2點(diǎn)的點(diǎn)的DFT運(yùn)算量運(yùn)算量: 復(fù)乘次數(shù)復(fù)乘次數(shù):復(fù)加次數(shù)復(fù)加次數(shù):(2)兩個(gè)兩個(gè)N

19、/2點(diǎn)的點(diǎn)的DFT運(yùn)算量運(yùn)算量:復(fù)乘次數(shù)復(fù)乘次數(shù):復(fù)加次數(shù)復(fù)加次數(shù): (3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量個(gè)蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù)復(fù)乘次數(shù):復(fù)加次數(shù)復(fù)加次數(shù): 運(yùn)算量運(yùn)算量復(fù)乘復(fù)乘:復(fù)加復(fù)加:總共運(yùn)算量總共運(yùn)算量: *N點(diǎn)點(diǎn)DFT的復(fù)乘為的復(fù)乘為N2 ;復(fù)加復(fù)加N(N-1);與分解后相比可知與分解后相比可知,計(jì)算工作點(diǎn)差不多減少計(jì)算工作點(diǎn)差不多減少 一半。一半。22()24NN(1)22NN22N(1)2NN2N22NN22(1)/ 2222NNNNN2(1)22NNNN第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 18 由于由于N=2L，因而，因而N/2仍是偶數(shù)，可以進(jìn)一步把每個(gè)仍是偶數(shù)

20、，可以進(jìn)一步把每個(gè)N/2點(diǎn)子序列再按其奇偶部分分解為兩個(gè)點(diǎn)子序列再按其奇偶部分分解為兩個(gè)N/4點(diǎn)的子序列。點(diǎn)的子序列。 1314(2 )( )0,1,1(21)( )4xlx lNlxlx l（4-13） 14, 1 , 0)()()()() 12()2()(42/31404/42/1404/3140)12(2/114022/11NkkXWkXWlxWWlxWlxWlxkXkNNllkNkNNllkNNlklNNllkN例如，例如，n為偶數(shù)時(shí)的為偶數(shù)時(shí)的 N/2點(diǎn)分解為點(diǎn)分解為:第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 19且且 )()(442/31kXWkXkNXkN14, 1 ,

21、 0Nk式中：式中： 1404/441404/33)()()()(NllkNNllkNWlxkXWlxkX（4-14） （4-15） 圖圖4-3給出給出N=8時(shí)，將一個(gè)時(shí)，將一個(gè)N/2點(diǎn)點(diǎn)DFT分解成兩個(gè)分解成兩個(gè)N/4點(diǎn)點(diǎn)DFT， 由這兩個(gè)由這兩個(gè)N/4點(diǎn)點(diǎn)DFT組合成一個(gè)組合成一個(gè)N/2點(diǎn)點(diǎn)DFT的流圖。的流圖。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 20圖圖 4-3 N/2點(diǎn)點(diǎn)DFT分解為兩個(gè)分解為兩個(gè)N/4點(diǎn)點(diǎn)DFT DFT4點(diǎn)NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4點(diǎn)NX4(0)X4(1)x4(0

22、) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3)1102/NW12/NW12(2 )( )0,1,1(21)( )2xrx rNrxrx r1314(2 )( )0,1,1(21)( )4xlx lNlxlx l第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 21X2(k)也可進(jìn)行同樣的分解：也可進(jìn)行同樣的分解： )()(4)()()(62/5262/52kXWkXkNXkXWkXkXkNkN14, 1 , 0Nk式中：式中： 1404/21404/661404/21404/55) 12()()()2()()(NllkNNllkNNllkNNllkNWlxWlx

23、kXWlxWlxkX同樣對(duì)同樣對(duì)n為奇數(shù)時(shí)，為奇數(shù)時(shí)，N/2點(diǎn)分為兩個(gè)點(diǎn)分為兩個(gè)N/4點(diǎn)點(diǎn) 的序列進(jìn)行的序列進(jìn)行DFT第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 22圖圖 4-4 一個(gè)一個(gè)N=8點(diǎn)點(diǎn)DFT分解為四個(gè)分解為四個(gè)N/4點(diǎn)點(diǎn)DFT DFT4點(diǎn)NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4點(diǎn)NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3)110NW2NWX(0)X(1)X(2)X(3)DFT4點(diǎn)NX5(0)X5(1)x5(0) x2(0) x(1)x5(

24、1) x2(2) x(5)X2(0)X2(1)DFT4點(diǎn)NX6(0)X6(1)x6(0) x2(1) x(3)x6(1) x2(3) x(7)X2(2)X2(3)11X(4)X(5)X(6)X(7)0NW1NW2NW3NW11110NW2NW第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 23 根據(jù)上面同樣的分析知道，利用四個(gè)根據(jù)上面同樣的分析知道，利用四個(gè)N/4點(diǎn)的點(diǎn)的DFT及兩級(jí)蝶及兩級(jí)蝶形組合運(yùn)算來計(jì)算形組合運(yùn)算來計(jì)算N點(diǎn)點(diǎn)DFT，比只用一次分解蝶形組合方式的，比只用一次分解蝶形組合方式的計(jì)算量又減少了大約一半。計(jì)算量又減少了大約一半。 對(duì)于對(duì)于N=8時(shí)的時(shí)的DFT, N/4點(diǎn)即為兩

25、點(diǎn)點(diǎn)即為兩點(diǎn)DFT,因此因此 133/40144/40155/40166/40( )( ), k0,1( )( ), k0,1( )( ), k0,1( )( ), k0,1lkNllkNllkNllkNlXkx l WXkx l WXkx l WXkx l W第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 24式中，式中， , 故上式不需要乘法。故上式不需要乘法。0122121NjjWeeW可得：可得：004424104424(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxW xxW xXxW xxW x005525105525(0)(0)(1)(1)(5)(1)(0

26、)(1)(1)(5)NNXxW xxW xXxW xxW x006626106626(0)(0)(1)(3)(7)(1)(0)(1)(3)(7)NNXxW xxW xXxW xxW x003323103323(0)(0)(1)(0)(4)(1)(0)(1)(0)(4)NNXxW xxW xXxW xxW x第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 25 這種方法的每一步分解，都是這種方法的每一步分解，都是按輸入序列在時(shí)間上的次序按輸入序列在時(shí)間上的次序是屬于偶數(shù)還是屬于奇數(shù)來分解是屬于偶數(shù)還是屬于奇數(shù)來分解為兩個(gè)更短的子序列，所以稱為兩個(gè)更短的子序列，所以稱為為“按時(shí)間抽取法按時(shí)間抽

27、取法”。 圖圖 4-5 N=8 按時(shí)間抽取的按時(shí)間抽取的FFT運(yùn)算流圖運(yùn)算流圖x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X(7)10NW0NW2NW110NW1NW2NW3NW1111第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 26二、二、 運(yùn)算量運(yùn)算量 由按時(shí)間抽取法由按時(shí)間抽取法FFT的流圖可見，當(dāng)?shù)牧鲌D可見，當(dāng)N=2L時(shí)，共有時(shí)，共有L級(jí)級(jí)蝶形，蝶形， 每級(jí)都由每級(jí)都由N/2個(gè)蝶形運(yùn)算組成，每個(gè)蝶形需要一次復(fù)個(gè)蝶形運(yùn)算組成，每個(gè)蝶形需要一次復(fù)乘、乘、 二次復(fù)加，因

28、而每級(jí)運(yùn)算都需二次復(fù)加，因而每級(jí)運(yùn)算都需N/2次復(fù)乘和次復(fù)乘和N次復(fù)加，次復(fù)加，這樣這樣L級(jí)運(yùn)算總共需要級(jí)運(yùn)算總共需要 復(fù)乘數(shù)復(fù)乘數(shù) 22log22logFFNNmLNaNLNN復(fù)加數(shù)復(fù)加數(shù) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 27 由于計(jì)算機(jī)上乘法運(yùn)算所需的時(shí)間比加法運(yùn)算所需由于計(jì)算機(jī)上乘法運(yùn)算所需的時(shí)間比加法運(yùn)算所需的時(shí)間多得多，故以乘法為例，直接的時(shí)間多得多，故以乘法為例，直接DFT復(fù)數(shù)乘法次數(shù)復(fù)數(shù)乘法次數(shù)是是N2，F(xiàn)FT復(fù)數(shù)乘法次數(shù)是復(fù)數(shù)乘法次數(shù)是(N/2) log2N。 直接計(jì)算直接計(jì)算DFT與與FFT算法的計(jì)算量之比為算法的計(jì)算量之比為 22222loglog22N

29、NNNNNLN當(dāng)當(dāng)N=2048時(shí)，這一比值為時(shí)，這一比值為372.4，即直接計(jì)算，即直接計(jì)算DFT的運(yùn)算量的運(yùn)算量是是FFT運(yùn)算量的運(yùn)算量的372.4倍。當(dāng)點(diǎn)數(shù)倍。當(dāng)點(diǎn)數(shù)N越大時(shí)，越大時(shí)，F(xiàn)FT的優(yōu)點(diǎn)更為的優(yōu)點(diǎn)更為明顯明顯(見書中見書中P150.表表4-1)。 （4-20） 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 28 三、按時(shí)間抽取的三、按時(shí)間抽取的FFT算法的特點(diǎn)算法的特點(diǎn) 1. 原位運(yùn)算（同址運(yùn)算）原位運(yùn)算（同址運(yùn)算） 從從圖圖4-5可以看出這種運(yùn)算是很有規(guī)律的，其每級(jí)（每列）可以看出這種運(yùn)算是很有規(guī)律的，其每級(jí)（每列）計(jì)算都是由計(jì)算都是由N/2 個(gè)蝶形運(yùn)算構(gòu)成的，每一個(gè)蝶形

30、結(jié)構(gòu)完成下述個(gè)蝶形運(yùn)算構(gòu)成的，每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算：基本迭代運(yùn)算： rNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111（4-21a） （4-21b） 式中，式中，m表示第表示第m列迭代，列迭代，k, j為數(shù)據(jù)所在行數(shù)。式（為數(shù)據(jù)所在行數(shù)。式（4-21）的蝶）的蝶形運(yùn)算形運(yùn)算如圖如圖4-7所示，由一次復(fù)乘和兩次復(fù)加（減）組成。所示，由一次復(fù)乘和兩次復(fù)加（減）組成。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 29圖圖 4-7 按時(shí)間抽選的蝶形運(yùn)算結(jié)構(gòu)按時(shí)間抽選的蝶形運(yùn)算結(jié)構(gòu)1rNWXm1(k)Xm1( j)Xm(k) Xm1(k) Xm1( j

31、)Xm( j) Xm1(k) Xm1( j)rNWrNW 在某列進(jìn)行蝶形運(yùn)算的任意兩個(gè)節(jié)點(diǎn)在某列進(jìn)行蝶形運(yùn)算的任意兩個(gè)節(jié)點(diǎn)(行行)k和和j的節(jié)點(diǎn)變量的節(jié)點(diǎn)變量 就完全可以確定蝶形運(yùn)算的結(jié)果就完全可以確定蝶形運(yùn)算的結(jié)果 ,與其它行與其它行(節(jié)點(diǎn)節(jié)點(diǎn))無關(guān)。無關(guān)。 這樣這樣,蝶形運(yùn)算的兩個(gè)輸出值仍可放蝶形運(yùn)算的兩個(gè)輸出值仍可放回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中,即實(shí)現(xiàn)所謂即實(shí)現(xiàn)所謂原位運(yùn)原位運(yùn)算算。每一組每一組(列列)有有N/2個(gè)蝶形運(yùn)算個(gè)蝶形運(yùn)算,所以只需所以只需N個(gè)存儲(chǔ)單元，個(gè)存儲(chǔ)單元，可以節(jié)省存儲(chǔ)單元?？梢怨?jié)省存儲(chǔ)單元。11( ),( )mmXkXj( ),

32、( )mmXkXj第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 30 由由圖圖4-5的流圖看出，某一列的任何兩個(gè)節(jié)點(diǎn)的流圖看出，某一列的任何兩個(gè)節(jié)點(diǎn)k和和j的節(jié)點(diǎn)變的節(jié)點(diǎn)變量進(jìn)行蝶形運(yùn)算后，得到結(jié)果為下一列量進(jìn)行蝶形運(yùn)算后，得到結(jié)果為下一列k, j兩節(jié)點(diǎn)的節(jié)點(diǎn)變量，兩節(jié)點(diǎn)的節(jié)點(diǎn)變量，而和其他節(jié)點(diǎn)變量無關(guān)，因而可以采用原位運(yùn)算，即某一列的而和其他節(jié)點(diǎn)變量無關(guān)，因而可以采用原位運(yùn)算，即某一列的N個(gè)數(shù)據(jù)送到存儲(chǔ)器后，經(jīng)蝶形運(yùn)算，其結(jié)果為下一列數(shù)據(jù)，它們個(gè)數(shù)據(jù)送到存儲(chǔ)器后，經(jīng)蝶形運(yùn)算，其結(jié)果為下一列數(shù)據(jù)，它們以蝶形為單位仍存儲(chǔ)在這同一組存儲(chǔ)器中，直到最后輸出，中間以蝶形為單位仍存儲(chǔ)在這同一組存儲(chǔ)

33、器中，直到最后輸出，中間無需其他存儲(chǔ)器。也就是蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸無需其他存儲(chǔ)器。也就是蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸入所在的存儲(chǔ)器中。每列的入所在的存儲(chǔ)器中。每列的N/2 個(gè)蝶形運(yùn)算全部完成后，再開始個(gè)蝶形運(yùn)算全部完成后，再開始下一列的蝶形運(yùn)算。這樣存儲(chǔ)器數(shù)據(jù)只需下一列的蝶形運(yùn)算。這樣存儲(chǔ)器數(shù)據(jù)只需N個(gè)存儲(chǔ)單元。下一級(jí)個(gè)存儲(chǔ)單元。下一級(jí)的運(yùn)算仍采用這種原位方式，只不過進(jìn)入蝶形結(jié)的組合關(guān)系有所的運(yùn)算仍采用這種原位方式，只不過進(jìn)入蝶形結(jié)的組合關(guān)系有所不同。不同。 這種這種原位運(yùn)算結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。原位運(yùn)算結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。 第第4章章 快速傅

34、里葉變換快速傅里葉變換(FFT) 31 2. 倒位序規(guī)律倒位序規(guī)律 FFT的輸出的輸出X(k)按正常順序排列在存儲(chǔ)單元中，即按按正常順序排列在存儲(chǔ)單元中，即按X(0)，X(1)，X(7)的順序排列，但是這時(shí)輸入的順序排列，但是這時(shí)輸入x(n)卻不是按自然順卻不是按自然順序存儲(chǔ)的，而是按序存儲(chǔ)的，而是按x(0)，x(4)， ， x(7)的順序存入存儲(chǔ)單元，的順序存入存儲(chǔ)單元，看起來好像是看起來好像是“混亂無序混亂無序”的，實(shí)際上是有規(guī)律的，我們稱之的，實(shí)際上是有規(guī)律的，我們稱之為倒位序。為倒位序。 這是由奇偶分組造成的這是由奇偶分組造成的,以以N=8為例為例 說明如下說明如下:第第4章章 快速傅

35、里葉變換快速傅里葉變換(FFT) 32 造成倒位序的原因是輸入造成倒位序的原因是輸入x(n)按標(biāo)號(hào)按標(biāo)號(hào)n的偶奇的不斷分組。的偶奇的不斷分組。 如果如果n用二進(jìn)制數(shù)表示為用二進(jìn)制數(shù)表示為(n2n1n0)2（當(dāng)（當(dāng)N=8=23時(shí)，二進(jìn)制為三時(shí)，二進(jìn)制為三位），位）， 第一次分組，由圖第一次分組，由圖4-2看出，看出，n為偶數(shù)（相當(dāng)于為偶數(shù)（相當(dāng)于n的二進(jìn)制的二進(jìn)制數(shù)的最低位數(shù)的最低位n0=0）在上半部分，）在上半部分，n為奇數(shù)（相當(dāng)于為奇數(shù)（相當(dāng)于n的二進(jìn)制數(shù)的二進(jìn)制數(shù)的最低位的最低位 n0=1）在下半部分。）在下半部分。 下一次則根據(jù)次最低位下一次則根據(jù)次最低位n1為為“0”或是或是“1”來分

36、偶奇（而不管原來的子序列是偶序列還是奇序來分偶奇（而不管原來的子序列是偶序列還是奇序列），列）， 如此繼續(xù)分下去，直到最后如此繼續(xù)分下去，直到最后N個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為1的子序列。的子序列。 圖圖4-8的樹狀圖描述了這種分成偶數(shù)子序列和奇數(shù)子序列的過程。的樹狀圖描述了這種分成偶數(shù)子序列和奇數(shù)子序列的過程。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 33圖圖4-8 描述倒位序的樹狀圖描述倒位序的樹狀圖 x(000)x(100)x(010)x(110)010101x(001)x(101)x(011)x(111)01010101x(n2n1n0)n2n1n0第第4章章 快速傅里葉變換快速傅里葉

37、變換(FFT) 34 3.倒位序?qū)崿F(xiàn)倒位序?qū)崿F(xiàn) 輸入序列先按自然順序存入存儲(chǔ)單元輸入序列先按自然順序存入存儲(chǔ)單元,然后經(jīng)變址運(yùn)算來然后經(jīng)變址運(yùn)算來實(shí)現(xiàn)實(shí)現(xiàn)倒位序排列倒位序排列。 設(shè)輸入設(shè)輸入序列的序號(hào)為序列的序號(hào)為n,二進(jìn)制為二進(jìn)制為(n2 n1 n0 )2 , 倒位序倒位序順序用順序用 表示表示,其倒位序其倒位序二進(jìn)制為二進(jìn)制為(n0 n1 n2 )2 , 例如例如 ，N=8時(shí)如下表：時(shí)如下表：表表4-2 碼位的倒位序（碼位的倒位序（N=8）自然順序（n） 二進(jìn)制數(shù) 倒位序二進(jìn)制數(shù) 倒位序順序（） 01234567000001010011100101110111000100010110001

38、10101111104261537第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 35圖圖 4-9 倒位序的變址處理倒位序的變址處理 (N=8)存儲(chǔ)單元自然順序輸入變址倒位序A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)變址處理方法變址處理方法第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 36 4. 蝶形運(yùn)算兩節(jié)點(diǎn)的蝶形運(yùn)算兩節(jié)點(diǎn)的“距離距離” 以以圖圖4-5的的8點(diǎn)點(diǎn)FFT為例，其輸入是倒位序的，輸出是自然順為例，其輸入是倒位序的，輸出是

39、自然順序的。序的。 其第一級(jí)（第一列）每個(gè)蝶形的兩節(jié)點(diǎn)間其第一級(jí)（第一列）每個(gè)蝶形的兩節(jié)點(diǎn)間“距離距離”為為1， 第二級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)第二級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)“距離距離”為為2， 第三級(jí)每個(gè)蝶形的兩節(jié)第三級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)點(diǎn)“距離距離”為為4。 由此類推得，對(duì)由此類推得，對(duì)N=2L點(diǎn)點(diǎn)FFT，當(dāng)輸入為倒位，當(dāng)輸入為倒位序，序， 輸出為正常順序時(shí)，其第輸出為正常順序時(shí)，其第m級(jí)運(yùn)算，級(jí)運(yùn)算，每個(gè)蝶形的兩節(jié)點(diǎn)每個(gè)蝶形的兩節(jié)點(diǎn)“距離距離”為為2m-1。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 37 5. WNr的確定的確定 由于對(duì)第由于對(duì)第m級(jí)運(yùn)算，一個(gè)級(jí)運(yùn)算，一個(gè)DFT蝶形運(yùn)算的兩節(jié)點(diǎn)

40、蝶形運(yùn)算的兩節(jié)點(diǎn)“距離距離”為為2m-1， 因而式（因而式（4-21）可寫成）可寫成: rNmmmmmrNmmmmWkXkXkXWkXkXkX)2()()2()2()()(1111111（4-22a） （4-22b） 為了完成上兩式運(yùn)算，還必須知道系數(shù)為了完成上兩式運(yùn)算，還必須知道系數(shù)Nr的變換規(guī)律：的變換規(guī)律： 把式（把式（4-22）中蝶形運(yùn)算兩節(jié)點(diǎn)中的第一個(gè)節(jié)點(diǎn)標(biāo)號(hào)值，）中蝶形運(yùn)算兩節(jié)點(diǎn)中的第一個(gè)節(jié)點(diǎn)標(biāo)號(hào)值， 即即k值，表示成值，表示成L位（注意位（注意N=2L）二進(jìn)制數(shù)；）二進(jìn)制數(shù)； 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 38 把此二進(jìn)制數(shù)乘上把此二進(jìn)制數(shù)乘上2L-m，即將

41、此，即將此L位二進(jìn)制數(shù)左移位二進(jìn)制數(shù)左移L-m位（注意位（注意m是第是第m級(jí)運(yùn)算），把右邊空出的位置補(bǔ)零，級(jí)運(yùn)算），把右邊空出的位置補(bǔ)零， 此數(shù)即此數(shù)即為所求為所求r的二進(jìn)制數(shù)。的二進(jìn)制數(shù)。 從圖從圖4-5看出，看出，WNr因子最后一列有因子最后一列有N/2種，順序?yàn)榉N，順序?yàn)閃N0， WN1， ， 其余可類推。其余可類推。 12NNW第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 39 6.存儲(chǔ)單元存儲(chǔ)單元 存輸入序列存輸入序列 需需N個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元存放系數(shù)存放系數(shù) 需需N/2個(gè)存儲(chǔ)單元；個(gè)存儲(chǔ)單元； 共計(jì)共計(jì)需需(N+N/2)個(gè)存儲(chǔ)單元。個(gè)存儲(chǔ)單元。(n)(n=0,1, ,N-1

42、)x(r=0,1, ,N/2 - 1)rNW第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 40四、四、 按時(shí)間抽取的按時(shí)間抽取的FFT算法的其他形式流圖算法的其他形式流圖 顯然，顯然，對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連的支路及傳輸對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連的支路及傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，所系數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，所得最后結(jié)果都是得最后結(jié)果都是x(n)的的DFT的正確結(jié)果的正確結(jié)果，只是數(shù)據(jù)的提取和存，只是數(shù)據(jù)的提取和存放的次序不同而已。這樣就可得到按時(shí)間抽取的放的次序不同而已。這樣就可得到按時(shí)間抽取的FFT算法的若算法的若干

43、其他形式流圖。干其他形式流圖。 將圖將圖4-5中和中和x(4)水平相連的所有節(jié)點(diǎn)和水平相連的所有節(jié)點(diǎn)和x(1)水平相連的所水平相連的所有節(jié)點(diǎn)位置對(duì)調(diào)，再將和有節(jié)點(diǎn)位置對(duì)調(diào)，再將和x(6)水平相連的所有節(jié)點(diǎn)與和水平相連的所有節(jié)點(diǎn)與和x(3)水平水平相連的所有節(jié)點(diǎn)對(duì)調(diào)，其余諸節(jié)點(diǎn)保持不變，可得相連的所有節(jié)點(diǎn)對(duì)調(diào)，其余諸節(jié)點(diǎn)保持不變，可得圖圖4-10的流的流圖。圖。 圖圖4-10與圖與圖4-5的蝶形相同，運(yùn)算量也一樣，不同點(diǎn)是：的蝶形相同，運(yùn)算量也一樣，不同點(diǎn)是： 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 41 數(shù)據(jù)存放的方式不同，圖數(shù)據(jù)存放的方式不同，圖4-5是輸入倒位序、輸出自然是輸入

44、倒位序、輸出自然順序，圖順序，圖4-10是輸入自然順序、輸出倒位序；是輸入自然順序、輸出倒位序； 取用系數(shù)的順序不同，圖取用系數(shù)的順序不同，圖4-5的最后一列是按的最后一列是按 的順序取用系數(shù)，且其前一列所用系數(shù)是的順序取用系數(shù)，且其前一列所用系數(shù)是后 一 列 所 用 系 數(shù) 中 具 有 偶 數(shù) 冪 的 那 些 系 數(shù) （ 例 如后 一 列 所 用 系 數(shù) 中 具 有 偶 數(shù) 冪 的 那 些 系 數(shù) （ 例 如 ） ； 圖） ； 圖 4 - 1 0 是 最 后 一 列 是 按是 最 后 一 列 是 按 的順序取用系數(shù)，且其前一列所用系數(shù)是后一列所用系數(shù)的前的順序取用系數(shù)，且其前一列所用系數(shù)是后

45、一列所用系數(shù)的前一半，一半， 這種流圖是最初由庫利和圖基給出的時(shí)間抽取法。這種流圖是最初由庫利和圖基給出的時(shí)間抽取法。 經(jīng)過簡(jiǎn)單變換，也可得輸入與輸出都是按自然順序排列的經(jīng)過簡(jiǎn)單變換，也可得輸入與輸出都是按自然順序排列的流圖以及其他各種形式的流圖流圖以及其他各種形式的流圖 。3210,NNNNWWWW,20NNWW3120,NNNNWWWW第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 42圖圖 4-10 時(shí)間抽取、時(shí)間抽取、 輸入自然順序、輸入自然順序、 輸出倒位序的輸出倒位序的FFT流圖流圖 0NW0NW0NW2NW1110NW10NW2NW1111X(0)x(0)X(4)x(1)X(

46、2)x(2)X(6)x(3)X(1)x(4)X(5)x(5)X(3)x(6)X(7)x(7)110NW0NW2NW1NW3NW11第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 434.4 按頻率抽?。ò搭l率抽?。―IF）的基）的基 -2 FFT算法（桑德算法（桑德-圖基算法）圖基算法） 一、一、 算法原理算法原理 仍設(shè)序列點(diǎn)數(shù)為仍設(shè)序列點(diǎn)數(shù)為N=2L，L為正整數(shù)。在把輸出為正整數(shù)。在把輸出X(k)按按k的奇的奇偶分組之前，先把輸入序列按前一半、后一半分開（不是按偶偶分組之前，先把輸入序列按前一半、后一半分開（不是按偶數(shù)、數(shù)、 奇數(shù)分開），奇數(shù)分開）， 把把N點(diǎn)點(diǎn)DFT寫成兩部分。寫成兩部

47、分。 1112002112220012/20( )( )( )( )( )2( )2NNNnknknkNNNNnnnNNNnknkNNnnNNknkNNnX kx n Wx nWx n WNx nWx nWNx nx nWWk=0, 1, , N-1 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 44由于由于 ，故，故，可得，可得1nkNWkNkNW) 1(2/nkNNnkWNnxnxkX1202) 1()()( k=0, 1, , N-1 當(dāng)當(dāng)k為偶數(shù)時(shí)，為偶數(shù)時(shí)，(-1)k=1；k為奇數(shù)時(shí)，為奇數(shù)時(shí)，(-1)k=-1。因此，按。因此，按k的奇偶可將的奇偶可將X(k)分為兩部分分為兩部

48、分: nrNNnnkNNnWNnxnxWNnxnxrX2/12021202)(2)()2(12, 1 , 0Nr為前一半輸入與后一半輸入之和的N/2點(diǎn)DFT第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 45nrNNnnNrnNNnWWNnxnxWNnxnxrX2/120)12(1202)(2)() 12(12, 1 , 0Nr為前一半輸入與后一半輸入之差再與為前一半輸入與后一半輸入之差再與WNn之積的之積的N/2點(diǎn)點(diǎn)DFT。nNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 46圖圖 4-14 按頻率抽取蝶形

49、運(yùn)算流圖符號(hào)按頻率抽取蝶形運(yùn)算流圖符號(hào) 1x(n)x(n N / 2)nNWx(n) x(n N / 2)x(n) x(n N / 2)nNWnNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 47 這樣可把一個(gè)這樣可把一個(gè)N點(diǎn)點(diǎn)DFT按按k的奇偶分解為兩個(gè)的奇偶分解為兩個(gè)N/2點(diǎn)的點(diǎn)的DFT。 N=8時(shí)，上述分解過程示于圖時(shí)，上述分解過程示于圖4-15。 圖圖 4-15 按頻率抽取，將按頻率抽取，將N點(diǎn)點(diǎn)DFT分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)點(diǎn)DFT的組合的組合 X(0)X(2)110NWDFT2點(diǎn)NX(4)X(6)

50、X(1)X(3)DFT2點(diǎn)NX(5)X(7)1NW2NW3NW11x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 48由于由于N=2L，N/2仍是一個(gè)偶數(shù)，因而可以將每個(gè)仍是一個(gè)偶數(shù)，因而可以將每個(gè)N/2點(diǎn)點(diǎn)DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點(diǎn)點(diǎn)DFT進(jìn)一步進(jìn)一步分解為兩個(gè)分解為兩個(gè)N/4 點(diǎn)點(diǎn)DFT。 圖圖4-16示出了這一步分解的過程示出了這一步分解的過程。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 49圖圖 4-16 按頻率抽取的第二次分解按頻率抽取的第二次分解 DFT4點(diǎn)N110NW2NWx(0)x(1)x(2)x(3)11x(4)x(5)x(6)x(7)0NW1NW2NW3NWDFT4點(diǎn)NDFT4點(diǎn)NDFT4點(diǎn)NX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)0NW2NW1111第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 50 這樣的分解可以一直進(jìn)行到第這樣的分解可以一直進(jìn)行到第L次（次（N=2L），第），第L次實(shí)際上次實(shí)際上是做兩點(diǎn)是做兩點(diǎn)DFT，它只有加減運(yùn)算。，它只有加減運(yùn)算。