數(shù)字信號處理 第四章

§4.1引言§4.2按時間抽取(DIT)的FFT算法§4.3按頻率抽取(DIF)的FFT算法§4.4離散傅立葉反變換(IDFT)的快速計算方法§4.5進一步減少運算量的措施第四章快速傅立葉變換(FFT)數(shù)字信號處理§4.1引言全部計算N個X(k)N2次

復(fù)數(shù)乘

N(N-1)次

復(fù)數(shù)加或4N

2次實數(shù)乘

N(4N-2)次

實數(shù)加例如

10點DFT100次

復(fù)數(shù)乘；

1024點DFT1,048,576次

復(fù)數(shù)乘，即100萬次的復(fù)數(shù)乘運算！結(jié)論：直接計算DFT的計算量和N的平方成正比一、DFT直接計算工作量很大計算一個X(k)工作量：N次

復(fù)數(shù)乘(N-1)次復(fù)數(shù)加或4N次

實數(shù)乘2N+2(N-1)=4N-2次

實數(shù)加????對稱性:周期性本章以基2的FFT算法為重點二、DFT的高效計算1965年

Cooley&Tukey

奠定FFT，把長序列短分解，利用WN因子的周期性和對稱性，可導(dǎo)出一個高效的快速算法使得乘法計算量由N

2

次降為次。以1024點為例，計算量降為5120次，僅為原來的4.88%?？杉s性:§4.2按時間抽取(DIT)的FFT算法(庫利-圖基算法)一、算法原理（時域奇偶分，頻域前后分）設(shè)x(n)長度N，N=2M，M為自然數(shù)x2(r)=x(2r+1)x1(r)=x(2r)

1、第一次抽取：x(n)的DFT為：將x(n)按偶、奇分成兩組，可得兩各自長度為N/2的奇偶序列其中X1

(k)和X2

(k)分別為

x(2r)和x(2r＋1)的N/2點DFT：由于它們均以N/2為周期，且，因此這樣，將一個N點DFT分解成兩個N/2點DFT。由于X1

(k)和X2

(k)都是N/2點DFT，而X(k)有N點，所以得計算后N/2點.????☉☉☉☉-1X(k)X1(k)X2(k)同理用下面的蝶形圖也可清楚地說明這種運算。AA+BCCBA-BC蝶形運算符號一個蝶形運算：一次復(fù)數(shù)乘、兩次復(fù)數(shù)加運算量：幾次乘？幾次加？運算量減少近一半經(jīng)過一次時域抽取計算量：復(fù)數(shù)加：復(fù)數(shù)乘：碟形運算2、蝶形運算????☉☉☉☉-1X(k)X1(k)X2(k)直接計算需要8×8次復(fù)數(shù)乘、8×7次復(fù)數(shù)加36次復(fù)數(shù)乘32次復(fù)數(shù)加以N＝8為例DFT(N=8)☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉x(0)x(1)x(2)...x(7)X(0)X(1)X(2)...X(7)DFT(N=4)☉☉☉☉DFT(N=4)☉☉☉☉x(0)x(2)x(4)x(6)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)3、第二次抽取將

x1(r)

按奇偶分解成兩個N/4長的子序列x3(l

)和

x4(l

)

于是同樣，將

按奇偶分解成兩個N/4長的子序列和

經(jīng)過第二次分解，將N/2點的DFT分解成兩個N/4點的DFT和N/4個蝶形運算。依次類推，經(jīng)過M－1次分解，最后將N點DFT分解成N/2個2點DFT。當N=8時，?DFT(N=2)☉☉DFT(N=2)☉☉DFT(N=2)☉☉DFT(N=2)☉☉???☉☉☉☉☉☉☉☉?☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉???????????8點FFT運算流圖2.DFT-FFT與直接計算DIT算法運算量比較每級蝶形有多少次復(fù)數(shù)乘和復(fù)數(shù)加？二、算法的討論1.級的概念DIT-FFT算法過程，將N點DFT先分成兩個N/2點DFT，再……直至

N/2個兩點DFT。每分一次，稱為一“級”運算。N點DFT可以分成M級，從左到右依次是1，2，…，M級，每級有N/2個蝶形M＝log2N。此算法以2為基，寫作

N＝2M(不足位，補零延伸)。全部“蝶形”數(shù)：NM/2，M級，每級N/2個蝶形；一個蝶形運算：一次復(fù)數(shù)乘、兩次復(fù)數(shù)加。復(fù)數(shù)乘法次數(shù)：NM/2，復(fù)數(shù)加法次數(shù)：NM。都<<N2，在N值很大時，十分高效。直接DFT，復(fù)數(shù)乘N平方次，復(fù)數(shù)加為N(N-1)次。N/2次復(fù)數(shù)乘，N次復(fù)數(shù)加FFT?????每次運算結(jié)果存入原輸入數(shù)據(jù)占用的存貯單元3.原位計算（同址運算）這種利用同一存貯單元存貯蝶形計算輸入輸出數(shù)據(jù)的方法稱為原位(址)計算。原位計算可節(jié)省大量內(nèi)存，使設(shè)備成本降低N＝2M點的FFT共進行M級運算，每級由N/2個蝶形運算組成設(shè)N個存貯單元存入數(shù)據(jù)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)????☉☉☉☉X

L

(k)X

L

(

j

)X

L-1

(k)X

L-1

(j)4.碼位倒置（倒位序規(guī)律）順位序二進順序碼二進倒置碼倒位序

0000000010011004201001023011110641000011510110156110011371111117

按相似原理：若按自然序x(0)，x(1)，x(2)，…輸入后不進行變址運算，則輸出將倒位序：X(0)，X(4)，X(2)，X(6)….…。由DIT－FFT流圖可以看出，變換后的輸出

X

(k)依照正序排列，輸入序列x

(n)

不再是原來的自然順序，這是由于對x

(n)作奇偶抽取所產(chǎn)生的。對N＝8，其自然序號是0，1，2，3，4，5，6，7第一次按奇偶分開，x(n)的序號是0，2，4，6|1，3，5，7每一組再作奇偶分開后序號是0，4|2，6|1，5|3，7先按自然順序輸入，

變址運算將順序碼的二進制位倒置倒位序x(n2n1n0)n0n1n201010101110100000100010110001101011111描述倒位序的樹狀圖掌握這一規(guī)律可以做到正確的編程4.旋轉(zhuǎn)因子的分布規(guī)律

在N點DIT－FFT運算流圖中，每級有N/2個蝶形，每個蝶形要乘以因子W

r；第一次將N點DFT分成兩個N/2點DFT，這時出現(xiàn)的W

r因子是：再往下分時，依次是，故每一級W

r因子的分布規(guī)律是：…W

r因子的一般分布規(guī)律：5、蝶形運算兩點間的距離

以8點FFT為例，輸入是倒位序的輸出是自然順序，第一級（第1列）每個蝶形兩點間的“距離”為1，第二級每個蝶形的兩點“間距離”為2，第三級為4，由此類推，對于點FFT，當輸入為倒位序，輸出為正常順序，其第L級運算，每個蝶形的兩點“距離”為?！?.3按頻率抽取(DIF)的FFT算法(桑德-圖基算法)一、算法原理（時域前后分，頻域奇偶分）設(shè)x(n)長度N=2M，并將x

(n)分成前后兩段：∴令后者的n=m+N/2，得：k為偶數(shù)k為奇數(shù)其中因此，按k奇偶將X(k)分解成偶數(shù)組和奇數(shù)組：令k＝2r令k＝2r+1☉☉☉☉x(n+N/2)x

(n)x1(n)x2(n)????☉☉☉☉X形運算單元蝶形運算單元☉☉☉☉?按頻率抽取法的蝶形運算流圖符號DIF-FFT一次分解運算流圖(N=8)☉☉☉☉☉☉☉☉??DFT(N/2)☉☉☉☉DFT(N/2)☉☉☉☉??X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)☉☉☉☉☉☉☉☉☉☉☉☉??☉☉☉☉????8點DFT的DIF-FFT三級運算流圖輸入為順序，輸出為倒序二、運算量次復(fù)數(shù)加法。次復(fù)數(shù)乘法，DIF和DIT具有一樣的運算量：三、原位運算

與DIT一樣，DIF很有規(guī)律，其每級（每列）計算都是由N/2個蝶形運算構(gòu)成，每一個蝶形結(jié)構(gòu)都完成下述基本迭代運算。此蝶形運算也是由一次復(fù)數(shù)乘和兩次復(fù)數(shù)加組成。三、按頻率抽取法和按時間抽取法的異同點1.基2DIT－FFT算法(1)算法思想：時域M級奇偶抽取，并利用，將N點DFT變成M級蝶形運算。(2)運算量：復(fù)數(shù)乘法次數(shù)復(fù)數(shù)加法次數(shù)(3)

特點：運算流圖結(jié)構(gòu)規(guī)則，可原位計算，程序簡短，應(yīng)用廣泛。2.基2DIF－FFT算法(1)算法思想：頻域?qū)(k)進行M級奇偶抽取，并利用

將N點DFT變成M級DIF－FFT蝶形運算.(2)運算量及特點與基2DIF－FFT相同。4、DIT與DIF的聯(lián)系5、通常多使用基2的FFT，因為它簡單、效率高。

當N為任意數(shù)時，可將x(n)延伸補0；若不允許延伸情況下，可考慮基r的FFT（如r=3,4,….），或混合基FFT。3、DIT與DIF的本質(zhì)區(qū)別在于基本蝶形的不同

(1)只要保持各節(jié)點所連的支路和傳輸系數(shù)不變，變換節(jié)點位置的排列，可以得到其它等效形式的流圖。(2)DIT與DIF的流圖滿足轉(zhuǎn)置定理：將所有支路方向都反向，并且交換輸入和輸出，但節(jié)點變量值不交換。DIF的復(fù)數(shù)乘法出現(xiàn)在減法之后，而DIT是先復(fù)數(shù)乘再作加法。?????按時間抽取蝶形運算單元按頻率抽取蝶形運算單元☉☉☉☉?時間抽取基2-FFT算法的原理示意圖X(n).........N/2點碟形組合N/4蝶形組合N/4蝶形組合N/8碟形組合N/8碟形組合N/8碟形組合N/8碟形組合X(k)NN/2N/4N/82點DFT2點DFT2點DFT...4點碟形組合2點DFT4點碟形組合...248x(n)N/2碟形分解N/4碟形分解N/4碟形分解N/8碟形分解N/8碟形分解N/8碟形分解N/8碟形分解NN/2N/4頻率抽取基2-FFT算法的原理示意圖N/8.........2點DFT2點DFT2點DFT...4點碟形分解2點DFT4點碟形分解...24X(k)§4.4離散傅立葉反變換(IDFT)的快速計算方法由定義：兩者作比較，得到啟發(fā)修改DFT運算中的各個系數(shù)-----將改為，最后乘以1/N。由于乘以1/N，等于各級乘以1/2因子，因此將常數(shù)1/N分解為，分散到各級中，即每一級都乘以因子1/2。方法一：不足：需要改變FFT的程序和參數(shù)才能實現(xiàn)。方法二：不修改FFT的程序和參數(shù)，利用共軛變換的方法∵∴

取共軛直接訪問FFT程序取共軛乘系數(shù)X(k)優(yōu)點：DFT和IDFT可以共用一個子程序模塊由定義：§4.5進一步減少運算量的措施1.多類蝶形單元運算2.旋轉(zhuǎn)因子的生成在FFT中，乘法主要來自旋轉(zhuǎn)因子，在編程時，正、余弦函數(shù)的產(chǎn)生