基時域頻域FFT算法

基時域頻域FFT算法第1頁，課件共33頁，創(chuàng)作于2023年2月4點序列{2，3，3，2}DFT的計算復雜度復數加法N(N-1)復數乘法N

2如何提高DFT的運算效率?問題的提出第2頁，課件共33頁，創(chuàng)作于2023年2月一般性DFT:直接計算的計算量：N-1復數乘法N對N個不同X[m]復數加法N(N-1)復數乘法N2對一固定的m復數加法如計算1024點DFT：復數乘法次數：N2=10242=220=1048576第3頁，課件共33頁，創(chuàng)作于2023年2月解決問題的思路1.將長序列DFT分解為短序列的DFT2.利用旋轉因子的周期性、對稱性、可約性。第4頁，課件共33頁，創(chuàng)作于2023年2月1)周期性(periodicity)2)復共軛對稱性(complexconjugate)3)當N是偶數時的性質第5頁，課件共33頁，創(chuàng)作于2023年2月解決問題的方法將時域序列逐次分解為一組子序列，利用旋轉因子的特性，由子序列的DFT來實現整個序列的DFT?；?時間抽取(Decimationintime)FFT算法基2頻率抽取(Decimationinfrequency)FFT算法第6頁，課件共33頁，創(chuàng)作于2023年2月3.1基2時域抽取FFT算法算法推導:N=2M時域抽取(Decimationintime)]a][1kx][2lx][][21lxkxa+[][21lxkxa--1(一)算法原理基本蝶形(butterfly)第7頁，課件共33頁，創(chuàng)作于2023年2月算法推導:N=2M時域抽取第8頁，課件共33頁，創(chuàng)作于2023年2月例：]0[X]1[X-11]0[x]1[x2點FFT流圖N=2基2時域FFT流圖的推導第9頁，課件共33頁，創(chuàng)作于2023年2月N=4時域基2FFT流圖的推導-1X[2]X[3]-12點DFT2點DFTx[0]x[3]x[1]x[2]X[0]X[1]2點DFT04W14Wx[0]x[3]x[1]x[2]X[3]X[1]X[2]X[0]-1-1-1-1第10頁，課件共33頁，創(chuàng)作于2023年2月N=8基2時域FFT流圖的推導08W18W28W38W4點DFT4點DFTX[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[2]x[4]x[1]x[3]x[5]x[7]-1-1-1-1第11頁，課件共33頁，創(chuàng)作于2023年2月08W18W28W38WX[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]04W14W04W14W-1-1-1-1-1-1-1-1-1-1-1-18點FFT流圖第三級第一級第二級第12頁，課件共33頁，創(chuàng)作于2023年2月(二)算法工作量a][1kx][2lx][][21lxkxa+][][21lxkxa--1一個蝶形計算量：復數乘法1，復數加法2復數乘法:N，NNM2log22=復數加法：N=2M時，分解級數為M，每級蝶形數N/2計算1024點復數乘法次數：DFT：N2=1024

2=220=1048576；FFT：第13頁，課件共33頁，創(chuàng)作于2023年2月(三)流圖規(guī)律1)原位運算(In-placeComputations)a][1kx][2lx][][21lxkxa+][][21lxkxa--1優(yōu)點：節(jié)省存儲空間第14頁，課件共33頁，創(chuàng)作于2023年2月(三)流圖規(guī)律第二級的蝶形系數為，蝶形節(jié)點的距離為2。第一級的蝶形系數均為，蝶形節(jié)點的距離為1。第三級的蝶形系數為，蝶形節(jié)點的距離為4。第M級的蝶形系數為，蝶形節(jié)點的距離為N/2。2)FFT算法流圖旋轉因子規(guī)律第15頁，課件共33頁，創(chuàng)作于2023年2月3)倒序規(guī)律k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[010]x[111]01010101第16頁，課件共33頁，創(chuàng)作于2023年2月例：試利用N=4基2時間抽取的FFT流圖計算8點序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：根據基2時間抽取FFT算法原理，8點序列的DFTX[m]可由兩個4點序列的DFTX1[m]和X2[m]表達。如果按照序列x[k]序號的奇偶分解為x1[k]和x2[k]，則存在其中x1[k]={1,1,2,1}，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通過4點的FFT來計算。第17頁，課件共33頁，創(chuàng)作于2023年2月解：

X1[m]={5,-1,1,-1},X2[m]={1,-2+3j,1,-2-3j}利用上述公式，可得序列x[k]的DFTX[m]為X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}例：試利用N=4基2時間抽取的FFT流圖計算8點序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。第18頁，課件共33頁，創(chuàng)作于2023年2月3.2基2頻域抽取FFT算法頻域奇偶分組第19頁，課件共33頁，創(chuàng)作于2023年2月頻域奇偶分組當m=2r,或2r+1，得到：第20頁，課件共33頁，創(chuàng)作于2023年2月基2頻率抽取蝶形運算的信號流圖基2頻率抽取蝶形運算的信號流圖第21頁，課件共33頁，創(chuàng)作于2023年2月x[3]x[7]x[2]x[6]x[1]x[5]x[0]x[4]3NW-12NW-11NW-1-10NW4點DFT4點DFTX[0]X[6]X[2]X[4]X[1]X[3]X[5]X[7]基2頻率抽取8點信號流圖第22頁，課件共33頁，創(chuàng)作于2023年2月0NW1NW2NW3NW2點DFT-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW2NW2NW0NW-1-1-1-12點DFT2點DFT2點DFT基2頻率抽取8點信號流圖第23頁，課件共33頁，創(chuàng)作于2023年2月基2頻率抽取8點信號流圖第24頁，課件共33頁，創(chuàng)作于2023年2月3.3實序列的FFT算法(二)利用N點復序列的FFT，計算2N點實序列FFT(一)利用N點復序列的FFT計算兩個N點實序列FFT第25頁，課件共33頁，創(chuàng)作于2023年2月已知x

[k],h[k]是實序列，構造N點復序列y[k]=x

[k]+jh[k](一)利用N點復序列的FFT計算兩個N點實序列FFT所以第26頁，課件共33頁，創(chuàng)作于2023年2月(二)利用N點復序列的FFT，計算2N點實序列FFT已知y[k]是2N點實序列，希望用一個N點FFT計算其DFT時域抽取FFT算法：第27頁，課件共33頁，創(chuàng)作于2023年2月3.4IDFT的快速算法第28頁，課件共33頁，創(chuàng)作于2023年2月IDFT的快速算法步驟步驟(1)將X[m]取共軛(3)對(2)中結果取共軛并除以N第29頁，課件共33頁，創(chuàng)作于2023年2月例：已知x[k]={1,2,3,4}利用頻域抽樣流圖，計算12344-262j10-2-2+2j-2-2jDFT{x[k]}={10,-2+2j,-2,-2-2j}利用頻域基2-FFT流圖計算DFT第30頁，課件共33頁，創(chuàng)作于2023年2月{4,8,12,16}{4,16,12,8}利用FFT流圖計算IFFT第31頁，課件共33頁，創(chuàng)作于2023年2月M=4;N=51;n=-(N-1)/2:(N-1)/2;x=[ones(1,M+1),zeros(1,N-2*M-1),ones(1,M)];X=fft(x,N);subplot(2,1,1);stem(n,fftshift(x));