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

學(xué)習(xí)目標(biāo)理解按時間抽選的基-2FFT算法的算法原理、運(yùn)算流圖、所需計算量和算法特點(diǎn)理解按頻率抽選的基-2FFT算法的算法原理、運(yùn)算流圖、所需計算量和算法特點(diǎn)理解IFFT算法理解FFT算法的應(yīng)用第4章快速傅里葉變換FFT:FastFourierTransform1965年，Cooley,Tukey《機(jī)器計算傅里葉級數(shù)的一種算法》一、直接計算DFT的問題及改進(jìn)途徑運(yùn)算量復(fù)數(shù)乘法復(fù)數(shù)加法一個X(k)NN–1N個X(k)N2N(N–1)實數(shù)乘法實數(shù)加法一次復(fù)乘42一次復(fù)加2一個X(k)4N2N+2(N–1)=2(2N–1)N個X(k)4N22N(2N–1)【例】：對一幅N×N點(diǎn)的二維圖像進(jìn)行DFT變換，如用每秒可做10萬次復(fù)數(shù)乘法的計算機(jī)，當(dāng)N=1024時，問需要多少時間（不考慮加法運(yùn)算時間）？解：直接計算DFT所需復(fù)乘次數(shù)為因此用每秒可做10萬（）次復(fù)數(shù)乘法的計算機(jī)，秒）。則需要近3000小時（這對實時性很強(qiáng)的信號處理來說，要么提高計算速度，而這樣，對計算機(jī)速度的要求太高了。所以，只能通過改進(jìn)對DFT的計算方法，以大大減少運(yùn)算次數(shù)。FFT算法分類:時間抽選法 DIT:Decimation-In-Time頻率抽選法 DIF:Decimation-In-Frequency§4.2按時間抽選的基-2FFT算法1、算法原理設(shè)序列點(diǎn)數(shù)N=2L，L為整數(shù)。若不滿足，則補(bǔ)零將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。則x(n)的DFT:再利用周期性求X(k)的后半部分蝶形運(yùn)算符號8點(diǎn)DFT一次時域抽取分解運(yùn)算流圖分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個N/2點(diǎn)DFT(N/2)2N/2(N/2–1)兩個N/2點(diǎn)DFTN2/2N(N/2–1)一個蝶形12N/2個蝶形N/2N總計運(yùn)算量減少了近一半N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4由兩個N/4點(diǎn)的DFT組合成一個N/2點(diǎn)的DFT同理：其中：8點(diǎn)DFT二次時域抽取分解運(yùn)算流圖這樣逐級分解，直到2點(diǎn)DFT當(dāng)N=8時，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1

8點(diǎn)DIT-FFT運(yùn)算流圖2、運(yùn)算量當(dāng)N=2M時，共有M級蝶形，每級N/2個蝶形，每個蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：比較DFT【例】：用FFT算法處理一幅N×N點(diǎn)的二維圖像，如用每秒可做10萬次復(fù)數(shù)乘法的計算機(jī)，當(dāng)N=1024時，問需要多少時間（不考慮加法運(yùn)算時間）？

解：當(dāng)N=1024點(diǎn)時，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為：次僅為直接計算DFT（次）所需時間的10萬分之一。

即原需要3000小時，現(xiàn)在只需要不到2分鐘。3、算法特點(diǎn)1）原位計算m表示第m級迭代，k，j表示數(shù)據(jù)所在的行數(shù)2）倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n200011011001101變址處理方法倒位序?qū)崿F(xiàn)

反序二進(jìn)制數(shù)N=8時的自然順序二進(jìn)制數(shù)和相應(yīng)的倒位序二進(jìn)制數(shù)0426153700010001011000110101111100000101001110010111011101234567倒位序（J）二進(jìn)制數(shù)自然順序（I）3）蝶形運(yùn)算的碟距即：兩輸入節(jié)點(diǎn)間“距離”對N=2M點(diǎn)FFT，輸入倒位序，輸出自然序，第m級運(yùn)算每個蝶形的兩節(jié)點(diǎn)距離為2m–1例如N=8=23,第一級(列)距離為21-1=1,第二級(列)距離為22-1=2，第三級(列)距離為23-1=4。L表示從左到右的運(yùn)算級數(shù)（L=1，2，…，M）。第L級共有2L–1個不同的旋轉(zhuǎn)因子。對N=2M的一般情況，第L級的旋轉(zhuǎn)因子為：WNP=W2LJJ=0，1，2，…，2L-1-14）旋轉(zhuǎn)因子的確定

5）存儲單元存輸入序列x(n):N個存儲單元(n=0,1,,N-1)存系數(shù)：N/2個存儲單元[P=0,1,,（N/2）-1,]共計(N+N/2)個存儲單元三、按頻率抽選的基-2FFT算法1、算法原理設(shè)序列點(diǎn)數(shù)N=2L，L為整數(shù)。將X(k)按k的奇偶分組前，先將輸入x(n)按n的順序分成前后兩半：按k的奇偶將X(k)分成兩部分：令則X(2r)和X(2r+1)分別是x1(n)和x2(n)的N/2點(diǎn)DFT，記為X1(k)和X2(k)DIF-FFT第一次分解運(yùn)算流圖（N=8）N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4同理：其中：逐級分解，直到2點(diǎn)DFT當(dāng)N=8時，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1DIF-FFT運(yùn)算流圖（N=8）2、算法特點(diǎn)1）原位計算-1L級蝶形運(yùn)算，每級N/2個蝶形，每個蝶形結(jié)構(gòu)：

m表示第m級迭代，k，j表示數(shù)據(jù)所在的行數(shù)2）蝶形運(yùn)算對N=2L點(diǎn)FFT，輸入自然序，輸出倒位序，兩節(jié)點(diǎn)距離：2L-m=N/2m例如N=23=8(1)m=1時的距離為8/2=4；(2)m=2時的距離為8/4=2;(3)m=3時的距離為8/8=13、DIT與DIF的異同基本蝶形不同DIT:先復(fù)乘后加減DIF:先減后復(fù)乘運(yùn)算量相同都可原位運(yùn)算DIT和DIF的基本蝶形互為轉(zhuǎn)置四、IFFT算法比較：IDFT:DFT:由DIF-FFT運(yùn)算流圖改成的DIT-IFFT運(yùn)算流圖如下所示：共軛FFT共軛乘1/N直接調(diào)用FFT子程序計算IFFT的方法：§4.3實序列的FFT算法問題的提出在實際工作中，數(shù)據(jù)x(n)常常是實數(shù)序列。如果直接按FFT運(yùn)算流圖計算，就是把x(n)看成一個虛部為零的復(fù)序列進(jìn)行計算，這就增加了存儲量和運(yùn)算時間。處理該問題的方法有兩種。一、一個N點(diǎn)FFT同時計算兩個N點(diǎn)實序列的FFT

設(shè)x1(n)，x2(n)是兩個N點(diǎn)實序列，它們的離散傅里葉變換分別為:構(gòu)造一個新的復(fù)序列其對應(yīng)的DFT變換為

根據(jù)第三章中有關(guān)復(fù)數(shù)序列的共軛（奇偶）對稱特性二、一個N點(diǎn)FFT運(yùn)算一個2N點(diǎn)實序列設(shè)x(n)是2N點(diǎn)的實序列，我們?nèi)藶榈貙(n)分為