快速傅里葉變換(FFT)

第三章快速傅里葉變換FFT:FastFourierTransform1965年，Cooley,Tukey《機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法》學(xué)習(xí)目標(biāo)理解按時(shí)間抽選的基-2FFT算法的算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)理解按頻率抽選的基-2FFT算法的算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)理解IFFT算法了解混合基、分裂基和基-4FFT算法了解CZT算法理解線性卷積的FFT算法及分段卷積方法一、直接計(jì)算DFT的問(wèn)題及改進(jìn)途徑運(yùn)算量復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X(k)NN–1N個(gè)X(k)(N點(diǎn)DFT)N2N(N–1)實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2一個(gè)X(k)4N2N+2(N–1)=2(2N–1)N個(gè)X(k)(N點(diǎn)DFT)4N22N(2N–1)FFT算法分類(lèi):時(shí)間抽選法

DIT:Decimation-In-Time頻率抽選法

DIF:Decimation-In-Frequency二、按時(shí)間抽選的基-2FFT算法1、算法原理設(shè)序列點(diǎn)數(shù)N=2L，L為整數(shù)。假設(shè)不滿足，那么補(bǔ)零將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱(chēng)基-2FFT算法。那么x(n)的N 點(diǎn)DFT:再利用周期性求X(k)的后半局部分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)N/2點(diǎn)DFT(N/2)2N/2(N/2–1)兩個(gè)N/2點(diǎn)DFTN2/2N(N/2–1)一個(gè)蝶形12N/2個(gè)蝶形N/2N總計(jì)運(yùn)算量減少了近一半N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4同理：其中：這樣逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1

2、運(yùn)算量當(dāng)N=2L時(shí)，共有L級(jí)蝶形，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：比較DFT圖直接計(jì)算DFT與FFT算法所需乘法次數(shù)的比較3、算法特點(diǎn)1〕原位計(jì)算m表示第m級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)2〕倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n2000110110011013〕蝶形運(yùn)算對(duì)N=2L點(diǎn)FFT，輸入倒位序，輸出自然序，第m級(jí)運(yùn)算每個(gè)蝶形的兩節(jié)點(diǎn)距離為2m–1第m級(jí)運(yùn)算：蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為k值，表示成L位二進(jìn)制數(shù)，左移L–

m位，把右邊空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。

4〕存儲(chǔ)單元輸入序列x(n):N個(gè)存儲(chǔ)單元系數(shù)：N/2個(gè)存儲(chǔ)單元4、DIT算法的其他形式流圖輸入倒位序輸出自然序輸入自然序輸出倒位序輸入輸出均自然序相同幾何形狀輸入倒位序輸出自然序輸入自然序輸出倒位序

三、按頻率抽選的基-2FFT算法1、算法原理設(shè)序列點(diǎn)數(shù)N=2L，L為整數(shù)。將X(k)按k的奇偶分組前，先將輸入x(n)按n的順序分成前后兩半：按k的奇偶將X(k)分成兩局部：令那么X(2r)和X(2r+1)分別是x1(n)和x2(n)的N/2點(diǎn)DFT，記為X1(k)和X2(k)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)同理：其中：逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,12、算法特點(diǎn)1〕原位計(jì)算-1L級(jí)蝶形運(yùn)算，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形結(jié)構(gòu)：

m表示第m級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)2〕蝶形運(yùn)算對(duì)N=2L點(diǎn)FFT，輸入自然序，輸出倒位序，兩節(jié)點(diǎn)距離：2L-m=N/2m第m級(jí)運(yùn)算：蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為k值，表示成L位二進(jìn)制數(shù)，左移m-1位，把右邊空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。3、DIT與DIF的異同根本蝶形不同DIT:先復(fù)乘后加減DIF:先減后復(fù)乘運(yùn)算量相同都可原位運(yùn)算DIT和DIF的根本蝶形互為轉(zhuǎn)置四、線性調(diào)頻z變換〔CZT)算法FFT不適用于：只研究信號(hào)的某一頻段，要求對(duì)該頻段抽樣密集，提高分辨率；研究非單位圓上的抽樣值；需要準(zhǔn)確計(jì)算N點(diǎn)DFT，且N為大的素?cái)?shù)；等等。CZT算法：對(duì)z變換采用螺線抽樣，chirp-z變換 線性調(diào)頻z變換1、算法原理

N點(diǎn)有限長(zhǎng)序列，其z變換：沿z平面上的一段螺線作等分角抽樣，抽樣點(diǎn)zk：其中：M為要分析的復(fù)頻譜點(diǎn)數(shù)則抽樣點(diǎn)：：起始抽樣點(diǎn)的矢量半徑長(zhǎng)度：起始抽樣點(diǎn)的相角：相鄰抽樣點(diǎn)的角度差：逆時(shí)針：順時(shí)針：螺線的伸展率W0>1：螺線內(nèi)縮W0<1：螺線外伸當(dāng)W0=1，那么表示半徑為A0的一段圓弧假設(shè)又有A0=1，那么表示單位圓上的一段圓弧若又有，M=N，即為序列的DFT。

求抽樣點(diǎn)處的z變換：NM次復(fù)乘(N-1)M次復(fù)加2、CZT的實(shí)現(xiàn)步驟及運(yùn)算量的估算1)選擇，且2)形成L點(diǎn)序列g(shù)(n)：(3N)求其L點(diǎn)FFT：(L/2*log2L)

3〕形成L點(diǎn)序列h(n):求其L點(diǎn)FFT:(L/2*log2L)(2N)4〕求乘積(M)(L)5〕求L點(diǎn)IFFT的q(k)(L/2*log2L)6〕求得抽樣點(diǎn)的z變換:總運(yùn)算量:3、CZT算法的優(yōu)點(diǎn)N，M可為任意數(shù)，可不等當(dāng)，，時(shí)，CZT=DFT，解決了N為素?cái)?shù)的快速算法問(wèn)題z0任意，從任意頻率開(kāi)始，便于窄帶高分辨率分析周線可以是螺線，而不一定是圓弧任意，易調(diào)整頻率分辨率五、利用DFT(FFT)對(duì)模擬信號(hào)作頻譜分析信號(hào)的頻譜分析：計(jì)算信號(hào)的傅里葉變換1、頻率響應(yīng)的混疊失真及參數(shù)的選擇同時(shí)提高信號(hào)最高頻率和頻率分辨率，需增加采樣點(diǎn)數(shù)N。信號(hào)最高頻率與頻率分