《快速傅里葉變換FFT.ppt》由會員分享，可在線閱讀，更多相關《快速傅里葉變換FFT.ppt（37頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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