0 引言
    在以前，外圍設(shè)備是更大的微處理器如特定用途集成電路和DSP中的內(nèi)存?，F(xiàn)在，低功率微處理器包括了外圍設(shè)備，這樣就有機(jī)會在低功耗的情況下進(jìn)行復(fù)雜的運(yùn)算。本文介紹了在低功率的微處理器中執(zhí)行快速傅里葉變換(FFT)，其中微處理器包括一周期的硬件乘法器。這個(gè)應(yīng)用可以實(shí)時(shí)計(jì)算輸入電壓的頻譜。
    為了完成此任務(wù)，一個(gè)模數(shù)轉(zhuǎn)換器對輸入信號進(jìn)行采樣然后傳輸?shù)轿⑻幚砥?。微處理器再對樣本信號進(jìn)行256點(diǎn)的FFT，這樣就獲得輸入電壓的頻譜。為了測試其有效性，微處理器計(jì)算頻譜的幅值然后實(shí)時(shí)地傳輸給示波器。

1 背景
    為了確定輸入樣本信號的頻譜信息，需要計(jì)算輸入樣本的離散傅里葉變換(DFT)。離散傅里葉變換定義為：
   
式中：N是樣本點(diǎn)數(shù)；X(k)是頻譜，與x(n)代表輸入樣本。利用歐拉方程的一致性將這個(gè)求和公式中的輸入樣本與頻譜分離為它們的實(shí)部與虛部，可得以下方程式：
   
    因?yàn)檩斎霕颖局皇强紤]實(shí)部。式(2)與式(3)中的求和公式的第二項(xiàng)消失了，假設(shè)有N個(gè)樣本，直接計(jì)算式(2)、式(3)需要2N2次乘法及2N(N-1)次加法。因此256點(diǎn)輸入樣本的DFT將要求131072次乘法和130560次加法。
    已經(jīng)出現(xiàn)了很多種FFT算法。普通的以基為2的算法連續(xù)將DFT分解成2個(gè)更小的DFT。為了使其變成可能，N必須分解為2的整數(shù)冪。轉(zhuǎn)化為以2為基的FFT的步驟見圖1的蝶形計(jì)算。從圖1的蝶形計(jì)算中可觀察到，獲得基為2的FFT算法的解只需要(N／2)log2N次乘法與Nlog2N次加法。在圖l中的值WH通常認(rèn)為是旋轉(zhuǎn)因子且能夠在執(zhí)行FFT前計(jì)算得到。

    在圖1中，F(xiàn)FT的輸入具有特殊的形式。它是具有位倒置下標(biāo)的原始順序。因此，當(dāng)計(jì)算基為2的N=8的FFT時(shí)，輸入數(shù)據(jù)的記錄順序要求為O(000b)，1(001b)，…，0(000b)，4(100b)，…。
    FFT是以正確的順序作為輸出。圖1同樣揭示了單一的蝶形計(jì)算的結(jié)果只是FFT的下一階段的輸入。因?yàn)橛?jì)算是在適當(dāng)?shù)奈恢弥型瓿傻?，舊值可以代替新獲得值且在計(jì)算N點(diǎn)的FFT只是需要2N個(gè)變量樣本(需要2N個(gè)變量是因?yàn)槊恳粋€(gè)變量值都有一個(gè)實(shí)部與虛部)。
    當(dāng)完成FFT時(shí)，結(jié)果是以復(fù)數(shù)為記法的。式(4)和式(5)將復(fù)數(shù)表示形式轉(zhuǎn)變?yōu)橐詷O坐標(biāo)表示：
   
    在DSP的文章里介紹了很多關(guān)于DFT／FFT的優(yōu)化方法，使其計(jì)算速度更快且需要的計(jì)算量更少，其中一個(gè)比較重要的優(yōu)化方法(也可能是最容易執(zhí)行的)。
    從觀察DFT中可以獲得，因?yàn)榫哂蠳點(diǎn)的實(shí)值信號的DFT是以X(N／2)為對稱的，因此有：
    [!--empirenews.page--]
2 執(zhí)行要點(diǎn)
    寫代碼實(shí)現(xiàn)DFT不是一件容易的事，因?yàn)橛玫凸β实奈⑻幚砥鲗?shí)現(xiàn)DFT算法的實(shí)際情況是相當(dāng)復(fù)雜的。例如，這些微處理器通常：
    (1)有限的內(nèi)存。選擇的微處理器只有2 KB的RAM。從上面敘述可知實(shí)現(xiàn)FFT至少需要2N×16 B變量。微處理器不能執(zhí)行樣本點(diǎn)數(shù)N大于512的FFT。這是不現(xiàn)實(shí)的，因?yàn)閯e的固件同樣需要一些字節(jié)的RAM。因此在實(shí)際執(zhí)行的過程中，通常將樣本點(diǎn)數(shù)局限在256點(diǎn)。使用16 B的變量表示每一個(gè)值的實(shí)部與虛部，這種情況下對于FFT的數(shù)據(jù)需要1024B的RAM。
    (2)有限的速度。盡管低功率的微處理器具有高達(dá)每秒百萬條指令的速度，仍然需要一些優(yōu)化方法來減少在執(zhí)行FFT過程中所用到的指令。所幸的是在應(yīng)用過程中。C編譯器包括很多優(yōu)化的級別設(shè)置。小心使用芯片的硬件乘法同樣可以使得代碼優(yōu)化到一個(gè)可以接受的水平。
    (3)沒有浮點(diǎn)數(shù)功能。所選擇的微處理器特別是那些低功率的微處理器沒有浮點(diǎn)數(shù)功能。因此所有的計(jì)算都需要定點(diǎn)算法。為了表示分?jǐn)?shù)，固件將使用有符號的Q8．7標(biāo)記。因此固件將假設(shè)：O～6 B表示每一數(shù)字的分?jǐn)?shù)部分；7～14 B表示每一數(shù)字的整數(shù)部分；第15字節(jié)是這個(gè)數(shù)字的符號位。
    這種形式對于加法和減法是沒有影響的，但是對于乘法則必須注意，使所有數(shù)據(jù)排成Q8．7的形式。例如對于Q8．7的乘法如下：

    為了獲得比較精確的FFT結(jié)果，Q8．7排列形式的一致性同樣適用于具有比較大樣本點(diǎn)數(shù)的FFT。例如，模／數(shù)轉(zhuǎn)換器以實(shí)部和虛部互補(bǔ)的形式提供8位的符號數(shù)。如果輸入的是直流電壓(+127為有符號的8位樣本數(shù))，從X(0)中將會完全獲得其頻譜，以Q8．7標(biāo)記等于32512。這個(gè)值很適合于用16位的符號數(shù)表示。

3 固件
    下面介紹計(jì)算基為2的FFT所需的固件。當(dāng)從模／數(shù)轉(zhuǎn)換器中讀取樣本數(shù)后，存儲在數(shù)組x_n_re中。這個(gè)數(shù)組表示x(n)的實(shí)部。在執(zhí)行FFT前，虛部的值初始化為零，存儲在數(shù)組x_n_im中。當(dāng)執(zhí)行完FFT時(shí)，頻域的幅值將代替原來的樣本值，且存儲在x_n_re和x_n_im中。
3．1 采集樣本
    FFT算法假設(shè)以固定采樣率來采集樣本的。盡管這是在本文考慮范圍之外，但是如果認(rèn)真對待采集樣本的代碼同樣會產(chǎn)生問題。例如，不穩(wěn)定的采樣率將會產(chǎn)生錯(cuò)誤的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個(gè)偽碼算法。第1個(gè)記為算法l，將會引起采樣率的不穩(wěn)定。因?yàn)樨?fù)數(shù)樣本比正的樣本需要更多的時(shí)間來讀取及存儲。中斷同樣不能保證采樣代碼的健全。
    模／數(shù)轉(zhuǎn)換器采樣(ADC)的偽碼：
    算法1：不一致的采樣率。
   
3．2 三角法來查尋表格
    FFT利用查尋表的方法(LUTs)來代替直接計(jì)算正弦與余弦的值。下面敘述中給出了對正弦與余弦的LUTs的聲明。固件中的聲明包括在程序中自動產(chǎn)生這些表格的原始代碼。LUTs中的正弦與余弦都具有N／2樣本，因?yàn)樾D(zhuǎn)因子的下標(biāo)從0～(N／2)-1變化。
    正弦與余弦函數(shù)的LUTs：

    包括這些LUTs的聲明為常量，強(qiáng)迫編譯器將這些數(shù)據(jù)存儲在碼區(qū)而不是數(shù)據(jù)區(qū)。由于微處理器中的RAM的有限性這樣做是很重要的。由于LUTs的值必須以Q8．7方式排列，因此與正弦和余弦對應(yīng)的值應(yīng)該乘以27。
3．3 位倒置
    位倒置(N是已知的)可以在運(yùn)行中計(jì)算，利用1個(gè)查尋表格標(biāo)記或者直接用一個(gè)打開的環(huán)來寫。每1種方法有其各自的大小與執(zhí)行速度的平衡。本文利用開環(huán)直接寫的方法來執(zhí)行位倒置。實(shí)際的固件由原碼來自動產(chǎn)生這個(gè)開環(huán)。[!--empirenews.page--]
    利用開環(huán)來獲得位倒置(其中N=256)：

3．4 基為2的FFT算法
    在對樣本執(zhí)行位倒置后，即可以計(jì)算FFT了。利用蝶形方法(見圖1)計(jì)算基為2的FFT的固件包括3個(gè)主要的循環(huán)。在循環(huán)之外包括log2N的FFT計(jì)算階段。在每一階段循環(huán)內(nèi)部執(zhí)行單獨(dú)的蝶形運(yùn)算。FFT算法的核心是執(zhí)行每一蝶形運(yùn)算的塊碼。不幸的是，這一塊碼的計(jì)算是不輕便的。MUL_1與MUL_2利用微處理器的硬件乘法來執(zhí)行乘法。
3．5 復(fù)數(shù)轉(zhuǎn)化為極坐標(biāo)表示
    為了計(jì)算輸入信號的幅值，必須將復(fù)數(shù)X(k)轉(zhuǎn)換為極坐標(biāo)來表示。幅值將代替在固件中不再需要的FFT中的原來的值。
    式(4)中決定了二維的LUT其幅值而不是其計(jì)算。第1個(gè)值是頻譜實(shí)部4個(gè)最重要的位，而第2個(gè)值是頻譜虛部4個(gè)最重要的位。為了獲得這些最重要的位，16位有符號數(shù)右移11次。頻譜的實(shí)部與虛部都可以被用作下標(biāo)時(shí)，它們被其絕對值代替了(因此符號位將是零)。
    從式(6)中，可以知道頻譜是以X(N／2)對稱的，只有前N／2+1個(gè)幅值被轉(zhuǎn)化為極坐標(biāo)表示。同樣，對于輸入樣本為實(shí)數(shù)的頻譜虛部中的X(0)與X(N／2)通常為零。因此這兩個(gè)幅值通常分別是單獨(dú)計(jì)算的。固件中用來自動計(jì)算X(k)的包括原碼。
3．6 海明窗或漢寧窗
    為了實(shí)現(xiàn)此任務(wù)的固件包括LUTs(Q8．7形式)將海明窗或漢寧窗應(yīng)用到輸入樣本中。加窗對于防止泄漏是有用的。加窗可以在時(shí)域上對輸入樣本截短。海明窗的方程如方式(8)所示，而漢寧窗則如式(9)所示。
   
    同樣，這些實(shí)際固件的注釋包括自動為這些窗函數(shù)產(chǎn)生LUTs的原碼。

4 測試結(jié)果
    為了對FFT結(jié)果測試，利用微處理器中的通用異步收發(fā)報(bào)機(jī)端口。固件將幅值X(k)上傳到PC上。這個(gè)程序包括FFT圖表，即利用一個(gè)窗口應(yīng)用程序從PC中的串行端口中讀取這些幅值，實(shí)時(shí)地將計(jì)算得到的幅值利用圖表畫出來。利用微處理器對4個(gè)不同輸入電壓信號進(jìn)行200Kb／s采樣，并在圖2中輸出其FFT圖像。

5 結(jié)語
    當(dāng)然你可以利用無限的時(shí)間來優(yōu)化及計(jì)算FFT。但是本文采取了基為2的FFT，這種方法可以很大限度地減少計(jì)算FFT所需要的加法與乘法。由于篇幅問題，有很多提高執(zhí)行FFT速度的優(yōu)化方法并沒有在本文中給出。例如，對于實(shí)數(shù)的輸入樣本信號，輸入樣本的虛部通常為零，而且只有開始的一半頻譜是重要的。利用這個(gè)信息，第一和最后一個(gè)FFT階段就可以更快速的執(zhí)行(但可能將需要編寫更多的代碼)。對于低功率的微處理器，在本文中所提到的關(guān)于FFT的算法是一個(gè)好的開始。