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

1、數(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ì)算量 非常大，所以人們開始探索一種簡(jiǎn)便的算法對(duì)于一個(gè)較大的 N 進(jìn)行傅里葉變換。 在 20世紀(jì) 60年代由 Cool

2、ey 和 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)甚至更多

3、的時(shí)候，需要 N2=1048576次運(yùn)算，在 FFT 中，利用 WN的周期性和對(duì)稱性，把一個(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變換

4、就只需要 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)用迅速普及， 不僅在頻譜分析， 而且在線性卷 積、線性相關(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才能在

5、工程 計(jì)算中具有實(shí)用價(jià)值。所以， FFT的出現(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 處理速度滿足對(duì)雷達(dá)信號(hào)處理實(shí)時(shí)性的，要求在 EW 接收機(jī)高速數(shù)據(jù)處理方面將有廣泛的應(yīng)用前景。 隨著科學(xué)技術(shù)的不斷進(jìn)步， 相控 陣體制已廣泛應(yīng)用于各種星載、 機(jī)載、艦載和地面雷達(dá)。 對(duì)于電尺寸較大幾十甚 至幾百個(gè)波長(zhǎng)的相控陣天線， (如高分辨率星載， SAR天線、大型稀布陣天線等 )， 用公式按級(jí)數(shù)求和計(jì)算陣列天線方向圖的方法效

6、率甚低。 FFT的引入將從根本上 解決這一難題。平面近場(chǎng)測(cè)量方法是天線測(cè)量的常規(guī)手段而 FFT 技術(shù)加快了天線 參數(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ù)表示傅立葉

7、級(jí)數(shù)系數(shù)的方程； 用三角級(jí)數(shù)來(lái)描述離散聲音在彈性媒介中傳 播，發(fā)現(xiàn)某些函數(shù)可以通過(guò)余弦函數(shù)之和來(lái)表達(dá)。 但在很長(zhǎng)時(shí)間內(nèi)，這種分析 方法并沒有引起更多的重視，最主要的原因在于這種方法運(yùn)算量比較大。直到 1965年，Cooley 和 Tukey在計(jì)算機(jī)科學(xué) 發(fā)表著名的機(jī)器計(jì)算傅立葉級(jí)數(shù) 的一種算法論文， FFT才開始大規(guī)模應(yīng)用。那個(gè)年代， 有個(gè)肯尼迪總統(tǒng)科學(xué)咨詢委員會(huì)。 其中有項(xiàng)研究主題是， 對(duì)蘇聯(lián) 核測(cè)試進(jìn)行檢測(cè)， Tukey 就是其中一員。美國(guó) / 蘇聯(lián)核測(cè)試提案的批準(zhǔn)，主要取 決于不實(shí)地訪問核測(cè)試設(shè)施而做出檢測(cè)的方法的發(fā)展。 其中一個(gè)想法是， 分析離 海岸的地震計(jì)情況，這種計(jì)算需要快速算法來(lái)

8、計(jì)算 DFT。其它應(yīng)用是國(guó)家安全， 如用聲學(xué)探測(cè)遠(yuǎn)距離的核潛艇。 所以在軍事上， 迫切需要一種快速的傅立葉變換 算法，這也促進(jìn)了 FFT的正式提出。FFT的這種方法充分利用了 DFT運(yùn)算中的對(duì)稱性和周期性， 從而將 DFT運(yùn)算 量從 N2減少到 N*log2N。當(dāng) N比較小時(shí)， FFT優(yōu)勢(shì)并不明顯。但當(dāng) N大于 32 開 始，點(diǎn)數(shù)越大， FFT對(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)序列

9、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ī)還沒發(fā)明。 在 20 世紀(jì) 60 年代，伴隨著計(jì)算機(jī)的發(fā)展和成熟，庫(kù)利和

10、圖基的成果掀起了數(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)，因而也稱為基 -2 算法。在這之后，又有一些新的算法，進(jìn)一步提高了 FFT 的運(yùn)算效率，比

11、如基 -4 算法，分裂基算法等。這些新算法對(duì) FFT 運(yùn)算效率的提 高一般在 50%以內(nèi)，遠(yuǎn)遠(yuǎn)不如 FFT對(duì) DFT運(yùn)算的提高幅度。 從這個(gè)意義上說(shuō)， FFT 算法是里程碑式的。 可以說(shuō)， 正是計(jì)算機(jī)技術(shù)的發(fā)展和 FFT的出現(xiàn)， 才使得數(shù)字 信號(hào)處理迎來(lái)了一個(gè)嶄新的時(shí)代。除了運(yùn)算效率的大幅度提高外， FFT還大大降 低了 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)狀

12、，國(guó)外圍繞快速傅立葉變換的并行計(jì)算進(jìn)行了多項(xiàng)研究和 開發(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ù)組開發(fā)的 FFTW。 FFTW是計(jì)算離散傅里葉變換 DFT的快速 C 程序的一個(gè)完整集合，它可計(jì)算一維或多維、實(shí)數(shù)據(jù)和復(fù)數(shù)據(jù)以及任意規(guī)模的DFT。 在 FFTW中， DFT的計(jì)算由執(zhí)行器完成。執(zhí)行器是由許多高度優(yōu)化的、可 組裝的子代碼模塊組成的。 FFTW有

13、一個(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 年代初就開展了并行算法研究。快速傅立葉變換 的并行算法主要包括基于 SIMD-MC、2 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

14、，P1，PN-1 排成的方陣。初始序列開始時(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-1 a1

15、，000。也就是說(shuō)將 i 的前 r 位取位反，即倒序，后面其余位補(bǔ) 零就可以得到 j 。因?yàn)榈尉W(wǎng)絡(luò)第 r-1 行和第 r 行之間的連接，正好能滿足直接 將 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)的遞歸可分解性的 多樣

16、性，提出了一種基于星型互聯(lián)網(wǎng)絡(luò)的并行快速傅立葉變換算法。 星圖具有層 次型結(jié)構(gòu)， 可由許多低維的子星圖組成。 國(guó)防科大就向量機(jī)上的 FFT并行算法作 了系統(tǒng)的研究， 并就離散變換、 卷積和濾波的并行算法， 用多項(xiàng)式變換計(jì)算離散 卷積以及短卷積嵌套計(jì)算長(zhǎng)卷積的并行算法，并研究了離散卷積的并行計(jì)算下 界，對(duì)一維和二維濾波給出了用變換法及遞推公式計(jì)算的并行算法。 可見無(wú)論在 與國(guó)內(nèi)還是國(guó)外， FFT算法都是研究的熱點(diǎn)，有著廣闊的發(fā)展前景。五基 4FFT 算法原理及介紹基 4FFT算法是把長(zhǎng)度 N=4的序列一分為四，將 N點(diǎn) DFT表示為 4個(gè) N/4 點(diǎn) DFT的線性組合。然后再把 N/4 點(diǎn) DF

17、T一分為四，表示為四個(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的線性組 合得到?；?4時(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)

18、 可以分解成如 下的 4 個(gè)子序列 :Nxm(i) x(4i m)(m 0,1,2,3;0 i1,i為整數(shù) )4子序列均為 N/4點(diǎn)序列，設(shè)它們的 N/4點(diǎn) DFT為xm(r)，則N 3 m(sN4 r )x(k) N x(s r )= WN 4 xm(r) k s4 r 4 m 0N 1 ，k,s,r 均為整數(shù)。4其中 0 k N 1,0 s 3,0 r 將 s=0,1 ， 2,3 代入上式，則：rx(r) x0(r) WN x1(r)2r 3rWN2r x2(r) WN3rx3(r),x(r N4 )4x0(r)WNx1(r)WN 4 x2(r )WN 4 x3(r) ,x(r N2 )x

19、0(r)rWNx1(r)WN 4 x2(r )WN 4 x3(r) ,3Nx(r 34N )x0(r)(r3Nx1(r)2(rWN3Nx2(r)3N3( r )WN 4 x3(r) ,其中 0 r N 1,r為整數(shù) ，上式就是基 4FFT蝶形運(yùn)算公式。其具體算法和 4基 2 算法相近。將式中的 N 序列整理為 4 個(gè)序列，然后繼續(xù)拆分，即可得最后 4結(jié)果。相比于基 2FFT算法，基 4FFT算法運(yùn)算量較小， 但是相應(yīng)的變換長(zhǎng)度更少， 靈活性不如基 2FFT算法。六實(shí)際應(yīng)用中的 FFT 典型算法描述及介紹1)余弦窗插值 FFT 算法加窗插值 FFT 算法是一種異步采樣方法， 它是以固定不變的采樣

20、頻率對(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)的基波和高次諧波譜線向附近展寬， 形成主瓣和旁瓣。 泄 漏的頻譜主瓣可能淹沒主譜附近的諧波分量， 影響是短范圍的。 旁瓣的影響是長(zhǎng) 范圍（譜間干擾 ）的，它對(duì)相鄰的基波和高次諧波分量影響較大。 當(dāng)采樣頻率是信 號(hào)基波頻率的整倍數(shù)時(shí)， 可以得到精確的計(jì)算結(jié)果， 但是當(dāng)采樣頻率不是信號(hào)頻 率的整倍數(shù)時(shí)，由于柵欄效應(yīng)，只能測(cè)得泄

21、漏的頻譜，計(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ù)就是相

22、鄰兩頻譜主譜線之間的譜線間隔數(shù)， 例如 加漢寧窗截?cái)嗟恼倚盘?hào)的頻譜泄漏主瓣的寬度為 4 個(gè)譜線間隔，要分辨出相鄰 的諧波 （消除主瓣的影響 ） ，加漢寧窗插值 FFT算法至少需要兩個(gè)基波周期的采樣 點(diǎn) （ 相鄰兩頻譜主譜線間隔兩個(gè)譜線間隔 ）；加 Blackman-harris 窗截?cái)嗟恼?信號(hào)的頻譜泄漏主瓣的寬度為 8 個(gè)譜線間隔，要分辨出相鄰諧波 （消除主瓣的影 響） ，加Blackman-harris 窗插值 FFT算法至少需要 4個(gè)基波周期的采樣點(diǎn) （相鄰 兩頻譜主譜線間隔 4 個(gè)譜線間隔 ） 。對(duì)旁瓣峰值高且衰減快的窗函數(shù)可再適當(dāng)增 加觀測(cè)時(shí)間 （ 采樣的基波周期數(shù) ） 來(lái)消除臨

23、近主瓣的峰值較高的幾個(gè)旁瓣對(duì)相鄰 諧波的影響 21 ，例如加漢寧窗插值 FFT 算法采用 4 個(gè)基波周期的采樣點(diǎn)進(jìn)行 FFT變換還能提高計(jì)算精度。 對(duì)旁瓣峰值不衰減的窗函數(shù)即使增加再多的觀測(cè)時(shí) 間（ 采樣的基波周期數(shù) ）也無(wú)法消除旁瓣對(duì)相鄰諧波計(jì)算精度的影響。余弦窗的一般表達(dá)式，N 1K i 2wi(n)( 1)i ai cos( in),n 0,1, i 0 N5 項(xiàng)余弦窗主瓣寬 10 /N ，6 項(xiàng)余弦窗主瓣寬 12 /N，7 項(xiàng)余弦窗主瓣寬 14 /N，8項(xiàng)余弦窗主瓣寬 16 /N。5項(xiàng)余弦窗最大旁瓣峰值 db ，6、7、8 項(xiàng)余 弦窗最大旁瓣峰值依次減小。從旁瓣衰減速度來(lái)看， 7 項(xiàng)余

24、弦窗旁瓣衰減速度很 慢，5、6、7 項(xiàng)余弦窗旁瓣衰減依次加快， 8 項(xiàng)余弦窗旁瓣衰減速度最快，頻率 為時(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ì)算量 越大。面以

25、單頻率信號(hào)為例進(jìn)行分析，設(shè)j2 fr tx(t)Amej2 frt復(fù)振幅 Am一般為復(fù)數(shù)，反映了初相角，實(shí)際頻率 fr= (l+r)*F ，它在頻率 lF 和(l+1)*F 之間，l 為整數(shù)，其中頻率分辨率 F=1/(NTs) ，Ts 為采樣時(shí)間間隔， r 為頻率偏移量， 0<r<1 。x(t) 的離散形式為 :x(n)Amej2 frnTsRN(n) Amej2 (l r)nlN RN(n)其 DFT為：X(k)1N1j 2N (K l r)n N n 0Ame NAmNsinsink l r(k lNj(kr)eN1r )NN1添加余弦窗后， DFT變?yōu)椋篨i(k)A2m iK

26、0 (2 i 0DFT x(n)in1)i a sin(k l r i)1) ai(k l r iNsin NN1l r i) e j(k l r i)NN1 (k l r i)Nsin Nsin(kj(ki)eN1r i)NN 1之后代入余弦窗系數(shù)可求得最終結(jié)果。余弦窗函數(shù)系數(shù)如下表所示：余弦窗頻譜如下圖所示：2)基于 Nuttall 窗的插值 FFT 算法上文使用的算法直接使用了余弦窗，在這里我們?cè)敿?xì)分析第二種基于 Nuttall 窗的插值 FFT算法。對(duì)于插值 FFT 算法而言，窗函數(shù)的不同會(huì)導(dǎo)致最終表達(dá)不同。 在選擇窗函數(shù) 時(shí)，對(duì)各種常見窗函數(shù)的頻譜特性進(jìn)行了比較， 得出以下結(jié)論： 如

27、果對(duì)實(shí)時(shí)性要 求高而計(jì)算精度要求一般， 應(yīng)選擇 2項(xiàng) Hanning 窗，由于觀測(cè)的周期數(shù)就是相鄰 兩頻譜主譜線之間的譜線間隔數(shù)， 加 Harming 窗截?cái)嗟恼倚盘?hào)的頻譜泄漏主瓣 的寬度為 4個(gè)譜線間隔，要分辨出相鄰的諧波， 至少需要 2個(gè)周期的采樣點(diǎn)， 所 需要的采樣周期數(shù)最少；如果對(duì)實(shí)時(shí)性要求較高且計(jì)算精度也較高，應(yīng)選擇 3 項(xiàng) Exact Blackman 窗，其至少需 4 個(gè)周期的采樣點(diǎn)；如果對(duì)實(shí)時(shí)性要求一般，但要求很高的測(cè)量精度， 應(yīng)當(dāng)選擇旁瓣衰減幅度大且衰減速率大的窗函數(shù)， 在這 里介紹的算法所采用的 4 項(xiàng) Nut-tall(I) 窗與 4 項(xiàng) Blackman-harris

28、 窗相比具有 這種特性，且頻率偏移量計(jì)算非常簡(jiǎn)單，計(jì)算量非常小，算是一種改進(jìn)算法。與普通的余弦窗插值方法一樣， 我們以但頻率信號(hào)為例進(jìn)行分析， 振幅設(shè)定 為復(fù)振幅， x(n) Amej2 (l r)n/NRN(n) ,則離散信號(hào)加余弦窗的 DFT有：k 2 A kDFT x(n) ( 1)iai cos(2 in) Am( 1)iaii 0 N 2 i 0r i ) N 1N sin(k l r i ) e j(k l Nsin(k l r i) eNsin(k l r i ) e j(k l eN sin(k l r i)i) N 1 i) N 當(dāng) k=l 時(shí)有如下關(guān)系式：當(dāng) N>&g

29、t;1 時(shí)，考慮到 e代入 a0Xi (l) A2m(2 i 01)iai sin( r i) e j ( ( r i ) eN sin Nsin( r i ) e j( r i )N sin Ni)有以下關(guān)系成立：N11，sinN N NN1N1,e j2 1，當(dāng) K=3時(shí)，可以得到加余弦窗 DFT的通用形式為sin( r ) jXi(l) 0.5Am2 a0jsin( r ) j(1 r) a1e1 (1 r )sin( r ) j(2 r eresin(r)e(1 re)sin(r)(2r)sin(r)r)r)j(3(3 r )e j (2 r )j (1 r )1032 ,a1a22

30、(2 r ) sin( r ) j(3a3e3 (3 r )15 615 , a3 6 ，可以得到 Nuttall32 3 32r ) 窗截?cái)嗪蟮男盘?hào)頻譜為XH(l) Am sin( r)eir11.25r (122r2)(1 r2)(3 r )(4 r)設(shè)定幅值比為1) XH (l)XH(l(r 3)/ (r 4)由上式聯(lián)立解出 r 值為： 43r1 由于頻率偏移量 r 的變化范圍為 0-1 ，所以幅值比 的變化范圍為 3。將 r代入 x(n) Amej2 (l r)n/NRN(n) 式子中，解得修正后的復(fù)振幅：XH(l)r(1 r 2)(4 r2)(9 r2) 11.25sin( r )所以諧波相位也可以求得為m angle XH (l ) r 到這步為止，已求得了信號(hào)的所需參數(shù)。插值算法的幅值比 是頻率偏移量 r 的一次多項(xiàng)式， r 的計(jì)算容易且計(jì)算量 很小，這在加 4項(xiàng)(及以上)窗插值 FFT算法中是很難找到的。 另外其窗函數(shù)頻譜 旁瓣的衰減速率快， 通過(guò)增加觀測(cè)時(shí)間， 能有效地提高