0 引言
    由于單片機(jī)的性價(jià)比高，因此在數(shù)據(jù)采集及頻譜分析系統(tǒng)中往往取代DSP芯片而被廣泛使用。在數(shù)字信號(hào)處理中，離散傅里葉變換(Discrete Fourier Transform，DFT)是常用的變換方法，它在各種數(shù)字信號(hào)處理系統(tǒng)中扮演著重要的角色?？焖俑道锶~變換(Fast Fourier Transfonn，FFT)并不是與離散傅里葉變換不同的另一種變換，而是為了減少DFT計(jì)算次數(shù)的一種快速有效的算法，且它們都是為了將信號(hào)變換到頻域并進(jìn)行相應(yīng)的頻譜分析。雖然FFT是一種快速的運(yùn)算方法，但是為了計(jì)算N點(diǎn)的FFT依然需要Nlog2N次加法和0．5Nlog2N次乘法。當(dāng)N比較大時(shí)，其運(yùn)算復(fù)雜度對(duì)RAM的需求也是很大的。在本文中，我們將探討如何優(yōu)化FFT算法，并將其在單片機(jī)中實(shí)現(xiàn)。
    雖然在實(shí)現(xiàn)FFT方面已有很好的芯片來解決其運(yùn)算速度及RAM容量的問題，但由于單片機(jī)的成本相對(duì)比較低。因此討論在單片機(jī)中實(shí)現(xiàn)FFT算法具有現(xiàn)實(shí)意義。最后本文還給出了用單片機(jī)實(shí)現(xiàn)FFT在雷達(dá)檢測(cè)中的應(yīng)用。

1 基數(shù)為2的FFT算法
    FFT的輸出與DFT的輸出是一致的，但冗余的計(jì)算在FFT中已被減去，使得其計(jì)算速度比較快。對(duì)于N-點(diǎn)的傅里葉變換，DFT需要的計(jì)算復(fù)雜度是N2，而FFT需要的計(jì)算復(fù)雜度是N/2log2N。因此當(dāng)N比較大時(shí)，使用FFT做傅里葉變換將會(huì)大大減少計(jì)算量。比如做64點(diǎn)的DFT需要4096的計(jì)算復(fù)雜度，而使用FFT只需要192的計(jì)算復(fù)雜度。在單片機(jī)中，當(dāng)使用別的優(yōu)化方法時(shí)，F(xiàn)FT的計(jì)算需要更少的時(shí)間。
    在本文中，使用FFT時(shí)，我們關(guān)心的是如何減少為了存儲(chǔ)中間數(shù)據(jù)所需要的臨時(shí)內(nèi)存空間。在執(zhí)行FFT時(shí)，輸入數(shù)據(jù)和輸出數(shù)據(jù)將以比特倒序的方式存儲(chǔ)。在順序與倒序之間改變時(shí)，每一數(shù)據(jù)點(diǎn)與數(shù)據(jù)集里的另一數(shù)據(jù)點(diǎn)的位置相換是由將樣本系列的順序倒置決定的。例如，在16點(diǎn)的FFT變換，樣本存儲(chǔ)的地址是001 b將與存儲(chǔ)在100 b位置上的樣本互換。具有倒序字節(jié)的位置是和沒有倒序字節(jié)的位置是相等的，比如0110 b是不互換位置的。計(jì)算FFT的順序是由FFT的輸入或輸出是否需要以倒序保存決定的。

2 對(duì)輸入數(shù)據(jù)加窗
    FFT變換可以作用在具有有限時(shí)間長(zhǎng)度的數(shù)據(jù)，但是對(duì)此數(shù)據(jù)集進(jìn)行一個(gè)假設(shè)：就是周期的，且無(wú)限次重復(fù)。當(dāng)樣本數(shù)據(jù)以這種方式重復(fù)時(shí)，最后一個(gè)樣本(下標(biāo)[N-1])是緊接著下一周期中的第一個(gè)樣本([0])的。如圖1所示，當(dāng)數(shù)據(jù)在整個(gè)樣本集中不是周期性的，則當(dāng)對(duì)整個(gè)樣本做FFT時(shí)會(huì)導(dǎo)致不連續(xù)性。正因?yàn)檫@樣，數(shù)據(jù)在進(jìn)行FFT變換前通常需要加窗。加窗使得樣本集變成周期性且去掉在第一個(gè)樣本與最后一個(gè)樣本之間的不連續(xù)。由于加窗改變了輸入數(shù)據(jù)，在頻域上它將產(chǎn)生一些噪聲。加窗會(huì)將信號(hào)的能量伸展到幾個(gè)點(diǎn)上。能量分布會(huì)削弱信號(hào)的峰值。大部分信號(hào)的原始內(nèi)容存儲(chǔ)在主要部分里，當(dāng)一部分發(fā)生旁瓣泄漏(如圖2所示)，主要部分的寬度和旁瓣的高度由應(yīng)用在信號(hào)的加窗算法決定。一些窗函數(shù)及其性能如表1所示。為計(jì)算N點(diǎn)FFT的加窗函數(shù)的系數(shù)的一些方程如表2所示。更多關(guān)于加窗算法與他們的參數(shù)參見文獻(xiàn)[2]。

3 FFT優(yōu)化
    已經(jīng)出現(xiàn)了很多優(yōu)化FFT的方法。而這些優(yōu)化方法的目的都是為了使得計(jì)算速度增快且盡可能的減少存儲(chǔ)數(shù)據(jù)所需要的RAM。
    我們都知道，計(jì)算FFT的一個(gè)重要方法是蝶式方法。但是蝶式計(jì)算的每一次迭代都需要一個(gè)復(fù)雜的乘法(總共是四次的長(zhǎng)整數(shù)乘法)。長(zhǎng)整數(shù)乘法需要很多處理內(nèi)存來完成。但是我們仔細(xì)觀察會(huì)發(fā)現(xiàn)其中一些乘法是不需要的，并且是可以省去的。特別是，當(dāng)乘數(shù)為零時(shí)，結(jié)果將為零和當(dāng)乘數(shù)為1時(shí)，相乘的結(jié)果將不變。對(duì)那些正弦和余弦函數(shù)是否為0或1進(jìn)行查詢的代碼可以利用這些優(yōu)點(diǎn)來減少計(jì)算量。這種優(yōu)化方法能節(jié)省的計(jì)算量為：其中N為FFT的點(diǎn)數(shù)。

4 程序總體設(shè)計(jì)
    首長(zhǎng)分成三個(gè)模塊集合而成。即數(shù)據(jù)采集模塊，A／D轉(zhuǎn)換模塊及FFT運(yùn)算模塊。數(shù)據(jù)采集模塊主要是通過定時(shí)器來控制A／D轉(zhuǎn)換器的采樣周期，將采集到的數(shù)據(jù)轉(zhuǎn)換成有符號(hào)數(shù)，并且可以以復(fù)數(shù)形式存貯。FFT的運(yùn)算模塊是在8051單片機(jī)的數(shù)據(jù)存貯器上運(yùn)行256點(diǎn)的FFT，并經(jīng)一快速平方根或快速對(duì)數(shù)運(yùn)算，計(jì)算出對(duì)應(yīng)128個(gè)頻率點(diǎn)的幅值或分貝表示值。具體流程如圖3。

5 在電話視頻中的應(yīng)用
    在一個(gè)會(huì)議中，當(dāng)說話人變換時(shí)。我們需要攝像頭能自動(dòng)跟蹤并檢測(cè)出說話人的位置，這就需要用到FFT及其反變換來計(jì)算角度。

6 結(jié)論
    本文主要介紹了一種在單片機(jī)中實(shí)現(xiàn)FFT算法的優(yōu)化方法，由于這可大大減少FFT的計(jì)算量及減少存儲(chǔ)數(shù)據(jù)所需要的RAM。因此其可應(yīng)用在電話視頻會(huì)議中。