|
由于單片機的性?xún)r(jià)比高，因此在數據采集及頻譜分析系統中往往取代DSP芯片而被廣泛使用。在數字信號處理中，離散傅里葉變換(Discrete Fourier Transform，DFT)是常用的變換方法，它在各種數字信號處理系統中扮演著(zhù)重要的角色�？焖俑道锶~變換(Fast Fourier Transfonn，FFT)并不是與離散傅里葉變換不同的另一種變換，而是為了減少DFT計算次數的一種快速有效的算法，且它們都是為了將信號變換到頻域并進(jìn)行相應的頻譜分析。雖然FFT是一種快速的運算方法，但是為了計算N點(diǎn)的FFT依然需要Nlog2N次加法和0．5Nlog2N次乘法。當N比較大時(shí)，其運算復雜度對RAM的需求也是很大的。在本文中，我們將探討如何優(yōu)化FFT算法，并將其在單片機中實(shí)現。 雖然在實(shí)現FFT方面已有很好的芯片來(lái)解決其運算速度及RAM容量的問(wèn)題，但由于單片機的成本相對比較低。因此討論在單片機中實(shí)現FFT算法具有現實(shí)意義。最后本文還給出了用單片機實(shí)現FFT在雷達檢測中的應用。 1 基數為2的FFT算法 FFT的輸出與DFT的輸出是一致的，但冗余的計算在FFT中已被減去，使得其計算速度比較快。對于N-點(diǎn)的傅里葉變換，DFT需要的計算復雜度是N2，而FFT需要的計算復雜度是N/2log2N。因此當N比較大時(shí)，使用FFT做傅里葉變換將會(huì )大大減少計算量。比如做64點(diǎn)的DFT需要4096的計算復雜度，而使用FFT只需要192的計算復雜度。在單片機中，當使用別的優(yōu)化方法時(shí)，FFT的計算需要更少的時(shí)間。 在本文中，使用FFT時(shí)，我們關(guān)心的是如何減少為了存儲中間數據所需要的臨時(shí)內存空間。在執行FFT時(shí)，輸入數據和輸出數據將以比特倒序的方式存儲。在順序與倒序之間改變時(shí)，每一數據點(diǎn)與數據集里的另一數據點(diǎn)的位置相換是由將樣本系列的順序倒置決定的。例如，在16點(diǎn)的FFT變換，樣本存儲的地址是001 b將與存儲在100 b位置上的樣本互換。具有倒序字節的位置是和沒(méi)有倒序字節的位置是相等的，比如0110 b是不互換位置的。計算FFT的順序是由FFT的輸入或輸出是否需要以倒序保存決定的。 2 對輸入數據加窗 FFT變換可以作用在具有有限時(shí)間長(cháng)度的數據，但是對此數據集進(jìn)行一個(gè)假設：就是周期的，且無(wú)限次重復。當樣本數據以這種方式重復時(shí)，最后一個(gè)樣本(下標[N-1])是緊接著(zhù)下一周期中的第一個(gè)樣本([0])的。如圖1所示，當數據在整個(gè)樣本集中不是周期性的，則當對整個(gè)樣本做FFT時(shí)會(huì )導致不連續性。正因為這樣，數據在進(jìn)行FFT變換前通常需要加窗。加窗使得樣本集變成周期性且去掉在第一個(gè)樣本與最后一個(gè)樣本之間的不連續。由于加窗改變了輸入數據，在頻域上它將產(chǎn)生一些噪聲。加窗會(huì )將信號的能量伸展到幾個(gè)點(diǎn)上。能量分布會(huì )削弱信號的峰值。大部分信號的原始內容存儲在主要部分里，當一部分發(fā)生旁瓣泄漏(如圖2所示)，主要部分的寬度和旁瓣的高度由應用在信號的加窗算法決定。一些窗函數及其性能如表1所示。為計算N點(diǎn)FFT的加窗函數的系數的一些方程如表2所示。更多關(guān)于加窗算法與他們的參數參見(jiàn)文獻。 3 FFT優(yōu)化 已經(jīng)出現了很多優(yōu)化FFT的方法。而這些優(yōu)化方法的目的都是為了使得計算速度增快且盡可能的減少存儲數據所需要的RAM。 我們都知道，計算FFT的一個(gè)重要方法是蝶式方法。但是蝶式計算的每一次迭代都需要一個(gè)復雜的乘法(總共是四次的長(cháng)整數乘法)。長(cháng)整數乘法需要很多處理內存來(lái)完成。但是我們仔細觀(guān)察會(huì )發(fā)現其中一些乘法是不需要的，并且是可以省去的。特別是，當乘數為零時(shí)，結果將為零和當乘數為1時(shí)，相乘的結果將不變。對那些正弦和余弦函數是否為0或1進(jìn)行查詢(xún)的代碼可以利用這些優(yōu)點(diǎn)來(lái)減少計算量。這種優(yōu)化方法能節省的計算量為： 其中N為FFT的點(diǎn)數。 4 程序總體設計 首長(cháng)分成三個(gè)模塊集合而成。即數據采集模塊，A／D轉換模塊及FFT運算模塊。數據采集模塊主要是通過(guò)定時(shí)器來(lái)控制A／D轉換器的采樣周期，將采集到的數據轉換成有符號數，并且可以以復數形式存貯。FFT的運算模塊是在8051單片機的數據存貯器上運行256點(diǎn)的FFT，并經(jīng)一快速平方根或快速對數運算，計算出對應128個(gè)頻率點(diǎn)的幅值或分貝表示值。具體流程如圖3。 5 在電話(huà)視頻中的應用 在一個(gè)會(huì )議中，當說(shuō)話(huà)人變換時(shí)。我們需要攝像頭能自動(dòng)跟蹤并檢測出說(shuō)話(huà)人的位置，這就需要用到FFT及其反變換來(lái)計算角度。 6 結論 本文主要介紹了一種在單片機中實(shí)現FFT算法的優(yōu)化方法，由于這可大大減少FFT的計算量及減少存儲數據所需要的RAM。因此其可應用在電話(huà)視頻會(huì )議中。 |
