數(shù)字信號(hào)處理教程 (第三版)程佩青 清華大學(xué)出版社dsp-ch4-2

§4.4按頻率抽?。―IF）的FFT算法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)-1-1-1-1WWWWNNNN0123N=8時(shí),按k的奇偶分解過程先蝶形運(yùn)算，后DFT:N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)按照以上思路繼續(xù)分解，即一個(gè)N/2的DFT分解成兩個(gè)N/4點(diǎn)DFT，直到只計(jì)算2點(diǎn)的DFT，這就是DIF-FFT算法。同理：其中：逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1

(0)X(0)

(1)X(4)

(2)X(2)

(3)X(6)

(4)X(1)

(5)X(5)

(6)X(3)

(7)X(7)-1-1-1-1WWWWNNNN0123-1-1-1-1WWWWNNNN0202-1-1-1-1WWWWNNNN0000例如N=8時(shí)DIF的FFT流圖如下：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第m級(jí)運(yùn)算：

蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)的k值，表示成L位二進(jìn)制數(shù)，左移m-1位，把右邊空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。存儲(chǔ)單元輸入序列x(n):N個(gè)存儲(chǔ)單元系數(shù)：N/2個(gè)存儲(chǔ)單元3、DIT與DIF的異同基本蝶形不同DIT:先復(fù)乘后加減DIF:先減后復(fù)乘運(yùn)算量相同都可原位運(yùn)算DIT和DIF的基本蝶形互為轉(zhuǎn)置一.稍微變動(dòng)FFT程序和參數(shù)可實(shí)現(xiàn)IFFT

§4.5IDFT的FFT算法（FFT應(yīng)用）

比較兩式可知,只要DFT的每個(gè)系數(shù)換成,最后再乘以常數(shù)1/N就可以得到IDFT的快速算法--IFFT。另外,可以將常數(shù)1/N分配到每級(jí)運(yùn)算中,∵,也就是每級(jí)蝶形運(yùn)算均乘以1/2。

圖DIT―IFFT運(yùn)算流圖二.不改(FFT)的程序直接實(shí)現(xiàn)IFFT

這就是說,先將X(k)取共軛,即將X(k)的虛部乘-1，直接利用FFT程序計(jì)算DFT；然后再取一次共軛；最后再乘1/N，即得x(n)。所以FFT，IFFT可用一個(gè)子程序。共軛FFT共軛乘1/N直接調(diào)用FFT子程序計(jì)算IFFT的方法：§4.10線性卷積的FFT算法（FFT應(yīng)用）1、線性卷積的FFT算法需運(yùn)算量：若系統(tǒng)滿足線性相位，即：則需運(yùn)算量：若L點(diǎn)x(n)，M點(diǎn)h(n)，則直接計(jì)算其線性卷積y(n)FFT法：以圓周卷積代替線性卷積1)H(k)=FFT[h(n)]N/2*log2N4)y(n)=IFFT[Y(k)]N/2*log2N3)Y(k)=H(k)X(k)N2)X(k)=FFT[x(n)]N/2*log2NN比較直接計(jì)算和FFT法計(jì)算的運(yùn)算量討論：1）當(dāng)2）當(dāng)1）重疊相加法

N

用FFT法實(shí)現(xiàn)重疊相加法的步驟如下:

①計(jì)算N點(diǎn)FFT，H(k)=DFT［h(n)］；②計(jì)算N點(diǎn)FFT，Xi(k)=DFT［xi(n)］；③相乘，Yi(k)=Xi(k)H(k)；④計(jì)算N點(diǎn)IFFT，yi(n)=IDFT［Yi(k)］；⑤將各段yi(n)（包括重疊部分）相加， 。重疊相加的名稱是由于各輸出段的重疊部分相加而得名的。例已知序列x[n]=n+2,0n12,h[n]={1,2,1}試?yán)弥丿B相加法計(jì)算線性卷積,取L=5。y[n]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}解:重疊相加法x1[n]={2,3,4,5,6}x2[n]={7,8,9,10,11}x3[n]={12,13,14}y1[n]={2,7,12,16,20,17,6}y2[n]={7,22,32,36,40,32,11}y3[n]={12,37,52,41,14}2）重疊保留法

舍棄yi(n)的前M-1個(gè)點(diǎn)，保留后面的L個(gè)點(diǎn)，再將yi(n)順次連接，即得y(n)。分段右移序列卷積N此方法與上述方法稍有不同。先將x(n)分段，每段L個(gè)點(diǎn)，這是相同的。不同之處是，序列中補(bǔ)零處不補(bǔ)零，而在每一段的前邊補(bǔ)上前一段保留下來的（M-1）個(gè)輸入序列值，組成L+M-1點(diǎn)序列xi(n)。如果L+M-1<2m，則可在每段序列末端補(bǔ)零值點(diǎn)，補(bǔ)到長(zhǎng)度為2m，這時(shí)如果用DFT實(shí)現(xiàn)h(n)和xi(n)圓周卷積，則其每段圓周卷積結(jié)果的前（M-1）個(gè)點(diǎn)的值不等于線性卷積值，必須舍去。

y[k]={2,7,12,16,20,24,28,32,36,40,44,48,52,41,14}x1[n]={0,0,2,3,4}x2[n]={3,4,5,6,7}x3[n]={6,7,8,9,10}y1[n]=x1[n]h[n]={11,4,2,7,12}x4[n]={9,10,11,12,13}y2[n]=x2[n]h[n]={23,17,16,20,24}y3[n]=x3[n]h[n]={35,29,28,32,36}y4[n]=x4[n]h[n]={47,41,40,44,48}x5[n]={12,13,14,0,0}y5[n]=x5[n]h[n]={12,37,52,41,14}解:重疊保留法例已知序列x[n]=n+2,0n12,h[n]={