快速付里葉變換FFTFastFourietTransform.ppt

第三章 快速付里葉變換(FFT) Fast Fouriet Transformer,第一節(jié) 引 言,一、快速付里葉變換FFT,有 限 長(zhǎng) 序 列 通 過 離 散 傅 里 葉 變 換 (D F T) 將 其 頻 域 離 散 化 成 有 限 長(zhǎng) 序 列 . 但 其 計(jì)算 量 太 大, 很 難 實(shí) 時(shí) 地 處 理 問 題 , 因 此 引 出 了 快 速 傅 里 葉 變 換(FFT) . FFT 并 不 是 一 種 新 的 變 換 形 式 ,它 只 是 DFT 的 一 種 快 速 算 法 . 并 且 根 據(jù) 對(duì) 序 列 分 解 與 選 取 方 法 的 不 同 而 產(chǎn) 生 了 FFT 的 多 種 算 法 . FFT 在 離 散 傅 里 葉 反 變 換 、 線 性 卷 積 和 線 性 相 關(guān) 等 方 面 也 有 重 要 應(yīng) 用.。,二、FFT產(chǎn)生故事,當(dāng)時(shí)加文(Garwin)在自已的研究中極需要一個(gè)計(jì)算付里葉變換的快速方法。他注意到圖基(J.W.Turkey)正在寫有關(guān)付里葉變換的文章，因此詳細(xì)詢問了圖基關(guān)于計(jì)算付里葉變換的技術(shù)知識(shí)。圖基概括地對(duì)加文介紹了一種方法，它實(shí)質(zhì)上就是后來的著名的庫(kù)利(Cooley J.W)圖基算法。在加文的迫切要求下，庫(kù)利很快設(shè)計(jì)出一個(gè)計(jì)算機(jī)程序。1965年庫(kù)利-圖基在、Mathematic of Computation 雜志上發(fā)表了著名的“機(jī)器計(jì)算付里級(jí)數(shù)的一種算法”文章，提出一種快速計(jì)算DFT的方法和計(jì)算機(jī)程序-揭開了FFT發(fā)展史上的第一頁(yè)，促使FFT算法產(chǎn)生原因還有1967年至1968年間FFT的數(shù)字硬件制成，電子數(shù)字計(jì)算機(jī)的條件， 使DFT的運(yùn)算大簡(jiǎn)化了。,三、本章主要內(nèi)容,1.直接計(jì)算DFT算法存在的問題及改進(jìn)途徑。 2.多種DFT算法(時(shí)間抽取算法DIT算法，頻率抽取算法DIF算法，線性調(diào)頻Z變換即CZT法) 3.FFT的應(yīng)用,第二節(jié) 直接計(jì)算DFT算法存在的問題及改進(jìn)途徑,一、直接計(jì)算DFT計(jì)算量,問題提出： 設(shè)有限長(zhǎng)序列x(n),非零值長(zhǎng)度為N,計(jì)算對(duì)x(n)進(jìn)行一次DFT運(yùn)算，共需多大的運(yùn)算工作量?,1.比較DFT與IDFT之間的運(yùn)算量,其中x(n)為復(fù)數(shù)， 也為復(fù)數(shù) 所以DFT與IDFT二者計(jì)算量相同。,2.以DFT為例，計(jì)算DFT復(fù)數(shù)運(yùn)算量,計(jì)算一個(gè)X(k)(一個(gè)頻率成分)值，運(yùn)算量為 例k=1則 要進(jìn)行N次復(fù)數(shù)乘法+(N-1)次復(fù)數(shù)加法 所以，要完成整個(gè)DFT運(yùn)算，其計(jì)算量為： N*N次復(fù)數(shù)相乘+N*(N-1)次復(fù)數(shù)加法,3.一次復(fù)數(shù)乘法換算成實(shí)數(shù)運(yùn)算量,復(fù)數(shù)運(yùn)算要比加法運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間長(zhǎng)。 一個(gè)復(fù)數(shù)乘法包括4個(gè)實(shí)數(shù)乘法和2個(gè)實(shí)數(shù)加法。 (a+jb)(c+jd)=(ac-bd)+j(bc+ad),4次復(fù)數(shù)乘法,2次實(shí)數(shù)加法,4.計(jì)算DFT需要的實(shí)數(shù)運(yùn)算量,每運(yùn)算一個(gè)X(k)的值，需要進(jìn)行 4N次實(shí)數(shù)相乘和 2N+2(N-1)=2(2N-1)次實(shí)數(shù)相加. 整個(gè)DFT運(yùn)算量為：4N2次實(shí)數(shù)相乘和2N(2N-1)次實(shí)數(shù)相加. 由此看出：直接計(jì)算DFT時(shí)，乘法次數(shù)與加法次數(shù)都是和N2成比例的。當(dāng)N很大時(shí)，所需工作量非?？捎^。,例子,例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要： N2=(1024)2=1048576次，即一百多萬次的復(fù)乘運(yùn)算這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理(如雷達(dá)信號(hào)處理)來講，它對(duì)計(jì)算速度有十分苛刻的要求迫切需要改進(jìn)DFT的計(jì)算方法，以減少總的運(yùn)算次數(shù)。 例2：石油勘探，24道記錄，每道波形記錄長(zhǎng)度5秒，若每秒抽樣500點(diǎn)/秒， 每道總抽樣點(diǎn)數(shù)=500*5=2500點(diǎn) 24道總抽樣點(diǎn)數(shù)=24*2500=6萬點(diǎn) DFT運(yùn)算時(shí)間=N2=(60000)2=36*108次,二、改善DFT運(yùn)算效率的基本途徑,利用DFT運(yùn)算系數(shù) 的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率。 1.合并法：合并DFT運(yùn)算中的某些項(xiàng)。 2.分解法：將長(zhǎng)序列DFT利用對(duì)稱性和周期性，分解為短序列DFT。,利用DFT運(yùn)算系數(shù) 的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率,的對(duì)稱性：,的周期性：,因?yàn)椋?由此可得出：,例子,例:,利用以上特性,得到改進(jìn)DFT直接算法的方法.,(1) 合并法：步驟1分解成虛實(shí)部,合并DFT運(yùn)算中的有些項(xiàng) 對(duì)虛實(shí)部而言 所以帶入DFT中：,(1) 合并法：步驟2代入DFT中,展開：,(1) 合并法：步驟3合并有些項(xiàng),根據(jù)：,有：,(1) 合并法：步驟4結(jié)論,由此找出其它各項(xiàng)的類似歸并方法：乘法次數(shù)可以減少一半。 例：,2、將長(zhǎng)序列DFT利用對(duì)稱性和周期性分解為短序列DFT-思路,因?yàn)镈FT的運(yùn)算量與N2成正比的 如果一個(gè)大點(diǎn)數(shù)N的DFT能分解為若干小點(diǎn)數(shù)DFT的組合，則顯然可以達(dá)到減少運(yùn)算工作量的效果。,2、將長(zhǎng)序更DFT利用對(duì)稱性和周期性分解為短序列DFT-方法,把N點(diǎn)數(shù)據(jù)分成二半：,其運(yùn)算量為：,再分二半：,+,=,+,+,+,=,這樣一直分下去，剩下兩點(diǎn)的變換。,2、將長(zhǎng)序更DFT利用對(duì)稱性和周期性分解為短序列DFT-結(jié)論,快速付里時(shí)變換(FFT)就是在此特性基礎(chǔ)上發(fā)展起來的，并產(chǎn)生了多種FFT算法，其基本上可分成兩大類： 按抽取方法分： 時(shí)間抽取法(DIT);頻率抽取法(DIF) 按“基數(shù)”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法 其它方法：線性調(diào)頻Z變換(CZT法),第三節(jié) 基-2按時(shí)間抽取的FFT算法Decimation-in-Time(DIT) (Coolkey-Tukey),一、算法原理,設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列按時(shí)間順序的奇偶分解為越來越短的子序列，稱為基2按時(shí)間抽取的FFT算法。也稱為Coolkey-Tukey算法。 其中基數(shù)2-N=2M，M為整數(shù).若不滿足這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)長(zhǎng)）使其達(dá)到 N=2M,例子,設(shè)一序列x(n)的長(zhǎng)度為L(zhǎng)=9,應(yīng)加零補(bǔ)長(zhǎng)為 N=24=16 應(yīng)補(bǔ)7個(gè)零值。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n,x(n),二、算法步驟 1.分組，變量置換,DFT變換：,先將x(n)按n的奇偶分為兩 組，作變量置換: 當(dāng)n=偶數(shù)時(shí)，令n=2r; 當(dāng)n=奇數(shù)時(shí)，令n=2r+1; 得到：x(2r)=x1(r); x(2r+1)=x2(r);r=0N/2-1; 則其DFT可化為兩部分： 前半部分： 后半部分：,2.代入DFT中,生成兩個(gè)子序列,x(0),x(2)x(2r)奇數(shù)點(diǎn) x(1),x(3)x(2r+1)偶數(shù)點(diǎn),代入DFT變換式：,3.求出子序列的DFT,上式得：,4.結(jié)論1,一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：,再應(yīng)用W系數(shù)的周期性，求出用X1(k),X2(k)表達(dá)的后半部的X(k+N/2)的值。,5.求出后半部的表示式,看出：后半部的k值所對(duì)應(yīng)的X1(k),X2(k)則完全重復(fù)了前半部分的k值所對(duì)應(yīng)的X1(k),X2(k)的值。,6.結(jié)論2,頻域中的N個(gè)點(diǎn)頻率成分為：,結(jié)論：只要求出（0N/2-1）區(qū)間內(nèi)的各個(gè)整數(shù)k值所對(duì)應(yīng)的X1(k),X2(k)值，即可以求出(0N-1)整個(gè)區(qū)間內(nèi)全部X(k)值，這就是FFT能大量節(jié)省計(jì)算的關(guān)鍵。,7.結(jié)論3,由于N=2L，因此N/2仍為偶數(shù)，可以依照上面方法進(jìn)一步把每個(gè)N/2點(diǎn)子序列，再按輸入n的奇偶分解為兩個(gè)N/4點(diǎn)的子序列，按這種方法不斷劃分下去，直到最后剩下的是2點(diǎn)DFT，兩點(diǎn)DFT實(shí)際上只是加減運(yùn)算。,三、蝶形結(jié),即蝶式計(jì)算結(jié)構(gòu)也即為蝶式信號(hào)流圖 上面頻域中前/后半部分表示式可以用蝶形信號(hào)流圖表示。,X1(k),X2(k),作圖要素： (1)左邊兩路為輸入 (2)右邊兩路為輸出 (3)中間以一個(gè)小圓表示加、減運(yùn)算（右上路為相加輸出、右下路為相減輸出),(4)如果在某一支路上信號(hào)需要進(jìn)行相乘運(yùn)算，則在該支路上標(biāo)以箭頭，將相乘的系數(shù)標(biāo)在箭頭旁。,(5)當(dāng)支路上沒有箭頭及系數(shù)時(shí)，則該支路的傳輸比為1。,例子：求 N=23=8點(diǎn)FFT變換 （1）先按N=8N/2=4，做4點(diǎn)的DFT：,先將N=8DFT分解成2個(gè)4點(diǎn)DFT： 可知：時(shí)域上：x(0),x(2),x(4),x(6)為偶子序列 x(1),x(3),x(5),x(7)為奇子序列 頻域上：X(0)X(3)，由X(k)給出 X(4)X(7),由X(k+N/2)給出,(a)比較N=8點(diǎn)直接DFT與分解2個(gè)4點(diǎn)DFT的FFT運(yùn)算量,N=8點(diǎn)的直接DFT的計(jì)算量為：N2次(64次）復(fù)數(shù)相乘,N(N-1)次(8(8-1)=56次)復(fù)數(shù)相加.共計(jì)120次。,（b)求 一個(gè)蝶形結(jié)需要的運(yùn)算量,要運(yùn)算一個(gè)蝶形結(jié)，需要一次乘法 ， 兩次加法。,（c）分解為兩個(gè)N/2=4點(diǎn)的DFT的運(yùn)算量,分解2個(gè)N/2點(diǎn)（4點(diǎn)）的DFT：,偶數(shù) 其復(fù)數(shù)相乘為 復(fù)數(shù)相加為,奇數(shù) 其復(fù)數(shù)相乘為 復(fù)數(shù)相加為,(d)用2個(gè)4點(diǎn)來求N=8點(diǎn)的FFT所需的運(yùn)算量,再將N/2點(diǎn)（4點(diǎn)）合成N點(diǎn)(8點(diǎn))DFT時(shí)，需要進(jìn)行N/2個(gè)蝶形運(yùn)算,還需N/2次（4次）乘法 及 次(8次）加法運(yùn)算。,(e)將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖,4點(diǎn) DFT,x(0) x(2) x(4) x(6),4點(diǎn) DFT,x(1) x(3) x(5) x(7),X(0) X(1) X(2) X(3),X(4) X(5) X(6) X(7),X1(0),X1(1),X1(2),X1(3),X2(0),X2(1),X2(2),X2(3),偶數(shù)序列,奇數(shù)序列,X(4)X(7) 同學(xué)們自已寫,x1(r),x2(r),(2)N/2(4點(diǎn))N/4(2點(diǎn))FFT (a)先將4點(diǎn)分解成2點(diǎn)的DFT：,因?yàn)?點(diǎn)DFT還是比較麻煩，所以再繼續(xù)分解。 若將N/2(4點(diǎn))子序列按奇/偶分解成兩個(gè)N/4點(diǎn)（2點(diǎn)）子序列。即對(duì)將x1(r)和x2(r)分解成奇、偶兩個(gè)N/4點(diǎn)（2點(diǎn)）點(diǎn)的子序列。,(b)求2點(diǎn)的DFT,（c)一個(gè)2點(diǎn)的DFT蝶形流圖,2點(diǎn)DFT,2點(diǎn)DFT,x(0) x(4),x(2) x(6),X3(0),X3(1),X4(0),X4(1),X1(0) X1(1),X1(2) X1(3),（d)另一個(gè)2點(diǎn)的DFT蝶形流圖,2點(diǎn)DFT,2點(diǎn)DFT,x(1) x(5),x(3) x(7),X5(0),X5(1),X6(0),X6(1),X2(0) X2(1),X2(2) X2(3),同理：,(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT (a)求2個(gè)一點(diǎn)的DFT,最后剩下兩點(diǎn)DFT,它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號(hào)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。,(b)2個(gè)1點(diǎn)的DFT蝶形流圖,1點(diǎn)DFT,x(0),1點(diǎn)DFT,x(4),X3(0) X3(1),進(jìn)一步簡(jiǎn)化為蝶形流圖：,X3(0) X3(1),x(0),x(4),(4)一個(gè)完整N=8的按時(shí)間抽取FFT的運(yùn)算流圖,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),m=0,m=1,m=2,四、FFT算法中一些概念 （1）“級(jí)”概念,將N 點(diǎn)DFT先分成兩個(gè)N/2點(diǎn)DFT，再是四個(gè)N/4點(diǎn)DFT直至N/2個(gè)兩點(diǎn)DFT.每分一次稱為“一”級(jí)運(yùn)算。 因?yàn)镹=2M所以N點(diǎn)DFT可分成M級(jí) 如上圖所示依次m=0,m=1.M-1共M級(jí),（2）“組”概念,每一級(jí)都有N/2個(gè)蝶形單元，例如：N=8,則每級(jí)都有4個(gè)蝶形單元。每一級(jí)的N/2個(gè)蝶形單元可以分成若干組，每一組具有相同的結(jié)構(gòu)，相同的 因子分布，第m級(jí)的組數(shù)為：,例：N=8=23，分3級(jí)。 m=0級(jí),分成四組,每組系數(shù)為 m=1級(jí),分成二組,每組系數(shù)為 m=2級(jí),分成一組,每組系數(shù)為,(3) 因子的分布,結(jié)論：每由后向前（m由M-10級(jí)）推進(jìn)一級(jí)，則此系數(shù)為后級(jí)系數(shù)中偶數(shù)序號(hào)的那一半。,（4）按時(shí)間抽取法,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,兩個(gè)2點(diǎn) DFT,兩個(gè)2點(diǎn) DFT,兩個(gè)2點(diǎn) DFT,兩個(gè)2點(diǎn) DFT,兩個(gè) 4點(diǎn)DFT,兩個(gè) 4點(diǎn)DFT,兩個(gè) N/2點(diǎn) DFT,X1(k),.,X2(k),X(k),由于每一步分解都是基于在每級(jí)按輸入時(shí)間序列的次序是屬于偶數(shù)還是奇數(shù)來分解為兩個(gè)更短的序列，所以稱為“按時(shí)間抽取法”.,x(n),五、按時(shí)間抽取的FFT算法與直接計(jì)算DFT運(yùn)算量的比較,由前面介紹的按時(shí)間抽取的FFT運(yùn)算流圖可見： 每級(jí)都由N/2個(gè)蝶形單元構(gòu)成，因此每一級(jí)運(yùn)算都需要N/2次復(fù)乘和N次復(fù)加（每個(gè)結(jié)加減各一次）。這樣（N=2M)M級(jí)運(yùn)算共需要： 復(fù)乘次數(shù)： 復(fù)加次數(shù)： 可以得出如下結(jié)論： 按時(shí)間抽取法所需的復(fù)乘數(shù)和復(fù)加數(shù)都是與 成正比。而直接計(jì)算DFT時(shí)所需的復(fù)乘數(shù)與復(fù)加數(shù)則都是與N2成正比.(復(fù)乘數(shù)md=N2,復(fù)加數(shù)ad=N(N-1)N2),例子,看N=8點(diǎn)和N=1024點(diǎn)時(shí)直接計(jì)算DFT與用基2-按時(shí)間抽取法FFT的運(yùn)算量。,看出：當(dāng)N較大時(shí)，按時(shí)間抽取法將比直接法快一、二個(gè)數(shù)量級(jí)之多。,作業(yè),1.N=16點(diǎn)的FFT基2-按時(shí)間抽取流程圖。 2.P252. 2，3，8,六、按時(shí)間抽取FFT算法的特點(diǎn),根據(jù)DIT基2-FFT算法原理，能得出任何N=2m點(diǎn)的FFT信號(hào)流圖，并進(jìn)而得出FFT計(jì)算程序流程圖。最后總結(jié)出按時(shí)間抽取法解過程的規(guī)律。 1.原位運(yùn)算（in-place) 2.碼位倒讀規(guī)則,1.原位運(yùn)算（in-place),原位運(yùn)算的結(jié)構(gòu)，可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。 定義：當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后，每一組運(yùn)算的結(jié)果，仍然存放在這同一組存儲(chǔ)器中直到最后輸出。,x(0),x(4),X3(0) X3(1),例子,例：N=8 FFT運(yùn)算,輸入:,x(0) x(4) x(2) x(6) x(1) x(5) x(3) 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),A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7),A(0)=x(0) A(1)=x(1) A(2)=x(2) A(3)=x(3) A(4)=x(4) A(5)=x(5) A(6)=x(6) A(7)=x(7),R1,R1,R1,R1,R1,R2,R1,R1,R2,R2,R3,R4,看出：用原位運(yùn)算結(jié)構(gòu)運(yùn)算后，A(0)A(7)正好順序存放X(0)X(7),可以直接順序輸出。,2.碼位倒讀規(guī)則,我們從輸入序列的序號(hào)及整序規(guī)律得到碼位倒讀規(guī)則。由N=8蝶形圖看出：原位計(jì)算時(shí)，F(xiàn)FT輸出的X(k)的次序正好是順序排列的，即X(0)X(7),但輸入x(n)都不能按自然順序存入到存儲(chǔ)單元中，而是按x(0),x(4),x(2), x(6).的順序存入存儲(chǔ)單元即為亂序輸入，順序輸出。這種順序看起來相當(dāng)雜亂，然而它是有規(guī)律的。即碼位倒讀規(guī)則。,例子,以N=8為例：,0 1 2 3 4 5 6 7,000 001 010 011 100 101 110 111,自然順序,二進(jìn)制碼表示,碼位倒讀,碼位倒置順序,000 100 010 110 001 101 011 111,0 4 2 6 1 5 3 7,看出：碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。,整序重排子程序,具體執(zhí)行時(shí)，只須將1與4對(duì)調(diào)送入，3與6對(duì)調(diào)送入，而0，2，5，7不變，僅需要一個(gè)中間存儲(chǔ)單元。,n 0 1 2 3 4 5 6 7,n 0 4 2 6 1 5 3 7,在實(shí)際運(yùn)算時(shí)，先按自然順序?qū)⑤斎胄蛄写嫒氪鎯?chǔ)單元，再通過變址運(yùn)算將自然順序變換成按時(shí)間抽取的FFT算法要求的順序。變址的過程可以用程序安排加以實(shí)現(xiàn)-稱為“整序”或“重排”（采用碼位倒讀）且注意： (1)當(dāng)n=n時(shí)，數(shù)據(jù)不必調(diào)換； (2)當(dāng)nn時(shí)，必須將原來存放數(shù)據(jù)x(n)送入暫存器R，再將x(n)送入x(n),R中