快速傅里葉變換和頻域分析

1、快速傅里葉變換和頻域分析 4-1 引言頻域分析：一種有效的工具DFT:問題：一、直接計算DFT的問題第四章 快速傅里葉變換 4-2 直接計算DFT的起源和改善DFT運算效率的途徑設(shè)二、改善DFT運算效率的基本途徑第四章 快速傅里葉變換 4-2 直接計算DFT的起源和改善DFT運算效率的途徑2長序列分解Decimation-in-Time (DIT)Decimation-in-Frequency (DIF)第四章 快速傅里葉變換 4-2 直接計算DFT的起源和改善DFT運算效率的途徑一、算法原理?第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)代入

2、(4-4)式第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)可見：?由(4-7)式第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)利用 的周期性，第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)代入(4-7)式，有:(4-10)同理有，(4-11)歸納起來有第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)可見，上述運算可用下列蝶形信號流圖表示:第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算

3、法(Cooley-Tukey算法)圖 4-1 蝶形運算流圖符號例：N=8N/2-DFTN/2-DFT 第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)計算量分析：相比N-DFT的運算量減小了一半。第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)2-DFT：可見僅需計算“+/-”運算。第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)例：N=8 (P129)第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)圖4

4、-5 N=8時的按頻率抽取FFT運算流圖例：N=2v _(P130)第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)圖4-5 N點基-2FFT的級迭代過程二、運算量比較1.DIT-FFT：N=2第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法) 由圖4-6可見，2. DFT3. DIT-FFT的運算效率三、DIT-FFT算法的特點1. 原位運算(In-place)第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)3. 輸入序列的序號及整序規(guī)律由圖4-5可見

5、，輸入x(n)：亂序的 如何做到？ 整序輸出X(k)：順序的第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)(1) 亂序的原因正好為DIT-FFT的輸入正序反序例：N=8第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)(2) 整序的規(guī)律四、DIT-FFT算法的若干變體詳見:圖4-11圖4-14第四章 快速傅里葉變換 4-3 按時間抽取(DIT)的FFT算法(Cooley-Tukey算法)一、算法原理將X(n)，0 n N-1 按順序分為前后兩半k=0,1,N-1(4-23)注意：兩個和式并不是 N/

6、2-DFT第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)所以，式(4-23)可改寫為(4-24)可按k的奇偶取值將X(k)分為兩部分：第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)(4-25)(4-26)第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)顯然，若令則有（式(4-25)(4-26)分別變?yōu)椋┑谒恼?快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)可見，按k為奇偶分解按頻率抽取第四章 快速傅里葉變換 4-4

7、 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)例：N=8，DIF的分解過程（見圖4-16）P.137第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)（顯然與DIT-FFT算法的分解類似）N/2點DFTN/2點DFTDIF-FFT算法上述分解過程可繼續(xù)下去，直至分解次/步后變成求 N/2 個 2-DFT 為止。例：N=8，DIF-FFT算法流圖 圖4-18，P.138注意:第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)依然保留（為了算法結(jié)構(gòu)上的統(tǒng)一）二、DIF-FFT與DIT-FFT的

8、比較圖4-18 N=8,DIF-FFT算法流圖第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)圖4-5 N=8,DIT-FFT算法流圖第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)1. 二者的區(qū)別 (1) 輸入與輸出DIF：順序 反序DIT：反序 順序(2) 蝶形運算第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)DIT：先相乘，后加減DIF：先加減，后相乘2. 二者的相似之處(1)分解過程DIF：列 每列N/2個蝶形運算DIT：列 同上 同上(2)原位運

9、算（所有運算均由蝶形運算構(gòu)成）3. 二者關(guān)系DIF-FFTDIT-FFT轉(zhuǎn)置第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)三、逆DFT的快速算法(IFFT)1. 算法一：比較IDFT與DFT，可見FFTIFFT第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)DIT-FFTDIF-IFFTDIF-FFTDIT-IFFT(1)(2)例：N=8，DIT-IFFT算法流圖圖4-19，P.138第四章 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)2. 算法二優(yōu)點：第四章

10、 快速傅里葉變換 4-4 按頻率抽取(DIF)的FFT算法(Sande-Tukey算法)四、DIF-FFT算法的若干變體DIF-FFTDIT-FFT轉(zhuǎn)置變體變體轉(zhuǎn)置(1)通過補零，使序列長度=2 基-2 FFT一、算法原理(2)N=ML（復(fù)合數(shù)） 統(tǒng)一的FFT算法(3)NML（素數(shù)） Chirp-Z 變換(CZT)處理方法：N-DFTN如果N-DFTM個L-DFTML2L個M-DFTLM2減少了運算第四章 快速傅里葉變換 4-5 N為復(fù)合數(shù)的FFT算法統(tǒng)一的FFT算法為此，令n=Mn1+n0 , n0=0,1,M-1 列號 n1=0,1,L-1 行號第四章 快速傅里葉變換 4-5 N為復(fù)合數(shù)的

11、FFT算法統(tǒng)一的FFT算法x(n)x( n1 , n0 )同理，對DFT的輸出X(k)做類似的處理：令 k=Lk1+k0k0=0,1,L-1 n1k1=0,1,M-1 n0第四章 快速傅里葉變換 4-5 N為復(fù)合數(shù)的FFT算法統(tǒng)一的FFT算法X(k)X( k1 , k0 )x(Mn1+n0)=110nkLW=01nkMW=第四章 快速傅里葉變換 4-5 N為復(fù)合數(shù)的FFT算法統(tǒng)一的FFT算法一列一列求DFT旋轉(zhuǎn)因子一行一行求DFT第四章 快速傅里葉變換 4-5 N為復(fù)合數(shù)的FFT算法統(tǒng)一的FFT算法式中二、運算步驟第四章 快速傅里葉變換 4-5 N為復(fù)合數(shù)的FFT算法統(tǒng)一的FFT算法例：N=1

12、2=43, M=4 , L=3 算法流圖：圖4-20,詳見(4-38) P.142第四章 快速傅里葉變換 4-5 N為復(fù)合數(shù)的FFT算法統(tǒng)一的FFT算法三、基數(shù)（指特定的分解）1. N=2基2 FFT算法2. N2N=r1,r2,rM M級r1,r2, rM點DFT 混合基算法r1=r2=rM N= rM M級r-DFT 基-r FFT算法比如：a) N=2M 基-2 FFT b) N=4M 基-4 FFT第四章 快速傅里葉變換 4-5 N為復(fù)合數(shù)的FFT算法統(tǒng)一的FFT算法四、運算量估算(1) M個L-DFT： ML2=NL ML(L-1)=N(L-1)(2) 乘N個 因子： N(3) L個

13、M-DFT：LM2=NM LM(M-1)=N(M-1)總運算量： NL+N+NM=N(L+M+1) N2 N(L-1)+N(M-1)=N(L+M-2) 50CZT優(yōu)于直接計算)第四章 快速傅里葉變換 4-8 線性調(diào)頻 Z 變換 (Chirp-Z Transform)五、CZT算法的特點 2) N,M均可為質(zhì)數(shù) 任意情況3) 取樣起始點z0任選： 4) 可任意取值 的角間隔（頻率）任意頻率分辨率可變進(jìn)行窄帶學(xué)分辨分析第四章 快速傅里葉變換 4-8 線性調(diào)頻 Z 變換 (Chirp-Z Transform)DFT的推廣第四章 快速傅里葉變換 4-9 細(xì)化FFT算法 (Zoom FFT or ZFFT)一、問題提出 1) FFT/DFT：分辨率 fN=fs/N ， (0 fs)第四章 快速傅里葉變換 4-9 細(xì)化FFT算法 (Zoom FFT or ZFFT)二、算法原理 (詳見圖4-30/P157)Zoom FFT第四章 快速傅里葉變換 4-10 FFT的應(yīng)用一、利用FFT求卷積快速卷積 第四章 快速傅里葉變換 4-10 FFT的應(yīng)用二、利用FFT求相關(guān)快速相關(guān) 第四章 快速傅