在以前，外圍設(shè)備是更大的微處理器如特定用途集成電路和DSP中的內(nèi)存?，F(xiàn)在，低功率微處理器包括了外圍設(shè)備，這樣就有機會在低功耗的情況下進行復(fù)雜的運算。本文介紹了在低功率的微處理器中執(zhí)行快速傅里葉變換(FFT)，其中微處理器包括一周期的硬件乘法器。這個應(yīng)用可以實時計算輸入電壓的頻譜。
為了完成此任務(wù)，一個模數(shù)轉(zhuǎn)換器對輸入信號進行采樣然后傳輸?shù)轿⑻幚砥?。微處理器再對樣本信號進行256點的FFT，這樣就獲得輸入電壓的頻譜。為了測試其有效性，微處理器計算頻譜的幅值然后實時地傳輸給示波器。
1 背景
為了確定輸入樣本信號的頻譜信息，需要計算輸入樣本的離散傅里葉變換(DFT)。離散傅里葉變換定義為：
式中：N是樣本點數(shù)；X(k)是頻譜，與x(n)代表輸入樣本。利用歐拉方程的一致性將這個求和公式中的輸入樣本與頻譜分離為它們的實部與虛部，可得以下方程式：
因為輸入樣本只是考慮實部。式(2)與式(3)中的求和公式的第二項消失了，假設(shè)有N個樣本，直接計算式(2)、式(3)需要2N2次乘法及2N(N-1)次加法。因此256點輸入樣本的DFT將要求131072次乘法和130560次加法。
已經(jīng)出現(xiàn)了很多種FFT算法。普通的以基為2的算法連續(xù)將DFT分解成2個更小的DFT。為了使其變成可能，N必須分解為2的整數(shù)冪。轉(zhuǎn)化為以2為基的FFT的步驟見圖1的蝶形計算。從圖1的蝶形計算中可觀察到，獲得基為2的FFT算法的解只需要(N／2)log2N次乘法與Nlog2N次加法。在圖l中的值WH通常認為是旋轉(zhuǎn)因子且能夠在執(zhí)行FFT前計算得到。
在圖1中，F(xiàn)FT的輸入具有特殊的形式。它是具有位倒置下標(biāo)的原始順序。因此，當(dāng)計算基為2的N=8的FFT時，輸入數(shù)據(jù)的記錄順序要求為O(000b)，1(001b)，…，0(000b)，4(100b)，…。
FFT是以正確的順序作為輸出。圖1同樣揭示了單一的蝶形計算的結(jié)果只是FFT的下一階段的輸入。因為計算是在適當(dāng)?shù)奈恢弥型瓿傻模f值可以代替新獲得值且在計算N點的FFT只是需要2N個變量樣本(需要2N個變量是因為每一個變量值都有一個實部與虛部)。
當(dāng)完成FFT時，結(jié)果是以復(fù)數(shù)為記法的。式(4)和式(5)將復(fù)數(shù)表示形式轉(zhuǎn)變?yōu)橐詷O坐標(biāo)表示：
在DSP的文章里介紹了很多關(guān)于DFT／FFT的優(yōu)化方法，使其計算速度更快且需要的計算量更少，其中一個比較重要的優(yōu)化方法(也可能是最容易執(zhí)行的)。
從觀察DFT中可以獲得，因為具有N點的實值信號的DFT是以X(N／2)為對稱的，因此有：
2 執(zhí)行要點
寫代碼實現(xiàn)DFT不是一件容易的事，因為用低功率的微處理器實現(xiàn)DFT算法的實際情況是相當(dāng)復(fù)雜的。例如，這些微處理器通常：
(1)有限的內(nèi)存。選擇的微處理器只有2 KB的RAM。從上面敘述可知實現(xiàn)FFT至少需要2N×16 B變量。微處理器不能執(zhí)行樣本點數(shù)N大于512的FFT。這是不現(xiàn)實的，因為別的固件同樣需要一些字節(jié)的RAM。因此在實際執(zhí)行的過程中，通常將樣本點數(shù)局限在256點。使用16 B的變量表示每一個值的實部與虛部，這種情況下對于FFT的數(shù)據(jù)需要1024B的RAM。
(2)有限的速度。盡管低功率的微處理器具有高達每秒百萬條指令的速度，仍然需要一些優(yōu)化方法來減少在執(zhí)行FFT過程中所用到的指令。所幸的是在應(yīng)用過程中。C編譯器包括很多優(yōu)化的級別設(shè)置。小心使用芯片的硬件乘法同樣可以使得代碼優(yōu)化到一個可以接受的水平。
(3)沒有浮點數(shù)功能。所選擇的微處理器特別是那些低功率的微處理器沒有浮點數(shù)功能。因此所有的計算都需要定點算法。為了表示分?jǐn)?shù)，固件將使用有符號的Q8．7標(biāo)記。因此固件將假設(shè)：O～6 B表示每一數(shù)字的分?jǐn)?shù)部分；7～14 B表示每一數(shù)字的整數(shù)部分；第15字節(jié)是這個數(shù)字的符號位。
這種形式對于加法和減法是沒有影響的，但是對于乘法則必須注意，使所有數(shù)據(jù)排成Q8．7的形式。例如對于Q8．7的乘法如下：
為了獲得比較精確的FFT結(jié)果，Q8．7排列形式的一致性同樣適用于具有比較大樣本點數(shù)的FFT。例如，模／數(shù)轉(zhuǎn)換器以實部和虛部互補的形式提供8位的符號數(shù)。如果輸入的是直流電壓(+127為有符號的8位樣本數(shù))，從X(0)中將會完全獲得其頻譜，以Q8．7標(biāo)記等于32512。這個值很適合于用16位的符號數(shù)表示。
3 固件
下面介紹計算基為2的FFT所需的固件。當(dāng)從模／數(shù)轉(zhuǎn)換器中讀取樣本數(shù)后，存儲在數(shù)組x_n_re中。這個數(shù)組表示x(n)的實部。在執(zhí)行FFT前，虛部的值初始化為零，存儲在數(shù)組x_n_im中。當(dāng)執(zhí)行完FFT時，頻域的幅值將代替原來的樣本值，且存儲在x_n_re和x_n_im中。
3．1 采集樣本
FFT算法假設(shè)以固定采樣率來采集樣本的。盡管這是在本文考慮范圍之外，但是如果認真對待采集樣本的代碼同樣會產(chǎn)生問題。例如，不穩(wěn)定的采樣率將會產(chǎn)生錯誤的FFT結(jié)果，所以應(yīng)該盡量使該情況最小化。對模／數(shù)轉(zhuǎn)換器采樣的原碼每一次循環(huán)以及輸出結(jié)果命令都有可能對采樣率產(chǎn)生不穩(wěn)定性。例如，系統(tǒng)從摸／數(shù)轉(zhuǎn)換器中讀取8位的有符號數(shù)，然后存儲在16位的數(shù)組變量中。
下面列出了關(guān)于從模／數(shù)轉(zhuǎn)換器中讀取及存儲數(shù)據(jù)的2個偽碼算法。第1個記為算法l，將會引起采樣率的不穩(wěn)定。因為負數(shù)樣本比正的樣本需要更多的時間來讀取及存儲。中斷同樣不能保證采樣代碼的健全。
模／數(shù)轉(zhuǎn)換器采樣(ADC)的偽碼：
算法1：不一致的采樣率。
3．2 三角法來查尋表格
FFT利用查尋表的方法(LUTs)來代替直接計算正弦與余弦的值。下面敘述中給出了對正弦與余弦的LUTs的聲明。固件中的聲明包括在程序中自動產(chǎn)生這些表格的原始代碼。LUTs中的正弦與余弦都具有N／2樣本，因為旋轉(zhuǎn)因子的下標(biāo)從0～(N／2)-1變化。
正弦與余弦函數(shù)的LUTs：
包括這些LUTs的聲明為常量，強迫編譯器將這些數(shù)據(jù)存儲在碼區(qū)而不是數(shù)據(jù)區(qū)。由于微處理器中的RAM的有限性這樣做是很重要的。由于LUTs的值必須以Q8．7方式排列，因此與正弦和余弦對應(yīng)的值應(yīng)該乘以27。
3．3 位倒置
位倒置(N是已知的)可以在運行中計算，利用1個查尋表格標(biāo)記或者直接用一個打開的環(huán)來寫。每1種方法有其各自的大小與執(zhí)行速度的平衡。本文利用開環(huán)直接寫的方法來執(zhí)行位倒置。實際的固件由原碼來自動產(chǎn)生這個開環(huán)。
利用開環(huán)來獲得位倒置(其中N=256)：
3．4 基為2的FFT算法
在對樣本執(zhí)行位倒置后，即可以計算FFT了。利用蝶形方法(見圖1)計算基為2的FFT的固件包括3個主要的循環(huán)。在循環(huán)之外包括log2N的FFT計算階段。在每一階段循環(huán)內(nèi)部執(zhí)行單獨的蝶形運算。FFT算法的核心是執(zhí)行每一蝶形運算的塊碼。不幸的是，這一塊碼的計算是不輕便的。MUL_1與MUL_2利用微處理器的硬件乘法來執(zhí)行乘法。
3．5 復(fù)數(shù)轉(zhuǎn)化為極坐標(biāo)表示
為了計算輸入信號的幅值，必須將復(fù)數(shù)X(k)轉(zhuǎn)換為極坐標(biāo)來表示。幅值將代替在固件中不再需要的FFT中的原來的值。
式(4)中決定了二維的LUT其幅值而不是其計算。第1個值是頻譜實部4個最重要的位，而第2個值是頻譜虛部4個最重要的位。為了獲得這些最重要的位，16位有符號數(shù)右移11次。頻譜的實部與虛部都可以被用作下標(biāo)時，它們被其絕對值代替了(因此符號位將是零)。
從式(6)中，可以知道頻譜是以X(N／2)對稱的，只有前N／2+1個幅值被轉(zhuǎn)化為極坐標(biāo)表示。同樣，對于輸入樣本為實數(shù)的頻譜虛部中的X(0)與X(N／2)通常為零。因此這兩個幅值通常分別是單獨計算的。固件中用來自動計算X(k)的包括原碼。
3．6 海明窗或漢寧窗
為了實現(xiàn)此任務(wù)的固件包括LUTs(Q8．7形式)將海明窗或漢寧窗應(yīng)用到輸入樣本中。加窗對于防止泄漏是有用的。加窗可以在時域上對輸入樣本截短。海明窗的方程如方式(8)所示，而漢寧窗則如式(9)所示。
同樣，這些實際固件的注釋包括自動為這些窗函數(shù)產(chǎn)生LUTs的原碼。
4 測試結(jié)果
為了對FFT結(jié)果測試，利用微處理器中的通用異步收發(fā)報機端口。固件將幅值X(k)上傳到PC上。這個程序包括FFT圖表，即利用一個窗口應(yīng)用程序從PC中的串行端口中讀取這些幅值，實時地將計算得到的幅值利用圖表畫出來。利用微處理器對4個不同輸入電壓信號進行200Kb／s采樣，并在圖2中輸出其FFT圖像。
5 結(jié)語
當(dāng)然你可以利用無限的時間來優(yōu)化及計算FFT。但是本文采取了基為2的FFT，這種方法可以很大限度地減少計算FFT所需要的加法與乘法。由于篇幅問題，有很多提高執(zhí)行FFT速度的優(yōu)化方法并沒有在本文中給出。例如，對于實數(shù)的輸入樣本信號，輸入樣本的虛部通常為零，而且只有開始的一半頻譜是重要的。利用這個信息，第一和最后一個FFT階段就可以更快速的執(zhí)行(但可能將需要編寫更多的代碼)。對于低功率的微處理器，在本文中所提到的關(guān)于FFT的算法是一個好的開始。
下載文檔
