1、2第第7章章 快速傅里葉變換快速傅里葉變換7.1 引言引言7.2 直接計算直接計算DFT的問題及改進的途徑的問題及改進的途徑7.3.1 按時間抽取（按時間抽取（DIT）的基）的基-2FFT算法算法7.3.2 按頻率抽取（按頻率抽取（DIF）的基）的基-2FFT算法算法補充內容：補充內容： IDFT的高效算法的高效算法補充內容：實補充內容：實序列的序列的FFT算法算法 37.1 引言引言 有限長序列通過離散傅里葉變換（有限長序列通過離散傅里葉變換（DFT）將其頻域離）將其頻域離散化成有限長序列，但其計算量太大，很難實時處理，因此散化成有限長序列，但其計算量太大，很難實時處理，因此引出了快速傅里葉

2、變換（引出了快速傅里葉變換（FFT）。）。 FFT并不是一種新的變換形式，它只是并不是一種新的變換形式，它只是DFT的一種的一種快快速算法速算法，并且根據(jù)對序列分解與選取方法的不同產(chǎn)生了多種，并且根據(jù)對序列分解與選取方法的不同產(chǎn)生了多種算法。算法。 FFT在離散傅里葉反變換、線性卷積和線性相關等方在離散傅里葉反變換、線性卷積和線性相關等方面也有重要應用。面也有重要應用。4 47.2.1 直接計算直接計算DFT的運算量問題的運算量問題 若若x(n)是是N點序列，實現(xiàn)點序列，實現(xiàn)x(n)的的DFT，即求出，即求出N個個X(k)，需要需要N2次復數(shù)乘法，次復數(shù)乘法，N(N-1)次復數(shù)加法。次復數(shù)加法

3、。 10)()()(NnknNDFTWnxkXnx1, 1 , 0 Nk 10)(1)()(NkknNIDFTWkXNnxkX1, 1 , 0 Nn5 5一個一個復數(shù)乘法復數(shù)乘法包括包括4個實數(shù)乘法和個實數(shù)乘法和2個實數(shù)加法。個實數(shù)加法。一次復數(shù)一次復數(shù)加法需二次實數(shù)加法。加法需二次實數(shù)加法。例如：例如： x(n) N=1024，N2=1048576)Re)(ImIm)(ReIm)(ImRe)(ReIm)Re(Im)(Re)()(101010nkNnkNnkNNnnkNNnnkNnkNNnnkNWnxWnxjWnxWnxWjWnxjnxWnxkX 因而每運算一個因而每運算一個X(k)需需4N次

4、實數(shù)乘法和次實數(shù)乘法和2N+2(N-1)=2(2N-1)次實數(shù)加法。次實數(shù)加法。 所以，整個所以，整個DFT運算總共需要運算總共需要4N2次實數(shù)乘法和次實數(shù)乘法和2N(2N-1)次實數(shù)加法次實數(shù)加法。 (a+jb)(c+jd)=(ac-bd)+j(bc+ad)6 解決耗時的乘法問題是將數(shù)字信號處理理論用于實際的解決耗時的乘法問題是將數(shù)字信號處理理論用于實際的關鍵問題。關鍵問題。特別是特別是40年前，計算機的速度相當慢。因此，很年前，計算機的速度相當慢。因此，很多學者對解決多學者對解決DFT的快速計算問題產(chǎn)生了極大的興趣。的快速計算問題產(chǎn)生了極大的興趣。 Cooley J W, Tukey J

5、W. An algorithm for the machine computation of complex Fourier series. Mathematics of Computation, 1965, pp29730177.2.2 改善途徑改善途徑 FFT的思路：的思路： 10)()(NnknNWnxkX1, 1 , 0 Nk 如何充如何充分利用這些分利用這些關系關系1. 10 W1, 1. 2 mNNWWrrNWW . 31. 42/ NWrrNWW 2/. 5對稱性對稱性周期性周期性8以四點以四點DFT為例為例11111111(0)11(1)(2)1111(3)11xWWxxxWW

6、0000012302460369(0)(0)(1)(1)(2)(2)(3)(3)WWWWXxXWWWWxXxWWWWXxWWWW 304)()(nknWnxkX3 , 2 , 1 , 0 k11111111(0)11(2)(1)1111(3)11xWWxxxWW911(0) (0)(2) (1)(3)(1) (0)(2) (1)(3)(2) (0)(2) (1)(3)(3) (0)(2) (1)(3)XxxxxXxxxxWXxxxxXxxxxW11(0)(2)xx(1)(3)xx(0)(1)XX(2)(3)XX111W(0)(2)xx(0)(2)xx(1)(3)xx(1)(3)xx10 利用利

7、用WNnk的對稱性和周期性，將大點數(shù)的的對稱性和周期性，將大點數(shù)的DFT分解成若分解成若干個小點數(shù)的干個小點數(shù)的DFT，F(xiàn)FT正是基于這個基本思路發(fā)展起來的。正是基于這個基本思路發(fā)展起來的。 分類：按時間抽取（分類：按時間抽取（DIT）算法和按頻率抽取（）算法和按頻率抽取（DIF）算法。算法。 問題是問題是如何分最有效？如何分最有效？ N點DFTN/2點DFTN/4點 DFT2點 DFT 1個 2個 4個 N/2個Decimation in Time Decimation in Frequency 11knNW的周期性周期性knNW的對稱性對稱性nkNnkNWW *)(nkNNnkNWW )2

8、/()()(NknNkNnNnkNWWW 127.3 .1按時按時間抽取（間抽取（DIT）的基）的基-2FFT算法算法 1.算法原理算法原理 設序列設序列x(n)長度為長度為N2M，M為整數(shù)，將為整數(shù)，將x(n)（n=0,1N-1）按）按n的奇偶分解成兩組的奇偶分解成兩組N/2點的子序列點的子序列 x1(r)= x(2r) x2(r)= x(2r+1) r =0,1N/2-1（長度為（長度為N/2）則則 10)()(NnnkNWnxkX 為奇數(shù)為奇數(shù)為偶數(shù)為偶數(shù)nnkNnnkNWnxWnx)()( 12/0)12(12/02)12()2(NrkrNNrrkNWrxWrx 12/02/12/02

9、/)12()2(NrrkNkNNrrkNWrxWWrx13 12/02/12/02/)12()2()(NrrkNkNNrrkNWrxWWrxkX)(1kX)(2kX12/,.,1 , 0)()()2/(21 NkkXWkXNkXkN12/,.,1 , 0)()()(21 NkkXWkXkXkN X1(k)、X2(k)都是都是 N/2 點的點的 DFT，它們各自又可分成，它們各自又可分成 N/4 點的點的DFT，如此繼續(xù)分下去，直至兩點，如此繼續(xù)分下去，直至兩點DFT。兩點。兩點DFT不需要乘法運算：不需要乘法運算：)1()0()1()1()0()0(xxXxxX 2點點DFT的運算流圖的運算流

10、圖15 由于每一步分解都是按輸入序列在時間上的奇偶次序，由于每一步分解都是按輸入序列在時間上的奇偶次序，分解成兩個半長的子序列，所以稱分解成兩個半長的子序列，所以稱“按時間抽取算法按時間抽取算法”。162.運算量比較運算量比較 對對N=2M，共可分，共可分M次次，即，即m =0,1M-1，每一級有，每一級有N/2個如下的蝶形單元個如下的蝶形單元 一個蝶形單元只需一個蝶形單元只需一一次復數(shù)乘法，次復數(shù)乘法，兩兩次復數(shù)加法。次復數(shù)加法。 總共復數(shù)乘法：總共復數(shù)乘法： 復數(shù)加法：復數(shù)加法： )()()()()()(11qXWpXqXqXWpXpXmrNmmmrNmmNNMN2log22 NNMN2l

11、og 可以共享可以共享17直接計算直接計算DFT與與FFT算法的計算量之比為算法的計算量之比為 NNNMNN222log22 183.算法特點算法特點1）原位運算原位運算 兩點構成一個蝶形單元，并且這兩點不再參與別的蝶形兩點構成一個蝶形單元，并且這兩點不再參與別的蝶形單元的運算。單元的運算。 所謂原位運算，就是當數(shù)據(jù)輸入到存儲器后，每一級運所謂原位運算，就是當數(shù)據(jù)輸入到存儲器后，每一級運算的結果仍然貯存在這同一組存儲器中，直到最后輸出，中算的結果仍然貯存在這同一組存儲器中，直到最后輸出，中間無需其它存儲器。間無需其它存儲器。192）旋轉因子的變化規(guī)律）旋轉因子的變化規(guī)律 如上所述，如上所述，N

12、點點DITFFT運算流圖中，每級都有運算流圖中，每級都有N/2個蝶個蝶形。每個蝶形都要乘以因子形。每個蝶形都要乘以因子 ，稱其為旋轉因子，稱其為旋轉因子，p稱為旋稱為旋轉因子的指數(shù)。轉因子的指數(shù)。 不難發(fā)現(xiàn)，不難發(fā)現(xiàn)，第第L級級共有共有2L-1個不同的旋轉因子。個不同的旋轉因子。N=23=8時的各級旋轉因子表示如下：時的各級旋轉因子表示如下： pNW3,2,1,0,31,0,20,1222/24/ JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL一般情況，第一般情況，第L級的旋轉因子指數(shù)為級的旋轉因子指數(shù)為L為從左到右的運算級數(shù)，編程時為從左到右的運算級數(shù)，編程時L為循環(huán)變量

13、。為循環(huán)變量。LMJp 2MLJL,.,2 , 1, 12,.,2 , 1 , 01 20 如果蝶形運算的兩個輸入數(shù)據(jù)相距如果蝶形運算的兩個輸入數(shù)據(jù)相距B個點，應用原位運個點，應用原位運算，則算，則pNLLLpNLLLWBJXJXBJXWBJXJXJX)()()()()()(1111 式中式中LMJp2MLJL,.,2 , 1, 12,.,2 , 1 , 01B 兩蝶形節(jié)點的兩蝶形節(jié)點的“距離距離”（蝶距）（蝶距）12LB 3）蝶形運算）蝶形運算21 4）倒位序）倒位序 輸入序列輸入序列x(n)的排列次序不符合自然順序。此現(xiàn)象是由的排列次序不符合自然順序。此現(xiàn)象是由于按于按n的奇偶分組進行的奇

14、偶分組進行DFT運算而造成的，這種排列方式稱運算而造成的，這種排列方式稱為為“倒位序倒位序”。 所謂所謂“倒位序倒位序”，是指按二進制表示的數(shù)字首尾位置顛，是指按二進制表示的數(shù)字首尾位置顛倒，重新按十進制讀數(shù)。倒，重新按十進制讀數(shù)。自然順序二進制順序碼位倒置碼位倒讀順序0 000000001 100110042 201001023 301111064 410000115 510110156 611001137 7111111722倒位序的實現(xiàn)倒位序的實現(xiàn) 在實際運算時，先按自然順序將輸入序列存入存儲單元，在實際運算時，先按自然順序將輸入序列存入存儲單元，再通過再通過變址運算變址運算將自然順序變

15、換成按將自然順序變換成按DIT-FFT算法要求的順算法要求的順序。序。 變址的過程可以用程序安排加以實現(xiàn)變址的過程可以用程序安排加以實現(xiàn)- 稱為稱為“整序整序”或或“重排重排”（采用碼位倒讀）（采用碼位倒讀）注意注意:(1)當當I=J時，數(shù)據(jù)不必調換；時，數(shù)據(jù)不必調換；(2)當當IJ時，必須將原來存放數(shù)據(jù)時，必須將原來存放數(shù)據(jù)x(I)送入暫存器送入暫存器R，再將，再將x(J)送入送入x(I)，R中內容送中內容送x(J)，進行數(shù)據(jù)對調。進行數(shù)據(jù)對調。(3)為了避免再次調換已調換過的數(shù)據(jù)，保證調換只進行一次，為了避免再次調換已調換過的數(shù)據(jù)，保證調換只進行一次，否則又變回原狀否則又變回原狀。JI（或

16、（或IJ)時，調換時，調換。23倒位序程序框圖 24DITFFT運算和程序框圖 254.小結小結 全部計算分解為全部計算分解為M級，或稱為級，或稱為M次迭代。次迭代。 輸入倒序，輸出正序輸入倒序，輸出正序。 每級都包含每級都包含N/2個蝶形單元。個蝶形單元。 每級的若干蝶形單元組成每級的若干蝶形單元組成“群群”。第。第1級群數(shù)為級群數(shù)為N/2，第，第2級群數(shù)為級群數(shù)為N/4，第第i級群數(shù)為級群數(shù)為N/2i，最后一級的群數(shù)為，最后一級的群數(shù)為1。 每個蝶形單元都包含乘每個蝶形單元都包含乘WNk與與-WNk的運算的運算（可簡化為乘（可簡化為乘WNk與加、減法各一次）。與加、減法各一次）。 同一級中

17、，各個群的同一級中，各個群的W分布規(guī)律完全相同分布規(guī)律完全相同。267.3.2按按頻率抽取（頻率抽取（DIF）的基）的基-2 FFT算法算法 把輸出序列把輸出序列X(k)按按k奇偶分解成越來越短的序列，稱為奇偶分解成越來越短的序列，稱為按頻率抽取按頻率抽取FFT算法。算法。 1算法原理算法原理 設序列設序列x(n)長度為長度為N2M，M為整數(shù)。在把為整數(shù)。在把X(k)按按k的奇的奇偶分組之前，先把偶分組之前，先把x(n)按按n的的順序分解為前后兩部分。順序分解為前后兩部分。 12/12/010)()()()(NNnnkNNnnkNNnnkNWnxWnxWnxkX 12/0)2/(12/0)2/

18、()(NnkNnNNnnkNWNnxWnx 12/0)2/()2/()(NnnkNkNNWNnxWnxk)1( 27 現(xiàn)在對頻率序列抽取，按現(xiàn)在對頻率序列抽取，按k是是奇數(shù)奇數(shù)還是還是偶數(shù)偶數(shù)將將X(k)分成分成兩部分。兩部分。 頻率序列頻率序列X(2r)是時間序列是時間序列x(n)+x(n+N/2)的的N/2點點DFT，頻率序列，頻率序列X(2r+1)是時間序列是時間序列x(n)-x(n+N/2)WNn的的N/2點點DFT。這樣，將。這樣，將N點點DFT分解成兩個分解成兩個N/2點點DFT運算。運算。 12/01-N , 1, 0,k,)2/()1()()(NnnkNkWNnxnxkX 12

19、/02)2/()()2(NnnrNWNnxnxrX 12/02)2/()()12(NnnrNnNWWNnxnxrX2812/,.,1 , 0,)2()()()2()()(21 NnWNnxnxnxNnxnxnxnN令令DIFFFT一次分解運算流圖（一次分解運算流圖（N=8） 12/02112/02)()2/()()2(NnnrNNnnrNWnxWNnxnxrX 12/012/0222)()2/()()12(NnNnnrNnrNnNWnxWWNnxnxrX30 類似的分解可以一直進行下去，直到最后剩下的全部是類似的分解可以一直進行下去，直到最后剩下的全部是2點的點的DFT。 DIFFFT運算流圖

20、（運算流圖（N=8）312算法特點算法特點 頻率抽取法的算法特點與時間抽取法基本相同。頻率抽取法的算法特點與時間抽取法基本相同。 DIF法與法與DIT法的根本區(qū)別是：基本蝶形有所不同法的根本區(qū)別是：基本蝶形有所不同，DIF的復數(shù)乘法只出現(xiàn)在減法之后，的復數(shù)乘法只出現(xiàn)在減法之后，DIT則是先作復乘后再作加則是先作復乘后再作加減法。減法。 DIF碟形運算單元碟形運算單元 DIT碟形運算單元碟形運算單元 32轉置定理轉置定理 將流圖的所有支路方向都反向，并且交換輸入與輸出，將流圖的所有支路方向都反向，并且交換輸入與輸出，但節(jié)點變量值不交換，這樣即可從一種流圖得到另一種。但節(jié)點變量值不交換，這樣即可從

21、一種流圖得到另一種。 這樣，對每一種按時間抽取的這樣，對每一種按時間抽取的FFT流圖都存在一個按頻流圖都存在一個按頻率抽取的率抽取的FFT流圖，反之亦然。流圖，反之亦然。 頻率抽取法與時間抽取法實質上是兩種等價的頻率抽取法與時間抽取法實質上是兩種等價的FFT運算。運算。 33比較比較DITDIF34補充內容：補充內容： IDFT的高效算法的高效算法 1.利用利用FFT流圖流圖計算計算IFFT 將下列兩式進行比較將下列兩式進行比較 只要把只要把DFT運算中的每個系數(shù)運算中的每個系數(shù) 改成改成 ，將運算結，將運算結果都除以果都除以N，那么以上討論的時間抽取或頻率抽取，那么以上討論的時間抽取或頻率抽

22、取FFT都可都可以用來運算以用來運算IDFT。 1010)()()()(1)()(NknkNNknkNWnxnxDFTkXWkXNkXIDFTnxnkNW nkNW35 利用利用FFT計算計算IFFT時在命名上應注意：時在命名上應注意：(1)把把FFT的時間抽取法用于的時間抽取法用于IDFT運算時，由于輸入變量運算時，由于輸入變量由時間序列由時間序列x(n)改成頻率序列改成頻率序列X(k),原來按原來按x(n)的奇、偶的奇、偶次序分組的時間抽取法次序分組的時間抽取法FFT，現(xiàn)在就變成了按，現(xiàn)在就變成了按X(k)的奇的奇偶次序抽取了。偶次序抽取了。(2)同樣，頻率抽取的同樣，頻率抽取的FFT運算

23、用于運算用于IDFT運算時，也應改運算時，也應改變?yōu)闀r間抽取的變?yōu)闀r間抽取的IFFT。即當把。即當把DIF-FFT流圖用于流圖用于IDFT時，應時，應改稱改稱DIT-IFFT流圖。流圖。36DITIFFT運算流圖 37 2.直接調用直接調用FFT子程序的方法子程序的方法 由于由于對上式兩邊同時取共軛，得對上式兩邊同時取共軛，得步驟步驟：(1) 將將X(k)的虛部乘以的虛部乘以-1，即先取，即先取X(k)的共軛，得的共軛，得X*(k); (2) 將將X*(k)直接送入直接送入FFT程序程序; (3)再對運算結果取再對運算結果取一次共軛變換，并乘以常數(shù)一次共軛變換，并乘以常數(shù)1/N，即可以求出，即

24、可以求出IFFT變換的變換的x(n)的值。的值。 10)(1)(NknkNWkXNnx 10)(*1)(*NknkNWkXNnx *)(*1*)(*1)(10kXDFTNWkXNnxNknkN 38實際應用中避免倒位序的方法實際應用中避免倒位序的方法在在許多實際應用中，都是將數(shù)據(jù)的許多實際應用中，都是將數(shù)據(jù)的DFTDFT經(jīng)系統(tǒng)處理后再作經(jīng)系統(tǒng)處理后再作IDFTIDFT得到處理后的數(shù)據(jù)。如：得到處理后的數(shù)據(jù)。如：對數(shù)據(jù)進行濾波處理時對數(shù)據(jù)進行濾波處理時, ,首先對輸入的一段數(shù)據(jù)作首先對輸入的一段數(shù)據(jù)作DFTDFT，乘，乘以系統(tǒng)的以系統(tǒng)的DFTDFT（H H( (k k) )），然后再作乘積的），然后再作乘積的IDFTIDFT，得到處理過，得到處理過的數(shù)據(jù)。這時的數(shù)據(jù)。這時DFTDFT與與IDFTIDFT相當是兩個變換的級聯(lián)。適當選擇相當是兩個變換的級聯(lián)。適當選擇FFTFFT與與IFFTIFFT算法，有可能避免倒序位的算法。算法，有可能避免倒序位的算法。391. 用一個用一個N點的點的FFT計算兩個計算兩個N