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

《《快速傅里葉變換》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《快速傅里葉變換》PPT課件.ppt（58頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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