FFT在低功率微程序控制器中的應用

摘 要:低功率微處理器的儲存空間比較小，如何用其實現FFT變換一直是一個比較重要且很難實現的問題。詳細介紹了實現FFT的具體算法包括低功率微處理器的固有缺點，采集樣本需要注意的問題及其程序實現，加窗程序以及在實現過程中應注意的問題。在低功率微處理器中實現了FFT變換，結果表明所設計的方法在低功率微處理器中具有良好的性能。

關鍵詞:低功率; 微處理器; 傅里葉變換; 加窗程序

中圖分類號:TP368.1 文獻標識碼:B

文章編號:1004-373X(2010)12-0169-04

Applications of FFT in Low-power Microcontrollers

ZHANG Hong-yun

(Huadu Polytechnic Vocational-technical School， Guangzhou 510800， China)

Abstract:It is difficult for a microcontroller to implement FFT because the random access memory (RAM) in the low-power microcontroller is very small. The low-power microcontroller and the realization condition of FFT are introduced. In addition， the algorithm to implement FFT and the disadvantages of the low-power microcontroller are presented. The matters needing attention to the acquisition of samples， programm realization and the matters for widowing to the raw signal are described. The FFT was achieved in the low-power microcontroller. An efficient method to perform FFT in the low-power microcontroller was designed. The results demonstrate that the approach is feasible .

Keywords:low-power; microcontroller; Fourier transform; windowing

0 引 言

在以前，外圍設備是更大的微處理器如特定用途集成電路和DSP中的內存[1]。現在，低功率微處理器包括了外圍設備，這樣就有機會在低功耗的情況下進行復雜的運算[2-3]。本文介紹了在低功率的微處理器中執行快速傅里葉變換(FFT)，其中微處理器包括一周期的硬件乘法器。這個應用可以實時計算輸入電壓的頻譜。為了完成此任務，一個模數轉換器對輸入信號進行采樣然后傳輸到微處理器[4]。微處理器再對樣本信號進行256點的FFT，這樣就獲得輸入電壓的頻譜。為了測試其有效性，微處理器計算頻譜的幅值然后實時地傳輸給示波器。

1 背 景

為了確定輸入樣本信號的頻譜信息，需要計算輸入樣本的離散傅里葉變換(DFT)。離散傅里葉變換定義為:

X(k)=∑ N-1 n=0 x(n)e-j2πkN，0≤k≤N-1 (1)

式中:N是樣本點數;X(k)是頻譜，與x(n)代表輸入樣本。利用歐拉方程的一致性將這個求和公式中的輸入樣本與頻譜分離為它們的實部與虛部，可得以下方程式:

XRe(k)=∑ N-1 n=0 [xRe(n)cos(2πknN)+xIm(n)sin(2πknN)]=

∑ N-1 n=0 xRecos(2πknN) (2)

XIm(k)= -∑ N-1 n=0 [xRe(n)sin(2πknN)-xIm(n)cos(2πknN)]=

-∑ N-1 n=0 xResin(2πknN) (3)

因為輸入樣本只是考慮實部。式(2)與式(3)中的求和公式的第二項消失了，假設有N個樣本，直接計算式(2)、式(3)需要2N2次乘法及2N(N-1)次加法。因此256點輸入樣本的DFT將要求131 072次乘法和130 560次加法。

已經出現了很多種FFT算法。普通的以基為2的算法連續將DFT分解成2個更小的DFT[5]。為了使其變成可能，N必須分解為2的整數冪。轉化為以2為基的FFT的步驟見圖1的蝶形計算。從圖1的蝶形計算[6]中可觀察到，獲得基為2的FFT算法的解只需要 (N/2)log2 N次乘法與Nlog2 N次加法。在圖1中的值WH通常認為是旋轉因子且能夠在執行FFT前計算得到[7]。

在圖1中，FFT的輸入具有特殊的形式。它是具有位倒置下標的原始順序。因此，當計算基為2的N=8的FFT時，輸入數據的記錄順序要求為0(000b)，1(001b)，…，0(000b)，4(100b)，…。

FFT是以正確的順序作為輸出。圖1同樣揭示了單一的蝶形計算的結果只是FFT的下一階段的輸入。因為計算是在適當的位置中完成的，舊值可以代替新獲得值且在計算N點的FFT只是需要2N個變量樣本(需要2N個變量是因為每一個變量值都有一個實部與虛部)。

圖1 利用蝶形計算FFT(其中N=8)

當完成FFT時，結果是以復數為記法的。式(4)和式(5)將復數表示形式轉變為以極坐標表示:

XMAGN(k)=X2Re(k)+X2Im(k) (4)

XPHASE(k)=arctan(XIm(k)XRe(k)) (5)

在DSP的文章里介紹了很多關于DFT/FFT的優化方法，使其計算速度更快且需要的計算量更少，其中一個比較重要的優化方法(也可能是最容易執行的)。從觀察DFT中可以獲得，因為具有N點的實值信號的DFT是以X(N/2)為對稱的，因此有:

X(k)=X*(N-k) (6)

2 執行要點

寫代碼實現DFT不是一件容易的事，因為用低功率的微處理器實現DFT算法的實際情況是相當復雜的。例如，這些微處理器通常:

(1) 有限的內存。選擇的微處理器只有2 KB的RAM。從上面敘述可知實現FFT至少需要2N×16 B變量。微處理器不能執行樣本點數N大于512的FFT。這是不現實的，因為別的固件同樣需要一些字節的RAM。因此在實際執行的過程中，通常將樣本點數局限在256點。使用16 B的變量表示每一個值的實部與虛部，這種情況下對于FFT的數據需要1 024 B的RAM。

(2) 有限的速度。盡管低功率的微處理器具有高達每秒百萬條指令的速度，仍然需要一些優化方法來減少在執行FFT過程中所用到的指令。所幸的是在應用過程中，C編譯器包括很多優化的級別設置。小心使用芯片的硬件乘法同樣可以使得代碼優化到一個可以接受的水平。

(3) 沒有浮點數功能。所選擇的微處理器特別是那些低功率的微處理器沒有浮點數功能。因此所有的計算都需要定點算法。為了表示分數，固件將使用有符號的Q8.7標記。因此固件將假設:0~6 B表示每一數字的分數部分;7~14 B表示每一數字的整數部分;第15字節是這個數字的符號位。

這種形式對于加法和減法是沒有影響的，但是對于乘法則必須注意，使所有數據排成Q8.7的形式。例如對于Q8.7的乘法如下:

-0.5×1.375 =-64×176=

(1111 1111 1100 0000)b×(0000 0000 1011 0000)b=

(1101 0100 0)b= -88= -0.687 5 (7)

為了獲得比較精確的FFT結果，Q8.7排列形式的一致性同樣適用于具有比較大樣本點數的FFT。例如，模/數轉換器以實部和虛部互補的形式提供8位的符號數。如果輸入的是直流電壓(+127為有符號的8位樣本數)，從X(0)中將會完全獲得其頻譜，以Q8.7標記等于32 512。這個值很適合于用16位的符號數表示。

3 固 件

下面介紹計算基為2的FFT所需的固件。當從模/數轉換器中讀取樣本數后，存儲在數組x_n_re中。這個數組表示x(n)的實部。在執行FFT前，虛部的值初始化為零，存儲在數組x_n_im中。當執行完FFT時，頻域的幅值將代替原來的樣本值，且存儲在x_n_re和x_n_im中。

3.1 采集樣本

FFT算法假設以固定采樣率來采集樣本的。盡管這是在本文考慮范圍之外，但是如果認真對待采集樣本的代碼同樣會產生問題。例如，不穩定的采樣率將會產生錯誤的FFT結果，所以應該盡量使該情況最小化。

對模/數轉換器采樣的原碼每一次循環以及輸出結果命令都有可能對采樣率產生不穩定性。例如，系統從模/數轉換器中讀取8位的有符號數，然后存儲在16位的數組變量中。

下面列出了關于從模/數轉換器中讀取及存儲數據的2個偽碼算法。第1個記為算法1，將會引起采樣率的不穩定。因為負數樣本比正的樣本需要更多的時間來讀取及存儲。中斷同樣不能保證采樣代碼的健全。

模/數轉換器采樣(ADC)的偽碼:

算法1:不一致的采樣率。

// sample[] 是一個16-bit變量數組

for i = 0 to (N-1)

begin

doADCSampleConversion() //通知ADC開始采樣

sample[i] = read8BitSampleFromADC() //從ADC中讀取8位樣本

if (sample[i] 0x0080) //如果8-bit 樣本為負

sample[i] = sample[i] + 0xFF00 //使得16-bit字為負

end

算法2:固定的采樣率。

// sample[]是一個16 bit變量數組

for i = 0 to (N-1)

begin

doADCSampleConversion() //通知ADC開始采樣

sample[i] = read8BitSampleFromADC() //從ADC中讀取8位樣本end

for i = 0 to (N-1)

begin

if (sample[i] 0x0080) //如果8-bit 樣本為負

sample[i] = sample[i] + 0xFF00 //使得16-bit字為負

end

3.2 三角法來查尋表格

FFT利用查尋表的方法(LUTs)來代替直接計算正弦與余弦的值。下面敘述中給出了對正弦與余弦的LUTs的聲明。固件中的聲明包括在程序中自動產生這些表格的原始代碼。LUTs中的正弦與余弦都具有N/2樣本，因為旋轉因子的下標從0~(N/2)-1變化。

正弦與余弦函數的LUTs:

const int cosLUT[N/2] = {+128，+127，+127， … ，-127，-127，-127};

const int sinLUT[N/2] = {+0 ，+3 ， +6， … ，+9 ， +6， +3};

包括這些LUTs的聲明為常量，強迫編譯器將這些數據存儲在碼區而不是數據區。由于微處理器中的RAM的有限性這樣做是很重要的。由于LUTs的值必須以Q8.7方式排列，因此與正弦和余弦對應的值應該乘以27。

3.3 位倒置

位倒置(N是已知的)可以在運行中計算，利用1個查尋表格標記或者直接用一個打開的環來寫。每1種方法有其各自的大小與執行速度的平衡。本文利用開環直接寫的方法來執行位倒置。實際的固件由原碼來自動產生這個開環。

利用開環來獲得位倒置(其中N=256):

i=x_n_re[ 1]; x_n_re[ 1]=x_n_re[128]; x_n_re[128]=i;

i=x_n_re[ 2]; x_n_re[ 2]=x_n_re[ 64]; x_n_re[ 64]=i;

i=x_n_re[ 3]; x_n_re[ 3]=x_n_re[192]; x_n_re[192]=i;

i=x_n_re[ 4]; x_n_re[ 4]=x_n_re[ 32]; x_n_re[ 32]=i;

…i=x_n_re[207]; x_n_re[207]=x_n_re[243]; x_n_re[243]=i;

i=x_n_re[215]; x_n_re[215]=x_n_re[235]; x_n_re[235]=i;

i=x_n_re[223]; x_n_re[223]=x_n_re[251]; x_n_re[251]=i;

i=x_n_re[239]; x_n_re[239]=x_n_re[247]; x_n_re[247]=i;

3.4 基為2的FFT算法

在對樣本執行位倒置后，即可以計算FFT了。利用蝶形方法(見圖1)計算基為2的FFT的固件包括3個主要的循環。在循環之外包括log2N的FFT計算階段。在每一階段循環內部執行單獨的蝶形運算。

FFT算法的核心是執行每一蝶形運算的塊碼。不幸的是，這一塊碼的計算是不輕便的。MUL_1與MUL_2利用微處理器的硬件乘法來執行乘法。

3.5 復數轉化為極坐標表示

為了計算輸入信號的幅值，必須將復數X(k)轉換為極坐標來表示。幅值將代替在固件中不再需要的FFT中的原來的值。

式(4)中決定了二維的LUT其幅值而不是其計算。第1個值是頻譜實部4個最重要的位，而第2個值是頻譜虛部4個最重要的位。為了獲得這些最重要的位，16位有符號數右移11次。頻譜的實部與虛部都可以被用作下標時，它們被其絕對值代替了(因此符號位將是零)。

從式(6)中，可以知道頻譜是以X(N/2)對稱的，只有前N/2+1個幅值被轉化為極坐標表示。同樣，對于輸入樣本為實數的頻譜虛部中的X(0)與X(N/2)通常為零。因此這兩個幅值通常分別是單獨計算的。固件中用來自動計算X(k)的包括原碼。

3.6 海明窗或漢寧窗

為了實現此任務的固件包括LUTs(Q8.7形式)將海明窗或漢寧窗應用到輸入樣本中。加窗對于防止泄漏是有用的。加窗可以在時域上對輸入樣本截短。海明窗的方程如方式(8)所示，而漢寧窗則如式(9)所示[8-10]。

h(n)=0.54-0.46cos 2πnN-1(8)

h(n)=0.5-0.5cos 2πnN-1(9)

同樣，這些實際固件的注釋包括自動為這些窗函數產生LUTs的原碼。

4 測試結果

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

圖2 通過低功率微處理器計算頻譜

5 結 語

當然你可以利用無限的時間來優化及計算FFT。但是本文采取了基為2的FFT，這種方法可以很大限度地減少計算FFT所需要的加法與乘法。由于篇幅問題，有很多提高執行FFT速度的優化方法并沒有在本 文中給出。例如，對于實數的輸入樣本信號，輸入樣本的虛部通常為零，而且只有開始的一半頻譜是重要的。利用這個信息，第一和最后一個FFT階段就可以更快速的執行(但可能將需要編寫更多的代碼)。

對于低功率的微處理器，在本文中所提到的關于FFT的算法是一個好的開始。

參考文獻

[1]雒雄，曹建.基于FPGA的簡易MCU設計[J].現代電子技術，2007，30(16):387- 40.

[2]周明德.微型計算機系統原理及應用[M].北京:清華大學出版社，2002.

[3]蔣存波，孫朝華，唐博，等.基于MCU控制的便攜式測控系統的設計[J].微計算機信息，2008(32):142-144.[4]鄒逢興.計算機硬件技術基礎[M].2版.北京:高等教育出版社，2005.

[5]段小東，顧立志.高性能基4快速傅里葉變換處理器的設計[J].計算機工程，2008，34(24):238-243.

[6]程佩青.數字信號處理教程[M].北京:清華大學出版社，1995.

[7]方潔，張可，王睿，等.改進的FFT算法及應用研究[J].四川電力技術，2007，30(6):9-11.

[8]侯朝煥，閻世尊，蔣銀林.實用FFT信號處理技術[M].北京:海洋出版社，1990.

[9]譚代倫，張世祿.FFT 復指數計算的改進算法[J].樂山師范學院學報，2006，21(5):13-14.

[10]劉歡，謝志遠.分裂基FFT算法的討論與改進[J].通信技術，2008，41(3):124-125.