數(shù)字信號處理（第3版）課件 第07章 FFT

第7章快速傅里葉變換（FFT）17.1時域抽選基2FFT算法7.2頻域抽選基2FFT算法7.3實現(xiàn)中的具體問題7.4實序列的FFT算法7.5IDFT的快速算法2復數(shù)乘法:復數(shù)加法:實數(shù)乘法:實數(shù)加法:直接計算的運算量37.1時域抽選基2FFT算法

1.

第1次分解4推導信號流圖由支路和節(jié)點組成。支路由箭頭表示信號的流向，箭頭旁的常數(shù)表示乘法運算；節(jié)點值等于所有輸入支路之和，也就是包含了加法運算。加法乘法節(jié)點值=所有輸入支路之和信號流圖簡介第1次分解后信號流圖（N=8）N/2PointsDFTN/2PointsDFT基本蝶形計算782.第2次分解9第2次分解后信號流圖103.完全分解后信號流圖114.計算量舉例125.其他形式13147.2頻域抽選基2FFT算法

1.

第1次分解15推導第1次分解后信號流圖（N=8）N/2PointsDFTN/2PointsDFT基本蝶形運算17182.第2次分解后信號流圖193.完全分解后信號流圖204.計算量同DIT-FFT215.其他形式22237.3實現(xiàn)中的具體問題

1.同址計算基本蝶形：若將和分別存放在原存放和的同一存儲器中，則實現(xiàn)全部的計算只需要一列存儲N個復數(shù)的存儲器。我們稱這種數(shù)據(jù)的存儲方式為同址計算.24DIT可以同址運算不可以同址運算252.位反轉(zhuǎn)或倒位序排列要確定在輸入數(shù)列中的位置，我們必須將序號的二進制位序顛倒一下。我們稱這種操作為倒位序。倒位序是由抽選導致的，N必須是2的整數(shù)冪次倒位序的實現(xiàn)方法專用硬件法：DSP芯片有硬件支持的倒位序?qū)ぶ罚幊毯唵?，倒?/p>

序過程不占用執(zhí)行時間軟件法事先做好倒位序表供使用時查表（反向進位法、生成法、

Matlab的bin2dec(fliplr(dec2bin([0:N-1])))）需要取數(shù)時順次遞推出下一個序號（反向進位法）26生成法N=2：倒位序[01]N=4：[01]*2=[02][02]+1=[13]所以倒位序：[0213]N=8：[0213]*2=[0426][0426]+1=[1537]所以倒位序：[04261537]N=16：[04261537]*2=[08412210614][08412210614]+1=[19513311715]所以倒位序：[0841221061419513311715]反向進位法

(最高bit加1，向低位進位)0000 01000 80100 41100 120010 21010 100110 60001 11001 90101 51101 130011 31101117111115N=16的倒位序排列確定x[n]后面是x[?]的軟件實現(xiàn)步驟：(1)序號n與N/2比較：大于等于則表示最高位是1，向下進位后該位變成0，所以n=n-N/2，繼續(xù)下一步；小于則表示最高位是0，所以n=n+N/2，結(jié)束，n就是接下來的序號。(2)n與N/4比較，大于等于則表示次高位是1，向下進位后該位變成0，所以n=n-N/4，繼續(xù)下一步；

小于則n=n+N/4，結(jié)束?！?考慮128點基2FFT算法輸入正常位序，輸出倒位序排列的信號流圖，排在X[98]后面的是

。X[18]98=62H=(110,0010)2

位置編碼(010,0011)2+1=(010,0100)2(001,0010)2=12H=18反向進位法：最高位加1，向下進位例題按藍色的路徑求解：寫出98的編碼，倒位序得到位置的編碼，加1得到下一個位置編碼，再倒位序得到下一個信號的序號；按照紅色的路徑求解：寫出98的編碼，最高位加1向下進位，得到下一個信號的序號。303.系數(shù)30N=8的基2FFT，r的取值規(guī)律:DIT從左到右第1級是4的倍數(shù)0~N/2-4，重復4遍

第2級是2的倍數(shù)0~N/2-2，重復2遍

第3級是連續(xù)取值0~N/2-1DIF正好相反（1）用到時計算系數(shù)的值：

省存儲空間，但費計算時間（2）事先做成數(shù)據(jù)表格供查表：

省計算時間，但費存儲空間N=16DIT-FFT31x[0]x[8]x[4]x[12]x[2]x[10]x[6]x[14]x[1]x[9]x[5]x[13]x[3]x[11]x[7]x[15]x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]x[8]x[9]x[10]x[11]x[12]x[13]x[14]x[15]WN0WN0WN0WN0WN0WN0WN0WN0WN0WN4WN0WN4WN0WN4WN0WN4-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1WN2WN0WN0WN2WN4WN4WN6WN6-1-1-1-1-1-1-1-1WN4WN5WN6WN1WN0WN2WN3WN7-1-1-1-1-1-1-1-1-1327.4實序列的FFT算法1.計算兩個N點實序列的N點DFT332.計算一個N點實序列的N點DFT復乘： 復加：347.5IDFT的快速算法方案1：對FFT算法流圖加以改動得到IFFT快速算法流圖35DIT-FFTIFFT36DIF-FFTIFFT37步驟：（1）X*[k]（2）FFT{}（3）()*/N優(yōu)點：可直接調(diào)用FFT子程序方案2：

利用FFT算法，增加一些預處理和后處理

38方案3：

利用FFT算法，根據(jù)DFT的對偶性質(zhì)

步驟：（1）FFT{X[k]}=g[n]（2）x[n]=g[N-n]/N優(yōu)點：可直接調(diào)用FFT子程序第7章總結(jié)397.1 時域抽選FFT算法7.2

頻域抽