fft的發(fā)展、現(xiàn)狀、典型算法.docx

數(shù)字信號(hào)處理期末大作業(yè)FFT的發(fā)展史、現(xiàn)狀及典型算法班級(jí)學(xué)號(hào)：姓名：FFT的發(fā)展史、現(xiàn)狀及典型算法傅里葉分析已有200多年的歷史，目前FFT及其校正算法在工程實(shí)際中仍在廣泛應(yīng)用，展現(xiàn)了其不竭的生命力。本次作業(yè)我們論述FFT的現(xiàn)狀，發(fā)展史以及一些算法，去詳細(xì)了解、擴(kuò)展這一算法，鞏固所學(xué)知識(shí)。一FFT的簡(jiǎn)介傅里葉變換是一種將信號(hào)從時(shí)域變換到頻域的變換形式，然而當(dāng)N很大的時(shí)候，求一個(gè)N點(diǎn)的DFT要完成N*N次復(fù)數(shù)乘法和N*（N-1）次復(fù)數(shù)加法，計(jì)算量非常大，所以人們開(kāi)始探索一種簡(jiǎn)便的算法對(duì)于一個(gè)較大的N進(jìn)行傅里葉變換。在20世紀(jì)60年代由Cooley和Tukey提出了快速傅里葉變換算法，它是快速計(jì)算DFT的一種簡(jiǎn)單高效的方法。關(guān)于何為FFT，它是根據(jù)離散傅氏變換的奇、偶、虛、實(shí)等特性，對(duì)離散傅立葉變換的算法進(jìn)行改進(jìn)獲得的。舉個(gè)例子，設(shè)x(n)為N項(xiàng)的復(fù)數(shù)序列，由DFT變換，任一X（m）的計(jì)算都需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法，而一次復(fù)數(shù)乘法等于四次實(shí)數(shù)乘法和兩次實(shí)數(shù)加法，一次復(fù)數(shù)加法等于兩次實(shí)數(shù)加法，即使把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運(yùn)算”（四次實(shí)數(shù)乘法和四次實(shí)數(shù)加法），那么求出N項(xiàng)復(fù)數(shù)序列的X（m）,即N點(diǎn)DFT變換大約就需要N2次運(yùn)算。當(dāng)N=1024點(diǎn)甚至更多的時(shí)候，需要N2=1048576次運(yùn)算，在FFT中，利用WN的周期性和對(duì)稱(chēng)性，把一個(gè)N項(xiàng)序列（設(shè)N=2k,k為正整數(shù)），分為兩個(gè)N/2項(xiàng)的子序列，每個(gè)N/2點(diǎn)DFT變換需要（N/2）2次運(yùn)算，再用N次運(yùn)算把兩個(gè)N/2點(diǎn)的DFT變換組合成一個(gè)N點(diǎn)的DFT變換。這樣變換以后，總的運(yùn)算次數(shù)就變成N+2*（N/2)2=N+（N2）/2。繼續(xù)上面的例子，N=1024時(shí)，總的運(yùn)算次數(shù)就變成了525312次，節(jié)省了大約50%的運(yùn)算量。而如果我們將這種“一分為二”的思想不斷進(jìn)行下去，直到分成兩兩一組的DFT運(yùn)算單元，那么N點(diǎn)的DFT變換就只需要Nlog2N次的運(yùn)算，N在1024點(diǎn)時(shí)，運(yùn)算量?jī)H有10240次，是先前的直接算法的1%，點(diǎn)數(shù)越多，運(yùn)算量的節(jié)約就越大，這就是FFT的優(yōu)越性。所以使用FFT算法，可以大大提高傅里葉變換的運(yùn)算速度，運(yùn)算時(shí)間縮短一到兩個(gè)數(shù)量級(jí)，從而使DFT變換應(yīng)用迅速普及，不僅在頻譜分析，而且在線(xiàn)性卷積、線(xiàn)性相關(guān)等方面得到廣泛應(yīng)用。二FFT的現(xiàn)實(shí)意義隨著計(jì)算機(jī)技術(shù)的發(fā)展，離散傅里葉變化的出現(xiàn)使得傅里葉變換在工程中進(jìn)入實(shí)際應(yīng)用階段。在信號(hào)處理中，DFT的計(jì)算具有舉足輕重的作用，信號(hào)的相關(guān)、濾波、譜估計(jì)等都要通過(guò)DFT來(lái)實(shí)現(xiàn)，但必須減少它的運(yùn)算量，DFT才能在工程計(jì)算中具有實(shí)用價(jià)值。所以，F(xiàn)FT的出現(xiàn)提高了它的實(shí)用價(jià)值。而FFT成為數(shù)字信號(hào)處理的關(guān)鍵技術(shù)，在信號(hào)處理領(lǐng)域扮演的角色越來(lái)越重要。高效率的快速傅立葉變換(FFT)算法是雷達(dá)信號(hào)處理、衛(wèi)星通訊、生物醫(yī)學(xué)和多媒體信號(hào)處理等基礎(chǔ)和核心算法。提高FFT處理速度滿(mǎn)足對(duì)雷達(dá)信號(hào)處理實(shí)時(shí)性的，要求在EW接收機(jī)高速數(shù)據(jù)處理方面將有廣泛的應(yīng)用前景。隨著科學(xué)技術(shù)的不斷進(jìn)步，相控陣體制已廣泛應(yīng)用于各種星載、機(jī)載、艦載和地面雷達(dá)。對(duì)于電尺寸較大幾十甚至幾百個(gè)波長(zhǎng)的相控陣天線(xiàn)，(如高分辨率星載，SAR天線(xiàn)、大型稀布陣天線(xiàn)等)，用公式按級(jí)數(shù)求和計(jì)算陣列天線(xiàn)方向圖的方法效率甚低。FFT的引入將從根本上解決這一難題。平面近場(chǎng)測(cè)量方法是天線(xiàn)測(cè)量的常規(guī)手段而FFT技術(shù)加快了天線(xiàn)參數(shù)評(píng)估的速度。三傅里葉變換的發(fā)展歷程對(duì)于發(fā)展史，我們由記載可知，離散傅里葉變換DFT是數(shù)字信號(hào)處理最重要的基石之一，也是對(duì)信號(hào)進(jìn)行分析和處理時(shí)最常用的工具之一。在200多年前法國(guó)數(shù)學(xué)家、物理學(xué)家傅里葉提出后來(lái)以他名字命名的傅里葉級(jí)數(shù)之后，用DFT這個(gè)工具來(lái)分析信號(hào)就已經(jīng)為人們所知。歷史上最偉大的數(shù)學(xué)家之一。歐拉是第一個(gè)使用“函數(shù)”一詞來(lái)描述包含各種參數(shù)的表達(dá)式的人，例如：y = f(x)。他是把微積分應(yīng)用于物理學(xué)的先驅(qū)者之一。 給出了一個(gè)用實(shí)變量函數(shù)表示傅立葉級(jí)數(shù)系數(shù)的方程； 用三角級(jí)數(shù)來(lái)描述離散聲音在彈性媒介中傳播，發(fā)現(xiàn)某些函數(shù)可以通過(guò)余弦函數(shù)之和來(lái)表達(dá)。 但在很長(zhǎng)時(shí)間內(nèi)，這種分析方法并沒(méi)有引起更多的重視，最主要的原因在于這種方法運(yùn)算量比較大。直到1965年，Cooley和Tukey在計(jì)算機(jī)科學(xué) 發(fā)表著名的機(jī)器計(jì)算傅立葉級(jí)數(shù)的一種算法論文，F(xiàn)FT才開(kāi)始大規(guī)模應(yīng)用。那個(gè)年代，有個(gè)肯尼迪總統(tǒng)科學(xué)咨詢(xún)委員會(huì)。其中有項(xiàng)研究主題是，對(duì)蘇聯(lián)核測(cè)試進(jìn)行檢測(cè)，Tukey就是其中一員。美國(guó)/蘇聯(lián)核測(cè)試提案的批準(zhǔn)，主要取決于不實(shí)地訪(fǎng)問(wèn)核測(cè)試設(shè)施而做出檢測(cè)的方法的發(fā)展。其中一個(gè)想法是，分析離海岸的地震計(jì)情況，這種計(jì)算需要快速算法來(lái)計(jì)算DFT。其它應(yīng)用是國(guó)家安全，如用聲學(xué)探測(cè)遠(yuǎn)距離的核潛艇。所以在軍事上，迫切需要一種快速的傅立葉變換算法，這也促進(jìn)了FFT的正式提出。FFT的這種方法充分利用了DFT運(yùn)算中的對(duì)稱(chēng)性和周期性，從而將DFT運(yùn)算量從N2減少到N*log2N。當(dāng)N比較小時(shí)，F(xiàn)FT優(yōu)勢(shì)并不明顯。但當(dāng)N大于32開(kāi)始，點(diǎn)數(shù)越大，F(xiàn)FT對(duì)運(yùn)算量的改善越明顯。比如當(dāng)N為1024時(shí)，F(xiàn)FT的運(yùn)算效率比DFT提高了100倍。在庫(kù)利和圖基提出的FFT算法中，其基本原理是先將一個(gè)N點(diǎn)時(shí)域序列的DFT分解為N個(gè)1點(diǎn)序列的DFT，然后將這樣計(jì)算出來(lái)的N個(gè)1點(diǎn)序列DFT的結(jié)果進(jìn)行組合，得到最初的N點(diǎn)時(shí)域序列的DFT值。實(shí)際上，這種基本的思想很早就由德國(guó)偉大的數(shù)學(xué)家高斯提出過(guò)，在某種情況下，天文學(xué)計(jì)算（也是現(xiàn)在FFT應(yīng)用的領(lǐng)域之一）與等距觀察的有限集中的行星軌道的內(nèi)插值有關(guān)。由于當(dāng)時(shí)計(jì)算都是靠手工，所以產(chǎn)生一種快速算法的迫切需要。 而且，更少的計(jì)算量同時(shí)也代表著錯(cuò)誤的機(jī)會(huì)更少，正確性更高。高斯發(fā)現(xiàn)，一個(gè)富氏級(jí)數(shù)有寬度N=N1*N2，可以分成幾個(gè)部分。計(jì)算N2子樣本DFT的N1長(zhǎng)度和N1子樣本DFT的N2長(zhǎng)度。只是由于當(dāng)時(shí)尚欠東風(fēng)計(jì)算機(jī)還沒(méi)發(fā)明。在20世紀(jì)60年代，伴隨著計(jì)算機(jī)的發(fā)展和成熟，庫(kù)利和圖基的成果掀起了數(shù)字信號(hào)處理的革命，因而FFT發(fā)明者的桂冠才落在他們頭上。之后，桑德-圖基等快速算法相繼出現(xiàn)，幾經(jīng)改進(jìn)，很快形成了一套高效運(yùn)算方法，這就是現(xiàn)在的快速傅立葉變換（FFT）。這種算法使DFT的運(yùn)算效率提高1到2個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了良好的條件，大大推進(jìn)了數(shù)學(xué)信號(hào)處理技術(shù)。1984年，法國(guó)的杜哈梅和霍爾曼提出的分裂基塊快速算法，使運(yùn)算效率進(jìn)一步提高。庫(kù)利和圖基的FFT算法的最基本運(yùn)算為蝶形運(yùn)算，每個(gè)蝶形運(yùn)算包括兩個(gè)輸入點(diǎn)，因而也稱(chēng)為基-2算法。在這之后，又有一些新的算法，進(jìn)一步提高了FFT的運(yùn)算效率，比如基-4算法，分裂基算法等。這些新算法對(duì)FFT運(yùn)算效率的提高一般在50%以?xún)?nèi)，遠(yuǎn)遠(yuǎn)不如FFT對(duì)DFT運(yùn)算的提高幅度。從這個(gè)意義上說(shuō)，F(xiàn)FT算法是里程碑式的?？梢哉f(shuō)，正是計(jì)算機(jī)技術(shù)的發(fā)展和FFT的出現(xiàn)，才使得數(shù)字信號(hào)處理迎來(lái)了一個(gè)嶄新的時(shí)代。除了運(yùn)算效率的大幅度提高外，F(xiàn)FT還大大降低了DFT運(yùn)算帶來(lái)的累計(jì)量化誤差，這點(diǎn)常為人們所忽略。以上為FFT的發(fā)展史，在整個(gè)發(fā)展歷程中，傅里葉的發(fā)明作用尤為重要，后人的推動(dòng)，改良在發(fā)展史上也起到了至關(guān)重要的作用。四FFT的現(xiàn)狀、發(fā)展熱度對(duì)于傅里葉變換的現(xiàn)狀，我們分為國(guó)內(nèi)國(guó)外兩部分進(jìn)行討論：首先介紹國(guó)外現(xiàn)狀，國(guó)外圍繞快速傅立葉變換的并行計(jì)算進(jìn)行了多項(xiàng)研究和開(kāi)發(fā)。美國(guó)新墨西哥大學(xué)Vasilios Georgitsis等人設(shè)計(jì)了2-DFFT程序，可處理512*512個(gè)點(diǎn)的圖像，其底層通信基于PVM，將2-DFFT轉(zhuǎn)化成1-DFFT并行計(jì)算，完成了二維圖像的變換。目前最新的研究成果是由麻省理工學(xué)院計(jì)算機(jī)科學(xué)實(shí)驗(yàn)室超級(jí)計(jì)算技術(shù)組開(kāi)發(fā)的FFTW。FFTW是計(jì)算離散傅里葉變換DFT的快速C程序的一個(gè)完整集合，它可計(jì)算一維或多維、實(shí)數(shù)據(jù)和復(fù)數(shù)據(jù)以及任意規(guī)模的DFT。 在FFTW中，DFT的計(jì)算由執(zhí)行器完成。執(zhí)行器是由許多高度優(yōu)化的、可組裝的子代碼模塊組成的。FFTW有一個(gè)規(guī)劃器。規(guī)劃器用以根據(jù)具體機(jī)器的體系結(jié)構(gòu)特點(diǎn)和具體的DFT寬度N。在運(yùn)行時(shí)尋找一種有效的子代碼塊組裝方式，因此使得FFTW具有很好的自適應(yīng)性和很快的運(yùn)行速度。FFTW還包含對(duì)共享和分布式存儲(chǔ)系統(tǒng)的并行變換。 對(duì)于國(guó)內(nèi)現(xiàn)狀，在我國(guó)80年代初就開(kāi)展了并行算法研究。快速傅立葉變換的并行算法主要包括基于SIMD-MC2、SIMD-BF、SIMD-CC、MIMD-DM四種體系結(jié)構(gòu)上的FFT算法，它們都是基-2FFT算法，算法各有利弊，受體系結(jié)構(gòu)影響較大。 SIMD-MC2上的FFT算法是按頻率抽取的快速傅立葉變換在網(wǎng)孔結(jié)構(gòu)上的具體實(shí)現(xiàn)。假設(shè)將n個(gè)處理器P0，P1，PN-1排成的方陣。初始序列開(kāi)始時(shí)已處于陣列的各處理器中，即ak處于Pk中。算法結(jié)束時(shí)，Pk保存bk。SIMD-BF上FFT算法是在一個(gè)n=2k的蝶形網(wǎng)絡(luò)，簡(jiǎn)記為BF。將(k+1)、2k個(gè)節(jié)點(diǎn)布局成(k+1)行，每行有n個(gè)節(jié)點(diǎn)。令(r，i)表示第r行和第i列的坐標(biāo)，0，i，n-1，exp(r，i)表示在BF中坐標(biāo)點(diǎn)(r，i)處的w的指數(shù)，它等于字長(zhǎng)為k的整數(shù)j，即exp(r，i)=j。使得如果i的二進(jìn)制表示為a1，a2，ar-1，ar，ak，則j的二進(jìn)制為ar，ar-1a1，000。也就是說(shuō)將i的前r位取位反，即倒序，后面其余位補(bǔ)零就可以得到j(luò)。因?yàn)榈尉W(wǎng)絡(luò)第r-1行和第r行之間的連接，正好能滿(mǎn)足直接將dr-1，i和dr-1，j傳到P(r，j)和P(r，j)，所以無(wú)需考慮選路時(shí)間。算法時(shí)間除計(jì)算w、exp(r，i)的時(shí)間外，主要是算法第2步進(jìn)行復(fù)數(shù)運(yùn)算的時(shí)間。它等于0( )，顯然優(yōu)于SIMD-MC2上的FFT算法，這也說(shuō)明算法和體系結(jié)構(gòu)的密切關(guān)系。西安電子科技大學(xué)信息科學(xué)研究所提出了一種基于共享存儲(chǔ)的多機(jī)系統(tǒng)并行計(jì)算FFT算法。中國(guó)科學(xué)院計(jì)算技術(shù)研究所利用星型互聯(lián)網(wǎng)的遞歸可分解性的多樣性，提出了一種基于星型互聯(lián)網(wǎng)絡(luò)的并行快速傅立葉變換算法。星圖具有層次型結(jié)構(gòu)，可由許多低維的子星圖組成。國(guó)防科大就向量機(jī)上的FFT并行算法作了系統(tǒng)的研究，并就離散變換、卷積和濾波的并行算法，用多項(xiàng)式變換計(jì)算離散卷積以及短卷積嵌套計(jì)算長(zhǎng)卷積的并行算法，并研究了離散卷積的并行計(jì)算下界，對(duì)一維和二維濾波給出了用變換法及遞推公式計(jì)算的并行算法?？梢?jiàn)無(wú)論在與國(guó)內(nèi)還是國(guó)外，F(xiàn)FT算法都是研究的熱點(diǎn)，有著廣闊的發(fā)展前景。五基4FFT算法原理及介紹基4FFT算法是把長(zhǎng)度N=4的序列一分為四，將N點(diǎn)DFT表示為4個(gè)N/4點(diǎn)DFT的線(xiàn)性組合。然后再把N/4點(diǎn)DFT一分為四，表示為四個(gè)N /16點(diǎn)的DFT。如此重復(fù)下去直至分解成兩點(diǎn)DFT的運(yùn)算。多基時(shí)分蝶式運(yùn)算定理在形式上比基2時(shí)分碟式運(yùn)算定理復(fù)雜，但在本質(zhì)上是一致的。前者表明,對(duì)N=p，q的情形，若按xm(i)=x(ip+m)將原N點(diǎn)序列分解成p個(gè)q點(diǎn)的子序列，則原序列x(n)的DFT可由各子序列xm(i)的DFT的線(xiàn)性組合得到?；?時(shí)分FFT算法是多基算法的特例，因此從多基時(shí)分FFT的蝶式運(yùn)算定理即可推導(dǎo)出基4時(shí)分FFT算法的蝶式運(yùn)算公式。具體算法如下：設(shè)p=4,q=N/4,這時(shí)由多基時(shí)分蝶式運(yùn)算定理,輸入序列x(n)可以分解成如下的4個(gè)子序列:子序列均為N/4點(diǎn)序列，設(shè)它們的N/4點(diǎn)DFT為，則其中，k,s,r均為整數(shù)。將s=0,1，2,3代入上式，則：,其中，上式就是基4FFT蝶形運(yùn)算公式。其具體算法和基2算法相近。將式中的序列整理為4個(gè)序列，然后繼續(xù)拆分，即可得最后結(jié)果。相比于基2FFT算法，基4FFT算法運(yùn)算量較小，但是相應(yīng)的變換長(zhǎng)度更少，靈活性不如基2FFT算法。六實(shí)際應(yīng)用中的FFT典型算法描述及介紹（1）余弦窗插值FFT算法加窗插值FFT算法是一種異步采樣方法，它是以固定不變的采樣頻率對(duì)信號(hào)進(jìn)行采樣，利用窗函數(shù)截?cái)嘈盘?hào)時(shí)產(chǎn)生的泄漏頻剖來(lái)得到信號(hào)的實(shí)際頻譜值。通過(guò)對(duì)信號(hào)加窗可以減小由頻譜泄漏現(xiàn)象引起的誤差，通過(guò)插值算法可以減小由柵欄效應(yīng)引起的誤差。用FFT計(jì)算電力系統(tǒng)諧波時(shí)需要將被測(cè)信號(hào)截?cái)啵@樣就會(huì)產(chǎn)生截?cái)嘈?yīng)，即產(chǎn)生頻譜泄漏，信號(hào)的基波和高次諧波譜線(xiàn)向附近展寬，形成主瓣和旁瓣。泄漏的頻譜主瓣可能淹沒(méi)主譜附近的諧波分量，影響是短范圍的。旁瓣的影響是長(zhǎng)范圍(譜間干擾)的，它對(duì)相鄰的基波和高次諧波分量影響較大。當(dāng)采樣頻率是信號(hào)基波頻率的整倍數(shù)時(shí)，可以得到精確的計(jì)算結(jié)果，但是當(dāng)采樣頻率不是信號(hào)頻率的整倍數(shù)時(shí)，由于柵欄效應(yīng)，只能測(cè)得泄漏的頻譜，計(jì)算產(chǎn)生誤差。加窗插值FFT算法可以計(jì)算出信號(hào)的頻率偏移量，再對(duì)測(cè)得的泄漏頻譜進(jìn)行修正，從而得到實(shí)際信號(hào)的頻譜。實(shí)際信號(hào)的頻譜的計(jì)算精度取決于所加窗函數(shù)的特性，選擇主瓣窄的窗函數(shù)可以減小短范圍的影響；選擇旁瓣峰值小、衰減速度快的窗函數(shù)，可以減小長(zhǎng)范圍的影響。一個(gè)理想的窗函數(shù)應(yīng)具有主瓣寬度窄、最大旁瓣峰值小和旁瓣衰減速度快的特點(diǎn)。但最大旁瓣峰值小且旁瓣衰減速度快的窗函數(shù)，其主瓣較寬，因此，要尋找主瓣窄且旁瓣峰值又小的窗函數(shù)是很困難的。泄漏頻譜主瓣的影響在實(shí)際應(yīng)用中可以通過(guò)增加觀測(cè)時(shí)間來(lái)消除，但這又影響了算法的實(shí)時(shí)性。實(shí)際上，觀測(cè)的基波周期數(shù)就是相鄰兩頻譜主譜線(xiàn)之間的譜線(xiàn)間隔數(shù)，例如加漢寧窗截?cái)嗟恼倚盘?hào)的頻譜泄漏主瓣的寬度為4個(gè)譜線(xiàn)間隔，要分辨出相鄰的諧波(消除主瓣的影響)，加漢寧窗插值FFT算法至少需要兩個(gè)基波周期的采樣點(diǎn) (相鄰兩頻譜主譜線(xiàn)間隔兩個(gè)譜線(xiàn)間隔)；加Blackman-harris窗截?cái)嗟恼倚盘?hào)的頻譜泄漏主瓣的寬度為8個(gè)譜線(xiàn)間隔，要分辨出相鄰諧波(消除主瓣的影響)，加Blackman-harris窗插值FFT算法至少需要4個(gè)基波周期的采樣點(diǎn)(相鄰兩頻譜主譜線(xiàn)間隔4個(gè)譜線(xiàn)間隔)。對(duì)旁瓣峰值高且衰減快的窗函數(shù)可再適當(dāng)增加觀測(cè)時(shí)間(采樣的基波周期數(shù))來(lái)消除臨近主瓣的峰值較高的幾個(gè)旁瓣對(duì)相鄰諧波的影響21，例如加漢寧窗插值FFT算法采用4個(gè)基波周期的采樣點(diǎn)進(jìn)行FFT變換還能提高計(jì)算精度。對(duì)旁瓣峰值不衰減的窗函數(shù)即使增加再多的觀測(cè)時(shí)間(采樣的基波周期數(shù))也無(wú)法消除旁瓣對(duì)相鄰諧波計(jì)算精度的影響。余弦窗的一般表達(dá)式5項(xiàng)余弦窗主瓣寬10/N，6項(xiàng)余弦窗主瓣寬12/N，7項(xiàng)余弦窗主瓣寬14/N，8項(xiàng)余弦窗主瓣寬16/N。5項(xiàng)余弦窗最大旁瓣峰值-89.69 db，6、7、8項(xiàng)余弦窗最大旁瓣峰值依次減小。從旁瓣衰減速度來(lái)看，7項(xiàng)余弦窗旁瓣衰減速度很慢，5、6、7項(xiàng)余弦窗旁瓣衰減依次加快，8項(xiàng)余弦窗旁瓣衰減速度最快，頻率為0.5時(shí)旁瓣峰值下降到-220db以下。7項(xiàng)余弦窗旁瓣基本不衰減，故加7項(xiàng)余弦窗插值FFT算法計(jì)算精度通過(guò)增加觀測(cè)時(shí)間不能有效提高，精度甚至低于加5、6項(xiàng)余弦窗插值FFT算法。根據(jù)圖1中的頻譜特性可以看出，8項(xiàng)余弦窗主瓣雖寬，但最大旁瓣峰值最小，旁瓣衰減速度最快，考慮到泄漏頻譜主瓣的影響可以通過(guò)增加觀測(cè)時(shí)間來(lái)消除，加8項(xiàng)余弦窗插值FFT算法在這4種加余弦窗插值FFT算法中具有最高的計(jì)算精度?？紤]到余弦窗項(xiàng)數(shù)越多，加余弦窗FFT算法計(jì)算量越大。下面以單頻率信號(hào)為例進(jìn)行分析，設(shè)復(fù)振幅Am一般為復(fù)數(shù)，反映了初相角，實(shí)際頻率fr= (l+r)*F，它在頻率lF和(l+1)*F之間，l 為整數(shù)，其中頻率分辨率F=1/(NTs)，Ts為采樣時(shí)間間隔，r為頻率偏移量，0r1時(shí)，有以下關(guān)系成立： 考慮到，當(dāng)K=3時(shí)，可以得到加余弦窗DFT的通用形式為代入，可以得到Nuttall窗截?cái)嗪蟮男盘?hào)頻譜為設(shè)定幅值比為由上式聯(lián)立解出r值為：由于頻率偏移量r的變化范圍為0-1，所以幅值比的變化范圍為0.75-4/3。將r代入式子中，解得修正后的復(fù)振幅：所以諧波相位也可以求得為到這步為止，已求得了信號(hào)的所需參數(shù)。插值算法的幅值比是頻率偏移量r的一次多項(xiàng)式，r的計(jì)算容易且計(jì)算量很小，這在加4項(xiàng)(及以上)窗插值FFT算法中是很難找到的。另外其窗函數(shù)頻譜旁瓣的衰減速率快，通過(guò)增加觀測(cè)時(shí)間，能有效地提高計(jì)算精度，計(jì)算精度優(yōu)于加Blackman-harris窗插值FFT算法。利用三次樣條插值函數(shù)計(jì)算復(fù)振幅的修正系數(shù)，能更好地提高加4項(xiàng)余弦窗Nuttall(I)窗插值FFT算法的計(jì)算速度。七FFT發(fā)展展望及啟示（1）快速變換算法的每一次突破都是找到一種數(shù)學(xué)工具以揭示變換的內(nèi)在關(guān)系,從而推動(dòng)了快速算法的發(fā)展構(gòu)造各種離散正交變換最小實(shí)數(shù)乘法次數(shù)的算法途徑已經(jīng)給出,但尚無(wú)法證明是最佳的。如果循環(huán)卷積找到乘法和加法次數(shù)均