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

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

復(fù)數(shù)乘

N(N-1)次

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

2次實(shí)數(shù)乘

N(4N-2)次

實(shí)數(shù)加例如

10點(diǎn)DFT100次

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

1024點(diǎn)DFT1,048,576次

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

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

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

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

Cooley&Tukey

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

2

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

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

(k)和X2

(k)分別為

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

(k)和X2

(k)都是N/2點(diǎn)DFT，而X(k)有N點(diǎn)，所以得計(jì)算后N/2點(diǎn).????☉☉☉☉-1X(k)X1(k)X2(k)同理用下面的蝶形圖也可清楚地說(shuō)明這種運(yùn)算。AA+BCCBA-BC蝶形運(yùn)算符號(hào)一個(gè)蝶形運(yùn)算：一次復(fù)數(shù)乘、兩次復(fù)數(shù)加運(yùn)算量：幾次乘？幾次加？運(yùn)算量減少近一半經(jīng)過(guò)一次時(shí)域抽取計(jì)算量：復(fù)數(shù)加：復(fù)數(shù)乘：碟形運(yùn)算2、蝶形運(yùn)算????☉☉☉☉-1X(k)X1(k)X2(k)直接計(jì)算需要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)

按奇偶分解成兩個(gè)N/4長(zhǎng)的子序列x3(l

)和

x4(l

)

于是同樣，將

按奇偶分解成兩個(gè)N/4長(zhǎng)的子序列和

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

N/2個(gè)兩點(diǎn)DFT。每分一次，稱為一“級(jí)”運(yùn)算。N點(diǎn)DFT可以分成M級(jí)，從左到右依次是1，2，…，M級(jí)，每級(jí)有N/2個(gè)蝶形M＝log2N。此算法以2為基，寫作

N＝2M(不足位，補(bǔ)零延伸)。全部“蝶形”數(shù)：NM/2，M級(jí)，每級(jí)N/2個(gè)蝶形；一個(gè)蝶形運(yùn)算：一次復(fù)數(shù)乘、兩次復(fù)數(shù)加。復(fù)數(shù)乘法次數(shù)：NM/2，復(fù)數(shù)加法次數(shù)：NM。都<<N2，在N值很大時(shí)，十分高效。直接DFT，復(fù)數(shù)乘N平方次，復(fù)數(shù)加為N(N-1)次。N/2次復(fù)數(shù)乘，N次復(fù)數(shù)加FFT?????每次運(yùn)算結(jié)果存入原輸入數(shù)據(jù)占用的存貯單元3.原位計(jì)算（同址運(yùn)算）這種利用同一存貯單元存貯蝶形計(jì)算輸入輸出數(shù)據(jù)的方法稱為原位(址)計(jì)算。原位計(jì)算可節(jié)省大量?jī)?nèi)存，使設(shè)備成本降低N＝2M點(diǎn)的FFT共進(jìn)行M級(jí)運(yùn)算，每級(jí)由N/2個(gè)蝶形運(yùn)算組成設(shè)N個(gè)存貯單元存入數(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ī)律）順位序二進(jìn)順序碼二進(jìn)倒置碼倒位序

0000000010011004201001023011110641000011510110156110011371111117

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

X

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

(n)

不再是原來(lái)的自然順序，這是由于對(duì)x

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

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

在N點(diǎn)DIT－FFT運(yùn)算流圖中，每級(jí)有N/2個(gè)蝶形，每個(gè)蝶形要乘以因子W

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

r因子是：再往下分時(shí)，依次是，故每一級(jí)W

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

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

以8點(diǎn)FFT為例，輸入是倒位序的輸出是自然順序，第一級(jí)（第1列）每個(gè)蝶形兩點(diǎn)間的“距離”為1，第二級(jí)每個(gè)蝶形的兩點(diǎn)“間距離”為2，第三級(jí)為4，由此類推，對(duì)于點(diǎn)FFT，當(dāng)輸入為倒位序，輸出為正常順序，其第L級(jí)運(yùn)算，每個(gè)蝶形的兩點(diǎn)“距離”為?！?.3按頻率抽取(DIF)的FFT算法(桑德-圖基算法)一、算法原理（時(shí)域前后分，頻域奇偶分）設(shè)x(n)長(zhǎng)度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形運(yùn)算單元蝶形運(yùn)算單元☉☉☉☉?按頻率抽取法的蝶形運(yùn)算流圖符號(hào)DIF-FFT一次分解運(yùn)算流圖(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點(diǎn)DFT的DIF-FFT三級(jí)運(yùn)算流圖輸入為順序，輸出為倒序二、運(yùn)算量次復(fù)數(shù)加法。次復(fù)數(shù)乘法，DIF和DIT具有一樣的運(yùn)算量：三、原位運(yùn)算

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

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

將N點(diǎn)DFT變成M級(jí)DIF－FFT蝶形運(yùn)算.(2)運(yùn)算量及特點(diǎn)與基2DIF－FFT相同。4、DIT與DIF的聯(lián)系5、通常多使用基2的FFT，因?yàn)樗?jiǎn)單、效率高。

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

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

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