快速傅里葉變換課件

1、快速傅里葉變換快速傅里葉變換快速傅里葉變換本章目錄直接計算DFT的問題及改進的途徑按時間抽取的基2-FFT算法 按頻率抽取的基2-FFT算法 快速傅里葉逆變換(IFFT)算法 Matlab實現(xiàn)2本章目錄直接計算DFT的問題及改進的途徑按時間抽取的基2-FFT算法 按頻率抽取的基2-FFT算法 快速傅里葉逆變換(IFFT)算法 Matlab實現(xiàn)24.1 引言 DFT在實際應用中很重要: 可以計算信號的頻譜、功率譜和線性卷積等。直接按DFT變換進行計算，當序列長度N很大時，計算量非常大，所需時間會很長,實時處理難以實現(xiàn)。1965年，圖基和庫利發(fā)表了機器計算快速傅立葉級數(shù)的一種算法論文后，很快形成了

2、快速計算DFT的計算機算法FFT。（Fast Fourier Transform)FFT并不是一種與DFT不同的變換，而是DFT的一種快速計算的算法。 34.2 直接計算DFT的問題及改進的途徑 DFT的運算量 設復序列x(n) 長度為N點，其DFT為k=0，N-1 （1）計算一個X(k) 值的運算量復數(shù)乘法次數(shù)： N復數(shù)加法次數(shù)： N1（2）計算全部N個X(k) 值的運算量復數(shù)乘法次數(shù)： N2復數(shù)加法次數(shù)： N(N1)4DFT運算量的結論N點DFT的復數(shù)乘法次數(shù)舉例NN2NN22464404941612816384864256 65 536 16256512 262 144 32102410

3、24 1 048 576 結論：當N很大時，其運算量很大，對實時性很強的信號處理來說，要求計算速度快，因此需要改進DFT的計算方法，以大大減少運算次數(shù)。 5 4.2.2 減少運算工作量的途徑 主要原理是利用系數(shù) 的以下特性對DFT進行分解： （2）對稱性 （1）周期性 （3）可約性 另外，64.3 按時間抽取的基2-FFT算法 算法原理按時間抽取基-2FFT算法與直接計算DFT運算量的比較按時間抽取的FFT算法的特點按時間抽取FFT算法的其它形式流程圖DIT-FFT(Decimation-In-Time)74.3.1 算法原理 設N2M，將x(n)按 n 的奇偶分為兩組： r =0，1， 則8

4、式中，X1(k)和X2(k)分別是x1(n)和x2(n)的N/2的DFT。另外，式中k的取值范圍是：0，1， ，N/21 。9因此， 只能計算出X(k)的前一半值。后一半X(k) 值， N/2 ， N/2 1， ，N-1 ？同理可得10因此可得后半部分X(k) 由前半部分X(k) k=0，1， ，N/21k=0，1， ，N/2111k=0，1， ，N/21結論：因此，只要求出2個N/2點的DFT，即X1(k)和X2(k)，再經過這種運算就可求出全部X(k)的值12新概念：蝶形運算蝶形運算式蝶形運算信號流圖符號 X1(k)X2(k)蝶形運算的運算量：每次蝶形含一次復數(shù)乘和兩 次復數(shù)加13以8點為

5、例第一次按奇偶分解以N=8為例，分解為2個4點的DFT，然后做8/2=4次蝶形運算即可求出所有8點X(k)的值。分解一次后所需的運算量2個N/2的DFTN/2蝶形14運算量比較復數(shù)乘法次數(shù)： N2復數(shù)加法次數(shù)： N(N1)復數(shù)乘法次數(shù)： 2*(N/2)2+N/2=N2/2+N/2復數(shù)加法次數(shù)： 2*(N/2)(N/21)+2*N/2=N2/2N點DFT的運算量 分解一次后所需的運算量2個N/2的DFTN/2蝶形：通過一次分解后，運算工作量減少了差不多一半。每次蝶形含一次復數(shù)乘和兩次復數(shù)加15進一步按奇偶分解 由于N2M，因而N/2仍是偶數(shù) ，可以進一步把每個N/2點子序列再按其奇偶部分分解為兩

6、個N/4點的子序列。 以N/2點序列x1(r)為例 則有 k=0,1, 16且k=0,1, 由此可見，一個N/2點DFT可分解成兩個N/4點DFT。 同理，也可對x2(n)進行同樣的分解，求出X2(k)。 17以8點為例第二次按奇偶分解概念：信號流圖18算法原理 對此例N=8，最后剩下的是4個N/4= 2點的DFT，2點DFT也可以由蝶形運算來完成。N=2這說明，N=2M的DFT可全部由蝶形運算來完成。因此：N必須是2的整數(shù)次冪. “基2”蝶形運算19以8點為例第三次按奇偶分解N=8按時間抽取法FFT信號流圖 x(n)抽取X(k)順序DIT-FFT(Decimation-In-Time)FFT

7、算法204.3.2 按時間抽取基2-FFT算法與直接計算DFT運算量的比較 由按時間抽取法FFT的信號流圖可知，當N=2M時，共有 級蝶形運算；每級都由 個蝶形運算組成，而每個蝶形有 次復乘、 次復加，因此每級運算都需 次復乘和 次復加。 MN/2 N/2 12N21FFT算法中，這樣 級運算總共需要： M復數(shù)乘法： 復數(shù)加法： 直接DFT算法運算量 復數(shù)乘法： 復數(shù)加法： N2N(N1)直接計算DFT與FFT算法的計算量之比為MN=2M22FFT算法與直接DFT算法運算量的比較NN2計算量之比M NN2計算量之比M 2414.012816 38444836.641644.025665 536

8、1 02464.0864125.4512262 1442 304113.816256328.010241 048 5765 120204.83210288012.820484 194 30411 264372.464404919221.42324N=1024; M=80;x=1:M,zeros(1,N-M);t=cputime;y1=fft(x,N);time_fft=cputime-t;t1=cputime;y2=dft(x,N);time_dft=cputime-t1;FFT算法與直接DFT算法運算量的比較time_dft=6.0290time_fft=0.010025L=1L=2L=3倒

9、序4.3.3 按時間抽取的FFT算法的特點26同址運算（原位運算）序列的逆序排列蝶形運算兩節(jié)點間的距離相同旋轉因子節(jié)點間的距離 (旋轉因子）的確定27同址運算（原位運算） 某一列任何兩個節(jié)點k 和j 的節(jié)點變量進行蝶形運算后，得到結果為下一列k、j兩節(jié)點的節(jié)點變量，而和其他節(jié)點變量無關。這種原位運算結構可以節(jié)省存儲單元，降低設備成本。運算前運算后例同址運算（原位運算）28觀察原位運算規(guī)律29序列的逆序排列 由于 x(n) 被反復地按奇、偶分組，所以流圖輸入端的排列不再是順序的，但仍有規(guī)律可循： 因為 N=2M ， 對于任意 n（0n N-1)，可以用M個二進制碼表示為： n 反復按奇、偶分解時

10、，即按二進制碼的“0” “1” 分解。序列的逆序排列30倒位序的樹狀圖（N=8） 31碼位的倒位序(N=8) 自然順序 n二進制數(shù)倒位序二進制數(shù)倒位序順序數(shù)0000000010011004201001023011110641000011510110156110011371111117IJ規(guī)律：最左端加1，向右進位倒序32倒位序的變址處理（N=8）I=J 不換IJ 不換IX= czt(x, M, W, A)其中，x是待變換的時域信號x(n)，其長度為N，M是變換長度，W確定變換的步長，A確定變換的起點。若M= N，A= 1，則CZT變成DFT。754.8.1 用FFT計算實信號的快速線性卷積設一

11、離散線性移不變系統(tǒng)的沖激響應為 ,其輸入信號為 .其輸出為 .并且 的長度為N點, 的長度為M點,計算其線性卷積。76用FFT算 的步驟： 77FFTFFTIFFTxx(n)h(n)y(n)X(k)H(k)Y(k)流程圖程序參考第三章幻燈片784.8.2 用FFT進行譜分析的Matlab實現(xiàn)例4.8.2 設模擬信號 ，以 t= 0.01n (n=0: N-1) 進行取樣，試用fft函數(shù)對其做頻譜分析。N分別為：(1) N=10；(2) N=50；(3) N=100；(2) N=1024。 程序清單如下 %計算N=10的FFT并繪出其幅頻曲線N=10;n=0:N-1;t=0.01*n;q=n*2

12、*pi/N;x=2*sin(20*pi*t)+5*cos(40*pi*t);y=fft(x,N);figure(1)subplot(2,2,1)plot(q,abs(y)title(FFT N=10)79例4.8.2 程序清單%計算N=50的FFT并繪出其幅頻曲線N=50;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(20*pi*t)+5*cos(40*pi*t);y=fft(x,N);figure(1)subplot(2,2,2)plot(q,abs(y)title(FFT N=50)80%計算N=100的FFT并繪出其幅頻曲線N=100;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(20*pi*t)+5*cos(40*pi*t);y=fft(x,N);figure(1)subplot(2,2,3)plot(q,abs(y)titl