《快速傅里葉變換》PPT課件.ppt

《《快速傅里葉變換》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《快速傅里葉變換》PPT課件.ppt（58頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第4章 快速傅里葉變換,4.1 引言 4.2 直接計(jì)算DFT的問題及改進(jìn)的途徑 4.3 按時(shí)間抽?。―IT）的基2-FFT算法 4.4 按頻率抽?。―IF）的基2-FFT算法 4.5 離散傅里葉反變換（IDFT）的快速計(jì)算方法 4.10 線性卷積的FFT算法,4.1 引 言,快速傅里葉變換（FFT）并不是一種新的變換， 而是離散傅里葉變換（DFT）的一種快速算法。  由于有限長(zhǎng)序列在其頻域也可離散化為有限長(zhǎng)序列（DFT），因此離散傅里葉變換（DFT）在數(shù)字信號(hào)處理中是非常有用的。例如，在信號(hào)的頻譜分析、 系統(tǒng)的分析、 設(shè)計(jì)和實(shí)現(xiàn)中都會(huì)用到DFT的計(jì)算。 但是，在相當(dāng)長(zhǎng)的時(shí)間里， 由于DFT的計(jì)算量太大，即使采用計(jì)算機(jī)也很難對(duì)問題進(jìn)行實(shí)時(shí)處理，所以并沒有得到真正的運(yùn)用。 直到1965年首次發(fā)現(xiàn)了DFT運(yùn)算的一種快速算法以后，情況才發(fā)生了根本的變化。人們開始認(rèn)識(shí)到DFT運(yùn)算的一些內(nèi)在規(guī)律，從而很快地發(fā)展和完善了一套高速有效的運(yùn)算方法， 這就是現(xiàn)在人們普遍稱之為快速傅里葉變換（FFT）的算法。 FFT出現(xiàn)后使DFT的運(yùn)算大大簡(jiǎn)化，運(yùn)算時(shí)間一般可縮短一二個(gè)數(shù)量級(jí)之多，從而使DFT的運(yùn)算在實(shí)際中真正得到了廣泛的應(yīng)用。,,4.2 直接計(jì)算DFT的問題及改進(jìn)的途徑,一、直接計(jì)算DFT的運(yùn)算量 設(shè)x(n)為N點(diǎn)有限長(zhǎng)序列，其DFT為,k=0, 1, …, N-1,（4-1）,反變換（IDFT）為,n=0, 1, …, N-1,（4-2）,二者的差別只在于WN的指數(shù)符號(hào)不同，以及差一個(gè)常數(shù)乘因子1/N，所以IDFT與DFT具有相同的運(yùn)算工作量。 下面我們只討論DFT的運(yùn)算量。 一般來說，x(n)和WNnk都是復(fù)數(shù)，X(k)也是復(fù)數(shù)，因此每計(jì)算一個(gè)X(k)值，需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法。而X(k)一共有N個(gè)點(diǎn)（k從0取到N-1），所以完成整個(gè)DFT運(yùn)算總共需要N2次復(fù)數(shù)乘法及N(N-1)次復(fù)數(shù)加法。 在這些運(yùn)算中乘法運(yùn)算要比加法運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間也多一些。因?yàn)閺?fù)數(shù)運(yùn)算實(shí)際上是由實(shí)數(shù)運(yùn)算來完成的， 這時(shí)DFT運(yùn)算式可寫成,（4-3）,由此可見，一次復(fù)數(shù)乘法需用四次實(shí)數(shù)乘法和二次實(shí)數(shù)加法；一次復(fù)數(shù)加法需二次實(shí)數(shù)加法。 因而每運(yùn)算一個(gè)X(k)需4N次實(shí)數(shù)乘法和2N+2(N-1)=2(2N-1)次實(shí)數(shù)加法。 所以，整個(gè)DFT運(yùn)算總共需要4N2次實(shí)數(shù)乘法和2N(2N-1)次實(shí)數(shù)加法。,當(dāng)然，上述統(tǒng)計(jì)與實(shí)際需要的運(yùn)算次數(shù)稍有出入，因?yàn)槟承￤Nnk可能是1或j，就不必相乘了，例如W0N=1，W NＮ／２=-1， WNN/4=-j等就不需乘法。 但是為了便于和其他運(yùn)算方法作比較， 一般都不考慮這些特殊情況，而是把WNnk都看成復(fù)數(shù)，當(dāng)N很大時(shí)，這種特例的影響很小。 從上面的統(tǒng)計(jì)可以看到，直接計(jì)算DFT，乘法次數(shù)和加法次數(shù)都是和N2成正比的，當(dāng)N很大時(shí)，運(yùn)算量是很可觀的，有時(shí)是無法忍受的。,例3-1 根據(jù)式（3-1），對(duì)一幅NN點(diǎn)的二維圖像進(jìn)行DFT變換，如用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？ 解 直接計(jì)算DFT所需復(fù)乘次數(shù)為（N2)2≈1012次，因此用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，則需要近3000小時(shí)。 這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理來說，要么提高計(jì)算速度，而這樣，對(duì)計(jì)算速度的要求太高了。另外，只能通過改進(jìn)對(duì)DFT的計(jì)算方法，以大大減少運(yùn)算次數(shù)。,二、 改善途徑 能否減少運(yùn)算量，從而縮短計(jì)算時(shí)間呢？仔細(xì)觀察DFT的運(yùn)算就可看出， 利用系數(shù)WＮnk的以下固有特性，就可減少運(yùn)算量：  （1） WNnk的共軛對(duì)稱性,（2） WNnk的周期性,（3） WNnk的可約性,另外,這樣，利用這些特性，使DFT運(yùn)算中有些項(xiàng)可以合并，并能使DFT分解為更少點(diǎn)數(shù)的DFT運(yùn)算。由于DFT的運(yùn)算量是與N2成正比的，所以N越小越有利，因而小點(diǎn)數(shù)序列的DFT比大點(diǎn)數(shù)序列的DFT的運(yùn)算量要小。  快速傅里葉變換算法正是基于這樣的基本思想而發(fā)展起來的。它的算法形式有很多種，但基本上可以分成兩大類： 按時(shí)間抽取(Ｄecimation inTime，縮寫為DIT)法 按頻率抽取(Decimationin Frequency，縮寫為DIF)法,,4.3 按時(shí)間抽取(DIT)的基-2 FFT算法 (庫(kù)利-圖基算法),一、 算法原理 設(shè)序列x(n)長(zhǎng)度為N，且滿足N=2L，L為正整數(shù)。按n的奇偶把x(n)分解為兩個(gè)N/2點(diǎn)的子序列：,（4-4）,則可將DFT化為,由于 ， 則上式可表示成,（4-5）,式中，X1(k)與X2(k)分別是x1(r)及x2(r)的N/2點(diǎn)DFT：,（4-6）,（4-7）,X1(k)，X2(k)只有N/2個(gè)點(diǎn)，即k=0, 1, …, N/2-1。 而X(k)卻有N個(gè)點(diǎn)，即k=0, 1, …, N-1， 故用式（4-5）計(jì)算得到的只是X(k)的前一半（ ）的結(jié)果。,所以,（4-8）,同理可得,（4-9）,式（4-8）、式（4-9）說明了后半部分k值（N/2≤k≤N-1）所對(duì)應(yīng)的X1(k),Ｘ2(k)分別等于前半部分k值（0≤k≤N/2-1）所對(duì)應(yīng)的X1(k), X2(k)。,（周期性）,由于,再考慮到WkN 的以下性質(zhì):,這樣，把式（4-8）、式（4-9）、式（4-10）代入式（4-5），就可將X(k)表達(dá)為前后兩部分：,（4-10）,（4-11）,（4-12）,圖 4-1 時(shí)間抽選法蝶形運(yùn)算流圖符號(hào),.蝶形運(yùn)算,圖 4-2 按時(shí)間抽選將一個(gè)N點(diǎn)DFT分解 為兩個(gè)N/2點(diǎn)DFT（N=8）,(1)N/2點(diǎn)的DFT運(yùn)算量: 復(fù)乘次數(shù): 復(fù)加次數(shù): (2)兩個(gè)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù): 復(fù)加次數(shù): (3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù): 復(fù)加次數(shù):,運(yùn)算量,,復(fù)乘:,復(fù)加:,總共運(yùn)算量:,*N點(diǎn)DFT的復(fù)乘為N2 ;復(fù)加N(N-1);與分解后相比可知,計(jì)算工作點(diǎn)差不多減少 一半。,由于N=2L，因而N/2仍是偶數(shù)，可以進(jìn)一步把每個(gè)N/2點(diǎn)子序列再按其奇偶部分分解為兩個(gè)N/4點(diǎn)的子序列。,（4-13）,例如，n為偶數(shù)時(shí)的 N/2點(diǎn)分解為:,且,式中：,（4-14）,（4-15）,圖4-3給出N=8時(shí)，將一個(gè)N/2點(diǎn)DFT分解成兩個(gè)N/4點(diǎn)DFT， 由這兩個(gè)N/4點(diǎn)DFT組合成一個(gè)N/2點(diǎn)DFT的流圖。,圖 4-3 N/2點(diǎn)DFT分解為兩個(gè)N/4點(diǎn)DFT,X2(k)也可進(jìn)行同樣的分解：,式中：,同樣對(duì)n為奇數(shù)時(shí)，N/2點(diǎn)分為兩個(gè)N/4點(diǎn) 的序列進(jìn)行DFT,圖 4-4 一個(gè)N=8點(diǎn)DFT分解為四個(gè)N/4點(diǎn)DFT,根據(jù)上面同樣的分析知道，利用四個(gè)N/4點(diǎn)的DFT及兩級(jí)蝶形組合運(yùn)算來計(jì)算N點(diǎn)DFT，比只用一次分解蝶形組合方式的計(jì)算量又減少了大約一半。,對(duì)于N=8時(shí)的DFT, N/4點(diǎn)即為兩點(diǎn)DFT,因此,式中， , 故上式不需要乘法。,可得：,這種方法的每一步分解，都是按輸入序列在時(shí)間上的次序是屬于偶數(shù)還是屬于奇數(shù)來分解為兩個(gè)更短的子序列，所以稱為“按時(shí)間抽取法”。,圖 4-5 N=8 按時(shí)間抽取的FFT運(yùn)算流圖,二、 運(yùn)算量 由按時(shí)間抽取法FFT的流圖可見，當(dāng)N=2L時(shí)，共有L級(jí)蝶形， 每級(jí)都由N/2個(gè)蝶形運(yùn)算組成，每個(gè)蝶形需要一次復(fù)乘、 二次復(fù)加，因而每級(jí)運(yùn)算都需N/2次復(fù)乘和N次復(fù)加，這樣L級(jí)運(yùn)算總共需要,由于計(jì)算機(jī)上乘法運(yùn)算所需的時(shí)間比加法運(yùn)算所需的時(shí)間多得多，故以乘法為例，直接DFT復(fù)數(shù)乘法次數(shù)是N2，F(xiàn)FT復(fù)數(shù)乘法次數(shù)是(N/2) log2N。 直接計(jì)算DFT與FFT算法的計(jì)算量之比為,當(dāng)N=2048時(shí)，這一比值為372.4，即直接計(jì)算DFT的運(yùn)算量是FFT運(yùn)算量的372.4倍。當(dāng)點(diǎn)數(shù)N越大時(shí)，F(xiàn)FT的優(yōu)點(diǎn)更為明顯(見書中P150.表4-1)。,（4-20）,三、按時(shí)間抽取的FFT算法的特點(diǎn),1. 原位運(yùn)算（同址運(yùn)算） 從圖4-5可以看出這種運(yùn)算是很有規(guī)律的，其每級(jí)（每列）計(jì)算都是由N/2 個(gè)蝶形運(yùn)算構(gòu)成的，每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算：,式中，m表示第m列迭代，k, j為數(shù)據(jù)所在行數(shù)。式（4-21）的蝶形運(yùn)算如圖4-7所示，由一次復(fù)乘和兩次復(fù)加（減）組成。,圖 4-7 按時(shí)間抽選的蝶形運(yùn)算結(jié)構(gòu),在某列進(jìn)行蝶形運(yùn)算的任意兩個(gè)節(jié)點(diǎn)(行)k和j的節(jié)點(diǎn)變量 就完全可以確定蝶形運(yùn)算的結(jié)果 ,與其它行(節(jié)點(diǎn))無關(guān)。 這樣,蝶形運(yùn)算的兩個(gè)輸出值仍可放回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中,即實(shí)現(xiàn)所謂原位運(yùn)算。每一組(列)有N/2個(gè)蝶形運(yùn)算,所以只需N個(gè)存儲(chǔ)單元，可以節(jié)省存儲(chǔ)單元。,由圖4-5的流圖看出，某一列的任何兩個(gè)節(jié)點(diǎn)k和j的節(jié)點(diǎn)變量進(jìn)行蝶形運(yùn)算后，得到結(jié)果為下一列k, j兩節(jié)點(diǎn)的節(jié)點(diǎn)變量，而和其他節(jié)點(diǎn)變量無關(guān)，因而可以采用原位運(yùn)算，即某一列的N個(gè)數(shù)據(jù)送到存儲(chǔ)器后，經(jīng)蝶形運(yùn)算，其結(jié)果為下一列數(shù)據(jù)，它們以蝶形為單位仍存儲(chǔ)在這同一組存儲(chǔ)器中，直到最后輸出，中間無需其他存儲(chǔ)器。也就是蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸入所在的存儲(chǔ)器中。每列的N/2 個(gè)蝶形運(yùn)算全部完成后，再開始下一列的蝶形運(yùn)算。這樣存儲(chǔ)器數(shù)據(jù)只需N個(gè)存儲(chǔ)單元。下一級(jí)的運(yùn)算仍采用這種原位方式，只不過進(jìn)入蝶形結(jié)的組合關(guān)系有所不同。 這種原位運(yùn)算結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。,2. 倒位序規(guī)律 FFT的輸出X(k)按正常順序排列在存儲(chǔ)單元中，即按X(0)，X(1)，…，X(7)的順序排列，但是這時(shí)輸入x(n)卻不是按自然順序存儲(chǔ)的，而是按x(0)，x(4)， …， x(7)的順序存入存儲(chǔ)單元，看起來好像是“混亂無序”的，實(shí)際上是有規(guī)律的，我們稱之為倒位序。,這是由奇偶分組造成的,以N=8為例 說明如下:,造成倒位序的原因是輸入x(n)按標(biāo)號(hào)n的偶奇的不斷分組。 如果n用二進(jìn)制數(shù)表示為(n2n1n0)2（當(dāng)N=8=23時(shí)，二進(jìn)制為三位）， 第一次分組，由圖4-2看出，n為偶數(shù)（相當(dāng)于n的二進(jìn)制數(shù)的最低位n0=0）在上半部分，n為奇數(shù)（相當(dāng)于n的二進(jìn)制數(shù)的最低位 n0=1）在下半部分。 下一次則根據(jù)次最低位n1為“0”或是“1”來分偶奇（而不管原來的子序列是偶序列還是奇序列）， 如此繼續(xù)分下去，直到最后N個(gè)長(zhǎng)度為1的子序列。 圖4-8的樹狀圖描述了這種分成偶數(shù)子序列和奇數(shù)子序列的過程。,圖4-8 描述倒位序的樹狀圖,3.倒位序?qū)崿F(xiàn) 輸入序列先按自然順序存入存儲(chǔ)單元,然后經(jīng)變址運(yùn)算來實(shí)現(xiàn)倒位序排列。 設(shè)輸入序列的序號(hào)為n,二進(jìn)制為(n2 n1 n0 )2 , 倒位序順序用 表示,其倒位序二進(jìn)制為(n0 n1 n2 )2 , 例如 ，N=8時(shí)如下表：,表4-2 碼位的倒位序（N=8）,存儲(chǔ)單元,自然順序,變址,倒位序,圖 4-9 倒位序的變址處理 (N=8),變址處理方法,4. 蝶形運(yùn)算兩節(jié)點(diǎn)的“距離” 以圖4-5的8點(diǎn)FFT為例，其輸入是倒位序的，輸出是自然順序的。 其第一級(jí)（第一列）每個(gè)蝶形的兩節(jié)點(diǎn)間“距離”為1， 第二級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)“距離”為2， 第三級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)“距離”為4。 由此類推得，對(duì)N=2L點(diǎn)FFT，當(dāng)輸入為倒位序， 輸出為正常順序時(shí)，其第m級(jí)運(yùn)算，每個(gè)蝶形的兩節(jié)點(diǎn)“距離”為2m-1。,5. WNr的確定 由于對(duì)第m級(jí)運(yùn)算，一個(gè)DFT蝶形運(yùn)算的兩節(jié)點(diǎn)“距離”為2m-1， 因而式（4-21）可寫成:,（4-22a）,（4-22b）,為了完成上兩式運(yùn)算，還必須知道系數(shù)ＷNr的變換規(guī)律：  ① 把式（4-22）中蝶形運(yùn)算兩節(jié)點(diǎn)中的第一個(gè)節(jié)點(diǎn)標(biāo)號(hào)值， 即k值，表示成L位（注意N=2L）二進(jìn)制數(shù)；,② 把此二進(jìn)制數(shù)乘上2L-m，即將此L位二進(jìn)制數(shù)左移M-m位（注意m是第m級(jí)運(yùn)算），把右邊空出的位置補(bǔ)零， 此數(shù)即為所求r的二進(jìn)制數(shù)。  從圖4-5看出，WNr因子最后一列有N/2種，順序?yàn)閃N0， WN1，…， ， 其余可類推。,6.存儲(chǔ)單元 存輸入序列 需N個(gè)存儲(chǔ)單元 存放系數(shù) 需N/2個(gè)存儲(chǔ)單元； 共計(jì)需(N+N/2)個(gè)存儲(chǔ)單元。,四、 按時(shí)間抽取的FFT算法的其他形式流圖 顯然，對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連的支路及傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，所得最后結(jié)果都是x(n)的DFT的正確結(jié)果，只是數(shù)據(jù)的提取和存放的次序不同而已。這樣就可得到按時(shí)間抽取的FFT算法的若干其他形式流圖。 將圖4-5中和x(4)水平相連的所有節(jié)點(diǎn)和x(1)水平相連的所有節(jié)點(diǎn)位置對(duì)調(diào)，再將和x(6)水平相連的所有節(jié)點(diǎn)與和x(3)水平相連的所有節(jié)點(diǎn)對(duì)調(diào)，其余諸節(jié)點(diǎn)保持不變，可得圖4-11的流圖。 圖4-11與圖4-5的蝶形相同，運(yùn)算量也一樣，不同點(diǎn)是：,① 數(shù)據(jù)存放的方式不同，圖4-5是輸入倒位序、輸出自然順序，圖4-11是輸入自然順序、輸出倒位序； ②取用系數(shù)的順序不同，圖4-5的最后一列是按 的順序取用系數(shù)，且其前一列所用系數(shù)是后一列所用系數(shù)中具有偶數(shù)冪的那些系數(shù)（例如 ）；圖4-11是最后一列是按 的順序取用系數(shù)，且其前一列所用系數(shù)是后一列所用系數(shù)的前一半， 這種流圖是最初由庫(kù)利和圖基給出的時(shí)間抽取法。 經(jīng)過簡(jiǎn)單變換，也可得輸入與輸出都是按自然順序排列的流圖以及其他各種形式的流圖 。,圖 4-10 時(shí)間抽取、 輸入自然順序、 輸出倒位序的FFT流圖,,4.4 按頻率抽取（DIF）的基 -2 FFT算法（桑德-圖基算法）,一、 算法原理 仍設(shè)序列點(diǎn)數(shù)為N=2L，L為正整數(shù)。在把輸出X(k)按k的奇偶分組之前，先把輸入序列按前一半、后一半分開（不是按偶數(shù)、 奇數(shù)分開）， 把N點(diǎn)DFT寫成兩部分。,k=0, 1, …, N-1,由于 ，故 ，可得,k=0, 1, …, N-1,當(dāng)k為偶數(shù)時(shí)，(-1)k=1；k為奇數(shù)時(shí)，(-1)k=-1。因此，按k的奇偶可將X(k)分為兩部分:,為前一半輸入與后一半輸入之和的N/2點(diǎn)DFT,為前一半輸入與后一半輸入之差再與WNn之積的N/2點(diǎn)DFT。,圖 4-14 按頻率抽取蝶形運(yùn)算流圖符號(hào),這樣可把一個(gè)N點(diǎn)DFT按k的奇偶分解為兩個(gè)N/2點(diǎn)的DFT。 N=8時(shí)，上述分解過程示于圖4-15。,圖 4-15 按頻率抽取，將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT的組合,由于N=2L，N/2仍是一個(gè)偶數(shù)，因而可以將每個(gè)N/2點(diǎn)DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點(diǎn)DFT進(jìn)一步分解為兩個(gè)N/4 點(diǎn)DFT。 圖4-16示出了這一步分解的過程。,圖 4-16 按頻率抽取的第二次分解,這樣的分解可以一直進(jìn)行到第L次（N=2L），第L次實(shí)際上是做兩點(diǎn)DFT，它只有加減運(yùn)算。 然而，為了有統(tǒng)一的運(yùn)算結(jié)構(gòu)，仍然用一個(gè)系數(shù)為WN0的蝶形運(yùn)算來表示， 這N/2個(gè)兩點(diǎn)DFT的N個(gè)輸出就是x(n)的N點(diǎn)DFT的結(jié)果X(k)。 圖4-16表示一個(gè)N=8 完整的按頻率抽取的基-2 FFT運(yùn)算結(jié)構(gòu)。,圖 4-16 按頻率抽取的FFT流圖 （N=8）,4.5 離散傅里葉反變換的快速計(jì)算方法(IFFT),一.稍微變動(dòng)FFT程序和參數(shù)可實(shí)現(xiàn)IFFT,比較兩式可知,只要DFT的每個(gè)系數(shù) 換成 ,最后再乘 以常數(shù)1/N就可以得到IDFT的快速算法--IFFT。 另外,可以將常數(shù)1/N分配到每級(jí)運(yùn)算中, ∵ , 也就是每級(jí)蝶形運(yùn)算均乘以1/2。,二.不改(FFT)的程序直接實(shí)現(xiàn)IFFT,,這就是說,先將X(k)取共軛,即將X(k)的虛部乘-1，直接利用FFT程序計(jì)算DFT；然后再取一次共軛；最后再乘1/N,即得x(n)。所以FFT,IFFT可用一個(gè)子程序。,一.線性卷積的長(zhǎng)度 設(shè)一離散線性移不變系統(tǒng)的沖激響應(yīng)為 ,其輸入信號(hào)為 . 其輸出為 . 并且 的長(zhǎng)度為L(zhǎng)點(diǎn), 的 長(zhǎng)度為M點(diǎn),則：,4.10 線性卷積的FFT算法,二.用FFT算 的步驟：,流程圖,三.幾點(diǎn)說明 1. 當(dāng) M=L 時(shí),用圓周卷積計(jì)算線性 卷積的速度快,點(diǎn)數(shù)越多,速度越快, N≥64時(shí),速度增加明顯. 2. LM 時(shí),速度增加不太明顯,為了 增加速度,采用 (1)重疊相加法 (2) 重疊保留法(從略).,