第四章快速傅立葉變換(FFT)4.1引言FFT是DFT的快速算法提出與發(fā)展由庫(kù)利(J.K.Cooly)和圖基(J.KTuky)相繼出現(xiàn)了桑得(G.Sand)-圖基等快速算法價(jià)值使運(yùn)算效率提高了1~2個(gè)數(shù)量級(jí)推動(dòng)了數(shù)字信號(hào)處理技術(shù)的應(yīng)用和發(fā)展分裂基FFTFFT是DFT的一類快速算法第四章快速傅立葉變換(FFT)4.1引言FFT是DFT的14.2基2FFT算法4.2.1直接計(jì)算DFT的問(wèn)題及改進(jìn)的方法4.2.2時(shí)域抽取法基2FFT基本原理4.2.3DIT-FFT算法運(yùn)算量4.2.4DIT-FFT的運(yùn)算規(guī)律及編程思想4.2.5頻域抽取法FFT（DIF-FFT)4.2.6IDFT的高效算法(實(shí)驗(yàn):要求購(gòu)買數(shù)字信號(hào)處理實(shí)習(xí)指導(dǎo)書,熟悉MATLAB語(yǔ)言等)4.2基2FFT算法4.2.1直接計(jì)算DFT的問(wèn)題24.2基2FFT算法4.2.1直接計(jì)算DFT的問(wèn)題及改進(jìn)的方法DFT的定義兩者形式類似，差別只在于的指數(shù)符號(hào)不同，及常數(shù)因子。運(yùn)算量是相同的4.2基2FFT算法4.2.1直接計(jì)算DFT的問(wèn)題3（1）正變換的運(yùn)算量每計(jì)算一個(gè)X(k)需要N次復(fù)數(shù)乘法,(N-1)次復(fù)數(shù)加法計(jì)算N點(diǎn)X(k),則需要N2次復(fù)數(shù)乘法，N(N-1)次復(fù)數(shù)加法即:計(jì)算量正比于N2,這也是產(chǎn)生快速算法的思想由來(lái).因?yàn)榫鶠閺?fù)數(shù)注意:指數(shù)運(yùn)算（1）正變換的運(yùn)算量每計(jì)算一個(gè)X(k)需要N次復(fù)數(shù)乘法,(4（2）減少運(yùn)算量的途徑(利用DFT的性質(zhì))對(duì)稱性周期性具有如下特性：旋轉(zhuǎn)因子利用這些特性：1.使DFT運(yùn)算中的有些項(xiàng)可以合并。2.可將長(zhǎng)序列的DFT分解為短序列的DFT。更加有用的性質(zhì)（2）減少運(yùn)算量的途徑(利用DFT的性質(zhì))對(duì)稱性周期性具有如5

FFT的基本思想在于,將原有的N點(diǎn)序列分成兩個(gè)較短的序列,這兩個(gè)序列的DFT組合起來(lái),得出原序列的DFT。剩下的問(wèn)題是怎么分?:前后分或抽取分.?4.2.2時(shí)域抽取法基2FFT基本原理FFT算法分為兩大類時(shí)域抽取法(DIT)頻域抽取法(DIF)此處可以說(shuō)明基2的由來(lái)FFT的基本思想在于,將原有的N點(diǎn)序列分成兩個(gè)較短的6設(shè)M為自然數(shù)將長(zhǎng)度為N的序列x(n)按n的奇偶分成兩組則x(n)的DFT為一、時(shí)域抽取法基本原理設(shè)M為自然數(shù)將長(zhǎng)度為N的序列x(n)按n的奇偶分成兩組則x(7由于所以時(shí)域抽取法基本原理式中，是x(2r)與x(2r+1)的N/2點(diǎn)DFT(因?yàn)殚L(zhǎng)度,求和范圍和W均是針對(duì)N/2的。由于所以時(shí)域抽取法基本原理式中，是x(2r)與x(2r+1)8時(shí)域抽取法基本原理上式可見，一個(gè)N點(diǎn)DFT已分解為兩個(gè)N/2點(diǎn)的DFTX1(k)與X2(k)的組合。此時(shí)計(jì)算量已經(jīng)變化。為使這種計(jì)算量變化更明顯地表現(xiàn)出來(lái):把分成兩部分來(lái)求，此時(shí)必須應(yīng)用旋轉(zhuǎn)因子的周期性：時(shí)域抽取法基本原理上式可見，一個(gè)N點(diǎn)DFT已分解為兩個(gè)N/29時(shí)域抽取法基本原理由于分成兩部分來(lái)求：時(shí)域抽取法基本原理由于分成兩部分來(lái)求：10X

(k)的后半部分為：時(shí)域抽取法基本原理再考慮到旋轉(zhuǎn)因子的特性:所以只要求出0～N/2-1區(qū)間上X1(k)與X2(k)的值，即可得到0～N-1區(qū)間內(nèi)所有X

(k)的值。X(k)的后半部分為：時(shí)域抽取法基本原理再考慮到旋轉(zhuǎn)因子的11時(shí)域抽取法基本原理X

(k)的運(yùn)算可用蝶形信號(hào)流圖表示簡(jiǎn)記為下圖形式：時(shí)域抽取法基本原理X(k)的運(yùn)算可用蝶形信號(hào)流圖表示簡(jiǎn)記為12N點(diǎn)DFT一次時(shí)域抽取分解圖（N=8）N/2點(diǎn)DFTN/2點(diǎn)DFT時(shí)域抽取法基本原理N點(diǎn)DFT一次時(shí)域抽取分解圖（N=8）N/2點(diǎn)N/2點(diǎn)時(shí)域抽13時(shí)域抽取法基本原理計(jì)算量分析:分成兩部分(1)DFT(2)蝶形運(yùn)算(1)每個(gè)N/2點(diǎn)的DFT需要（N/2)2次復(fù)數(shù)乘，N/2(N/2-1)次復(fù)數(shù)加。兩個(gè)N/2點(diǎn)的DFT需要N2/2次復(fù)數(shù)乘，N(N/2-1)次復(fù)數(shù)加。(2)計(jì)算一個(gè)蝶形，需要1次復(fù)乘，2次復(fù)加。將兩個(gè)N/2點(diǎn)的DFT合并成N點(diǎn)DFT，有N/2個(gè)蝶形運(yùn)算，還需要N/2次復(fù)數(shù)乘及N次復(fù)數(shù)加?？傆?jì)算量:計(jì)算N點(diǎn)DFT共需要N2/2＋N/2

N2/2次復(fù)數(shù)乘，N(N/2-1)＋N

N2/2次復(fù)數(shù)加。只分解一次運(yùn)算量就減少一半。這種分解方法可一直進(jìn)行到左側(cè)為兩點(diǎn)DFT為止。時(shí)域抽取法基本原理計(jì)算量分析:分成兩部分(1)DFT14時(shí)域抽取法基本原理與第一次分解相同，將x1(r)按r的奇偶分成兩個(gè)長(zhǎng)為N/4的子序列：且時(shí)域抽取法基本原理與第一次分解相同，將x1(r)按r的奇偶分15時(shí)域抽取法基本原理x2(r)也可以進(jìn)行同樣的處理，得到X2(k)其中，將旋轉(zhuǎn)因子統(tǒng)一為，則一個(gè)N點(diǎn)DFT就可分解為4個(gè)N/4點(diǎn)的DFT.時(shí)域抽取法基本原理x2(r)也可以進(jìn)行同樣的處理，得到X216N點(diǎn)DIT-FFT運(yùn)算流圖N/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFTN點(diǎn)DIT-FFT運(yùn)算流圖N/4點(diǎn)N/4點(diǎn)N/4點(diǎn)N/4點(diǎn)17時(shí)域抽取法基本原理最后剩下的是2點(diǎn)DFT，當(dāng)N=8時(shí)，其輸出為：以X4(k)為例，因?yàn)榧磝(2),x(6)通過(guò)蝶形運(yùn)算得到X4(k)時(shí)域抽取法基本原理最后剩下的是2點(diǎn)DFT，當(dāng)N=8時(shí)，其輸出18N點(diǎn)DIT-FFT運(yùn)算流圖N點(diǎn)DIT-FFT運(yùn)算流圖19N點(diǎn)DIT-FFT運(yùn)算流圖N點(diǎn)DIT-FFT運(yùn)算流圖N=8此圖的重要性:理解FFT算法實(shí)質(zhì);分析計(jì)算量;設(shè)計(jì)FFT算法程序等N點(diǎn)DIT-FFT運(yùn)算流圖N點(diǎn)DIT-FFT運(yùn)算流圖20當(dāng)時(shí)，可分解為M級(jí)蝶形，每級(jí)都有N/2個(gè)蝶形運(yùn)算。(基2由來(lái))每一級(jí)N/2次復(fù)數(shù)乘；N次復(fù)數(shù)加。則M級(jí)次復(fù)數(shù)乘次復(fù)數(shù)加與直接計(jì)算DFT的運(yùn)算量之比4.2.3DIT-FFT算法運(yùn)算量當(dāng)時(shí)，可分解為M級(jí)蝶形，每級(jí)都有N/2個(gè)蝶形運(yùn)算。(基2由來(lái)21與直接計(jì)算DFT的運(yùn)算量之比計(jì)算速度的提高是巨大的:例如P101圖4.2.54.2.3DIT-FFT算法運(yùn)算量與直接計(jì)算DFT的運(yùn)算量之比4.2.3DIT-FFT算法221、原位計(jì)算（就地算法）4.2.4DIT-FFT的運(yùn)算規(guī)律及編程思想3、蝶形運(yùn)算規(guī)律及編程思想2、旋轉(zhuǎn)因子的變化規(guī)律4、倒位序規(guī)律5、倒位序?qū)崿F(xiàn)1、原位計(jì)算（就地算法）4.2.4DIT-FFT的運(yùn)算23DIT-FFT的運(yùn)算規(guī)律及編程思想1.原位計(jì)算（就地算法）用同一地址既存輸入序列又存輸出序列的算法。如圖4.2.4，每級(jí)運(yùn)算由N/2個(gè)蝶形構(gòu)成，每個(gè)蝶形完成下述基本運(yùn)算：式中L代表第L級(jí)蝶形運(yùn)算。J、J+B代表數(shù)據(jù)所在行。B表示蝶形運(yùn)算的兩個(gè)輸入相距B個(gè)點(diǎn)。DIT-FFT的運(yùn)算規(guī)律及編程思想1.原位計(jì)算（就地算法）24運(yùn)算規(guī)律DIT-FFT的運(yùn)算規(guī)律及編程思想每個(gè)蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)又在同一水平線上。這樣，蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸入所在的存儲(chǔ)器中。每列的N/2個(gè)蝶形運(yùn)算全部完成后，再開始下一列的蝶形運(yùn)算。下一列仍采用原位運(yùn)算，只是進(jìn)入蝶形的組合關(guān)系有所不同。運(yùn)算規(guī)律DIT-FFT的運(yùn)算規(guī)律及編程思想每個(gè)蝶形運(yùn)算的兩個(gè)25DIT-FFT的運(yùn)算規(guī)律及編程思想2.旋轉(zhuǎn)因子的變化規(guī)律觀察圖4.2.4，第L級(jí)共有2L-1個(gè)不同的旋轉(zhuǎn)因子。稱為旋轉(zhuǎn)因子，p稱為旋轉(zhuǎn)因子的指數(shù)。級(jí)(L):從左到右的運(yùn)算級(jí)數(shù)。(L=1,2,…M)DIT-FFT的運(yùn)算規(guī)律及編程思想2.旋轉(zhuǎn)因子26旋轉(zhuǎn)因子與級(jí)數(shù)（L）的關(guān)系更一般地第L級(jí)的旋轉(zhuǎn)因子為DIT-FFT的運(yùn)算規(guī)律及編程思想旋轉(zhuǎn)因子與級(jí)數(shù)（L）的關(guān)系更一般地第L級(jí)的旋轉(zhuǎn)因子為DI27蝶形運(yùn)算兩輸入點(diǎn)間距離為：第1級(jí)：1第2級(jí)：2第3級(jí)：4第L級(jí)：2L-1

每一級(jí)的兩個(gè)輸入節(jié)點(diǎn)進(jìn)行蝶形運(yùn)算后，得到下一級(jí)的相同序號(hào)的兩個(gè)輸出節(jié)點(diǎn)。DIT-FFT的運(yùn)算規(guī)律及編程思想3.蝶形運(yùn)算規(guī)律(1.端點(diǎn)間距2.相鄰間距)蝶形運(yùn)算兩輸入點(diǎn)間距離為：第1級(jí)：1第2級(jí)：228對(duì)于每個(gè)旋轉(zhuǎn)因子，有2M-L個(gè)蝶形運(yùn)算。第一個(gè)蝶形的第一個(gè)輸入所在行為J，第二個(gè)蝶形的第一個(gè)輸入所在行為J+2L，相鄰兩個(gè)蝶形運(yùn)算第一個(gè)輸入相距2L。DIT-FFT的運(yùn)算規(guī)律及編程思想對(duì)于每個(gè)旋轉(zhuǎn)因子，有2M-L個(gè)蝶形運(yùn)算。DIT-FFT的運(yùn)算29編程思想先從輸入端開始，逐級(jí)進(jìn)行計(jì)算，共進(jìn)行M級(jí)運(yùn)算。在進(jìn)行第L級(jí)運(yùn)算時(shí)，依次求出2L-1個(gè)不同的旋轉(zhuǎn)因子，每求一個(gè)旋轉(zhuǎn)因子，就計(jì)算完它對(duì)應(yīng)的所有2M-L個(gè)蝶形。(結(jié)合編程說(shuō)明:三層循環(huán),最內(nèi)層計(jì)算為:一個(gè)蝶形的計(jì)算,結(jié)合圖4.2.4)DIT-FFT的運(yùn)算規(guī)律及編程思想編程思想先從輸入端開始，逐級(jí)進(jìn)行計(jì)算，共進(jìn)行M級(jí)運(yùn)算。DIT30開始輸入x(n),MN=2M倒序L=1,MB2L-1J=0,B-1P=2M-L.Jk=J,N-1,2L輸出結(jié)束L表示運(yùn)算級(jí)數(shù)旋轉(zhuǎn)因子個(gè)數(shù)對(duì)旋轉(zhuǎn)因子計(jì)數(shù)計(jì)算旋轉(zhuǎn)因子指數(shù)每個(gè)旋轉(zhuǎn)因子對(duì)應(yīng)2M-L個(gè)蝶形運(yùn)算。兩個(gè)蝶形運(yùn)算第一個(gè)輸入點(diǎn)‘距離’是2L此流程圖是針對(duì)C寫的,MATLAB時(shí)要相應(yīng)修改開始輸入x(n),MN=2M倒序L=1,MB2L314.倒位序規(guī)律若是三位二進(jìn)制數(shù)，則就是它的倒位序。按原位計(jì)算時(shí)，F(xiàn)FT的輸出X(k)是按自然順序存儲(chǔ)的，但這時(shí)輸入序列卻不是按自然順序存儲(chǔ)的。輸入序列初看起來(lái)，好象沒有規(guī)律，實(shí)際是按倒位序存儲(chǔ)的。DIT-FFT的運(yùn)算規(guī)律及編程思想4.倒位序規(guī)律若是三位二進(jìn)制數(shù)，則就是它的倒位序。按原位計(jì)32DIT-FFT的運(yùn)算規(guī)律及編程思想倒位序的形成00100011010111x(111)=x(7)x(000)=x(0)x(010)=x(2)x(110)=x(6)x(001)=x(1)x(101)=x(5)x(100)=x(4)造成倒位序的原因是輸入序列x(n)，按標(biāo)號(hào)(序號(hào))n的奇偶不斷地分組造成的。x(011)=x(3)DIT-FFT的運(yùn)算規(guī)律及編程思想倒位序的形成0010001335.倒位序的實(shí)現(xiàn)DIT-FFT的運(yùn)算規(guī)律及編程思想（1）只要將順序二進(jìn)制數(shù)（n2n1n0）的二進(jìn)制位倒置，得（n0n1n2）。根據(jù)這種規(guī)律，容易用硬件電路和匯編語(yǔ)言產(chǎn)生倒位序數(shù)。（2）用高級(jí)語(yǔ)言程序?qū)崿F(xiàn)時(shí)，必須找出產(chǎn)生倒序數(shù)的十進(jìn)制運(yùn)算規(guī)律。5.倒位序的實(shí)現(xiàn)DIT-FFT的運(yùn)算規(guī)律及編程思想（134DIT-FFT的運(yùn)算規(guī)律及編程思想000000001

001

4

100201020103

011

6

1104

100

1

001510151016

110

3

01171117111左邊為按自然順序排列的二進(jìn)制數(shù)，下面的一個(gè)數(shù)是上面一個(gè)數(shù)的最低位上加上1，且向高位進(jìn)位。右邊為倒位序數(shù)，下面的一個(gè)數(shù)是上面一個(gè)數(shù)的最高位上加上1，且由高位向低位進(jìn)位。稱為反向進(jìn)位加法順序與倒序二進(jìn)制對(duì)照表可由當(dāng)前任一倒序值求得下一個(gè)倒序值DIT-FFT的運(yùn)算規(guī)律及編程思想000035反向進(jìn)位加法的實(shí)現(xiàn)(十進(jìn)制情況)若已知某個(gè)倒位序數(shù)J，求下一個(gè)倒位序數(shù)，判斷J的最高位是否為“0”,讓J與N/2比較，因?yàn)镹/2總是100……,如果J<N/2,則J

的最高位為零,只需把該位變?yōu)?(J=J+N/2),就得到下一個(gè)倒位序數(shù),否則,把最高位變?yōu)?(J=J-N/2)判斷J的次高位是否為“0”,讓J與N/4比較，如果J

的次高位為零,只需把該位變?yōu)?(J=J+N/4),其它位不變,就得到下一個(gè)倒位序數(shù),否則,還需判斷下一位(與N/8比較),如此依次進(jìn)行下去,總會(huì)碰到某位為0,將此位改為1即可.DIT-FFT的運(yùn)算規(guī)律及編程思想反向進(jìn)位加法的實(shí)現(xiàn)(十進(jìn)制情況)若已知某個(gè)倒位序數(shù)J，求下一36J<KNo實(shí)現(xiàn)倒位序的流程圖DIT-FFT的運(yùn)算規(guī)律及編程思想上一個(gè)倒序數(shù)下一個(gè)倒序數(shù)J<KNo實(shí)現(xiàn)倒位序的流程圖DIT-FFT的運(yùn)算規(guī)律及編程思37形成倒序數(shù)后，把原來(lái)按自然順序存放在存儲(chǔ)單元的輸入序列x(n)重新按倒序排列。通過(guò)變址運(yùn)算完成倒位序時(shí)，不必調(diào)換。而當(dāng)時(shí)，需調(diào)換。變址形成倒序數(shù)后，把原來(lái)按自然順序存放在存儲(chǔ)單元的輸入序列x(n384.2.5頻域抽取法FFT（DIF-FFT)與DIT相對(duì)應(yīng)，DIF算法是將頻域X(k)的序號(hào)k按奇偶分開。推導(dǎo)過(guò)程設(shè)M為自然數(shù)則x(n)的DFT為4.2.5頻域抽取法FFT（DIF-FFT)與DIT相39式中分別令k=2r,k=2r+1,r=0.1……,N/2-14.2.5頻域抽取法FFT（DIF-FFT)式中分別令k=2r,k=2r+1,r=0.1……,N/2-140令則4.2.5頻域抽取法FFT（DIF-FFT)令則4.2.5頻域抽取法FFT（DIF-FFT)414.2.5頻域抽取法FFT（DIF-FFT)由于N=2M，N/2仍然是偶數(shù)，繼續(xù)將N/2點(diǎn)的DFT分成偶數(shù)組和奇數(shù)組。這樣每個(gè)N/2點(diǎn)DFT可由兩個(gè)N/4點(diǎn)DFT形成。其輸入序列分別是x1(n)和x2(n)按上下對(duì)半分開形成的四個(gè)子序列。4.2.5頻域抽取法FFT（DIF-FFT)由于N=242DIF與DIT算法的比較基本蝶形不同都有M級(jí)運(yùn)算,每級(jí)有N/2個(gè)蝶形都可進(jìn)行原位計(jì)算運(yùn)算次數(shù)相同輸入為自然順序,輸出為倒位序4.2.5頻域抽取法FFT（DIF-FFT)這樣將X(k)按k的