Chap4快速傅立葉變換FFT

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

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

3、類算法分成兩大類按時(shí)間抽取法（按時(shí)間抽取法（DIT）按頻率抽取法（按頻率抽取法（DIF）knnW2、按時(shí)間抽取的基、按時(shí)間抽取的基-2 FFT算法算法 設(shè)時(shí)域序列設(shè)時(shí)域序列x(n)x(n)的點(diǎn)數(shù)的點(diǎn)數(shù)N N2 2M M如果不滿足，則可以如果不滿足，則可以人為地補(bǔ)零至人為地補(bǔ)零至N N為為2 2的冪級(jí)數(shù)。的冪級(jí)數(shù)。一、算法原理一、算法原理1.1. 將將N N2 2M M的序列的序列x(n)x(n)按按n n的奇偶分成兩組；的奇偶分成兩組；) 12()()2()(orxrxrxrxe奇數(shù)項(xiàng)一組：偶數(shù)項(xiàng)一組：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 只需要計(jì)算兩個(gè)只需要計(jì)算兩個(gè)N/2N/2點(diǎn)的點(diǎn)的DFTDFT： X X1 1(k)(k)、X X2 2(k)(k)就可求就可求出所有出所有N N點(diǎn)的點(diǎ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 只需要計(jì)算兩個(gè)只需要計(jì)算兩個(gè)N/2N/2點(diǎn)的點(diǎn)的DFTDFT： X X1 1(k)(k)、X X2 2(k)(k)就可求出所就可求出所有有N N點(diǎn)的點(diǎn)的X(k)X

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

7、：以例：以N8為例，第一次抽取分解圖為例，第一次抽取分解圖N/2點(diǎn)DFTWN0N/2點(diǎn)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點(diǎn)點(diǎn)DFT的第二次時(shí)域抽取分解圖的第二次時(shí)域抽取分解圖(N=8) N/4點(diǎn)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點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFTWN02WN023.繼續(xù)分解直至繼續(xù)分解直至2點(diǎn)的點(diǎn)的DFT 圖圖4.2.4 N點(diǎn)點(diǎn)DITFFT運(yùn)算流圖運(yùn)算流圖(N=8) 由于每次分解都是將序列從時(shí)域上按奇偶抽取一分由于每次分解都是將序列從時(shí)域上按奇偶抽取一分為二，所以稱基為二，所以稱基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)三、運(yùn)算量三、運(yùn)算量四、四、DIT的基的基2FFT算法的特點(diǎn)算法的特點(diǎn)運(yùn)算量：運(yùn)算量：N越大，運(yùn)算量可減少的更多越大，運(yùn)算量可減少的更多同址運(yùn)算（原位運(yùn)算）同址運(yùn)算（原位運(yùn)算）輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。后輸出均用同一存儲(chǔ)器。 輸入、輸出量互不相重，即任一蝶形結(jié)的二輸入量經(jīng)蝶形運(yùn)算后便失輸入、輸出量互不相重，即任一蝶形

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

14、點(diǎn)的DFT，按，按k的奇偶分解為的奇偶分解為N/2點(diǎn)的點(diǎn)的DFT。點(diǎn)的再分解，直至仍是偶數(shù)，可繼續(xù)往下，由于DFT222. 3NNMknNNknWnxnxkXN)() 1()()(2102二、運(yùn)算流圖二、運(yùn)算流圖1. 按頻率抽取的蝶形結(jié)運(yùn)算流圖符號(hào)按頻率抽取的蝶形結(jié)運(yùn)算流圖符號(hào))()()(21NnxnxnxnNNWnxnxnx)()()(22nNW)2(Nnx)(nx)(2nx)(1nx2.DIF基基-2FFT第一次分解運(yùn)算流圖第一次分解運(yùn)算流圖(N=8)（圖（圖4.2.11） N/2點(diǎn)DFTWN0N/2點(diǎn)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第二次分解運(yùn)算流圖第二次分解運(yùn)算流圖(N=8)（圖（圖4.2.12）N/4點(diǎn)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點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFT4.DIF基基-2FFT運(yùn)算流圖運(yùn)算流圖(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)三、運(yùn)算量：三、運(yùn)算量：由蝶形結(jié)個(gè)數(shù)來看，與由蝶形結(jié)個(gè)數(shù)來看，與DIT的運(yùn)算量一致。的運(yùn)算量一致。四、特點(diǎn)：四、特點(diǎn)：同址運(yùn)算、蝶形結(jié)點(diǎn)同址運(yùn)算、蝶形結(jié)點(diǎn)“距離距離”、系數(shù)、系數(shù)W等等5、比較、比較DIT與與DIF的蝶形結(jié)：的蝶形結(jié)：（DIT的蝶形結(jié)）的蝶形結(jié)）（DIF的蝶形結(jié)）的蝶形結(jié)）實(shí)質(zhì)上的差異：實(shí)質(zhì)上的差異：DIT：先作復(fù)乘，然后加減；：先作復(fù)乘，然后加減；DIF：先作加減，然后復(fù)乘。：先作加減，然后復(fù)乘。CABA+BCA-BCnNW)2(Nnx)

17、(nx)(2nx)(1nx輸入順序，輸入順序，輸出倒位序，輸出倒位序，DIF的基的基-2 FFT算法算法(8點(diǎn)點(diǎn))流程圖流程圖基2 FFT的兩種流程圖（DIT、DIF）比較： 輸入順序，輸入順序，輸出倒位序，輸出倒位序，DIT的基的基-2 FFT算法算法(8點(diǎn)點(diǎn))流程圖流程圖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)分散到各級(jí)中）因子（一般將MNNii21)2、具體編程實(shí)現(xiàn)方法：、具體編程實(shí)現(xiàn)方法：按照按照FFT程序過程，將兩個(gè)參數(shù)稍作改動(dòng)：程序過程，將兩個(gè)參數(shù)稍作改動(dòng)： （主要是參數(shù)主要是參數(shù)1/N，W系數(shù)上標(biāo)的負(fù)號(hào)）系數(shù)上標(biāo)的負(fù)號(hào)）直接利用現(xiàn)成的直接利用現(xiàn)成的F

19、FT算法原程序來實(shí)現(xiàn)算法原程序來實(shí)現(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、進(jìn)一步減少運(yùn)算量的措施、進(jìn)一步減少運(yùn)算量的措施一、多類蝶形單元運(yùn)算一、多類蝶形單元運(yùn)算減少復(fù)數(shù)乘法的運(yùn)算量減少復(fù)數(shù)乘法的運(yùn)算量二、旋轉(zhuǎn)因子的生成二、旋轉(zhuǎn)因子的生成三、實(shí)序列的三、實(shí)序列的FFT算法算法6 分裂基分裂基FFT算法算法一、基一、基4FFT算法算法二、任意基數(shù)（二、任意基數(shù)（N=p q）7、線性卷積的、線性卷積的FFT算法算法一、兩個(gè)長度相仿的序列：一、兩個(gè)長度相仿的序列：x(n)*h(n)(1)計(jì)算線性卷積的步驟計(jì)算線性卷積的步驟將將x(n)、h(n)補(bǔ)零點(diǎn)，至少為補(bǔ)零點(diǎn)，至少為(N1+N2-1)點(diǎn)；點(diǎn)；計(jì)算計(jì)算 H(k)=FFTh(n)；計(jì)算計(jì)算 X(k)=FFTx(n)；計(jì)算計(jì)算 Y(k)=X(k)Y(k)；計(jì)算計(jì)算 y(n)=IFFTY(k)。 (2)運(yùn)算量：運(yùn)算量：復(fù)數(shù)加法：復(fù)數(shù)乘法：共需NNN2l