快速傅里葉變換FFT.ppt

本章主要內(nèi)容引言基2FFT算法進(jìn)一步減少運(yùn)算量的措施,第4章快速傅里葉變換(FFT),DFT是信號(hào)分析與處理中的一種重要變換。但直接計(jì)算DFT的計(jì)算量與變換區(qū)間長(zhǎng)度N的平方成正比，當(dāng)N較大時(shí)，計(jì)算量太大，直接用DFT算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。1965年發(fā)現(xiàn)了DFT的一種快速算法，使DFT的運(yùn)算效率提高12個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了條件，推動(dòng)了數(shù)字處理技術(shù)的發(fā)展。1984年，提出了分裂基快速算法，使運(yùn)算效率進(jìn)一步提高；,4.1引言,4.2.1直接計(jì)算DFT的特點(diǎn)及減少運(yùn)算量的基本途徑直接計(jì)算DFT長(zhǎng)度為N的有限長(zhǎng)序列x(n)的DFT為：2、減少運(yùn)算量的思路和方法思路：N點(diǎn)DFT的復(fù)乘次數(shù)等于N2。把N點(diǎn)DFT分解為幾個(gè)較短的DFT，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子WmN具有周期性和對(duì)稱性。,4.2基2FFT算法,考慮x(n)為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)k值，直接按上式計(jì)算X(k)值需要N次復(fù)數(shù)乘法、(N-1)次復(fù)數(shù)加法。,方法：分解N為較小值：把序列分解為幾個(gè)較短的序列，分別計(jì)算其DFT值，可使乘法次數(shù)大大減少；利用旋轉(zhuǎn)因子WNk的周期性、對(duì)稱性進(jìn)行合并、歸類處理，以減少DFT的運(yùn)算次數(shù)。周期性：對(duì)稱性：3、FFT算法思想不斷地把長(zhǎng)序列的DFT分解成幾個(gè)短序列的DFT，并利用旋轉(zhuǎn)因子的周期性和對(duì)稱性來減少DFT的運(yùn)算次數(shù)。,4.2基2FFT算法,4.2.2時(shí)域抽取法基2FFT基本原理FFT算法基本上分為兩大類：時(shí)域抽取法FFT(簡(jiǎn)稱DIT-FFT)和頻域抽取法FFT(簡(jiǎn)稱DIFFFT)。1、時(shí)域抽取法FFT的算法思想：將序列x(n)按n為奇、偶數(shù)分為x1(n)、x2(n)兩組序列；用2個(gè)N/2點(diǎn)DFT來完成一個(gè)N點(diǎn)DFT的計(jì)算。設(shè)序列x(n)的長(zhǎng)度為N，且滿足：(1)按n的奇偶把x(n)分解為兩個(gè)N/2點(diǎn)的子序列,4.2基2FFT算法,為自然數(shù),(2)用N/2點(diǎn)X1(k)和X2(k)表示序列x(n)的N點(diǎn)DFTX(k),4.2基2FFT算法,注意：這里的k的取值范圍為0，1，N-1,由于X1(k)和X2(k)均以N/2為周期，且,X(k)又可表示為:對(duì)上式的運(yùn)算用下圖所示的流圖符號(hào)來表示,4.2基2FFT算法,這樣將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)的DFT,完成一個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘和兩次復(fù)數(shù)加法運(yùn)算，經(jīng)過一次分解后，共需要復(fù)數(shù)乘和復(fù)數(shù)加的次數(shù)為2(N/2)2+N/2和N2/2,4.2基2FFT算法,N=8點(diǎn)的DIT-2FFT(時(shí)域抽取圖)一次分解圖,(3)第二次分解：將x1(r)按r取奇、偶可分解成2個(gè)長(zhǎng)度為N/4的子序列x3(l)=x1(2l)、x4(l)=x1(2l+1)，根據(jù)上面推導(dǎo)可得：X1(k)=X3(k)+WN/2kX4(k)，k=0,1,N/2-1將x2(r)按r取奇、偶可分解成2個(gè)長(zhǎng)N/4的子序列x5(l)=x2(2l)，l=0,1,，N/4x6(l)=x2(2l+1)；同理得,4.2基2FFT算法,l=0,1,，N/4-1；,4.2基2FFT算法,N=8點(diǎn)DFT的二次時(shí)域抽取分解圖,k=0,1,N/4-1；,再次分解，對(duì)N=8點(diǎn)，可分解三次。,4.2基2FFT算法,4.2基2FFT算法,4.2.3DITFFT算法與直接計(jì)算DFT運(yùn)算量的比較1、直接DFT運(yùn)算N點(diǎn)運(yùn)算：復(fù)數(shù)乘次數(shù)：NN復(fù)數(shù)加次數(shù)：N(N-1)2、用DIT-FFT作N點(diǎn)運(yùn)算：復(fù)數(shù)乘次數(shù)：MN/2=N/2log2N；復(fù)加次數(shù)：2N/2M=Nlog2N?？梢奆FT大大減少了運(yùn)算次數(shù)，提高了運(yùn)算速度。,4.2基2FFT算法,整個(gè)運(yùn)算流圖中有M級(jí)蝶形，每一級(jí)運(yùn)算流圖中有N/2個(gè)蝶形，每個(gè)蝶形需一次復(fù)乘和兩次復(fù)數(shù)加運(yùn)算。,4.2.4DITFFT的運(yùn)算規(guī)律及編程思想1.原位計(jì)算序列長(zhǎng)為N=2M點(diǎn)的FFT，有M級(jí)蝶形，每級(jí)有N/2個(gè)蝶形運(yùn)算。同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)本蝶形有用，每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在用一條水平線上。這樣，當(dāng)計(jì)算完一個(gè)蝶形后，所得的輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元。經(jīng)過M級(jí)運(yùn)算后，原來存放輸入序列數(shù)據(jù)的N個(gè)存儲(chǔ)單元中可依次存放X(k)的N個(gè)值。原位計(jì)算：利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸出數(shù)據(jù)的方法。優(yōu)點(diǎn)：節(jié)約存儲(chǔ)空間、降低設(shè)備成本。,4.2基2FFT算法,2.旋轉(zhuǎn)因子的變化規(guī)律N點(diǎn)DITFFT運(yùn)算流圖中，每個(gè)蝶形都要乘以旋轉(zhuǎn)因子WpN，p稱為旋轉(zhuǎn)因子的指數(shù)。N823時(shí)各級(jí)的旋轉(zhuǎn)因子第一級(jí)：L=1，有1個(gè)旋轉(zhuǎn)因子：WNp=WN/4J=W2LJJ=0第二級(jí)：L=2，有2個(gè)旋轉(zhuǎn)因子：WNp=WN/2J=W2LJJ=0,1第三級(jí)：L=3，有4個(gè)旋轉(zhuǎn)因子：WNp=WNJ=W2LJJ=0,1,2,3對(duì)于N2M的一般情況，第L級(jí)共有2L-1個(gè)不同的旋轉(zhuǎn)因子：WNp=W2LJJ=0,1,2,2L-112L=2LM2M=N2LM故：按照上面兩式可以確定第L級(jí)運(yùn)算的旋轉(zhuǎn)因子。,4.2基2FFT算法,p=J2M-L，J=0,1,2,2L-11,3、同一級(jí)中，同一旋轉(zhuǎn)因子對(duì)應(yīng)蝶形數(shù)目第L級(jí)FFT運(yùn)算中，同一旋轉(zhuǎn)因子用在2M-L個(gè)蝶形中；4、同一級(jí)中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間相隔的“距離”第L級(jí)中，蝶距：D=2L。5、同一蝶形運(yùn)算兩輸入數(shù)據(jù)的距離在輸入倒序，輸出原序的FFT變換中，第L級(jí)的每一個(gè)蝶形的2個(gè)輸入數(shù)據(jù)相距：B=2L-1。6、碼位顛倒輸入序列x(n)經(jīng)過M級(jí)時(shí)域奇、偶抽選后，輸出序列X(k)的順序和輸入序列的順序關(guān)系為倒位關(guān)系。,4.2基2FFT算法,7、蝶形運(yùn)算的規(guī)律序列經(jīng)過時(shí)域抽選后，存入數(shù)組中，如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，蝶形運(yùn)算可表示成如下形式：,4.2基2FFT算法,8、DIT-FFT程序框圖根據(jù)DIT-FFT原理和過程，DIT-FFT的完整程序框圖包括以下幾部分：(1)倒序:輸入自然順序序列x(n)，根據(jù)倒序規(guī)律，進(jìn)行倒序處理；(2)循環(huán)層1:確定運(yùn)算的級(jí)數(shù)，L=1M(N=2M)；確定一蝶形兩輸入數(shù)據(jù)距離B=2L-1(3)循環(huán)層2:確定L級(jí)的(B=)2L-1個(gè)旋轉(zhuǎn)因子；旋轉(zhuǎn)因子指數(shù)p=2M-LJ，J=0B-1；(4)循環(huán)層3:對(duì)于同一旋轉(zhuǎn)因子，用于同一級(jí)2M-L個(gè)蝶形運(yùn)算中：k的取值從J到N-1，步長(zhǎng)為2L(使用同一旋轉(zhuǎn)因子的蝶形相距的距離)(5)完成一個(gè)蝶形運(yùn)算。,4.2基2FFT算法,9.序列的倒序N=2M，用M位二進(jìn)制數(shù)(nM-1nM-2n1n0)2表示序列的序號(hào)n.M次偶奇時(shí)域抽選過程為：對(duì)最低位按0、1分為偶、奇兩組，次低位也按0、1分組，依此類推，M次分解后形成倒序圖為：,4.2基2FFT算法,二進(jìn)制數(shù)(N=8)分解倒序圖,可見，只要將順序數(shù)的二進(jìn)制位倒置可得到對(duì)應(yīng)的二進(jìn)制倒序值。,(n2n1n0)2,思考題：已知N=16點(diǎn)，在DIT-FFT運(yùn)算中，序數(shù)為2的二進(jìn)制經(jīng)數(shù)倒序后為多少?,4.2基2FFT算法,順序數(shù)增加1，是在順序數(shù)的二進(jìn)制數(shù)的最低位加1，向左進(jìn)位,到序數(shù)是在M位二進(jìn)制數(shù)的最高位加1，向右進(jìn)位,(0010->0100),順序和倒序二進(jìn)制數(shù)對(duì)照表,N=2M，用M位二進(jìn)制數(shù)表示，則從左至右的十進(jìn)制權(quán)值為：N/2、N/4、N/8,、2,1對(duì)倒序數(shù)J，其下一個(gè)序數(shù)是在該序數(shù)J的二進(jìn)制首位碼加1，相當(dāng)于十進(jìn)制運(yùn)算J+N/2。計(jì)算機(jī)上倒序數(shù)的實(shí)現(xiàn)過程為：,4.2基2FFT算法,倒序數(shù)的十進(jìn)制運(yùn)算規(guī)律,倒序程序框圖為了實(shí)現(xiàn)原位運(yùn)算，以節(jié)約存貯空間，提高運(yùn)算速率。在倒序數(shù)J形成后，需將原存儲(chǔ)器中存放的輸入序列重新排列。下面先分析N=8點(diǎn)的倒序規(guī)律。,4.2基2FFT算法,輸入序列,數(shù)組,分析上圖N=8點(diǎn)倒序規(guī)律，順序數(shù)I與倒序數(shù)J存在關(guān)系：I=J時(shí)，不交換；IJ時(shí)，不交換，直接更新序數(shù)值；,I,J,x(0),x(2),x(5),x(7),計(jì)算倒序值,交換數(shù)組中的數(shù)據(jù),不交換數(shù)據(jù)，避免再次調(diào)換前面調(diào)換過的一對(duì)數(shù)據(jù)，計(jì)算下一個(gè)倒數(shù)值。,4.2.5頻域抽取法FFT(DIFFFT)在基2快速算法中，頻域抽取法FFT也是一種常用的快速算法。1、算法思想和運(yùn)算過程設(shè)序列x(n)長(zhǎng)度為N=2M，將序列x(n)前后對(duì)半分為x1(n)、x2(n)兩組序列，用2個(gè)N/2點(diǎn)DFT來完成一個(gè)N點(diǎn)DFT的計(jì)算。,4.2基2FFT算法,n,4.2基2FFT算法,將X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2r,r=0,1,N/2-1)時(shí)當(dāng)k取奇數(shù)(k=2r+1,r=0,1,N/2-1)時(shí)：將x1(n)和x2(n)分別代入上式，可得,x2(n),表明：X(k)按奇偶k值分為兩組:偶數(shù)組是x1(n)的N/2點(diǎn)DFT奇數(shù)組是x2(n)的N/2點(diǎn)DFT,n=0,1,N/2-1,那么對(duì)序列x1(n)、x2(n)和x(n)可用蝶形運(yùn)算符號(hào)表示,4.2基2FFT算法,N=8時(shí)第1次分解的運(yùn)算流圖,N=2M，N/2仍是偶數(shù)，繼續(xù)將N/2點(diǎn)進(jìn)行分解。將輸入序列x1(n)、x2(n)分別按前、后對(duì)半分解成4個(gè)長(zhǎng)N/4的子序列,其n=0,1,，N/4-1,4.2基2FFT算法,經(jīng)過三次分解后，DIFFFT運(yùn)算流圖(N=8)為：,4.2基2FFT算法,2、DIF-FFT運(yùn)算規(guī)律DIF-FFT算法也可采用原位計(jì)算；N=2M時(shí)，共有M級(jí)運(yùn)算，每級(jí)共有N/2個(gè)蝶形，DIT與DIF算法的運(yùn)算次數(shù)相同。DIT與DIF不同的是：DIF-FFT算法輸入序列為自然序列，輸出為倒序序列。因此，在M級(jí)運(yùn)算完成后，需對(duì)輸出數(shù)據(jù)進(jìn)行倒序才能得到自然順序的X(k)。蝶形運(yùn)算符號(hào)不同：DIT-FFT蝶形是先相乘，后加/減；而DIF-FFT蝶形是先加/減，后相乘。,4.2基2FFT算法,3、其它形式的DIT-FFT運(yùn)算流圖通過改變輸入/輸出節(jié)點(diǎn),中間節(jié)點(diǎn)的排列順序,可以得到不同變形的FFT運(yùn)算流圖。因此，前面介紹的DIT-FFT和DIF-FFT運(yùn)算流圖都不是唯一的。,4.2基2FFT算法,用同樣的方法可得DIT-FFT的另外一種變形運(yùn)算流圖，輸入和輸出均為順序排列，但不能采用原位計(jì)算。,4.2基2FFT算法,DITFFT的一種變形運(yùn)算流圖,4.2.6IDFT的高效算法1DFT和IDFT的公式比較上述FFT算法流圖也可以用于離散傅里葉逆變換IDFT根據(jù)運(yùn)算公式可以看出，只需將DFT的系數(shù)WNkn變?yōu)閃N-kn，最后結(jié)果乘以1/N，就是IDFT的運(yùn)算公式。,第4章快速傅里葉變換(FFT),X(k),n,2用FFT流圖實(shí)現(xiàn)IDFT快速算法將DIT-FFT或DIF-FFT蝶形運(yùn)算流圖中旋轉(zhuǎn)因子WNp改為WN-p在IDFT快速算法的最后結(jié)果輸出前，乘以1/N常數(shù)；如要防止溢出，可在每一級(jí)運(yùn)算中，輸出支路分別乘以1/2，實(shí)現(xiàn)系數(shù)分級(jí)分擔(dān)。在IDFT快速算法中，輸入序列為X(k)，而輸出序列為x(n)。節(jié)點(diǎn)對(duì)應(yīng)關(guān)系：DIT-FFT對(duì)應(yīng)DIF-IFFTDIF-FFT對(duì)應(yīng)DIT-IFFT,第4章快速傅里葉變換(FFT),第4章快速傅里葉變換(FFT),DITIFFT運(yùn)算流圖,第4章快速傅里葉變換(FFT),DITIFFT運(yùn)算流圖(防止溢出),3、直接調(diào)用FFT程序?qū)崿F(xiàn)IFFT的計(jì)算對(duì)FFT流程作一些修改后，調(diào)用FFT程序?qū)崿F(xiàn)IFFT的快速計(jì)算。具體實(shí)現(xiàn)方法：先將X(k)取共軛，得到X*(k)；直接調(diào)用FFT子程序計(jì)算出DFTX*(k)的值；對(duì)輸出序列取共軛，并乘以1/N常數(shù)。雖然2次用了取共軛運(yùn)算，但可以和FFT共用一個(gè)子程序，實(shí)現(xiàn)方便。,第4章快速傅里葉變換(FFT),本章作業(yè)本章第一次作業(yè)習(xí)題1習(xí)題2本章第二次作業(yè)習(xí)題3習(xí)題4,