數(shù)字信號(hào)處理快速變換

第四章快速傅里葉變換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算法理解線(xiàn)性卷積的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ù)。若不滿(mǎn)足，則補(bǔ)零將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱(chēng)基-2FFT算法。則x(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ù)加法：比較DFT3、算法特點(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)算：第m級(jí)蝶形運(yùn)算中，每個(gè)蝶形兩節(jié)點(diǎn)中的上節(jié)點(diǎn)的行號(hào)為k，將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)置四、IFFT算法比較：IDFT:DFT:共軛FFT共軛乘1/N直接調(diào)用FFT子程序計(jì)算IFFT的方法：直接DFT方法/CZT方法：當(dāng)要求準(zhǔn)確的N點(diǎn)DFT，且N是素?cái)?shù)時(shí)五、N為復(fù)合數(shù)的FFT算法

——混合基算法基-2FFT算法：補(bǔ)零使?jié)M足混合基FFT算法：N是復(fù)合數(shù)1、整數(shù)的多基多進(jìn)制表示形式

（1）二進(jìn)制：

（2）r進(jìn)制：

（3）多基多進(jìn)制（混合基）：

例：

2、的快速算法

行列行序號(hào)列序號(hào)行列行變量列變量的DFT

算法

(1)改寫(xiě)成

做個(gè)點(diǎn)DFT，得為參量，輸入變量，輸出變量的點(diǎn)DFT(3)N個(gè)（旋轉(zhuǎn)因子）做個(gè)點(diǎn)DFT，得為參量，輸入變量，輸出變量的點(diǎn)DFT(5)整序

例當(dāng)N為高組合素?cái)?shù)時(shí)：

個(gè)

點(diǎn)DFT，乘以旋轉(zhuǎn)因子

個(gè)

點(diǎn)DFT個(gè)

點(diǎn)DFT，乘以旋轉(zhuǎn)因子個(gè)

點(diǎn)DFT，乘以旋轉(zhuǎn)因子L級(jí)r點(diǎn)DFT稱(chēng)基

算法，

基

算法

混合基算法（基算法）

基算法混合基算法的運(yùn)算量不計(jì)譯序、整序工作量（2）乘N個(gè)旋轉(zhuǎn)因子

復(fù)乘

N總計(jì)：

（1）個(gè)點(diǎn)DFT復(fù)乘復(fù)加

（3）個(gè)點(diǎn)DFT

復(fù)乘復(fù)加

混合基節(jié)省的運(yùn)算量

次乘N個(gè)旋轉(zhuǎn)因子個(gè)

點(diǎn)DFT個(gè)

點(diǎn)DFT

個(gè)

點(diǎn)DFT六、基-4FFT算法

當(dāng)混合基FFT算法中

時(shí)，

即為基-4FFT算法，n、k都為4進(jìn)制數(shù)個(gè)

點(diǎn)DFT

乘N個(gè)旋轉(zhuǎn)因子個(gè)

點(diǎn)DFT

乘N個(gè)旋轉(zhuǎn)因子個(gè)

點(diǎn)DFT1)的4點(diǎn)DFT的四進(jìn)制數(shù)按二進(jìn)制倒位序排列成

3)的4點(diǎn)DFT一個(gè)4點(diǎn)FFT不需乘法，只需3次乘旋轉(zhuǎn)因子（除外）而基-2FFT基-4FFT運(yùn)算量：每級(jí)有N/4個(gè)4點(diǎn)FFT，共L級(jí)（L-1級(jí)要乘旋轉(zhuǎn)因子）七、分裂基FFT算法對(duì)偶序號(hào)使用基-2FFT算法，對(duì)奇序號(hào)使用基-4FFT算法，稱(chēng)分裂基FFT算法

針對(duì)

的算法中具有最少乘法次數(shù)，且同址運(yùn)算。將分成三個(gè)序列。

偶序號(hào)的點(diǎn)DFT

奇序號(hào)的點(diǎn)DFT

利用周期性

分成四段：的第一級(jí)分解得4個(gè)分裂基同樣對(duì)、、作進(jìn)一步分解。和的第二級(jí)分解分別是基-4的4點(diǎn)DFT。的第二級(jí)分解得2個(gè)分裂基。一個(gè)基-4的4點(diǎn)DFT和2個(gè)基-2的4點(diǎn)DFT?；?2，基-4等基本碟形結(jié)都沒(méi)有乘法，只有每個(gè)分裂基有兩次復(fù)乘。運(yùn)算量：

分裂基碟形數(shù)：

八、線(xiàn)性調(diào)頻z變換（CZT)算法FFT不適用于：只研究信號(hào)的某一頻段，要求對(duì)該頻段抽樣密集，提高分辨率；研究非單位圓上的抽樣值；需要準(zhǔn)確計(jì)算N點(diǎn)DFT，且N為大的素?cái)?shù)；等等。CZT算法：對(duì)z變換采用螺線(xiàn)抽樣，chirp-z變換 線(xiàn)性調(diào)頻z變換1、算法原理

N點(diǎn)有限長(zhǎng)序列，其z變換：沿z平面上的一段螺線(xiàn)作等分角抽樣，抽樣點(diǎn)zk：其中：M為要分析的復(fù)頻譜點(diǎn)數(shù)則抽樣點(diǎn)：：起始抽樣點(diǎn)的矢量半徑長(zhǎng)度：起始抽樣點(diǎn)的相角：相鄰抽樣點(diǎn)的角度差：逆時(shí)針：順時(shí)針：螺線(xiàn)的伸展率W0>1：螺線(xiàn)內(nèi)縮W0<1：螺線(xiàn)外伸當(dāng)W0=1，則表示半徑為A0的一段圓弧若又有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)始，便于窄帶高分辨率分析周線(xiàn)可以是螺線(xiàn)，而不一定是圓弧任意，易調(diào)整頻率分辨率九、線(xiàn)性卷積和線(xiàn)性相關(guān)的FFT算法1、線(xiàn)性卷積的FFT算法需運(yùn)算量：若系統(tǒng)滿(mǎn)足線(xiàn)性相位，即：則需運(yùn)算量：若L點(diǎn)x(n)，M點(diǎn)h(n)，則直接計(jì)算其線(xiàn)性卷積y(n)FFT法：以圓周卷積代替線(xiàn)性卷積1)

H(k)=FFT[h(n)]N/2*log2N4)

y(n)=IFFT[Y(k)]N/2*log2N3)