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

§4.4按頻率抽取（DIF）的FFT算法1、算法原理設序列點數(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點DFT，記為X1(k)和X2(k)-1-1-1-1WWWWNNNN0123N=8時,按k的奇偶分解過程先蝶形運算，后DFT:N/2仍為偶數(shù)，進一步分解：N/2N/4x3(0)x3(1)-1-1x4(0)x4(1)N/4點DFTN/4點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ù)分解，即一個N/2的DFT分解成兩個N/4點DFT，直到只計算2點的DFT，這就是DIF-FFT算法。同理：其中：逐級分解，直到2點DFT當N=8時，即分解到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時DIF的FFT流圖如下：2、算法特點1）原位計算-1L級蝶形運算，每級N/2個蝶形，每個蝶形結(jié)構(gòu)：

m表示第m級迭代，k，j表示數(shù)據(jù)所在的行數(shù)2）蝶形運算對N=2L點FFT，輸入自然序，輸出倒位序，兩節(jié)點距離：2L-m=N/2m第m級運算：

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

§4.5IDFT的FFT算法（FFT應用）

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

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

這就是說,先將X(k)取共軛,即將X(k)的虛部乘-1，直接利用FFT程序計算DFT；然后再取一次共軛；最后再乘1/N，即得x(n)。所以FFT，IFFT可用一個子程序。共軛FFT共軛乘1/N直接調(diào)用FFT子程序計算IFFT的方法：§4.10線性卷積的FFT算法（FFT應用）1、線性卷積的FFT算法需運算量：若系統(tǒng)滿足線性相位，即：則需運算量：若L點x(n)，M點h(n)，則直接計算其線性卷積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比較直接計算和FFT法計算的運算量討論：1）當2）當1）重疊相加法

N

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

①計算N點FFT，H(k)=DFT［h(n)］；②計算N點FFT，Xi(k)=DFT［xi(n)］；③相乘，Yi(k)=Xi(k)H(k)；④計算N點IFFT，yi(n)=IDFT［Yi(k)］；⑤將各段yi(n)（包括重疊部分）相加， 。重疊相加的名稱是由于各輸出段的重疊部分相加而得名的。例已知序列x[n]=n+2,0n12,h[n]={1,2,1}試利用重疊相加法計算線性卷積,取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個點，保留后面的L個點，再將yi(n)順次連接，即得y(n)。分段右移序列卷積N此方法與上述方法稍有不同。先將x(n)分段，每段L個點，這是相同的。不同之處是，序列中補零處不補零，而在每一段的前邊補上前一段保留下來的（M-1）個輸入序列值，組成L+M-1點序列xi(n)。如果L+M-1<2m，則可在每段序列末端補零值點，補到長度為2m，這時如果用DFT實現(xiàn)h(n)和xi(n)圓周卷積，則其每段圓周卷積結(jié)果的前（M-1）個點的值不等于線性卷積值，必須舍去。

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]={