《第四章 快速傅里葉變換(FFT)》

本章主要內(nèi)容引言基2FFT算法第4章快速傅里葉變換(FFT)DFT是信號分析與處理中的一種重要變換。但直接計算DFT的計算量與變換區(qū)間長度N的平方成正比，當(dāng)N較大時，計算量太大，不適合直接用DFT算法進(jìn)行譜分析和信號的實時處理。1965年發(fā)現(xiàn)了DFT的快速算法，使DFT的運算效率提高1～2個數(shù)量級，為數(shù)字信號處理技術(shù)應(yīng)用于各種信號的實時處理創(chuàng)造了條件，推動了數(shù)字處理技術(shù)的發(fā)展。1984年，提出了分裂基快速算法，使運算效率進(jìn)一步提高；4.1引言

4.2.1直接計算DFT的特點及減少運算量的途徑

直接計算DFT

長度為N的有限長序列x(n)的DFT為：2、減少運算量的思路

N點DFT的復(fù)乘次數(shù)等于N2。把N點DFT分解為幾個較短的DFT，可使乘法次數(shù)減少。4.2基2FFT算法考慮x(n)為復(fù)數(shù)序列的一般情況，對某一個k值，直接按上式計算X(k)值需要N次復(fù)數(shù)乘法、(N-1)次復(fù)數(shù)加法。3、減少運算量的方法分解N為較小值，把序列分解為幾個較短的序列，分別計算其DFT值；利用旋轉(zhuǎn)因子WNk的周期性、對稱性進(jìn)行合并、歸類處理，以減少DFT的運算次數(shù)。

周期性：

對稱性：4、FFT算法思想不斷地把長序列的DFT分解成幾個短序列的DFT，并利用旋轉(zhuǎn)因子的周期性和對稱性來減少DFT的運算次數(shù)。4.2.2時域抽取法基2FFT基本原理

FFT算法分為兩大類：時域抽取法FFT(簡稱DIT-FFT)

頻域抽取法FFT(簡稱DIF―FFT)。1、時域抽取法FFT的算法思想

將序列x(n)按n為奇、偶數(shù)分為x1(n)、x2(n)兩組序列；用2個N/2點DFT來完成一個N點DFT的計算。

設(shè)序列x(n)的長度為N，且滿足：

(1)按n的奇偶把x(n)分解為兩個N/2點的子序列為自然數(shù)

｛(2)用N/2點X1(k)和X2(k)表示序列x(n)的N點DFTX(k)偶數(shù)奇數(shù)注意：這里的k的取值范圍為0，1，…，N-1由于X1(k)和X2(k)均以N/2為周期，且,X(k)可表示為:

對上式的運算用下圖所示的流圖符號來表示這樣將N點DFT分解為兩個N/2點的DFTX1(k)X2(k)X1(k)+WNkX2(k)X1(k)WNkX2(k)WNk圖：蝶形運算符號完成一個蝶形運算需要一次復(fù)數(shù)乘和兩次復(fù)數(shù)加法運算，經(jīng)過一次分解后，共需要復(fù)數(shù)乘和復(fù)數(shù)加的次數(shù)為2(N/2)2+N/2和N2/2｛11N/2點DFTN/2點DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X2(0)WN0X(0)X(4)｛N=8點的DIT-2FFT(時域抽取圖)一次分解圖X1(1)X2(1)WN1X(1)X(5)X1(2)X2(2)WN2X(2)X(6)X1(3)X2(3)WN3X(3)X(7)將x1(r)按r取奇、偶可分解成2個長度為N/4的子序列

根據(jù)上面推導(dǎo)可得：將x2(r)按r取奇、偶可分解成2個長N/4的子序列k=0,1,…,N/4-1；(3)第二次分解k=0,1,…,N/2-1k=0,1,…,N/4-1；N/4點DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4點DFTN/4點DFTN/4點DFTX1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N=8點DFT的二次時域抽取分解圖X3(0)X4(0)WN/20X3(1)X4(1)WN/21X5(0)X6(0)WN/20X5(1)X6(1)WN/21k=0,1,…,N/4-1；再次分解，對N=8點，可分解三次。X(5)N=8點DIT-FFT運算流圖x(0)x(4)x(2)x(6)x(1)x(5)x(3)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(6)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/20WN/40x(7)WN/21L=1級L=2L=3X(7)X3(0)X1(0)WN/40WN/40WN/40N=8點DIT-FFT運算流圖x(0)x(4)x(2)x(6)x(1)x(5)x(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)WN0WN2WN0WN0WN0WN0x(7)WN2WN0L=1級L=2L=3X(7)4.2.3DIT―FFT算法與直接計算DFT運算量的比較1、直接DFT運算N點運算

復(fù)數(shù)乘次數(shù)：N×N復(fù)數(shù)加次數(shù)：N×(N-1)2、用DIT-FFT作N點運算復(fù)數(shù)乘次數(shù)：M×N/2=N/2×log2N復(fù)加次數(shù)：2×N/2×M=N×log2N可見FFT大大減少了運算次數(shù)，提高了運算速度。整個運算流圖中有M級蝶形，每一級運算流圖中有N/2個蝶形，每個蝶形需一次復(fù)乘和兩次復(fù)數(shù)加運算。1.原位計算

序列長為N=2M點的FFT，有M級蝶形，每級有N/2個蝶形運算。同一級中，每個蝶形的兩個輸入數(shù)據(jù)只對本蝶形有用，每個蝶形的輸入、輸出數(shù)據(jù)節(jié)點在用一條水平線上。這樣，當(dāng)計算完一個蝶形后，所得的輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲單元。經(jīng)過M級運算后，原來存放輸入序列數(shù)據(jù)的N個存儲單元中可依次存放X(k)的N個值。原位計算：利用同一存儲單元存儲蝶形輸入、輸出數(shù)據(jù)的方法。優(yōu)點：節(jié)約存儲空間、降低設(shè)備成本。4.2.4DIT-FFT的運算規(guī)律及編程思想每蝶形都要乘以旋轉(zhuǎn)因子，p稱為旋轉(zhuǎn)因子的指數(shù)。N＝8＝23時各級的旋轉(zhuǎn)因子第一級:L=1,有1個旋轉(zhuǎn)因子：第二級:L=2,有2個旋轉(zhuǎn)因子：第三級:L=3,有4個旋轉(zhuǎn)因子：對于N＝2M

的一般情況，第L級共有2L-1個不同的旋轉(zhuǎn)因子：2.旋轉(zhuǎn)因子和運算級數(shù)的關(guān)系可以確定第L級運算的旋轉(zhuǎn)因子3、同一級中，同一旋轉(zhuǎn)因子對應(yīng)蝶形數(shù)目第L級FFT運算中，同一旋轉(zhuǎn)因子用在2M-L個蝶形中；4、同一級中，使用相同旋轉(zhuǎn)因子的蝶形之間相隔的“距離”第L級中，蝶距：D=2L。5、同一蝶形運算兩輸入數(shù)據(jù)的距離

在輸入倒序，輸出原序的FFT變換中，第L級的每個蝶形的兩個輸入數(shù)據(jù)相距：B=2L-1。6、碼位顛倒輸入序列x(n)經(jīng)過M級時域奇、偶抽選后，輸出序列X(k)的順序和輸入序列的順序關(guān)系為倒位關(guān)系。7、蝶形運算的規(guī)律

序列經(jīng)過時域抽選后，存入數(shù)組中，如果蝶形運算的兩個輸入數(shù)據(jù)相距B個點，應(yīng)用原位計算，蝶形運算可表示成如下形式：XL-1(J)XL-1(J+B)XL(J)=XL-1(J)+WNpXL-1(J+B)XL(J)=XL-1(J)WNpXL-1(J+B)WNpp=J×2M-L，J=0,1,2,…,2L-1－1B=2L-1(1)倒序:根據(jù)倒序規(guī)律，對輸入自然順序序列x(n)進(jìn)行倒序處理；(2)循環(huán)層1:確定運算的級數(shù)，L=1M(N=2M)；確定一蝶形兩輸入數(shù)據(jù)距離B=2L-1(3)循環(huán)層2:確定L級的(B=)2L-1個旋轉(zhuǎn)因子；旋轉(zhuǎn)因子指數(shù)p=2M-LJ，J=0B-1；(4)循環(huán)層3:對于同一旋轉(zhuǎn)因子，用于同一級2M-L個蝶形運算中：k的取值從J到N-1，步長為2L(使用同一旋轉(zhuǎn)因子的蝶形相距的距離)(5)完成一個蝶形運算8、DIT-FFT程序框圖N=2M，用M位二進(jìn)制數(shù)(nM-1nM-2…n1n0)2表示序列的序號n.M次偶奇時域抽選過程為：對最低位按0、1分為偶、奇兩組，次低位也按0、1分組，依此類推，M次分解后形成倒序圖為：二進(jìn)制數(shù)(N=8)分解倒序圖10041015110611170000001101020113倒序前00111015011311170000100401021106倒序后可見，只要將順序數(shù)的二進(jìn)制位倒置可得到對應(yīng)的二進(jìn)制倒序值。10n20101n100010n0111(n2n1n0)29、序列的倒序思考題：已知N=16點，在DIT-FFT運算中，序數(shù)為2的二進(jìn)制經(jīng)數(shù)倒序后為多少?順序數(shù)增加1，是在順序數(shù)的二進(jìn)制數(shù)的最低位加1，向左進(jìn)位到序數(shù)是在M位二進(jìn)制數(shù)的最高位加1，向右進(jìn)位(0010->0100)順序和倒序二進(jìn)制數(shù)對照表N=2M，用M位二進(jìn)制數(shù)表示，則從左至右的十進(jìn)制權(quán)值為：N/2、N/4、N/8,…、2,1

對倒序數(shù)J，其下一個序數(shù)是在該序數(shù)J的二進(jìn)制首位碼加1，相當(dāng)于十進(jìn)制運算J+N/2。

計算機上倒序數(shù)的實現(xiàn)過程為：J>N/2？J>N/4輸入當(dāng)前倒序數(shù)十進(jìn)制數(shù)值JNYNYJ>N/2MNY結(jié)束J=J-N/2倒序數(shù)的十進(jìn)制運算規(guī)律為了實現(xiàn)原位運算，在倒序數(shù)J形成后，需將原存儲器中存放的輸入序列重新排列。下面先分析N=8點的倒序規(guī)律。

x(0)A(0)x(1)A(1)x(2)A(2)x(3)A(3)x(4)A(4)x(5)A(5)x(6)A(6)x(7)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)輸入序列數(shù)組分析上圖N=8點倒序規(guī)律，順序數(shù)I與倒序數(shù)J存在關(guān)系：

I=J時，不交換；

I<J時，交換存儲器內(nèi)容。

I>J時，不交換，直接更新序數(shù)值；IJx(0)x(2)x(4)x(1)x(5)x(6)x(3)x(7)倒序程序框圖計算倒序值交換數(shù)組中的數(shù)據(jù)不交換數(shù)據(jù)，避免再次調(diào)換前面調(diào)換過的一對數(shù)據(jù)，計算下一個倒數(shù)值。在基2快速算法中，頻域抽取法FFT也是一種常用的快速算法。1、算法思想和運算過程設(shè)序列x(n)長度為N=2M，將序列x(n)前后對半分為x1(n)、x2(n)兩組序列，用2個N/2點DFT來完成一個N點DFT的計算。nk=偶數(shù)

,k=奇數(shù)

4.2.5頻域抽取法FFT(DIF―FFT)將X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2r,r=0,1,…,N/2-1)時當(dāng)k取奇數(shù)(k=2r+1,r=0,1,…,N/2-1)時：將x1(n)和x2(n)分別代入上式，可得x1(n)x2(n)表明：X(k)按奇偶k值分為兩組:偶數(shù)組是x1(n)的N/2點DFT奇數(shù)組是x2(n)的N/2點DFT｛r=0,1,…,N/2-1那么對序列x1(n)、x2(n)和x(n)可用蝶形運算符號表示x(n)x1(n)=x(n)+x(n+N/2)x2(n)=[x(n)x(n+N/2)]WNnWNnx(n+N/2)DIF-FFT蝶形運算流圖符號N=8時第1次分解的運算流圖N/2點DFTN/2點DFTx1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(4)WN0X(3)X(0)X(2)X(4)X(6)X(1)X(5)X(7)x(1)x(5)WN1x(2)x(6)WN2x(3)x(7)WN3N=2M，N/2仍是偶數(shù)，繼續(xù)將N/2點進(jìn)行分解。將輸入序列x1(n)、x2(n)分別按前、后對半分解成4個長N/4的子序列，其n=0,1,…，N/4-1｛x3(n)=x1(n)+x1(n+N/4)

x4(n)=[x1(n)-x1(n+N/4)]WN/2n

x5(n)=x2(n)+x2(n+N/4)

x6(n)=[x2(n)-x2(n+N/4)]WN/2nX(0)X(4)X(2)X(6)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0x1(0)x1(1)x1(2)x1(3)N/4點DFTx3(0)x3(1)N/4點DFTx4(0)x4(1)WN0WN1WN2WN3X(1)X(5)X(3)X(7)WN2WN0WN2N/4點DFTN/4點DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)DIF―FFT二次分解運算流圖(N=8)

｛經(jīng)過三次分解后，DIF―FFT運算流圖(N=8)為x(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)WN0WN1WN2WN3X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)WN0WN2WN0WN2WN0WN0WN0WN0DIF-FFT算法也可采用原位計算；N=2M時，共有M級運算，每級共有N/2個蝶形，DIT與DIF算法的運算次數(shù)相同。DIT與DIF不同的是：

DIF-FFT算法輸入序列為自然序列，輸出為倒序序列。在M級運算完成后，需對輸出數(shù)據(jù)進(jìn)行倒序才能得到自然順序的X(k)。

蝶形運算符號不同：DIT-FFT蝶形是先相乘，后加/減；而DIF-FFT蝶形是先加/減，后相乘。DIT-FFT蝶形運算符號X1(k)X2(k)X1(k)+WNkX2(k)X1(k)WNkX2(k)WNkx2(n)=[x(n)x(n+N/2)]WNnx(n)x1(n)=x(n)+x(n+N/2)WNnx(n+N/2)DIF-FFT蝶形運算流圖符號2、DIF-FFT運算規(guī)律改變輸入/輸出節(jié)點,中間節(jié)點的排列順序,可得到不同變形的FFT運算流圖。因此，DIT-FFT和DIF-FFT運算流圖都不是唯一的。X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)X3(0)X5(0)X4(0)X6(0)X3(1)X5(1)X4(1)X6(1)WN0x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN0WN0WN2WN1WN3X1(0)X2(0)X1(