【學(xué)習(xí)課件】第4章快速付立葉變換(FFT)

1、第四章 FFT編輯ppt4-5線性卷積的FFT算法4-3 DIF的FFT算法4-4 IFFT算法4-2按時間抽取(DIT)的FFT算法4-1 引言目編輯ppt4-1引言一.DFT的計(jì)算工作量 兩者的差別僅在指數(shù)的符號和因子1/N. 編輯pptDFT與IDFT運(yùn)算特點(diǎn)復(fù)數(shù)乘法復(fù)數(shù)加法一個X(k)NN 1N個X(k)(N點(diǎn)DFT)N 2N (N 1)同理：IDFT運(yùn)算量與DFT相同。實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2一個X (k)4N2N+2 (N 1)=2 (2N 1)N個X (k)(N點(diǎn)DFT)4N 22N (2N 1)編輯ppt 通常x(n)和都是復(fù)數(shù),所以計(jì)算一個 X(k)的值需要N次

2、復(fù)數(shù)乘法運(yùn)算,和 次 復(fù)數(shù)加法運(yùn)算.那么,所有的X(k)就要N2次復(fù) 數(shù)乘法運(yùn)算,N(N-1)次復(fù)數(shù)加法運(yùn)算.當(dāng)N很 大時,運(yùn)算量將是驚人的,如N=1024,則要完 成1048576 次(一百多萬次)運(yùn)算.這樣,難以做到實(shí)時處理.一個X(k)的值的工作量,如X(1)編輯ppt二.改進(jìn)的途徑 1. 的對稱性和周期性得:對稱性:周期性:編輯ppt 利用上述特性,可以將有些項(xiàng)合并,并將DFT分解為短序列,從而降低運(yùn)算次數(shù),提高運(yùn)算速度.1965年,庫利(cooley)和圖基(Tukey)首先提出FFT算法.對于N點(diǎn)DFT,僅需(N/2)log2N 次復(fù)數(shù)乘法運(yùn)算.例如N=1024=210 時，需要(

3、1024/2)log2 210 =512*10=5120次。5120/1048576=4.88% ,速度提高20倍編輯pptFFT算法分類:時間抽選法DIT: Decimation-In-Time頻率抽選法DIF: Decimation-In-Frequency編輯ppt4-2 按時間抽取(DIT)的FFT算法 庫利-圖基算法一.算法原理(基2FFT)(一)N/2點(diǎn)DFT1.先將 按n的奇偶分為兩組作DFT,設(shè)N=2L ,不足時,可補(bǔ)些零。這樣有: n為偶數(shù)時: n為奇數(shù)時:因此，編輯ppt由于: 所以,上式可表示為:(n為偶數(shù)) (n為奇數(shù))編輯ppt 其中,2.兩點(diǎn)結(jié)論: (1) X (k

4、),X (k)均為N/2點(diǎn)的DFT。 (2) X(k)=X (k)+W X (k)只能確定出 X(k)的k= 個；即前一半的結(jié)果。1 21 2kN編輯ppt 同理, 這就是說,X1(k),X2(k)的后一半,分別 等于其前一半的值。3.X(k)的后一半的確定由于 （周期性）,所以:編輯ppt 可見,X(k)的后一半，也完全由X1(k), X2 (k)的前一半所確定。 *N點(diǎn)的DFT可由兩個N/2點(diǎn)的DFT來計(jì)算。又由于 ,所以編輯ppt實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算 前一半4.蝶形運(yùn)算 后一半（N/2個蝶形)(前一半)(后一半)1 1 11-1由X1(k)、X 2(k)表示X(k)的運(yùn)算是一種

5、特殊的運(yùn)算-碟形運(yùn)算編輯ppt5.分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個N/2點(diǎn)DFT(N/2)2N/2 (N/2 1)兩個N/2點(diǎn)DFTN2/2N (N/2 1)一個蝶形12N/2個蝶形N/2N總計(jì)運(yùn)算量減少了近一半編輯ppt 例如 N=8 時的DFT,可以分解為兩個 N/2=4點(diǎn)的DFT.具體方法如下: (1)n為偶數(shù)時,即 分別記作: 編輯ppt (2) n為奇數(shù)時,分別記作:編輯ppt x1(0)=x(0) x1(1)=x(2) N/2點(diǎn) x1(2)=x(4) DFT x1(3)=x(6) x2(0)=x(1) x2(1)=x(3) N/2點(diǎn) x2(2)=x(5) DFT x2(3)=x

6、(7) 1 2 X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)對X (k)和X (k)進(jìn)行蝶形運(yùn)算,前半部為 X(0) X(3),后半部分為X(4) X(7) 整個過程如下圖所示:編輯ppt 由于N=2 L ,所以 N/2仍為偶數(shù),可以進(jìn) 一步把每個N/2點(diǎn)的序列再按其奇偶部分 分解為兩個N/4的子序列。例如，n為偶數(shù)時的 N/2點(diǎn)分解為:(二) N/4點(diǎn)DFT進(jìn)行N/4點(diǎn)的DFT,得到(偶中偶)(偶中奇)編輯ppt從而可得到前N/4的X1(k)后N/

7、4的X1(k)為注意到編輯ppt(奇中偶)(奇中奇)同樣對n為奇數(shù)時，N/2點(diǎn)分為兩個N/4點(diǎn) 的序列進(jìn)行DFT，則有:編輯ppt 例如,N=8時的DFT可分解為四個N/4的DFT, 具體步驟如下:(1) 將原序列x(n)的“偶中偶”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X3(0), X3(1)。編輯ppt(2) 將原序列x(n)的“偶中奇”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X4(0), X4(1)。(3) 將原序列x(n)的“奇中偶”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X5(0), X5(1)。編輯ppt(4) 將原序列x(n)的“奇中奇”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X6(0), X6(1)

8、。（5）由 X3(0), X3(1), X4(0), X4(1)進(jìn)行碟形運(yùn)算, 得到X1(0), X1(1), X1(2), X1(3)。（6）由 X5(0), X5(1), X6(0), X6(1)進(jìn)行碟形運(yùn)算, 得到X2(0), X2(1), X2(2), X2(3)。編輯ppt (0)= (0)= (0) N/4 (1)= (2)= (4) DFT (0)= (1)= (2) N/4 (1)= (3)= (6) DFT (0)= (0)= (1) N/4 (1)= (2)= (5) DFT (0)= (1)= (3) N/4 (1)= (3)= (7) DFT3 13 14 14 15

9、25 26 26 2 02NN02NNWWWW0123NNNN-1-1-1-2-1-1WWWWX (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566X (0)X (1)X (2)X (3)X (0)X (1)X (2)X (3)11122221X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（7）由X1(0), X1(1), X1(2), X1(3)，X2(0), X2(1),X2(2), X2(3)進(jìn)行碟形運(yùn)算, 得到 X(0), X(1), X(2), X(3) X(4), X(5), X(6), X(7) 。編輯ppt 這樣,又一

10、次分解,得到四個N/4點(diǎn)DFT, 兩級蝶形運(yùn)算,其運(yùn)算量有大約減少一半 即為N點(diǎn)DFT的1/4。 對于N=8時DFT,N/4點(diǎn)即為兩點(diǎn)DFT,因此 編輯ppt 亦即, 編輯ppt (0) (4) (2) (6) (1) (5) (3) (7)WN0WN0WN0W0N-1-1-1-1X (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566WN0WN2WN0WN2-1-1-1-1X (0)X (1)X (2)X (3)X (0)X (1)X (2)X (3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5

11、)X(6)X(7)因此,8點(diǎn)DFT的FFT的運(yùn)算流圖如下編輯ppt 這種FFT算法,是在時間上對輸入序列 的次序是屬于偶數(shù)還是屬于奇數(shù)來進(jìn)行分 解的,所以稱作按時間抽取的算法 。(DIT)編輯ppt（三）FFT運(yùn)算量與運(yùn)算特點(diǎn) 1 N=2L時，共有L=log2N級運(yùn)算；每一級有N/2個蝶形結(jié)。2每一級有N個數(shù)據(jù)中間數(shù)據(jù)），且每級只用到本級的轉(zhuǎn)入中間數(shù)據(jù)，適合于迭代運(yùn)算。3計(jì)算量： 每級N/2次復(fù)乘法，N次復(fù)加。（每蝶形只乘一次，加減各一次）。共有L*N/2=N/2log2N 次復(fù)乘法；復(fù)加法L*N=Nlog2N 次。與直接DFT定義式運(yùn)算量相比(倍數(shù)) N2/(Nlog2N) 。當(dāng) N大時，此

12、倍數(shù)很大。編輯ppt比較DFT 參考P150 表4-1 圖4-6可以直觀看出，當(dāng)點(diǎn)數(shù)N越大時，F(xiàn)FT的優(yōu)點(diǎn)更突出。編輯ppt (0)=X0(0) X1(0) X2(0) X3(0)=X(0) (4)=X0(1) X1(1) X2(1) X3(1)=X(1) (2)=X0(2) X3(2)=X(2) (6)=X0(3) X3(3)=X(3) (1)=X0(4) X1(4) X2(4) X3(4)=X(4) (5)=X0(5) X3(5)=X(5) (3)=X0(6) X3(6)=X(6) (7)=X0(7) X1(7) X2(7) X3(7)=X(7)WWWWN0N0N0N0-1-1-1-1WW

13、WWN0N2N0N2-1-1-1-1WWWWNNNN0123.三.DIT的FFT算法的特點(diǎn) 1.原位運(yùn)算輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲器。編輯ppt 設(shè)用m(m=1,2, ,L)表示第m列;用k,j表示蝶形輸入數(shù)據(jù)所在的（上/下）行數(shù)(0,1,2, ,N-1);這時任何一個蝶形運(yùn)算可用下面通用式表示，即 由運(yùn)算流圖可知,一共有N個輸入/出行,一共有l(wèi)og2 N=L列（級）蝶形運(yùn)算(基本迭代運(yùn)算). 1 1 11-1編輯ppt 所以,當(dāng)m=1時,則有（前兩個蝶形） 編輯ppt 當(dāng)m=2時,則有（前兩個蝶形） 當(dāng)m=3時,則有（前兩個蝶形） 編輯ppt 可見,在某列進(jìn)行蝶形運(yùn)算的任意

14、兩個節(jié)點(diǎn)(行)k和j的節(jié)點(diǎn)變量 就完全可以確定蝶形運(yùn)算的結(jié)果 ,與其它行(節(jié)點(diǎn))無關(guān)。 這樣,蝶形運(yùn)算的兩個輸出值仍可放回蝶形運(yùn)算的兩個輸入所在的存儲器中,即實(shí)現(xiàn)所謂原位運(yùn)算。每一組(列)有N/2個蝶形運(yùn)算,所以只需N個存儲單元，可以節(jié) 省存儲單元。編輯ppt 2 倒位序規(guī)律 由圖可知,輸出X(k)按正常順序排列在存儲單元,而輸入是按順序: 這種順序稱作倒位序,即二進(jìn)制數(shù)倒位。編輯pptn =00n =10n =01n =11n =01n =1101010101 (n2)x(000) 0 x(100) 4 x(010) 2 x(110) 6 x(001) 1x(101) 5 x(011) 3

15、x(111) 7 （偶）（奇） 這是由奇偶分組造成的,以N=8為例 說明如下:編輯ppt 3.倒位序?qū)崿F(xiàn) 輸入序列先按自然順序存入存儲單 元,然后經(jīng)變址運(yùn)算來實(shí)現(xiàn)倒位序排列 設(shè)輸入序列的序號為n,二進(jìn)制為 (n2 n1 n0 )2 ,倒位序順序用 表示,其倒位序二進(jìn)制為(n0 n1 n2 )2 ,例如 ，N=8時如下表： 編輯ppt 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 自然順序

16、n 二進(jìn)制n n n 倒位序二進(jìn)制n n n 倒位順序n2 1 0 0 1 2編輯ppt編輯pptA(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8)x(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)變址處理方法存儲單元自然順序變址倒位序4.蝶形運(yùn)算兩節(jié)點(diǎn)的距離:2m-1 其中,m表示第m列,且m =1, ,L 例如N=8=23 ,第一級(列)距離為21-1=1, 第二級(列)距離為22-1=2， 第三級(列)距離為23-1=4。編輯ppt (0) (4) (2)

17、 (6) (1) (5) (3) (7)WN0WN0WN0W0N-1-1-1-1X (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566WN0WN2WN0WN2-1-1-1-1X (0)X (1)X (2)X (3)X (0)X (1)X (2)X (3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)結(jié)點(diǎn)距離為1節(jié)（結(jié)）點(diǎn)距離為2編輯ppt5.WNr 的確定(僅給出方法) 考慮蝶形運(yùn)算兩節(jié)點(diǎn)的距離為2m-1 ,蝶 形運(yùn)算可表為 Xm(k)=Xm-1(k)+Xm-1(k+2m-1)W

18、Nr Xm(k+2m-1)=Xm-1(k)-Xm-1(k+2m-1)WNr 由于N為已知,所以將r的值確定即可。r的求解方法：（1）將上式的第一個節(jié)點(diǎn)標(biāo)號值k表示為L位二進(jìn)制數(shù)，注意：（2）把此二進(jìn)制數(shù)乘上 ，即左移L-m位，右邊空出位添0，此數(shù)即為所求r的二進(jìn)制數(shù)。（嚴(yán)格證明參考有關(guān)書籍）編輯ppt 例如 N=8=23 (1)k=2 , m=3 的r值,k=2=(010)2 左移L-m=3-3=0 , r=(010)2=2; (2)k=3 ,m=3 的r值; k= 3=(011)2,左移0位,r=3； (3)k=5 ,m=2的值; k=5=(101)2 左移L-m=1位 r=(010)2 =

19、2。 為此，令k=(n2n1n0)2 ,再將k= (n2n1n0)2 左移(L-m)位,右邊位置補(bǔ)零,就可得到(r)2 的值，即(r)2 =(k)22L-m 。 編輯ppt 6.存儲單元 存輸入序列 (n),n=0,1, ,N-1, 計(jì)N 個單元; 存放系數(shù) , r=0,1, ,N/2-1, 需N/2個存儲單元； 共計(jì)(N+N/2)個存儲單元。編輯ppt4-3 DIF的FFT算法(桑德圖基算法) 一.算法原理 1.N點(diǎn)DFT的另一種表達(dá)形式編輯ppt 由于 故 因此 X(k)可表為 編輯ppt 2.N點(diǎn)DFT按k的奇偶分組可分為兩個N/2的DFT 當(dāng)k為偶數(shù),即 k=2r時,(-1)k =1；

20、 當(dāng)k為奇數(shù),即 k=2r+1 時 (-1)k =-1 。 這時 X(k) 可分為兩部分： k為偶數(shù)時：編輯ppt 可見,上面兩式均為N/2的DFT。k為奇數(shù)時：編輯ppt-13.蝶形運(yùn)算編輯ppt-1-1-1-1WWWWNNNN01234.N=8時,按k的奇偶分解過程 先蝶形運(yùn)算，后DFT:編輯ppt 5.仿照DIT的方法 再將N/2點(diǎn)DFT按k的奇偶分解為兩個N/4點(diǎn)的DFT,如此進(jìn)行下去,直至分解為2點(diǎn)DFT。 編輯ppt (0) X(0) (1) X(4) (2) X(2) (3) X(6) (4) X(1) (5) X(5) (6) X(3) (7) X(7)-1-1-1-1WWWW

21、NNNN0123-1-1-1-1WWWWNNNN0202-1-1-1-1WWWWNNNN0000例如 N=8時DIF的FFT流圖如下：編輯ppt 二.原位運(yùn)算 每級(列)都是由N/2個蝶形運(yùn)算構(gòu) 成,即 -1WNr編輯ppt三.蝶形運(yùn)算兩節(jié)點(diǎn)的距離 一般公式為2L-m =N/2m 例如 N=23 =8 ： (1)m=1 時的距離為 8/2=4； (2)m=2 時的距離為 8/4=2; (3)m=3 時的距離為 8/8=1。編輯pptr的求法： k=(n2 n1 n0 ) ,左移m-1位,右邊空出補(bǔ)零,得(r)2 ,亦即(r)2 =(k)2 2m-1 .例如,N=8:(1)m=1,k=2, k=

22、(010)2 左移0位,(r)2=(010)2=2;(2)m=2,k=1, k=(001)2 左移1位,(r)2=(010)2=2;(3)m=2,k=5, k=(101)2 左移1位,(r)2=(010)2=2 .四. 的計(jì)算 由于DIF蝶形運(yùn)算的兩節(jié)點(diǎn)的距離為 N/2m , 所以蝶形運(yùn)算可表為：編輯ppt 1.相同點(diǎn) (1)進(jìn)行原位運(yùn)算； (2)運(yùn)算量相同,均為（N/2) Log2N次復(fù)乘,N Log2N次復(fù)加。 2.不同點(diǎn) (1)DIT輸入為倒位序,輸出為自然順序； DIF正好與此相反。但DIT也有輸入為自然順序,輸出為倒位序的情況。五.DIF法與DIT法的異同編輯ppt(2)蝶形運(yùn)算不同a.(DIT)用矩陣表示=11編輯pptb.(DFT)用矩陣表示=11編輯