Chap4快速傅立葉變換FFT

1、第四章第四章 快速傅立葉變換快速傅立葉變換FFT算法算法快速傅立葉變換快速傅立葉變換FFT不是一種新的變換不是一種新的變換而是而是DFTDFT的快速算法的快速算法1、直接計算、直接計算DFT的問題及改進的途徑的問題及改進的途徑1.直接計算直接計算N點點DFT的運算量：的運算量： 次復(fù)數(shù)加法次復(fù)數(shù)乘法，需要一個1NN)(X k1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx 次復(fù)數(shù)加法次復(fù)數(shù)乘法運算，需要整個) 1N(NNDFT2一次復(fù)數(shù)乘法需一次復(fù)數(shù)乘法需4次實數(shù)乘法，次實數(shù)乘法，2次實數(shù)加法；次實數(shù)加法；一次復(fù)數(shù)加法需要一次

2、復(fù)數(shù)加法需要2次實數(shù)加法次實數(shù)加法次實數(shù)加法次實數(shù)乘法運算，需要整個)24(2) 12N(N4NDFT222NNN 從上面的統(tǒng)計可以看出：從上面的統(tǒng)計可以看出：直接計直接計DFT，運算量幾乎與，運算量幾乎與N2成正成正比，且當(dāng)比，且當(dāng)N很大時，運算量相當(dāng)可觀。很大時，運算量相當(dāng)可觀。2.改善途徑改善途徑(1)根據(jù)根據(jù)DFT的特性：的特性： 如如 的對稱性、周期性、可約性、常數(shù)值的對稱性、周期性、可約性、常數(shù)值(2)DFT運算量與運算量與N平方成正比：平方成正比： 使使N點點DFT分解為更少點數(shù)的分解為更少點數(shù)的 DFT （這一點也是這一點也是FFT運算的關(guān)鍵）運算的關(guān)鍵）3.FFT算法分成兩大

3、類算法分成兩大類按時間抽取法（按時間抽取法（DIT）按頻率抽取法（按頻率抽取法（DIF）knnW2、按時間抽取的基、按時間抽取的基-2 FFT算法算法 設(shè)時域序列設(shè)時域序列x(n)x(n)的點數(shù)的點數(shù)N N2 2M M如果不滿足，則可以如果不滿足，則可以人為地補零至人為地補零至N N為為2 2的冪級數(shù)。的冪級數(shù)。一、算法原理一、算法原理1.1. 將將N N2 2M M的序列的序列x(n)x(n)按按n n的奇偶分成兩組；的奇偶分成兩組；) 12()()2()(orxrxrxrxe奇數(shù)項一組：偶數(shù)項一組：12102Nr， 10102222)()()()()()(NNNNrrkeorrkeeeWr

4、xrxDFTkXoWrxrxDFTkX12102Nk， 2.2.相應(yīng)的相應(yīng)的DFTDFT也分成兩組也分成兩組10)()()(NnnkNWnxnxDFTkX1010)12(222) 12()2(NNrrrkNrkNWrxWrx1010N2222)()(NNNNrrrkekrkeWrxWWrx利用可約性22)()()()(222NokNNerkrkkXWkXWWkXNNN 1, 0Nk3.3.考慮考慮W WN N的周期性，的周期性，X(k)X(k)分成前后兩部分；分成前后兩部分； 12, 0)(NkkX：前半部分)()(kXWkXokNe 12, 0)2(NkNkX：后半部分)()(kXWkXok

5、Ne 只需要計算兩個只需要計算兩個N/2N/2點的點的DFTDFT： X X1 1(k)(k)、X X2 2(k)(k)就可求就可求出所有出所有N N點的點的X(k)X(k) 一、算法原理一、算法原理 將將N N2 2M M的序列的序列x(n)x(n)按按n n的奇偶分成兩組；的奇偶分成兩組； 相應(yīng)的相應(yīng)的DFTDFT也分成兩組；也分成兩組； 考慮考慮W WN N的周期性，的周期性，X(k)X(k)分成前后兩部分；分成前后兩部分；v 只需要計算兩個只需要計算兩個N/2N/2點的點的DFTDFT： X X1 1(k)(k)、X X2 2(k)(k)就可求出所就可求出所有有N N點的點的X(k)X

6、(k)運算量：抽取分解一次，運算量約省一半運算量：抽取分解一次，運算量約省一半 由于由于N/2N/2 2 2M M1 1 ，仍然是偶數(shù)，則可繼續(xù)將一個，仍然是偶數(shù)，則可繼續(xù)將一個N/2N/2點序列的點序列的DFTDFT分解為兩個分解為兩個N/4N/4點的點的DFTDFT；1.1. 繼續(xù)這樣的分解，直至最后是二點的繼續(xù)這樣的分解，直至最后是二點的DFTDFT為止。為止。二、信號流圖（蝶形信號流圖）二、信號流圖（蝶形信號流圖）n對N2 2M M如果進行第一次抽取如果進行第一次抽取)()()(21kXWkXkXkN)()()2(21kXWkXkNXkNCABA+BCA-BC蝶形運算符號蝶形運算符號例

7、：以例：以N8為例，第一次抽取分解圖為例，第一次抽取分解圖N/2點DFTWN0N/2點DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)2.繼續(xù)分解繼續(xù)分解圖圖4.2.3 N點點DFT的第二次時域抽取分解圖的第二次時域抽取分解圖(N=8) N/4點DFTWN12WN12WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(

8、5)X(6)X(7)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4點DFTN/4點DFTN/4點DFTWN02WN023.繼續(xù)分解直至繼續(xù)分解直至2點的點的DFT 圖圖4.2.4 N點點DITFFT運算流圖運算流圖(N=8) 由于每次分解都是將序列從時域上按奇偶抽取一分由于每次分解都是將序列從時域上按奇偶抽取一分為二，所以稱基為二，所以稱基2的算法。的算法。WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 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

9、)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(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)三、運算量三、運算量四、四、DIT的基的基2FFT算法的特點算法的特點運算量：運算量：N越大，運算量可減少的更多越大，運算量可減少的更多同址運算（原位運算）同址運算（原位運算）輸入數(shù)據(jù)、中間運算結(jié)果和最輸入數(shù)據(jù)、中間運算結(jié)果和最后輸出均用同一存儲器。后輸出均用同一存儲器。 輸入、輸出量互不相重，即任一蝶形結(jié)的二輸入量經(jīng)蝶形運算后便失輸入、輸出量互不相重，即任一蝶形

10、結(jié)的二輸入量經(jīng)蝶形運算后便失去利用價值，所以可將計算結(jié)果存入原輸入量的寄存器單元中。去利用價值，所以可將計算結(jié)果存入原輸入量的寄存器單元中。輸入倒位序，輸出順序：輸入倒位序，輸出順序：蝶形運算兩結(jié)點間的蝶形運算兩結(jié)點間的“距離距離”：蝶形運算系數(shù)蝶形運算系數(shù)WNk五、時間抽取基五、時間抽取基2FFT算法，用計算機程序來實現(xiàn)：算法，用計算機程序來實現(xiàn)：三級循環(huán)：第三級循環(huán)：第m級中的級中的2Mm簇中每簇有簇中每簇有2m1個蝶形結(jié)個蝶形結(jié)六、六、 DIT基基-2 FFT算法流圖，用其它流圖形式表示：算法流圖，用其它流圖形式表示： 輸入順位序，輸出倒位序輸入順位序，輸出倒位序輸入順序輸出倒位序輸入倒

11、位序輸出順序DIT的基的基2 FFT的兩種流程圖的兩種流程圖WN0WN0WN2WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN2WN1WN3WN2WN0WN0WN0WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 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(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X

12、(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)3、頻域抽取（、頻域抽?。―IF）的基）的基-2 FFT算法算法按頻率抽取按頻率抽取把輸出序列把輸出序列X(k)按按k的奇偶分解為越來越短的序列。的奇偶分解為越來越短的序列。 一、算法原理一、算法原理1.(在在X(k)按奇偶分組之前，先按奇偶分組之前，先)將輸入序列將輸入序列x(n)按前后順序?qū)Π氚辞昂箜樞驅(qū)Π敕纸?；分解?注：這不是頻率抽取注：這不是頻率抽取10)()(NnknNWnxkX11022)()(NnknNnknNNNWnxWnx10)2(21022)()(NNnNnkNNnknNWnxWnxknNNkNnWnx

13、WnxNN)()(21022knNNknWnxnxN)() 1()(21022.按輸出序列按輸出序列X(k)中中k的奇偶性的奇偶性將它分為兩組將它分為兩組為奇數(shù)：為偶數(shù)：kknrNNnWnxnxrXkXrkN2210)()()2()(,22rnNnNNWnxnx22)()(210nrNNnWnxnxrXkXrkN)12(210)()() 12()(, 122nrnNNnNNWWnxnx22)()(210nNNNWnxnxnxnxnxnx)()()()()()(2221令1022101122)()() 12()()()2(NNnrnNnrnNrXWnxrXrXWnxrX這樣，就將這樣，就將N點的

14、點的DFT，按，按k的奇偶分解為的奇偶分解為N/2點的點的DFT。點的再分解，直至仍是偶數(shù)，可繼續(xù)往下，由于DFT222. 3NNMknNNknWnxnxkXN)() 1()()(2102二、運算流圖二、運算流圖1. 按頻率抽取的蝶形結(jié)運算流圖符號按頻率抽取的蝶形結(jié)運算流圖符號)()()(21NnxnxnxnNNWnxnxnx)()()(22nNW)2(Nnx)(nx)(2nx)(1nx2.DIF基基-2FFT第一次分解運算流圖第一次分解運算流圖(N=8)（圖（圖4.2.11） N/2點DFTWN0N/2點DFTWN1WN2WN3X(0)x1(0)X(2)X(4)X(6)X(1)X(3)X(5

15、)X(7)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)3.DIF基基-2FFT第二次分解運算流圖第二次分解運算流圖(N=8)（圖（圖4.2.12）N/4點DFTWN0WN1WN2WN3x(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)WN0WN2WN0WN2N/4點DFTN/4點DFTN/4點DFT4.DIF基基-2FFT運算流圖運算流圖(N=8)（圖（圖4.2.13）WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0

16、WN0WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)三、運算量：三、運算量：由蝶形結(jié)個數(shù)來看，與由蝶形結(jié)個數(shù)來看，與DIT的運算量一致。的運算量一致。四、特點：四、特點：同址運算、蝶形結(jié)點同址運算、蝶形結(jié)點“距離距離”、系數(shù)、系數(shù)W等等5、比較、比較DIT與與DIF的蝶形結(jié)：的蝶形結(jié)：（DIT的蝶形結(jié)）的蝶形結(jié)）（DIF的蝶形結(jié)）的蝶形結(jié)）實質(zhì)上的差異：實質(zhì)上的差異：DIT：先作復(fù)乘，然后加減；：先作復(fù)乘，然后加減；DIF：先作加減，然后復(fù)乘。：先作加減，然后復(fù)乘。CABA+BCA-BCnNW)2(Nnx)

17、(nx)(2nx)(1nx輸入順序，輸入順序，輸出倒位序，輸出倒位序，DIF的基的基-2 FFT算法算法(8點點)流程圖流程圖基2 FFT的兩種流程圖（DIT、DIF）比較： 輸入順序，輸入順序，輸出倒位序，輸出倒位序，DIT的基的基-2 FFT算法算法(8點點)流程圖流程圖WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN0WN2WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(

18、4)x(5)x(6)x(7)WN0WN2WN1WN3WN2WN0WN0WN04、離散傅立葉反變換、離散傅立葉反變換(IDFT)的快速算法（的快速算法（IFFT）1、IFFT原理原理 比較比較1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx二者差別：二者差別：knNknNWWi)分散到各級中）因子（一般將MNNii21)2、具體編程實現(xiàn)方法：、具體編程實現(xiàn)方法：按照按照FFT程序過程，將兩個參數(shù)稍作改動：程序過程，將兩個參數(shù)稍作改動： （主要是參數(shù)主要是參數(shù)1/N，W系數(shù)上標的負號）系數(shù)上標的負號）直接利用現(xiàn)成的直接利用現(xiàn)成的F

19、FT算法原程序來實現(xiàn)算法原程序來實現(xiàn): P.109X(k)變?yōu)樽優(yōu)閄*(k) 直接訪問直接訪問FFT程序程序 結(jié)果取共軛，再乘以結(jié)果取共軛，再乘以1/N。1)直接訪問直接訪問FFT程序得程序得x1(n) 將結(jié)果倒序排列，再乘以將結(jié)果倒序排列，再乘以1/N得得x(n)。注：區(qū)別與倒位序注：區(qū)別與倒位序 排列排列5、進一步減少運算量的措施、進一步減少運算量的措施一、多類蝶形單元運算一、多類蝶形單元運算減少復(fù)數(shù)乘法的運算量減少復(fù)數(shù)乘法的運算量二、旋轉(zhuǎn)因子的生成二、旋轉(zhuǎn)因子的生成三、實序列的三、實序列的FFT算法算法6 分裂基分裂基FFT算法算法一、基一、基4FFT算法算法二、任意基數(shù)（二、任意基數(shù)（N=p q）7、線性卷積的、線性卷積的FFT算法算法一、兩個長度相仿的序列：一、兩個長度相仿的序列：x(n)*h(n)(1)計算線性卷積的步驟計算線性卷積的步驟將將x(n)、h(n)補零點，至少為補零點，至少為(N1+N2-1)點；點；計算計算 H(k)=FFTh(n)；計算計算 X(k)=FFTx(n)；計算計算 Y(k)=X(k)Y(k)；計算計算 y(n)=IFFTY(k)。 (2)運算量：運算量：復(fù)數(shù)加法：復(fù)數(shù)乘法：共需NNN2l