第5章 離散傅立葉變換與快速算法2(FFT)

1、15.2DFT的快速計(jì)算的快速計(jì)算(FFT)n一、一、DFT存在的問(wèn)題及改進(jìn)的途徑存在的問(wèn)題及改進(jìn)的途徑n二、戈澤爾算法二、戈澤爾算法n三、時(shí)域抽取基三、時(shí)域抽取基-2算法（庫(kù)利算法（庫(kù)利-圖基算法）圖基算法）n四、頻域抽取基四、頻域抽取基-2算法（桑德算法（桑德-圖基算法）圖基算法）n五、線性調(diào)頻五、線性調(diào)頻Z變換變換2nN點(diǎn)有限長(zhǎng)序列，其點(diǎn)有限長(zhǎng)序列，其DFT變換對(duì)為：變換對(duì)為：nn 可以看出，可以看出，變換與反變換變換與反變換的差別僅在于的差別僅在于 的指數(shù)符號(hào)和常數(shù)乘因子的指數(shù)符號(hào)和常數(shù)乘因子1/N。實(shí)際上：實(shí)際上：n 因而我們因而我們只討論只討論DFT正變換的運(yùn)算量正變換的運(yùn)算量，反

2、，反變換的運(yùn)算量是完全相同的。變換的運(yùn)算量是完全相同的。 )()(1)()()()(1010nRWkXNnxIDFTkRWnxkXDFTNNknkNNNnnkN：)(1)(*kXDFTNkXIDFT5.2.1DFT存在的問(wèn)題及改進(jìn)途徑存在的問(wèn)題及改進(jìn)途徑3n一般來(lái)說(shuō)一般來(lái)說(shuō) 和和 都是復(fù)數(shù)，都是復(fù)數(shù)，n每一個(gè)每一個(gè) 值的計(jì)算，需要值的計(jì)算，需要N次復(fù)數(shù)乘次復(fù)數(shù)乘法法以及（以及（N-1）次復(fù)數(shù)加法，次復(fù)數(shù)加法，n完成整個(gè)完成整個(gè)DFT運(yùn)算總需要運(yùn)算總需要 次復(fù)數(shù)乘次復(fù)數(shù)乘法法和和N（N-1）次復(fù)數(shù)加法次復(fù)數(shù)加法。)(nxnkNW)(kX2N10( )( )( )NnkNNnDFTX kx n W

3、Rk：DFT直接計(jì)算的運(yùn)算量4n復(fù)數(shù)運(yùn)算實(shí)際上是由實(shí)數(shù)運(yùn)算來(lái)完成的，如：復(fù)數(shù)運(yùn)算實(shí)際上是由實(shí)數(shù)運(yùn)算來(lái)完成的，如：n一次復(fù)數(shù)乘法需用：一次復(fù)數(shù)乘法需用：n四次實(shí)數(shù)乘法四次實(shí)數(shù)乘法n二次實(shí)數(shù)加法；二次實(shí)數(shù)加法；n一次復(fù)數(shù)加法則需：一次復(fù)數(shù)加法則需：n二次實(shí)數(shù)加法。二次實(shí)數(shù)加法。n整個(gè)整個(gè)DFT運(yùn)算總共需要：運(yùn)算總共需要：n4N2次實(shí)數(shù)乘法次實(shí)數(shù)乘法n 次次實(shí)數(shù)加法實(shí)數(shù)加法。)()()()()()()(dcjbajdbjcaBAbcadjcdabjdbjcaAB) 12(2) 1(222NNNNN5n上述統(tǒng)計(jì)與實(shí)際的運(yùn)算次數(shù)有上述統(tǒng)計(jì)與實(shí)際的運(yùn)算次數(shù)有少許出入少許出入，某些，某些因子不能按照一般的復(fù)

4、數(shù)來(lái)計(jì)算運(yùn)算量因子不能按照一般的復(fù)數(shù)來(lái)計(jì)算運(yùn)算量,如如:n當(dāng)當(dāng)N很大時(shí)，這種特例很小。很大時(shí)，這種特例很小。 n直接計(jì)算直接計(jì)算DFT運(yùn)算量是很可觀的運(yùn)算量是很可觀的:nN=8時(shí)，時(shí)，DFT需需64次復(fù)乘，次復(fù)乘，nN=1024時(shí)，時(shí)，DFT所需復(fù)乘為所需復(fù)乘為1 048 576次，次，n對(duì)對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理實(shí)時(shí)性很強(qiáng)的信號(hào)處理來(lái)說(shuō)，對(duì)來(lái)說(shuō)，對(duì)硬件的計(jì)算硬件的計(jì)算速度要求是太高速度要求是太高了。為了實(shí)用的需要，了。為了實(shí)用的需要，需要改需要改進(jìn)進(jìn)DFT的計(jì)算方法，減少運(yùn)算次數(shù)。的計(jì)算方法，減少運(yùn)算次數(shù)。1j10NW12/NNWjWNN4/6如何才能減少運(yùn)算量？仔細(xì)觀察如何才能減少運(yùn)算量？仔

5、細(xì)觀察DFTDFT的運(yùn)算就可看的運(yùn)算就可看出，其出，其變換系數(shù)變換系數(shù) 的具有如下的具有如下特性特性：（1 1） 的的對(duì)稱(chēng)對(duì)稱(chēng)性性（2 2） 的的周期周期性性 = = =（3 3） 的的可約可約性性 由此可得由此可得: :knNWknNWnkNknNWW*knNWknNWkNnNW)( )(NknNWknNWkmnmNknNWWmnkmNknNWW/nkNknNNkNnNWWW)()(/21NNW kNNkNWW)2/(變換基底的特性7n（1）利用）利用 的的對(duì)稱(chēng)性對(duì)稱(chēng)性，合并合并DFT運(yùn)算中某些項(xiàng)，并且可以計(jì)算反變換；運(yùn)算中某些項(xiàng)，并且可以計(jì)算反變換；n（2）由于）由于DFT的運(yùn)算量是與的運(yùn)

6、算量是與 成正成正比，利用比，利用 周期性周期性和和可約性可約性將長(zhǎng)序?qū)㈤L(zhǎng)序的的DFT分解為短序列分解為短序列的的DFT。nFFT基本可以分成基本可以分成兩大類(lèi)兩大類(lèi)n按時(shí)間抽取按時(shí)間抽取(Decimation-in-time,DIT）n按頻率抽取按頻率抽取(Decimation-in-frequency,DIF）。）。knNW2NknNWFFT的基本的基本出發(fā)點(diǎn)出發(fā)點(diǎn)85.2.1 戈澤爾算法戈澤爾算法戈澤爾算法是一個(gè)利用復(fù)變換基W的周期性減少運(yùn)算量的典型例子可以用于單離散頻點(diǎn)或少數(shù)任意離散頻點(diǎn)場(chǎng)合（如DTMF辨識(shí)）的有效計(jì)算910)(1010)()()()(NrrNkNNrkrNkNNNrk

7、rNWrxWrxWWrxkX10)()()()()(*)()(NrrnkNnxknNkrnuWrxnuWnxny為有限長(zhǎng)10)(10)()()()()(| )(NrrNkNNrrNkNNnkkXWrxrNuWrxny變形10推論：n如果構(gòu)造沖擊響應(yīng)h(n)為 的系統(tǒng)，則該系統(tǒng)對(duì)有限長(zhǎng)輸入在 時(shí)刻的響應(yīng)即為 。n 下圖給出了該系統(tǒng)的計(jì)算流圖：)()(nuWnhknNNn )(kX11n由上圖可以看出計(jì)算一個(gè)X(k)需要N次復(fù)乘和N次復(fù)加，即4N次實(shí)乘和4N次實(shí)加。n比直接計(jì)算DFT的運(yùn)算量稍大一些，但是卻避免了計(jì)算或存儲(chǔ)復(fù)系數(shù) 。n另外，立足于上面用卷積實(shí)現(xiàn)卷積實(shí)現(xiàn)DFT的方法，我們是有可能通過(guò)

8、某種變形將上面的運(yùn)算量減小一半。 knNW12)1 (*)/2cos(211)1 (*)1)(1 (111)(1211111zWzzNkzWzWzWzWzHkNkNkNkNkNkn注意到系統(tǒng)函數(shù)：13利用迭代實(shí)現(xiàn)了復(fù)因子的計(jì)算如果輸入序列是復(fù)數(shù)，由于系數(shù)是實(shí)數(shù)并且-1不必作乘法運(yùn)算，所以計(jì)算一個(gè)X(K)只需要2N次實(shí)數(shù)乘法和4N次實(shí)數(shù)加法。戈澤爾算法還有另外一個(gè)優(yōu)點(diǎn)是只需要將前饋環(huán)節(jié)中的復(fù)因子取共軛就可以計(jì)算X(N-K)，可以將運(yùn)算量再次減半。戈澤爾算法雖然比直接運(yùn)算有效的多，但是無(wú)論如何變形，其運(yùn)算量將仍然正比于N2。戈澤爾算法特點(diǎn)14n一、算法原理一、算法原理n 假設(shè)序列點(diǎn)數(shù)為假設(shè)序列點(diǎn)數(shù)

9、為 ,L為整數(shù)。如果為整數(shù)。如果不滿足，可以人為加上若干零值點(diǎn)，使不滿足，可以人為加上若干零值點(diǎn)，使之達(dá)到這一要求。這種之達(dá)到這一要求。這種N為為2的整數(shù)冪的的整數(shù)冪的FFT也稱(chēng)基也稱(chēng)基-2 FFT。n 將將 的序列按的序列按n的奇偶的奇偶分成兩組：分成兩組： n n r=0,1,N/2-1LN2LN2)() 12()()2(21rxrxrxrx5.2.2 DIT的的2MFFT(庫(kù)利庫(kù)利-圖基算法圖基算法)151202212021120)12(1202101010)()() 12()2()()()()(NrrkNkNNrrkNNrkrNNrrkNnNnnkNnNnnkNNnnkNWrxWWrx

10、WrxWrxWnxWnxWnxkX 為奇數(shù)為偶數(shù)16n利用利用 的的可約性可約性：n式中式中 與與 均為均為N/2點(diǎn)點(diǎn)DFT：knNW222222NNjNjNWeeW)()()()()(212011202/22/1kXWkXWrxWWrxkXkNNrNrrkNkNrkN kX1 kX21202/1202/221202/1202/11) 12()()()2()()(NrrkNNrrkNNrrkNNrrkNWrxWrxkXWrxWrxkX一分為二一分為二17n但但 以及以及 ， 都是都是N/2點(diǎn)的點(diǎn)的序列，即序列，即n而而 卻有卻有N點(diǎn)，因而點(diǎn)，因而計(jì)算全部計(jì)算全部的的 ，必須應(yīng)用必須應(yīng)用DFT隱

11、含的周期性擴(kuò)展：隱含的周期性擴(kuò)展： rxrx21, kX1 kX212, 1 , 0,Nkr kX kX)(2, )(22211kXkNXkXkNX定義的擴(kuò)展18n同時(shí)考慮到同時(shí)考慮到 的以下的以下性質(zhì)性質(zhì)n n這樣就可將這樣就可將 表達(dá)為前后兩部分：表達(dá)為前后兩部分：n kNWkNkNNNkNNWWWW2/2)(kX1221212( )( )( )0,1,12( )()( )( )0,1,1222kNNrrNNNX kX kW XkkNNNX kX rWXrX rW Xrr1920 上面的運(yùn)算可以抽象為下面的蝶形信號(hào)流圖單元：上面的運(yùn)算可以抽象為下面的蝶形信號(hào)流圖單元： 可以看出，每個(gè)蝶形運(yùn)

12、算需要可以看出，每個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法一次復(fù)數(shù)乘法 及及兩次復(fù)數(shù)加兩次復(fù)數(shù)加（減）法。（減）法。)(1kX)(2kXkNW1)()()(21kXWkXkXkN)()()2(21kXWkXNkXkNkNWkX)(221nN/2點(diǎn)點(diǎn)DFT復(fù)乘復(fù)乘:n 復(fù)加復(fù)加:n蝶形運(yùn)算蝶形運(yùn)算 復(fù)乘復(fù)乘:n 復(fù)加復(fù)加:n總運(yùn)算量總運(yùn)算量 復(fù)乘復(fù)乘:n 復(fù)加復(fù)加:n直接直接N點(diǎn)點(diǎn)DFT復(fù)乘復(fù)乘: N2 復(fù)加復(fù)加:N(N-1)22222NN12122*2NNNN2/NNN2*22212222NNNNN2122NNNN運(yùn)算量-減少一半22LN2n既然如此，由于既然如此，由于 ，因此，因此N/2仍是仍是偶數(shù)，可以

13、進(jìn)一步偶數(shù)，可以進(jìn)一步按時(shí)間按時(shí)間的的奇偶性分解奇偶性分解，并且并且一直進(jìn)行下去一直進(jìn)行下去。n由于這種方法每一步都是按輸入序列由于這種方法每一步都是按輸入序列時(shí)時(shí)間的奇、偶性間的奇、偶性分解為兩個(gè)更短的子序列，分解為兩個(gè)更短的子序列，所以稱(chēng)為所以稱(chēng)為“按時(shí)間抽選法按時(shí)間抽選法”（DIT）。）。n分解過(guò)程如下分解過(guò)程如下：231、原位運(yùn)算，2、倒位序，3、疊型間距24n由按時(shí)間抽選法由按時(shí)間抽選法FFT的流圖可見(jiàn)，當(dāng)?shù)牧鲌D可見(jiàn)，當(dāng) 時(shí)，共有：時(shí)，共有：nL級(jí)蝶形，每級(jí)都由級(jí)蝶形，每級(jí)都由N/2個(gè)蝶形個(gè)蝶形運(yùn)算組成運(yùn)算組成n每個(gè)蝶形有一次復(fù)乘、二次復(fù)加，因而每級(jí)每個(gè)蝶形有一次復(fù)乘、二次復(fù)加，因而

14、每級(jí)運(yùn)算都需運(yùn)算都需N/2次復(fù)乘和次復(fù)乘和N次復(fù)加次復(fù)加nL級(jí)級(jí)FFT運(yùn)算總共需要：運(yùn)算總共需要：n 復(fù)乘數(shù)：復(fù)乘數(shù)： (DFT: )n 復(fù)加數(shù)：復(fù)加數(shù)： (DFT: )LN22log22FNNmLN2NNNNLaF2log) 1(NN二、運(yùn)算量二、運(yùn)算量25n由于計(jì)算機(jī)上乘法運(yùn)算所需時(shí)間比加法由于計(jì)算機(jī)上乘法運(yùn)算所需時(shí)間比加法運(yùn)算所需時(shí)間多得多，所以乘法是主要運(yùn)算所需時(shí)間多得多，所以乘法是主要的運(yùn)算量。的運(yùn)算量。n直接計(jì)算直接計(jì)算DFT與與FFT算法計(jì)算量之比為算法計(jì)算量之比為:NNNNNLNN2222log2log222627)(1kXm)(1jXmrNW1)()()(11jXWkXkXm

15、rNmm)()()(11jXWkXjXmrNmm三、三、DIT算法的特點(diǎn)算法的特點(diǎn)n1、原位運(yùn)算（同址運(yùn)算）原位運(yùn)算（同址運(yùn)算）n每級(jí)（每列）都由每級(jí)（每列）都由N/2個(gè)蝶形運(yùn)算構(gòu)成個(gè)蝶形運(yùn)算構(gòu)成n每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算：每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算： nm表示第表示第m級(jí)迭代，級(jí)迭代， k、j為數(shù)據(jù)所在行為數(shù)據(jù)所在行28n按原位計(jì)算時(shí)，按原位計(jì)算時(shí)，F(xiàn)FT的的輸出輸出 是按是按正常順正常順序排列序排列在存儲(chǔ)單元中在存儲(chǔ)單元中:n X（0），），X（1），），X（7），n但是但是輸入輸入 卻不是按自然順序存儲(chǔ)的卻不是按自然順序存儲(chǔ)的:n看起來(lái)好像是看起來(lái)好像是“混亂無(wú)序混亂無(wú)

16、序”，實(shí)際是有規(guī)律，實(shí)際是有規(guī)律的，稱(chēng)之為的，稱(chēng)之為倒位序倒位序。n造成倒位序的原因是輸入造成倒位序的原因是輸入 按標(biāo)號(hào)按標(biāo)號(hào)n的的奇、奇、偶性的不斷分組偶性的不斷分組造成。造成。n倒位序的實(shí)現(xiàn)倒位序的實(shí)現(xiàn))(kX)(nx)7(,),4(),0(xxx)(nx012nnn210nnn)3(x)011(x)110(x2、倒位序規(guī)律、倒位序規(guī)律2912m3、蝶形運(yùn)算兩結(jié)點(diǎn)的、蝶形運(yùn)算兩結(jié)點(diǎn)的“距離距離”n由由8點(diǎn)點(diǎn)FFT的信號(hào)流圖可以看出，其輸入的信號(hào)流圖可以看出，其輸入是倒位序的，輸出是自然順序。是倒位序的，輸出是自然順序。n第一級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)間第一級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)間“距離距離”為為1，n

17、第二級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)第二級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)“距離距離”為為2，n第三級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)第三級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)“距離距離”為為4，n由此類(lèi)推得，對(duì)由此類(lèi)推得，對(duì)N2L ，當(dāng)輸入為倒位當(dāng)輸入為倒位序，輸出為正常順序時(shí)，其序，輸出為正常順序時(shí)，其第第m級(jí)運(yùn)算，級(jí)運(yùn)算，每個(gè)蝶形的兩節(jié)點(diǎn)每個(gè)蝶形的兩節(jié)點(diǎn)“距離距離”為為 。30四、四、DIT算法的其他形式流圖算法的其他形式流圖n對(duì)于對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連任何流圖，只要保持各節(jié)點(diǎn)所連的各支路及其傳輸系數(shù)不變的各支路及其傳輸系數(shù)不變，則不論，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效節(jié)點(diǎn)位置怎么排列所得流圖總是等效n所得最后結(jié)果都是所得最后結(jié)果都是D

18、FT的正確結(jié)果，的正確結(jié)果，只是只是數(shù)據(jù)的提取和存放的次序不同而數(shù)據(jù)的提取和存放的次序不同而已已。3132335.2.3 DIF的的2M FFT(桑德桑德-圖基算法圖基算法)n頻率抽選（頻率抽選（DIF）的的FFT算法，是把頻域算法，是把頻域序列（也是序列（也是N點(diǎn)）按點(diǎn)）按K的奇偶性分解為越的奇偶性分解為越來(lái)越短的序列。來(lái)越短的序列。 n一、算法原理一、算法原理n假設(shè)序列點(diǎn)數(shù)為假設(shè)序列點(diǎn)數(shù)為 ，L為整數(shù)。為整數(shù)。n在將在將 按按k的奇偶分組之前，先把輸入的奇偶分組之前，先把輸入按按n的順序分成前后兩半的順序分成前后兩半LN2 kX34nkNNkNNnNnknNNNnnkNNNnnkNNnnk

19、NNnnkNWWNnxnxWNnxWnxWnxWnxWnxkX)2()()2()()()()()(2/120120)2(120121201012/NNW35n由于由于 ，故，故 ，可得：，可得：n n k=0,1,N-1n當(dāng)當(dāng)k為偶數(shù)時(shí)，為偶數(shù)時(shí)， ；n k為奇數(shù)時(shí)，為奇數(shù)時(shí)， 。n因此，按因此，按 k的奇偶可將的奇偶可將 分為兩部分。分為兩部分。 12/NNWkNkNW) 1(2/nkNkNnWNnxnxkX).2() 1()()(1201) 1(k1) 1(k)(kXnkNNkNNnWWNnxnxkX)2()()(2/12036n令令 n n則：則：120,1, ,122NrrkrknrN

20、nNNnrnNNnnrNNnrnNNnWWNnxnxWNnxnxrXWNnxnxWNnxnxrX2/120)12(1202/1202120).2()().2()()12().2()().2()()2(nkNkNnWNnxnxkX).2() 1()()(12037n令令 n則：則：12,.,1 , 0)2()()()2()()(21NnWNnxnxnxNnxnxnxnN12,.,1 , 0)() 12()()2(1202/21202/1NrWnxrXWnxrXNnnrNNnnrN38)(nx)2(NnxnNW1)2()()(1NnxnxnxnNWNnxnxnx)2()()(2DIF運(yùn)算關(guān)系的基本

21、蝶形運(yùn)算關(guān)系的基本蝶形39N=8點(diǎn)點(diǎn)DIF FFT結(jié)構(gòu)結(jié)構(gòu)40二、二、DIT與與DIF的異同的異同n形式上的區(qū)別是：形式上的區(qū)別是：DIF輸入是自然順序，輸入是自然順序，輸出是倒位序的，與輸出是倒位序的，與DIT正好相反。正好相反。n但這不是實(shí)質(zhì)性的區(qū)別，因?yàn)榈@不是實(shí)質(zhì)性的區(qū)別，因?yàn)镈IF與與DIT都可將輸入或輸出按照要求進(jìn)行重排。都可將輸入或輸出按照要求進(jìn)行重排。n實(shí)質(zhì)性的區(qū)別是：實(shí)質(zhì)性的區(qū)別是：nDIF的基本蝶形與的基本蝶形與DIT的基本蝶形不同。的基本蝶形不同。414243作業(yè)：n9.6n9.7 n9.14n9.17n9.26n9.27五、chirp Z變換n對(duì)對(duì)非單位圓上的抽樣感非單

22、位圓上的抽樣感興趣興趣n語(yǔ)音信號(hào)處理中往往需要知道極語(yǔ)音信號(hào)處理中往往需要知道極點(diǎn)所在處的復(fù)頻率，如果極點(diǎn)位點(diǎn)所在處的復(fù)頻率，如果極點(diǎn)位置離單位圓較遠(yuǎn)，只利用單位圓置離單位圓較遠(yuǎn)，只利用單位圓上的頻譜，就很難知道極點(diǎn)所在上的頻譜，就很難知道極點(diǎn)所在處的復(fù)頻率。處的復(fù)頻率。nz變換采用變換采用螺線抽樣螺線抽樣就適就適應(yīng)于這些需要，稱(chēng)為線應(yīng)于這些需要，稱(chēng)為線性調(diào)頻性調(diào)頻z變換變換(CZT)4445n已知已知 是有限長(zhǎng)序列，其是有限長(zhǎng)序列，其z變換為：變換為：n為適應(yīng)為適應(yīng)z可以沿可以沿Z平面更一般的路徑取值，沿平面更一般的路徑取值，沿z平面上的一段平面上的一段螺線螺線作作等分角等分角的的抽樣抽樣，

23、z的這的這些抽樣點(diǎn)些抽樣點(diǎn)zk為為: 10Nnnx nNnznxzX101, 1 , 0,MkAWzkk一、算法的基本原理一、算法的基本原理46n M為所要分析的復(fù)頻譜的點(diǎn)數(shù)，不一為所要分析的復(fù)頻譜的點(diǎn)數(shù)，不一定等于定等于N，A和和W都是任意復(fù)數(shù)都是任意復(fù)數(shù):00jeAA 00jeWW00000000kjkjkkjkeWAeWeAz1, 1 , 0,MkAWzkk47n當(dāng)當(dāng) 各各zk就均勻等間隔地就均勻等間隔地分布在單位圓上，這時(shí)就是求序列的分布在單位圓上，這時(shí)就是求序列的DFT。NjeWANM2, 1,48nCZT的快速算法的快速算法n直接計(jì)算這一公式，與直接計(jì)算直接計(jì)算這一公式，與直接計(jì)算

24、DFT相相似，總共算出似，總共算出M個(gè)抽樣點(diǎn)，需要個(gè)抽樣點(diǎn)，需要NM次復(fù)次復(fù)數(shù)乘法數(shù)乘法與（與（N-1）M次復(fù)數(shù)加法，當(dāng)次復(fù)數(shù)加法，當(dāng)N，M較大時(shí)，運(yùn)算量將很大。較大時(shí)，運(yùn)算量將很大。 10,1010MkWAnxznxzXnknNnnkNnk49n采用采用布魯斯坦布魯斯坦（Bluestein）提出的等式，）提出的等式，可以將以上運(yùn)算可以將以上運(yùn)算轉(zhuǎn)換為卷積和轉(zhuǎn)換為卷積和形式，進(jìn)而形式，進(jìn)而采用采用FFT算法，提高運(yùn)算速度。算法，提高運(yùn)算速度。n布魯斯坦所提出的等式為：布魯斯坦所提出的等式為：n 由此可得：由此可得：22221nkknnk 2)(102222210222222nkNnnnkknknnNnkWWAnxWWWWAnxzX50 1, 1 , 0,22NnWAnxngnn 1, 1 , 0,1022MknkhngWzXNnkk 22nWnh 2)(102222210222222nkNnnnkknknnNnkWWAnxWWWWAnxzX51nCZT變換可以通過(guò)求變換可以通過(guò)求g(n)與與h(n)的線性的線性卷積，然后乘上卷積，然后乘上1/h(n)而得到，即：而得到，即：nh(n)為角為角頻率頻率隨時(shí)間隨時(shí)間線性增長(zhǎng)線性增長(zhǎng)的復(fù)指數(shù)序的復(fù)指數(shù)序列，稱(chēng)為線性調(diào)頻信號(hào)（列，稱(chēng)為線性調(diào)頻信號(hào)（Chirp signal），），因此，稱(chēng)為線調(diào)頻因此，稱(chēng)為線調(diào)頻z變換。變