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

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

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

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

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

5）存儲(chǔ)單元存輸入序列x(n):N個(gè)存儲(chǔ)單元(n=0,1,,N-1)存系數(shù)：N/2個(gè)存儲(chǔ)單元[P=0,1,,（N/2）-1,]共計(jì)(N+N/2)個(gè)存儲(chǔ)單元三、按頻率抽選的基-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同理：其中：逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1DIF-FFT運(yùn)算流圖（N=8）2、算法特點(diǎn)1）原位計(jì)算-1L級(jí)蝶形運(yùn)算，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形結(jié)構(gòu)：

m表示第m級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)2）蝶形運(yùn)算對(duì)N=2L點(diǎn)FFT，輸入自然序，輸出倒位序，兩節(jié)點(diǎn)距離：2L-m=N/2m例如N=23=8(1)m=1時(shí)的距離為8/2=4；(2)m=2時(shí)的距離為8/4=2;(3)m=3時(shí)的距離為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子程序計(jì)算IFFT的方法：§4.3實(shí)序列的FFT算法問(wèn)題的提出在實(shí)際工作中，數(shù)據(jù)x(n)常常是實(shí)數(shù)序列。如果直接按FFT運(yùn)算流圖計(jì)算，就是把x(n)看成一個(gè)虛部為零的復(fù)序列進(jìn)行計(jì)算，這就增加了存儲(chǔ)量和運(yùn)算時(shí)間。處理該問(wèn)題的方法有兩種。一、一個(gè)N點(diǎn)FFT同時(shí)計(jì)算兩個(gè)N點(diǎn)實(shí)序列的FFT

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

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