離散傅里葉變換快速算法

離散傅里葉變換快速算法(FFT)快速傅里葉變換(FFT)問題的提出基2時(shí)間抽取FFT算法基2頻率抽取FFT算法IFFT算法的實(shí)際應(yīng)用掌握基2時(shí)間抽取FFT算法的基本思想和方法掌握基2頻率抽取FFT算法的基本思想和方法掌握實(shí)序列FFT計(jì)算，以及由N點(diǎn)序列FFT計(jì)算2N點(diǎn)序列FFT的方法掌握利用FFT計(jì)算IDFT的過程，以及IFFT實(shí)現(xiàn)的原理快速傅里葉變換(FFT)重點(diǎn)：基2時(shí)間/頻率抽取FFT算法的基本原理，F(xiàn)FT蝶形運(yùn)算流圖難點(diǎn)：由短序列的DFT表達(dá)相應(yīng)長(zhǎng)序列的DFT的基本原理及方法快速傅里葉變換(FFT)DFTIDFT乘法次數(shù)N加法次數(shù)N-1DFT

通常x[k]和WNkm都是復(fù)數(shù)，所以計(jì)算一個(gè)X[m]的值需要N次復(fù)數(shù)乘法運(yùn)算和N-1次復(fù)數(shù)加法運(yùn)算。所有的X[m]就要N2次復(fù)數(shù)乘法運(yùn)算，N(N-1)次復(fù)數(shù)加法運(yùn)算。當(dāng)N很大時(shí)，運(yùn)算量將是驚人的，如N=1024，則要完成1048576次(一百多萬(wàn)次)運(yùn)算。Cooley,JamesW.,andJohnW.Tukey,"AnalgorithmforthemachinecalculationofcomplexFourierseries,"Math.Comput.19,297–301(1965)1965年，庫(kù)利(cooley)和圖基(Tukey)首先在《機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法》文章中提出FFT算法。/view/d5628524192e45361066f549.htmlN/2點(diǎn)DFTN/2點(diǎn)DFTX1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]_X[0]X[4]X[1]X[5]X[2]X[6]X[3]X[7]+N/2點(diǎn)DFTN/2點(diǎn)DFTX1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]+X[0]X[4]X[1]X[5]X[2]X[6]X[3]X[7]+++----N/2點(diǎn)DFTN/2點(diǎn)DFTX[0]X[4]X[1]X[5]X[2]X[6]X[3]X[7]將DFT長(zhǎng)序列分解為短序列，降低運(yùn)算次數(shù)。復(fù)數(shù)乘法復(fù)數(shù)加法1個(gè)

點(diǎn)DFT

2個(gè)點(diǎn)DFT1個(gè)蝶形12N/2個(gè)蝶形N總計(jì)當(dāng)N很大時(shí)，運(yùn)算量減少了近一半N點(diǎn)有限長(zhǎng)序列的DFTN/2點(diǎn)有限長(zhǎng)序列的DFTx[1]x[2r+1]x[N-1]x[3]x[0]x[2r]x[N-2]x[2]x[0]x[1]x[2r]x[2r+1]x[N-2]x[N-1]x[2]x[3]x1[0]x1[1]x1[m]x1[N/2-1]x2[0]x2[1]x2[m]x2[N/2-1]旋轉(zhuǎn)因子的可約性m范圍如何求？旋轉(zhuǎn)因子的周期性旋轉(zhuǎn)因子的對(duì)稱性旋轉(zhuǎn)因子周期性可約性對(duì)稱性4點(diǎn)DFTx1[0]=x[0]x1[1]=x[2]x1[2]=x[4]x1[3]=x[6]4點(diǎn)DFTx2[0]=x[1]x2[1]=x[3]x2[2]=x[5]x2[3]=x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]-1X[0]X[4]W80-1X[1]X[5]W81-1X[2]X[6]W82-1X[3]X[7]W83-1X

[m]前半部分后半部分碟形運(yùn)算*X1[m]X2[m]x1[0]=x[0]x1[1]=x[2]x1[2]=x[4]x1[3]=x[6]x2[0]=x[1]x2[1]=x[3]x2[2]=x[5]x2[3]=x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]-1X[0]X[4]W80-1X[1]X[5]W81-1X[2]X[6]W82-1X[3]X[7]W83x11[0]=x[0]x11[1]=x[4]x12[0]=x[2]x12[1]=x[6]2點(diǎn)DFT2點(diǎn)DFTX11[0]X11[1]X12[0]X12[1]W40W41-1-1x21[0]=x[1]x21[1]=x[5]x22[0]=x[3]x22[1]=x[7]2點(diǎn)DFT2點(diǎn)DFTX21[0]X21[1]X22[0]X22[1]W40W41-1-18點(diǎn)基2時(shí)間抽取FFT算法流圖4點(diǎn)DFT4點(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]-1-1-1-18點(diǎn)基2時(shí)間抽取FFT算法流圖第一級(jí)第二級(jí)第三級(jí)

這種FFT算法,是在時(shí)間上對(duì)輸入序列的次序是屬于偶數(shù)還是屬于奇數(shù)來(lái)進(jìn)行分解的，所以稱作按時(shí)間抽取的算法(DIT，DecimationinTime)。

二、運(yùn)算量x[0]WN0X[0]WN0WN0WN2WN0WN0WN0WN2WN0WN1WN2WN3x[4]x[2]x[6]x[1]x[5]x[3]x[7]X[1]X[2]X[3]X[4]X[5]X[6]X[7]-1-1-1-1-1-1-1-1-1-1-1-1當(dāng)N=8=23時(shí)，由3級(jí)蝶形運(yùn)算組成；每級(jí)由4個(gè)蝶形運(yùn)算組成；共有12個(gè)蝶形運(yùn)算；每個(gè)蝶形運(yùn)算有1次復(fù)乘，2次復(fù)加；共有12次復(fù)乘，24次復(fù)加；當(dāng)N=2L時(shí)，共有L級(jí)蝶形，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：復(fù)數(shù)乘法次數(shù)與DFT比較：N點(diǎn)的FFT的運(yùn)算量：1024點(diǎn)來(lái)說，比值為204.8FFT算法特點(diǎn)第一級(jí)第二級(jí)第三級(jí)000001010011100101110111000100010110001101011111FFT算法特點(diǎn)級(jí)數(shù)

碟形運(yùn)算的數(shù)量:N/2第一級(jí)第二級(jí)第三級(jí)0000010100111001011101110001000101100011010111110

0

0

0

0

0

0

0自然順序二進(jìn)制k2k1k0倒位序二進(jìn)制k0k1k2倒位順序1

0

0

1

1

0

0

4

2

0

1

0

0

1

0

2

30

1

1

1

1

0

6

4

1

0

0

0

0

1

15

1

0

1

1

0

1

5

6

1

1

0

0

1

1

37

1

1

1

1

1

1

7倒位序規(guī)律由按時(shí)間抽選法FFT運(yùn)算流圖(書140頁(yè)圖3-6)可知，輸出X[m]按正常順序排列在存儲(chǔ)單元，而輸入x[k]是按順序:01010101以N=8為例，說明如下:k0=1(奇)k0=0(偶)k1=0k1=1k1=0k1=1k0k1k2x[000]0x[100]4x[010]2x[110]6x[001]1x[101]5x[011]3x[111]7序號(hào)kx[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]x[5]x[3]x[7]變址處理方法存儲(chǔ)單元自然順序變址倒位序A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)不必調(diào)換數(shù)值交換x[k]與x[]之間數(shù)值1.原位計(jì)算n表示第n級(jí)迭代，m，j表示數(shù)據(jù)所在的行數(shù)輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器Xn-1[m]Xn-1[j]第二級(jí)的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為2。第一級(jí)的蝶形系數(shù)均為，蝶形節(jié)點(diǎn)的距離為1。第三級(jí)的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為4。第M級(jí)的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為N/2。級(jí)數(shù)碟形運(yùn)算的數(shù)量序列倒序序列原位旋轉(zhuǎn)因子分布例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。(書上作業(yè)3-5)解：

根據(jù)基2時(shí)間抽取FFT算法原理，8點(diǎn)序列的DFTX[m]可由兩個(gè)4點(diǎn)序列的DFTX1[m]和X2[m]表達(dá)。如果按照序列x[k]序號(hào)的奇偶分解為x1[k]和

x2[k]，則存在

其中x1[k]={1,1,2,1}，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通過4點(diǎn)的FFT來(lái)計(jì)算。例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：

X1[m]={5,-1,1,-1},X2[m]={1,-2+3j,1,-2-3j}利用上述公式，可得序列x[k]的DFTX[m]為X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}快速傅里葉變換(FFT)基2時(shí)間抽取FFT算法與DFT的運(yùn)算量對(duì)比算法的特點(diǎn)在基-2FFT算法的流圖中，當(dāng)序列長(zhǎng)度N=32時(shí)，一共有_________級(jí)蝶形運(yùn)算，蝶形個(gè)數(shù)為________，共完成______次復(fù)數(shù)加法、_______次復(fù)數(shù)乘法。若直接完成DFT計(jì)算共需要_____次復(fù)數(shù)加法、______次復(fù)數(shù)乘法。若輸入序列按自然順序排列，序號(hào)為13的輸出序列號(hào)(倒位序)是_____________。畫出N=4基-2FFT時(shí)間抽取蝶形流程圖。42本節(jié)課內(nèi)容按頻率抽選的基-2FFT算法*FFT算法應(yīng)用433.2按頻率抽取(DIF)的基-2FFT算法

—桑德-圖基（Sand-Tukey）算法基2時(shí)間抽取FFT算法輸入序列x[k]按其順序的偶、奇數(shù)分解為越來(lái)越短的序列?；?頻率抽取(DIF)FFT算法輸出序列X[m](也是N點(diǎn)序列)按其順序的偶、奇來(lái)分解為越來(lái)越短的序列。44一、算法原理設(shè)序列點(diǎn)數(shù)N=2L，L為整數(shù)。將X[m]按m的奇偶分組前，先將輸入x[k]按k的順序分成前后兩半：4546

按m的奇偶將X[m]分成兩部分：x1[k]x2[k]47則X[2r]和X[2r+1]分別是x1[k]和x2[k]的N/2點(diǎn)DFT，記為X1[m]和X2[m]，碟形運(yùn)算為：令-1WNk48x1[0]x1[1]x1[2]x1[3]x2[0]x2[1]x2[2]x2[3]N/2點(diǎn)DFTN/2點(diǎn)DFTx[0]x[7]x[1]x[2]x[3])x[4]x[5]x[6]X1[0]=X[0]X1[1]=X[2]X1[2]=X[4]X1[3]=X[6]X2[0]=X[1]X2[1]=X[3]X2[2]=X[5]X2[3]=X[7]-1-1-1-13NW-12NW-11NW-10NW-1x[0]x[4]x[1]x[5]x[2]x[6]x[3]x[7]4點(diǎn)DFTX[0]X[6]X[2]X[4]4點(diǎn)DFTX[1]X[3]X[5]X[7]50N/2仍為偶數(shù)，進(jìn)一步分解：N/2

N/451x3[0]x4[0]x3[1]x4[1]N/4點(diǎn)DFTN/4點(diǎn)DFTx1[0]x1[1]x1[2]x1[3]X3[0]=X1[0]=X[0]X3[1]=X1[2]=X[4]X4[0]=X1[1]=X[2]X4[1]=X1[3]=X[6]-1-152同理：其中：X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2點(diǎn)DFT-1-12NW0NW-1-12點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-1已知有限長(zhǎng)序列x[k]

數(shù)值為

{1,2,-1,3}，請(qǐng)按頻率抽選的基-2FFT(快速傅里葉變換)運(yùn)算過程求X[m]，并畫出蝶形流程圖

解：56二、算法特點(diǎn)1.原位計(jì)算L級(jí)蝶形運(yùn)算，每級(jí)N/2個(gè)蝶形。2.蝶形運(yùn)算距離對(duì)N=2L點(diǎn)FFT，輸入自然序，輸出倒位序，兩節(jié)點(diǎn)距離：2L-n=N/2n例如N=23=8

：

(1)n=1時(shí)的距離為

8/2=4；

(2)n=2

時(shí)的距離為

8/4=2;

(3)n=3

時(shí)的距離為

8/8=1。0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-158二、算法特點(diǎn)3.運(yùn)算量級(jí)數(shù)：log2N每級(jí)的蝶形數(shù)：N/2每蝶形：復(fù)乘1次，復(fù)加2次總運(yùn)算量：

復(fù)乘(N*log2N)/2次

復(fù)加N*log2N次59(1)相同點(diǎn)

(a).進(jìn)行原位運(yùn)算；

(b).運(yùn)算量相同，均為(N/2)Log2N次復(fù)乘，NLog2N次復(fù)加。3.DIF法與DIT法的異同60(2)不同點(diǎn)

(a).DIT輸入為倒位序，輸出為自然順序；

DIF輸入為自然順序，輸出為倒位序；61(b).蝶形運(yùn)算不同DITDIF62(c)兩種蝶形運(yùn)算的關(guān)系

互為轉(zhuǎn)置(矩陣)；將算法流圖的所有支路方向都反向，交換輸入和輸出，即可得到另一種蝶形。

(DIT)1111(DIF)638點(diǎn)序列DIT8點(diǎn)序列DIFX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]648點(diǎn)序列DIT8點(diǎn)序列DIFX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]65FFT算法應(yīng)用

利用N點(diǎn)復(fù)序列的FFT，計(jì)算兩個(gè)N點(diǎn)實(shí)序列FFT

利用N點(diǎn)復(fù)序列的FFT，計(jì)算2N點(diǎn)序列的FFT

利用FFT計(jì)算IFFT利用N點(diǎn)復(fù)序列的FFT算法計(jì)算兩個(gè)N點(diǎn)實(shí)序列FFT2個(gè)N點(diǎn)實(shí)序列：x[k],h[k]y[k]=x[k]+jh[k]目的：通過一次FFT求出X[m],H[m]構(gòu)成復(fù)序列y*[k]=x[k]–jh[k]利用N點(diǎn)復(fù)序列的FFT算法計(jì)算兩個(gè)N點(diǎn)實(shí)序列FFT2個(gè)N點(diǎn)實(shí)序列：x[k],h[k]目的：通過一次FFT求出X[m],H[m]利用N點(diǎn)復(fù)序列的FFT算法計(jì)算兩個(gè)N點(diǎn)實(shí)序列FFT2個(gè)N點(diǎn)實(shí)序列：x[k],h[k]目的：通過一次FFT求出X[m],H[m]利用N點(diǎn)復(fù)序列的FFT

計(jì)算2N點(diǎn)序列的FFT69y[k]是一個(gè)長(zhǎng)度為2N的序列例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：

根據(jù)基2時(shí)間抽取FFT算法原理，8點(diǎn)序列的DFTX[m]可由兩個(gè)4點(diǎn)序列的DFTX1[m]和X2[m]表達(dá)。如果按照序列x[k]序號(hào)的奇偶分解為x1[k]和

x2[k]，則存在

其中x1[k]={1,1,2,1}x2[k]={-1,-1,1,2}

71例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。如何求X1[m]和X2[m]可通過一次的y[m]的DFT來(lái)計(jì)算。y[m]=x1[k]+jx2[k]={1-j,1-j,2+j,1+2j}x1[k]={1,1,2,1}x2[k]={-1,-1,1,2}

72Y*[(-m)4]={5-j,2+2j,1+j,-4+2j}Y[m]={5+j,-4-2j,1-j,2-2j}例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。73例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}74利用FFT實(shí)現(xiàn)IFFT75IDFT的快速計(jì)算方法1.稍微變動(dòng)FFT程序和參數(shù)可實(shí)現(xiàn)IFFT76DIF