FFT 在單片機C8051中的實現
加入技術交流群
0 引言
由于單片機的性價比高，因此在數據采集及頻譜分析系統(tǒng)中往往取代DSP芯片而被廣泛使用。在數字信號處理中，離散傅里葉變換(Discrete Fourier Transform，DFT)是常用的變換方法，它在各種數字信號處理系統(tǒng)中扮演著重要的角色?？焖俑道锶~變換(Fast Fourier Transfonn，FFT)并不是與離散傅里葉變換不同的另一種變換，而是為了減少DFT計算次數的一種快速有效的算法，且它們都是為了將信號變換到頻域并進行相應的頻譜分析。雖然FFT是一種快速的運算方法，但是為了計算N點的FFT依然需要Nlog2N次加法和0．5Nlog2N次乘法。當N比較大時，其運算復雜度對RAM的需求也是很大的。在本文中，我們將探討如何優(yōu)化FFT算法，并將其在單片機中實現。
雖然在實現FFT方面已有很好的芯片來解決其運算速度及RAM容量的問題，但由于單片機的成本相對比較低。因此討論在單片機中實現FFT算法具有現實意義。最后本文還給出了用單片機實現FFT在雷達檢測中的應用。
1 基數為2的FFT算法
FFT的輸出與DFT的輸出是一致的，但冗余的計算在FFT中已被減去，使得其計算速度比較快。對于N-點的傅里葉變換，DFT需要的計算復雜度是N2，而FFT需要的計算復雜度是N/2log2N。因此當N比較大時，使用FFT做傅里葉變換將會大大減少計算量。比如做64點的DFT需要4096的計算復雜度，而使用FFT只需要192的計算復雜度。在單片機中，當使用別的優(yōu)化方法時，FFT的計算需要更少的時間。
在本文中，使用FFT時，我們關心的是如何減少為了存儲中間數據所需要的臨時內存空間。在執(zhí)行FFT時，輸入數據和輸出數據將以比特倒序的方式存儲。在順序與倒序之間改變時，每一數據點與數據集里的另一數據點的位置相換是由將樣本系列的順序倒置決定的。例如，在16點的FFT變換，樣本存儲的地址是001 b將與存儲在100 b位置上的樣本互換。具有倒序字節(jié)的位置是和沒有倒序字節(jié)的位置是相等的，比如0110 b是不互換位置的。計算FFT的順序是由FFT的輸入或輸出是否需要以倒序保存決定的。
2 對輸入數據加窗
FFT變換可以作用在具有有限時間長度的數據，但是對此數據集進行一個假設：就是周期的，且無限次重復。當樣本數據以這種方式重復時，最后一個樣本(下標[N-1])是緊接著下一周期中的第一個樣本([0])的。如圖1所示，當數據在整個樣本集中不是周期性的，則當對整個樣本做FFT時會導致不連續(xù)性。正因為這樣，數據在進行FFT變換前通常需要加窗。加窗使得樣本集變成周期性且去掉在第一個樣本與最后一個樣本之間的不連續(xù)。由于加窗改變了輸入數據，在頻域上它將產生一些噪聲。加窗會將信號的能量伸展到幾個點上。能量分布會削弱信號的峰值。大部分信號的原始內容存儲在主要部分里，當一部分發(fā)生旁瓣泄漏(如圖2所示)，主要部分的寬度和旁瓣的高度由應用在信號的加窗算法決定。一些窗函數及其性能如表1所示。為計算N點FFT的加窗函數的系數的一些方程如表2所示。更多關于加窗算法與他們的參數參見文獻[2]。
相關推薦技術專區(qū) |
評論