數(shù)字信號處理（MATLAB版）第5章快速傅立葉變換（FFT）第5章快速傅立葉變換（FFT）5.1引入FFT的概念5.1.1各種離散傅立葉變換總結(jié)1.DTFT與DFS（1）在對離散信號的傅立葉變換中，離散非周期信號使用DTFT、離散周期信號使用DFS。（2）但是DTFT與DFS是有關(guān)系的：可以把有限長非周期序列假設(shè)為一無限長周期序列的一個主值周期，將離散非周期信號進(jìn)行周期延拓后，就成為無限長的離散周期信號，也可以使用DFS計算。（3）DFS的時域與頻域函數(shù)都是離散信號，可以滿足計算機(jī)進(jìn)行信號處理的離散性問題。（4）DFS處理的是無限長信號，而引入DFT概念解決了計算機(jī)進(jìn)行信號處理的有限長問題。第5章快速傅立葉變換（FFT）5.1引入FFT的概念5.1.1各種離散傅立葉變換總結(jié)2.DFT（1）DFS是對離散周期信號進(jìn)行級數(shù)展開，是DFT的周期延拓、DFT是將DFS取主值，因此DFT信號類似于DTFT信號，都是離散非周期信號。（2）除正弦函數(shù)等特殊函數(shù)外（其變換后是沖激串），DTFT變換后的圖形中的頻率一般是連續(xù)的，而DFT是DTFT的等間隔抽樣，DFT變換后的頻率響應(yīng)是離散的。（3）DTFT是以為周期的，而DFT的序列是有限長的。第5章快速傅立葉變換（FFT）5.1引入FFT的概念5.1.1各種離散傅立葉變換總結(jié)2.DFT（4）DFT的函數(shù)表示為，而DTFT的函數(shù)表示為（5）DFT是DTFT的等間隔抽樣。（6）DTFT和DFT都能表征原序列的信息。（7）通過時域和頻域采樣將連續(xù)信號離散，可使用該方法對連續(xù)信號進(jìn)行分析和處理。第5章快速傅立葉變換（FFT）5.1引入FFT的概念5.1.2FFT是DFT的快速算法FFT是實現(xiàn)DFT的一種快速運(yùn)算手段，實際中可以使用FFT取代其它各種傅立葉算法，成為數(shù)字信號處理強(qiáng)有力的工具。第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.1減少運(yùn)算量的分析1.直接計算DFT（1）從DFT定義可知，長度為N的有限長序列的DFT為：IDFT：，第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.1減少運(yùn)算量的分析2.減少運(yùn)算量的思路和方法（1）如何減少運(yùn)算量是解決譜分析和信號的實時處理的主要途徑。顯然，把N點(diǎn)DFT分解為幾個較短的DFT，可使乘法次數(shù)大大減少。（2）DFT運(yùn)算中含有大量的重復(fù)運(yùn)算，旋轉(zhuǎn)因子具有明顯的周期性和對稱性，充分利用這些特性可以減少重復(fù)運(yùn)算，從而減少運(yùn)算量提高運(yùn)算速度。（3）根據(jù)DFT的對稱性，利用DFT計算IDFT，這樣就極大地減少了運(yùn)算次數(shù)、提高了運(yùn)算速度。無論是時域抽取法還是頻域抽取法都是基于該原理進(jìn)行簡化運(yùn)算。第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.2FFT“基2”-時間抽選算法時間抽選法（稱為：DIT-FFT），就是在時域內(nèi)逐次將序列分解成奇數(shù)子序列和偶數(shù)子序列，通過求子序列的DFT而實現(xiàn)整個序列的DFT，將計算DFT的運(yùn)算量從次復(fù)乘減少到次復(fù)乘?！盎?”-FFT算法的思路和方法如下：（1）把一個序列分為長度減半的偶序列和奇序列，原序列的DFT就由這兩個序列求得。

（2）進(jìn)一步把序列分解成兩個序列，一直分解到單點(diǎn)序列。

第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.2FFT“基2”-時間抽選算法（3）N點(diǎn)DFT的第一級時域抽取分解圖(N=8)，也叫信號流圖，如圖5-2-3所示。第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.2FFT“基2”-時間抽選算法（4）依此類推，直到M=3，N點(diǎn)DFT的第3級時域抽取分解圖(N=8)，如圖5-2-4所示。第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.3DIT-FFT算法與直接計算DFT運(yùn)算量的比較在DIT-FFT算法中，每一級運(yùn)算都需要（每個蝶形需要兩次復(fù)數(shù)加法）。所以，M級運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為：次復(fù)數(shù)乘和N次復(fù)數(shù)加復(fù)數(shù)加次數(shù)為：第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.4DIT-FFT的運(yùn)算規(guī)律（1）原位計算（2）旋轉(zhuǎn)因子的變化規(guī)律（3）序列的倒序（4）蝶形運(yùn)算規(guī)律第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.5DIT-IFFT的運(yùn)算規(guī)律把DFT的快速算法FFT進(jìn)行變動即可得到IDFT的快速算法IFFT：（1）將X(k)取共軛得（2）調(diào)用原FFT子程序，將進(jìn)行FFT運(yùn)算；（3）對FFT的結(jié)果取共軛，并除以N即可得第5章快速傅立葉變換（FFT）5.2FFT的基2算法5.2.6頻率抽選法頻率抽選法（稱為：DIF-FFT），就是在頻域內(nèi)將逐次分解成偶數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)子序列，然后對這些分解得越來越短的子序列進(jìn)行DFT運(yùn)算，就可得整個頻域內(nèi)序列的FFT流圖，其抽取方法和過程與時域抽選法類似。第5章快速傅立葉變換（FFT）5.3實現(xiàn)FFT的常用MATLAB函數(shù)信號處理函數(shù)用

途conv卷積conv22維卷積fft快速傅立葉變換fft22維快速傅立葉變換ifft快速傅立葉逆變換ifft22維快速傅立葉逆變換filter離散時間濾波器filter22維離散時間濾波器abs求函數(shù)的絕對值，信號的幅值angle四個象限的相角，信號的相位角unwrap在360°邊界清除相角突變fftshift把0頻率點(diǎn)平移到頻譜的中心位置pow2、nextpow22的冪、2的下一個最接近的冪次數(shù)std計算標(biāo)準(zhǔn)偏差表5-2信號處理函數(shù)第5章快速傅立葉變換（FFT）5.3實現(xiàn)FFT的常用MATLAB函數(shù)5.3.1fft(x)和ifft(X)X=fft(x)和x=ifft(X)：按給出的向量長度N執(zhí)行傅立葉變換和反變換。語法如下：（1）X=fft(x)：使用快速傅立葉算法(FFT)，返回向量x的512點(diǎn)離散傅立葉變換(DFT)，當(dāng)x是一個矩陣時，fft返回矩陣的每一列的傅立葉變換。（2）X=fft(x,n)使用快速傅立葉算法(FFT)，返回向量x的n點(diǎn)DFT，如果x長度小于n，在x的后端加0使長度等于n。如果x長度大于n，在x的后端截斷使長度等于n。當(dāng)x是一個矩陣時，列的長度按同樣的規(guī)則調(diào)整為n。（3）X=fft(x,[],dim)和X=fft(x,n,dim)：按維數(shù)參數(shù)dim提供跨維的FFT操作。（4）x=ifft(X)：是向量X的512點(diǎn)離散傅立葉反變換(IDFT)。其它與fft()函數(shù)相同。第5章快速傅立葉變換（FFT）5.3實現(xiàn)FFT的常用MATLAB函數(shù)5.3.2fftshift()、ifftshift()fftshift(X)函數(shù)是針對頻域的，將FFT后的頻譜函數(shù)X的直流分量移到頻譜中心。ifftshift()函數(shù)是fftshift()函數(shù)的相反操作，其語法與之類似。

當(dāng)X的長度為偶數(shù)時，ifftshift()函數(shù)與fftshift()函數(shù)的作用相同，即連續(xù)使用2次fftshift()函數(shù)與使用fftshift()函數(shù)后再使用ifftshift()函數(shù)的作用相同。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.1三種卷積的比較1.用途在用途方面，3種卷積的異同如下：（1）周期卷積用于周期相同的兩個周期序列。DFS使用周期卷積。（2）循環(huán)卷積用于有限長的兩個非周期序列。DFT使用循環(huán)卷積。（3）線性卷積可用于有限、無限長，周期、非周期序列。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.1三種卷積的比較2.對序列長度的要求3種卷積對序列長度的要求如下：（1）線性卷積的求和運(yùn)算對參與卷積的兩個序列無任何要求。線性卷積的求和范圍由兩個序列的長度和所在的區(qū)間決定，區(qū)間從負(fù)無窮大到正無窮大。（2）而周期卷積、循環(huán)卷積要求兩個序列是長度相同：周期卷積要求兩個序列是長度相同的周期序列。循環(huán)卷積要求兩個序列是長度相同的非周期序列。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.1三種卷積的比較3.移位方法3種卷積的移位方法如下：（1）線性卷積與周期卷積采用線性移位。（2）而循環(huán)卷積采用N點(diǎn)循環(huán)移位，因它與N有關(guān)，也叫做N點(diǎn)循環(huán)卷積。（3）周期卷積等同于兩個周期序列在一個周期上的線性卷積計算，而循環(huán)卷積把看作排列在N等分的圓周上，循環(huán)移位就相當(dāng)于序列在圓周上循環(huán)移動，故稱為圓周移位。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.1三種卷積的比較4.卷積結(jié)果比較3種卷積結(jié)果比較如下：（1）線性卷積所得序列的長度為(N1+N2-1)，由參與卷積的兩個序列的長度確定，兩個N點(diǎn)序列的線性卷積將導(dǎo)致一個更長的序列(2N-1)。（2）而循環(huán)卷積與周期卷積一樣將區(qū)間限制在0≤n≤N-1，結(jié)果仍為N點(diǎn)序列。（3）循環(huán)卷積與線性卷積的結(jié)果是不同的，但循環(huán)卷積對應(yīng)于DFT，可以直接使用快速傅立葉運(yùn)算FFT。線性卷積如果使用FFT實現(xiàn)快速卷積，需要滿足一定條件。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.2用FFT計算圓周卷積和周期卷積及MATLAB實現(xiàn)1.用FFT計算圓周卷積（循環(huán)卷積）（1）將兩個序列補(bǔ)0，使其長度都為點(diǎn)。（2）根據(jù)時域離散圓周卷積定理：

*（3）對其乘積進(jìn)行反變換，即可用FFT完成圓周（循環(huán)）卷積，其長度為N。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.2用FFT計算圓周卷積和周期卷積及MATLAB實現(xiàn)1.用FFT計算圓周卷積（循環(huán)卷積）*

【例5-4-1】用FFT計算圓周卷積已知序列x1=[1111]，x2=[12345]，求其圓周卷積

解：根據(jù)上述分析，得出MATLAB程序如下：第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.2用FFT計算圓周卷積和周期卷積及MATLAB實現(xiàn)

x1=[1111];x2=[12345];N=length(x1)+length(x2)-1;n=0:N-1;X1=fft(x1,N);X2=fft(x2,N);Y=X1.*X2;y=ifft(Y,N);ystem(n,y);title('y(n)=IFFT(X1.*X2)');axis([-1,6,0,15]);第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.2用FFT計算圓周卷積和周期卷積及MATLAB實現(xiàn)

運(yùn)行程序，結(jié)果與例4-4-1相同，圖像如圖5-4-2所示。y=1.00003.00006.000010.000014.000012.00009.00005.0000第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.2用FFT計算圓周卷積和周期卷積及MATLAB實現(xiàn)

2.用FFT求周期卷積求周期卷積，同樣可以從先用傅立葉變換求出頻譜函數(shù)，然后對兩個頻譜函數(shù)的乘積進(jìn)行傅立葉反變換，求出周期卷積。【例5-4-2】用FFT求周期卷積。用FFT求例4-2-4中兩序列的周期卷積。解：程序如下：第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.2用FFT計算圓周卷積和周期卷積及MATLAB實現(xiàn)

x1=[111100];x2=[123450];N=6;n=0:N-1;X1=fft(x1,N);X2=fft(x2,N);Y=X1.*X2;y=ifft(Y,N);ysubplot(311);stem(n,x1);title('x1=[111100]');axis([-1,6,0,1.2]);subplot(312);stem(n,x2);title('x2=[123450]');axis([-1,6,0,5]);subplot(313);stem(n,y);title('y(n)=IDFS(X1.*X2)');axis([-1,6,0,15]);第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.2用FFT計算圓周卷積和周期卷積及MATLAB實現(xiàn)

運(yùn)行程序，結(jié)果與例4-2-3相同，圖像如圖5-4-3所示。y=1086101412，結(jié)果與圖4-2-7相同。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.3用FFT計算線性卷積及MATLAB實現(xiàn)1.用FFT計算線性卷積的條件、步驟用FFT運(yùn)算來求線性卷積的步驟如下：（1）對序列、補(bǔ)零，使長度L=N＋M－1，并且（k為整數(shù)），即：

第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.3用FFT計算線性卷積及MATLAB實現(xiàn)1.用FFT計算線性卷積的條件、步驟（2）用FFT計算的L點(diǎn)離散傅立葉變換、（3）計算（4）用IFFT計算的L點(diǎn)離散傅立葉變換得：第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.3用FFT計算線性卷積及MATLAB實現(xiàn)2.重疊相加法

重疊相加法是將待卷積的信號分割成長為M的若干段，每一段都可以和有限時寬單位取樣響應(yīng)作卷積，再將卷積后的各段重疊相加。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.3用FFT計算線性卷積及MATLAB實現(xiàn)3.重疊保留法重疊保留法的步驟：（1）對輸入數(shù)據(jù)重疊分段為L點(diǎn)，將N點(diǎn)補(bǔ)零為L點(diǎn)；（2）對每一段，計算L點(diǎn)循環(huán)卷積*（3）每段循環(huán)卷積輸出去掉前面N-1點(diǎn)只保留后面M點(diǎn)；（4）將每段M點(diǎn)輸出拼接構(gòu)成最終的線性卷積。第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.3用FFT計算線性卷積及MATLAB實現(xiàn)【例5-4-5】用重疊相加法和重疊保留法求線性卷積。設(shè)，，=[1,2,3,4]，對分段，分別采用重疊相加法（DFT長度為10點(diǎn)）和重疊保留法（DFT長度為7點(diǎn)）計算線性卷積：解：（1）重疊相加法：L=10，則M=L-N+1=7，需要把x(n)分成3段。=[3,5,7,9,11,13,15]，=[17,19,21,23,25,27,29]，=[31,33,35,0,0,0,0]第5章快速傅立葉變換（FFT）5.4用FFT計算卷積5.4.3用FFT計算線性卷積及MATLAB實現(xiàn)【例5-4-5】用重疊相加法和重疊保留法求線性卷積。

利用10點(diǎn)DFT可得每一段與的線性卷積：

=[3,11,26,50,70,90,110,113,97,60]=[17,53,110,190,210,230,250,239,195,116]=[31,95,194,293,237,140,0,0,0,0]將的最后N-1=3項與重疊部分相加，得到對應(yīng)的各項，最后輸出為：最開始的N-1=3項對應(yīng)=[3,11,26,5