fft算法原理學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1fft算法原理算法原理第一節(jié)第一節(jié) 直接計(jì)算直接計(jì)算DFTDFT的問題及改進(jìn)途徑的問題及改進(jìn)途徑1、問題的提出、問題的提出 設(shè)有限長序列設(shè)有限長序列x(n)，非零值長度為非零值長度為N，若對(duì)若對(duì)x(n)進(jìn)行一次進(jìn)行一次DFT運(yùn)算，共需運(yùn)算，共需多大的運(yùn)算工作多大的運(yùn)算工作量量？計(jì)算成本計(jì)算成本?計(jì)算速度計(jì)算速度?第1頁/共61頁2. DFT的運(yùn)算量的運(yùn)算量 回憶回憶DFT和和IDFT的變換式：的變換式： 10)(1)()(10 NnWkXNkXIDFTnxNknk10)()()(10 NkWnxnxDFTkXNnnkN1）x(n)為為復(fù)數(shù)復(fù)數(shù)， 也為也為復(fù)數(shù)復(fù)數(shù)。2）DFT與與IDFT

2、的的計(jì)算量相當(dāng)。計(jì)算量相當(dāng)。nkNjnkNeW 2 注意：注意： 第2頁/共61頁計(jì)算機(jī)運(yùn)算時(shí)（編程實(shí)現(xiàn)）：計(jì)算機(jī)運(yùn)算時(shí)（編程實(shí)現(xiàn)）： 0k0)1(0100) 1() 1 ()0()0(NNNNWNxWxWxX1k 0111(1)1(1)(0)(1)(1)NNNNXxWxWx NW 2k 0 212(1) 2(2)(0)(1)(1)NNNNXxWxWx NW1Nk0111(1)1(1)(0)(1)(1)NNNNNNNX NxWxWx NW 10)()()(10 NkWnxnxDFTkXNnnkN以以DFT為例：為例： 第3頁/共61頁復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法一個(gè)一個(gè)X(k)NN 1N個(gè)

3、個(gè)X(k)(N點(diǎn)點(diǎn)DFT)N 2N (N 1)實(shí)數(shù)乘法實(shí)數(shù)乘法實(shí)數(shù)加法實(shí)數(shù)加法一次復(fù)乘一次復(fù)乘42一次復(fù)加一次復(fù)加2一個(gè)一個(gè)X (k)4N2N+2 (N 1)=2 (2N 1)N個(gè)個(gè)X (k)(N點(diǎn)點(diǎn)DFT)4N 22N (2N 1)10( )NnkNnx n W運(yùn)算量運(yùn)算量(a+jb)(c+jd)=(ac-bd)+j(bc+ad)第4頁/共61頁例：計(jì)算一個(gè)例：計(jì)算一個(gè) N點(diǎn)點(diǎn)DFT ，共需共需N2次復(fù)乘次復(fù)乘。以做一次。以做一次 復(fù)乘復(fù)乘1s計(jì)，若計(jì)，若N =4096，所需時(shí)間為所需時(shí)間為ss1716777216)4096(2 例：石油勘探，有例：石油勘探，有24個(gè)通道的記錄，每通道波形記

4、個(gè)通道的記錄，每通道波形記 錄長度為錄長度為5秒，若每秒抽樣秒，若每秒抽樣500點(diǎn)點(diǎn)/秒，秒， 1）每道總抽樣點(diǎn)數(shù)：）每道總抽樣點(diǎn)數(shù)：500*5=2500點(diǎn)點(diǎn) 2）24道總抽樣點(diǎn)數(shù)：道總抽樣點(diǎn)數(shù)：24*2500=6萬點(diǎn)萬點(diǎn) 3）DFT復(fù)乘運(yùn)算時(shí)間：復(fù)乘運(yùn)算時(shí)間：N2=(60000)2=36*108次次ss360010*36)60000(82 第5頁/共61頁 由于計(jì)算量大，且要求由于計(jì)算量大，且要求相當(dāng)大的內(nèi)存相當(dāng)大的內(nèi)存，難以實(shí)現(xiàn)實(shí)時(shí)處理難以實(shí)現(xiàn)實(shí)時(shí)處理，限制了，限制了DFT的應(yīng)用。長期以來，人們一直在尋求一種能的應(yīng)用。長期以來，人們一直在尋求一種能提高提高DFT運(yùn)算速度運(yùn)算速度的方法。的方

5、法。 FFT便是便是 Cooley & Tukey 在在1965 年提出的的快速算法，它可以使運(yùn)算速度提高幾百倍，從而使數(shù)字信號(hào)處理學(xué)科成為一個(gè)新興的應(yīng)用學(xué)科。年提出的的快速算法，它可以使運(yùn)算速度提高幾百倍，從而使數(shù)字信號(hào)處理學(xué)科成為一個(gè)新興的應(yīng)用學(xué)科。第6頁/共61頁第二節(jié)第二節(jié) 改善改善DFTDFT運(yùn)算效率的基本途徑運(yùn)算效率的基本途徑knNW 1、利用、利用DFT運(yùn)算的系數(shù)運(yùn)算的系數(shù) 的固有對(duì)稱性和周期的固有對(duì)稱性和周期 性，改善性，改善DFT的運(yùn)算效率。的運(yùn)算效率。 1）對(duì)稱性）對(duì)稱性 2）周期性周期性 3）可約性）可約性第7頁/共61頁()() nkN n kn N kNNNW

6、WW周期性 nkmnkNmNWW可約性/nknk mNN mWW2jmnkmNe221NjjNee 0/2(/2) 11Nk NkNNNNWWWW 特殊點(diǎn)：nkNW 的特性2jnknkNNWe*()() ()nknkN n kn N kNNNNWWWW對(duì)稱性NknkNNWWnNnkNNWW第8頁/共61頁2、將長序列、將長序列DFT利用對(duì)稱性和周期性分解為短利用對(duì)稱性和周期性分解為短 序列序列DFT的的思路思路 因?yàn)橐驗(yàn)镈FT的運(yùn)算量與的運(yùn)算量與N2成正比的，如果一個(gè)成正比的，如果一個(gè)大點(diǎn)數(shù)大點(diǎn)數(shù)N的的DFT能分解為能分解為若干小點(diǎn)數(shù)若干小點(diǎn)數(shù)DFT的組合的組合，則顯然可以達(dá)到，則顯然可以達(dá)到

7、減少運(yùn)算工作量減少運(yùn)算工作量的效果。的效果。第9頁/共61頁N點(diǎn)點(diǎn)DFTN/2點(diǎn)點(diǎn)DFTN/2點(diǎn)點(diǎn)DFTN/4點(diǎn)點(diǎn)DFTN/4點(diǎn)點(diǎn)DFTN/4點(diǎn)點(diǎn)DFTN/4點(diǎn)點(diǎn)DFT.復(fù)乘：復(fù)乘：2N2222 NN22N22224444 NNNN42N第10頁/共61頁 FFT算法的基本思想：算法的基本思想： 利用利用DFT系數(shù)的特性，合并系數(shù)的特性，合并DFT運(yùn)算中的某些項(xiàng)運(yùn)算中的某些項(xiàng) 把長序列把長序列DFT短序列短序列DFT，從而減少運(yùn)算量。從而減少運(yùn)算量。FFT算法分類算法分類:時(shí)間抽選法時(shí)間抽選法 DIT: Decimation-In-Time頻率抽選法頻率抽選法 DIF: Decimation-

8、In-Frequency第11頁/共61頁第三節(jié)第三節(jié) 按時(shí)間抽選的基按時(shí)間抽選的基2-FFT算法算法1、算法原理、算法原理 設(shè)輸入序列長度為設(shè)輸入序列長度為N=2M(M為正整數(shù)，將該序列為正整數(shù)，將該序列按時(shí)間順序的奇偶分解按時(shí)間順序的奇偶分解為越來越短的子序列，稱為基為越來越短的子序列，稱為基2按時(shí)間抽取的按時(shí)間抽取的FFT算法。也稱為算法。也稱為Coolkey-Tukey算法。算法。 其中其中基基2表示：表示：N=2M，M為整數(shù)為整數(shù).若不滿足這個(gè)條件，可以人為地加上若干零值（若不滿足這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)長加零補(bǔ)長）使其達(dá)到）使其達(dá)到 N=2M。第12頁/共61頁先將

9、先將x(n)按按n的奇偶分為兩組，作變量置換的奇偶分為兩組，作變量置換: 當(dāng)當(dāng)n=偶數(shù)時(shí)，令偶數(shù)時(shí)，令n=2r; 當(dāng)當(dāng)n=奇數(shù)時(shí)，令奇數(shù)時(shí)，令n=2r+1; 分組，變量置換分組，變量置換2、算法步驟、算法步驟10)()()(10 NkWnxnxDFTkXNnnkN得到：得到：1,.,0)() 12()()2(221 Nrrxrxrxrx第13頁/共61頁 帶入帶入DFT中中 10)()()(NnnkNWnxnxDFTkX 12/0)12(12/02)12()2(NrkrNNrrkNWrxWrx 1010)()(NnnkNNnnkNnnWnxWnx為為奇奇數(shù)數(shù)為為偶偶數(shù)數(shù) 12/02212/02

10、1)()(NrrkNkNNrrkNWrxWWrx第14頁/共61頁所以所以 12/02212/021)()()(NrrkNkNNrrkNWrxWWrxkX由于由于nNnNjnNjnNWeeW2/2/2222 12/02/212/02/1)()(NrrkNkNNrrkNWrxWWrx)()(21kXWkXkN 1, 1 , 02 Nk1, 1 , 0 Nk? ?1, 1 , 02 Nk第15頁/共61頁 X1(k)、X2(k)只有只有N/2個(gè)點(diǎn)，以個(gè)點(diǎn)，以N/2為周期；而為周期；而X (k)卻有卻有N個(gè)點(diǎn)，以個(gè)點(diǎn)，以N為周期。要用為周期。要用X1(k)、X2(k)表達(dá)全部的表達(dá)全部的X (k)

11、值，還必須利用值，還必須利用WN系數(shù)的系數(shù)的周期特性周期特性。rkNkNrNWW2/)2/(2/ 12/02/112/0)2/(2/11)()()2/(NrrkNNrkNrNWrxWrxkNX )()2/()()2/(2211kXkNXkXkNX第16頁/共61頁后半部分后半部分前半部分前半部分又考慮到又考慮到 的對(duì)稱性：的對(duì)稱性：kNWkNkNNNkNNWWWW 2/)2/()2/()2/()2/(2)2/(1kNXWkNXkNXkNN 有：有：1, 1 , 0)()()(221 NkNkkXWkXkX1, 1 , 0)()(221 NkNkkXWkX第17頁/共61頁后半部分后半部分前半部

12、分前半部分)()()2/(21kXWkXkNXkN )()()(21kXWkXkXkN 1, 1 , 02 Nk)(1kX)(2kXkNW)()(21kXWkXkN )()(21kXWkXkN 蝶形運(yùn)算流圖符號(hào)蝶形運(yùn)算流圖符號(hào)說明：說明： (1) 左邊兩路為輸入左邊兩路為輸入 (2) 右邊兩路為輸出右邊兩路為輸出 (3) 中間以一個(gè)小圓表示加、中間以一個(gè)小圓表示加、 減運(yùn)算（右上路為相加減運(yùn)算（右上路為相加 輸出、右下路為相減輸輸出、右下路為相減輸 出出)1個(gè)蝶形運(yùn)算需要個(gè)蝶形運(yùn)算需要1次復(fù)乘，次復(fù)乘，2次復(fù)加次復(fù)加第18頁/共61頁復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法一個(gè)一個(gè)N 點(diǎn)點(diǎn)DFTN 2

13、N (N1)一個(gè)一個(gè)N / 2點(diǎn)點(diǎn)DFT(N / 2)2N / 2 (N / 2 1)兩個(gè)兩個(gè)N / 2點(diǎn)點(diǎn)DFTN 2 / 2N (N / 2 1)一個(gè)蝶形一個(gè)蝶形12N / 2個(gè)蝶形個(gè)蝶形N / 2N總計(jì)總計(jì)N2/2 + N/2 N2/2N(N/2-1) + N N2/2運(yùn)算量減少了近一半運(yùn)算量減少了近一半 分解后的運(yùn)算量：分解后的運(yùn)算量：第19頁/共61頁)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN 12/, 0 Nk先將先將N=8點(diǎn)的點(diǎn)的DFT分解成分解成2個(gè)個(gè)4點(diǎn)點(diǎn)DFT：可知：可知：時(shí)域上：時(shí)域上：x(0),x(2),x(4),x(6)為偶子序列為偶子

14、序列 x(1),x(3),x(5),x(7)為奇子序列為奇子序列 頻域上：頻域上：X(0)X(3)，由，由X(k)給出給出 X(4)X(7)，由，由X(k+N/2)給出給出例子：求例子：求 N=23=8點(diǎn)點(diǎn)FFT變換變換 按按N=8N/2=4，做做4點(diǎn)的點(diǎn)的DFT：第20頁/共61頁 N=8點(diǎn)的直接點(diǎn)的直接DFT的計(jì)算量為：的計(jì)算量為： 復(fù)乘：復(fù)乘：N2次次 = 64次次 復(fù)加：復(fù)加：N(N-1)次次 = 87=56次次)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN 12/, 0 Nk 此外，還有此外，還有4個(gè)蝶形結(jié)，每個(gè)蝶形結(jié)需要個(gè)蝶形結(jié)，每個(gè)蝶形結(jié)需要1次復(fù)乘，

15、次復(fù)乘，2次復(fù)加。次復(fù)加。一共是：復(fù)乘一共是：復(fù)乘4次，復(fù)加次，復(fù)加8次。次。得到得到X1(k)和和X2(k)需要：需要： 復(fù)乘：復(fù)乘：(N/2)2+ (N/2)2次次 = 32次次 復(fù)加：復(fù)加：N/2(N/2-1)+N/2(N/2-1) =12+12 =24次次用分解的方法得到用分解的方法得到X (k)需要：需要： 復(fù)乘：復(fù)乘：32+4 = 36次次 復(fù)加：復(fù)加：24+8 = 32次次第21頁/共61頁N點(diǎn)點(diǎn)DFT的一次時(shí)域抽取分解圖的一次時(shí)域抽取分解圖(N=8) 4點(diǎn)點(diǎn)DFT4點(diǎn)點(diǎn)DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)

16、X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)38W28W18W08W第22頁/共61頁 奇奇序序列列、偶偶序序列列、)6()2()4()0(: )(1xxxxrx 奇奇序序列列、偶偶序序列列、同同理理：)7()3()5() 1 (: )(2xxxxrx因?yàn)橐驗(yàn)?點(diǎn)點(diǎn)DFT還是比較麻煩，所以再繼續(xù)分解。還是比較麻煩，所以再繼續(xù)分解。 若將若將N/2(4點(diǎn)點(diǎn))子序列按奇子序列按奇/偶分解成兩個(gè)偶分解成兩個(gè)N/4點(diǎn)點(diǎn)(2點(diǎn)點(diǎn))子序列。即對(duì)將子序列。即對(duì)將x1(r)和和x2(r)分解成奇、偶兩個(gè)分解成奇、偶兩個(gè)N/4點(diǎn)點(diǎn)(2點(diǎn)點(diǎn))點(diǎn)的子序列。

17、點(diǎn)的子序列。1 , 0) 1.0()() 12()()2(44131 lllxlxlxlxN此此處處，奇奇序序列列偶偶序序列列設(shè)設(shè)：1 , 0) 1.0()() 12()()2(46252 lllxlxlxlxN此此處處，奇奇序序列列偶偶序序列列設(shè)設(shè)：第23頁/共61頁那么，那么，X1(k)又可表示為又可表示為 14/0)12(2/114/022/11)12()2()(NlklNNllkNWlxWlxkX 14/04/42/14/04/3)()(NllkNkNNllkNWlxWWlx)()(42/3kXWkXKN 1,.1 , 0)()()()()()(442/34142/31 NkNNkNk

18、kXWkXkXkXWkXkX第24頁/共61頁 14/0)12(2/214/022/22)21()2()(NlklNNllkNWlxWlxkX 14/04/62/14/04/5)()(NllkNkNNllkNWlxWWlx1,.1 , 0)()()()()()(462/54262/52 NkNNkNkkXWkXkXkXWkXkXX2(k)也可以進(jìn)行相同的分解：也可以進(jìn)行相同的分解： 注意：通常我們會(huì)把注意：通常我們會(huì)把 寫成寫成 。kNW2/kNW2)()(62/5kXWkXKN 第25頁/共61頁N點(diǎn)點(diǎn)DFT的第二次時(shí)域抽取分解圖的第二次時(shí)域抽取分解圖(N=8) 2點(diǎn)點(diǎn)DFT2點(diǎn)點(diǎn)DFT2點(diǎn)

19、點(diǎn)DFT2點(diǎn)點(diǎn)DFTx(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)08W28W08W28WX1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)38W28W18W08WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)4點(diǎn)點(diǎn)DFT4點(diǎn)點(diǎn)DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(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(5)X(6)X(7)38W28W

20、18W08W第26頁/共61頁)1()0()()()(32314/04/333xWxWlxlxDFTkXkNlklN )1()0()1()0()1()1()0()0(30233123330233xWxxWxXxWxX 8808WX3(0)X3(1)x(0)=x3(0)x(4)=x3(1)第27頁/共61頁N點(diǎn)點(diǎn)DITFFT運(yùn)算流圖運(yùn)算流圖(N=8) x(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) 0NW0NW0NW0NW0NW2NW0NW2NW0NW2NW1NW3NW第28頁/共61

21、頁3、DITFFT算法與直接計(jì)算算法與直接計(jì)算DFT運(yùn)算量的比較運(yùn)算量的比較22log2NNN 1)、N=2M的的DFT運(yùn)算可分成運(yùn)算可分成M級(jí)，每一級(jí)有級(jí)，每一級(jí)有N/2個(gè)蝶形個(gè)蝶形 ，每個(gè)蝶形有一次復(fù)乘兩次復(fù)加。，每個(gè)蝶形有一次復(fù)乘兩次復(fù)加。NN2log2NN2log2)、所以、所以M級(jí)共有級(jí)共有 次復(fù)乘和次復(fù)乘和 次復(fù)加。次復(fù)加。3)、若直接計(jì)算、若直接計(jì)算DFT，需需N2次復(fù)乘和次復(fù)乘和N(N-1)次復(fù)加。次復(fù)加。顯然，當(dāng)顯然，當(dāng)N較大時(shí)，有：較大時(shí)，有：例如，例如，N=210=1024時(shí)時(shí)221048576204.8(/2)log5120NNN第29頁/共61頁FFT算法與直接計(jì)算算

22、法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線所需乘法次數(shù)的比較曲線第30頁/共61頁4、DITFFT的運(yùn)算規(guī)律及編程思想的運(yùn)算規(guī)律及編程思想 FFT的每級(jí)（列）計(jì)算都是由的每級(jí)（列）計(jì)算都是由N個(gè)復(fù)數(shù)數(shù)據(jù)（輸入）兩兩構(gòu)個(gè)復(fù)數(shù)數(shù)據(jù)（輸入）兩兩構(gòu)成一個(gè)蝶型（共成一個(gè)蝶型（共N/2個(gè)蝶形）運(yùn)算而得到另外個(gè)蝶形）運(yùn)算而得到另外N個(gè)復(fù)數(shù)數(shù)據(jù)（輸出個(gè)復(fù)數(shù)數(shù)據(jù)（輸出）。）。 當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后，每一組運(yùn)算的結(jié)果，當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后，每一組運(yùn)算的結(jié)果，仍然存放在這同一仍然存放在這同一組存儲(chǔ)器中組存儲(chǔ)器中直到最后輸出。直到最后輸出。例：將例：將x(0)放在單元放在單元A(0)中，將中，將x(4)放在單元放在

23、單元A(1)中，中，W80 放在一個(gè)暫存器中。放在一個(gè)暫存器中。將將x(0) + W80 x(4) 送回送回A(0)單元單元將將x(0) - W80 x(4) 送回送回A(1)單元單元08WX3(0)X3(1)x(0)x(4)1） 原位運(yùn)算原位運(yùn)算 (亦稱同址計(jì)算亦稱同址計(jì)算)第31頁/共61頁x(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) 0NW0NW0NW0NW0NW2NW0NW2NW0NW2NW1NW3NW回顧：回顧：N點(diǎn)點(diǎn)DITFFT運(yùn)算流圖運(yùn)算流圖(N=8) 第32頁/共6

24、1頁 如上所述，如上所述，N點(diǎn)點(diǎn)DITFFT運(yùn)算流圖中，每級(jí)都有運(yùn)算流圖中，每級(jí)都有N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子個(gè)蝶形。每個(gè)蝶形都要乘以因子WNP，稱其為稱其為旋轉(zhuǎn)因子旋轉(zhuǎn)因子，p稱為旋轉(zhuǎn)因子的指數(shù)。稱為旋轉(zhuǎn)因子的指數(shù)。2)旋轉(zhuǎn)因子的變化規(guī)律旋轉(zhuǎn)因子的變化規(guī)律 觀察觀察FFT運(yùn)算流圖發(fā)現(xiàn)，第運(yùn)算流圖發(fā)現(xiàn)，第L級(jí)共有級(jí)共有2L-1個(gè)不同的旋轉(zhuǎn)因子。個(gè)不同的旋轉(zhuǎn)因子。N=23=8時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下：時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下：L=1時(shí)，時(shí)，WNp=WN/4J， N/4 =21 =2L， J=0L=2時(shí)，時(shí)， WNp =WN/2J， N/2 =22 =2L， J=0，1L=3時(shí)，時(shí)， WN

25、p =WNJ， N =23 =2L， J=0，1，2，3第33頁/共61頁對(duì)對(duì)N=2M的一般情況，第的一般情況，第L級(jí)的旋轉(zhuǎn)因子為：級(jí)的旋轉(zhuǎn)因子為：12,.,1 , 012 LJPNJWWLMLMLMLN 222212,.,1 , 0122 LJNJNPNJWWWLMMLLMJp 2第34頁/共61頁 設(shè)序列設(shè)序列x(n)經(jīng)時(shí)域抽選經(jīng)時(shí)域抽選(倒序倒序)后，存入數(shù)組后，存入數(shù)組X中。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距中。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)個(gè)點(diǎn)(B=2L-1)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式：應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式：pNLLLpNLLLWBJXJXBJX

26、WBJXJXJX)()()()()()(1111 MLJJpLLM,.,2 , 112,.,1 , 021 ，式式中中： 下標(biāo)下標(biāo)L表示第表示第L級(jí)運(yùn)算，級(jí)運(yùn)算，XL(J)則表示第則表示第L級(jí)運(yùn)算后數(shù)組元素級(jí)運(yùn)算后數(shù)組元素X(J)的值。的值。第35頁/共61頁3) 編程思想及流程圖編程思想及流程圖開始開始送入送入x(n)和和N=2M調(diào)整輸入調(diào)整輸入x(n)的順序的順序for(L=1; L=M; L+)B = 2L-1for(J=0; J=B-1; J+)p = J2M-Lfor(k = J; k= N-1; k=k+2L) pNpNWBkXkXBkXWBkXkXkX)()()()()()( 輸

27、出結(jié)果輸出結(jié)果結(jié)束結(jié)束第36頁/共61頁4）碼位倒序碼位倒序 由由N=8蝶形圖看出：原位計(jì)算時(shí)，蝶形圖看出：原位計(jì)算時(shí)，F(xiàn)FT輸出的輸出的X(k)的次序正好是順序排列的，即的次序正好是順序排列的，即X(0)X(7),但輸入但輸入x(n)都不能按自然順序存入到存儲(chǔ)單元中，而是按都不能按自然順序存入到存儲(chǔ)單元中，而是按x(0),x(4),x(2),x(6) ,x(1),x(5),x(3),x(7)的順序存入存儲(chǔ)單元的順序存入存儲(chǔ)單元，即為亂序輸入，順序輸出。即為亂序輸入，順序輸出。 這種順序看起來相當(dāng)雜亂，然而它是這種順序看起來相當(dāng)雜亂，然而它是有規(guī)律有規(guī)律的。即的。即碼位倒讀規(guī)則碼位倒讀規(guī)則。第

28、37頁/共61頁自然順序自然順序n二進(jìn)制碼表二進(jìn)制碼表示示碼位倒讀碼位倒讀碼位倒置順序碼位倒置順序n以以N=8為例：為例：0123456700000101001110010111011100010001011000110101111104261537看出：看出：碼位倒讀后碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。第38頁/共61頁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)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)x(0)x(4)x(2)x(6)x(

29、1)x(5)x(3)x(7)倒序規(guī)律倒序規(guī)律第39頁/共61頁第40頁/共61頁正序序列已在數(shù)組正序序列已在數(shù)組A 中，輸中，輸 入入 NLH= N/2 , j=LH , N1 = N-2j=j-kk=k/2 k=LHjkj=j+k T = A(j) A(i) = A(j) A(j) = Tfor(i=1; i=N1; i+) i j第41頁/共61頁第四節(jié)第四節(jié) 按頻率抽選的基按頻率抽選的基2-FFT算法算法 在基在基2快速算法中，頻域抽取法快速算法中，頻域抽取法FFT也是一種常用的快速算法，簡稱也是一種常用的快速算法，簡稱DIFFFT。 設(shè)序列設(shè)序列x(n)長度為長度為N=2M，首先將首先

30、將x(n)前后對(duì)半分開，得到兩個(gè)子序列，其前后對(duì)半分開，得到兩個(gè)子序列，其DFT可表示為如下形式可表示為如下形式第42頁/共61頁 1-NN/2nknN1-N/20nknN1-N0nknNWnxWnxWnxX(k)()()( -1N/20n)2/(-1N/20n)2/()( NnkNknNWNnxWnx -1N/20n-1N/20n)2/()1()(knNkknNWNnxWnx1,.1 , 0 Nk kjkkNNjkNNeeW1222/ 式式中中， 12/01,.1 , 0,)2/(1)()(NnknNkNkWNnxnxkX第43頁/共61頁:)(k分為兩部分分為兩部分的奇偶可把的奇偶可把按按

31、kX12/.2 , 1 , 0,12,2 Nrrkrk及及令令為偶數(shù)時(shí)，為偶數(shù)時(shí)，K 12/02/12/02) 2/()() 2/()(2NnrnNNnrnNWNnxnxWNnxnxrX為奇數(shù)時(shí)，為奇數(shù)時(shí)，K 12/02/12/012)2/()()2/()(12NnrnNnNNnnrNWWNnxnxWNnxnxrX）（第44頁/共61頁nNW)2/()()(1Nnxnxnx nNWNnxnxnx)2/()()(2 )(nx)2/(Nnx 1,.,1 , 0)2/()()()2/()()(221 NnNnWNnxnxnxNnxnxnx令令 nrNNnnrNNnWnxrXkXWnxrXkX2/12

32、/0222/12/011)()12()()()2()(第45頁/共61頁DIFFFT一次分解運(yùn)算流圖一次分解運(yùn)算流圖(N=8) 4點(diǎn)點(diǎn)DFT4點(diǎn)點(diǎn)DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)3NW2NW1NW0NWx1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)第46頁/共61頁DIFFFT二次分解運(yùn)算流圖二次分解運(yùn)算流圖(N=8) 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)

33、X(5)X(3)X(7)WN0WN2WN0WN2N/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFT第47頁/共61頁DIFFFT運(yùn)算流圖運(yùn)算流圖(N=8) 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)第48頁/共61頁 時(shí)間抽取算法與頻率抽取算法的比較時(shí)間抽取算法與頻率抽取算法的比較1) 頻率抽選法和時(shí)間抽選法總的計(jì)算量是相同的頻率抽選法和時(shí)間抽選法總的計(jì)算量是相同的NN2log2NN2log復(fù)乘：復(fù)乘：復(fù)加：復(fù)加：2) 頻率抽取法和時(shí)間抽取法一樣

34、，都適用于頻率抽取法和時(shí)間抽取法一樣，都適用于原位運(yùn)原位運(yùn) 算算， 即蝶形的輸入和輸出占用同一個(gè)存儲(chǔ)單元。即蝶形的輸入和輸出占用同一個(gè)存儲(chǔ)單元。3) 均存在碼位倒序問題。均存在碼位倒序問題。4) 頻率抽選法和時(shí)間抽選法一樣，基本運(yùn)算也是蝶形頻率抽選法和時(shí)間抽選法一樣，基本運(yùn)算也是蝶形 運(yùn)算。但兩者的蝶形形式略有不同。運(yùn)算。但兩者的蝶形形式略有不同。第49頁/共61頁第五節(jié)第五節(jié) IDFT的快速算法的快速算法IFFT上述上述FFT算法流圖也可以用于離散傅里葉逆變換算法流圖也可以用于離散傅里葉逆變換(Inverse Discrete Fourier Transform，簡稱簡稱IDFT)。比較比較

35、DFT和和IDFT的運(yùn)算公式：的運(yùn)算公式：10)(1)()(10 NnWkXNkXIDFTnxNknk10)()()(10 NkWnxnxDFTkXNnnkN1) 旋轉(zhuǎn)因子：旋轉(zhuǎn)因子：kNkNWW 2) 系數(shù)：系數(shù)：MNN21 ，第50頁/共61頁DITIFFT運(yùn)算流圖運(yùn)算流圖 WN0WN1WN2WN3WN0WN0N1x(0)x(4)x(2)x(6)x(4)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN2WN2N1N1N1N1N1N1N1第51頁/共61頁DITIFFT運(yùn)算流圖運(yùn)算流圖(防止溢出防止溢出) WN02121x(0)x(4)x(2)x(

36、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)212121WN121WN221WN3212121WN021WN2212121WN021WN22121WN02121WN0212121WN021WN021第52頁/共61頁 如果希望直接調(diào)用如果希望直接調(diào)用FFT子程序計(jì)算子程序計(jì)算IFFT，則可用下面的方法：則可用下面的方法：10101( )( )1( )( )NknNkNknNkx nX k WNx nXk WN對(duì)上式兩邊同時(shí)取共軛，得：對(duì)上式兩邊同時(shí)取共軛，得：1011( )( )( )NknNkx nX k WDFT X kNN第53頁/共61頁例例1、如果通用計(jì)算機(jī)的速度為平均每次復(fù)乘需要、如果通用計(jì)算機(jī)的速度為平均每次