摘 要：在A/D轉(zhuǎn)換過程中，物理量回歸的速度直接影響到系統(tǒng)的性能。首先探討在低端嵌入式系統(tǒng)中兩種物理量回歸的常用方法：公式法和查表法。在具體應(yīng)用實(shí)例的基礎(chǔ)上，分析比較這兩種常用的方法，對(duì)它們算法的時(shí)間空間復(fù)雜度分析，指出其不足之處。然后參考操作系統(tǒng)中分頁(yè)的思想，把一維表改成二維表，對(duì)查表法進(jìn)行優(yōu)化。而后分析具體情況又做了進(jìn)一步優(yōu)化，分析得出優(yōu)化后程序在時(shí)間空間上都有很大的改進(jìn)。最后指出在其他低端嵌入式產(chǎn)品開發(fā)中，該方法同樣適用，并總結(jié)其在嵌入式系統(tǒng)與PC機(jī)程序開發(fā)的不同點(diǎn)。

關(guān)鍵詞：低端嵌入式系統(tǒng);A/D;物理量回歸;查表法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1004373X(2008)1803104

Optimized Physical Quantity Regression Algorithm in Lowend Embedded System

LIU Wei，SHEN Andong，WANG Yihuai

(Department of Computer Science and Technology，Soochow University，Suzhou，215006，China)

Abstract：In the process of A/D conversion，system performance is directly effected by the speed of physical regression.First，two common physical quantity regression methods and their limits are presented by analyzing the time and space complexity in a concrete project.Then two dimensions table is introduced by extended the one dimension table as the pagination introduced in operating system.The abovementioned method is farther optimized its time and space complexity proved to be improved rapidly.The method′s application in other lowend embedded systems and the difference of development methods between embedded system and common PC system are discussed at the end of the paper.

Keywords：lowend embedded system;A/D;physical quantity regress;searching table

低端嵌入式系統(tǒng)是以8位或16位低端微控制器(Microcontroller Unit，MCU)為核心，軟硬件復(fù)雜度比較小的系統(tǒng)。但它們以性價(jià)比高、穩(wěn)定性好等優(yōu)點(diǎn)仍然占據(jù)著巨大的市場(chǎng)。低端MCU運(yùn)算能力和內(nèi)存容量有限，因此在使用時(shí)應(yīng)注意提高程序執(zhí)行速度和節(jié)約內(nèi)存。嵌入式系統(tǒng)感知外界信息大部分是通過A/D轉(zhuǎn)換來實(shí)現(xiàn)，因此，A/D轉(zhuǎn)換是嵌入式系統(tǒng)的一個(gè)重要組成部分^［1］。物理量回歸A/D轉(zhuǎn)換中的重要步驟，其速度的快慢直接影響系統(tǒng)性能。因此，在系統(tǒng)開發(fā)過程中，物理量回歸算法的優(yōu)化顯得尤為重要。

A/D轉(zhuǎn)換即數(shù)/模轉(zhuǎn)換，其目的是把模擬信號(hào)轉(zhuǎn)換為數(shù)字信號(hào)。圖1表示A/D轉(zhuǎn)換的過程，其中，①表示A/D采樣的過程，采集實(shí)際物理量經(jīng)過傳感器和相應(yīng)的變換電路轉(zhuǎn)化成MCU能夠處理的數(shù)字量，也稱A/D采樣值或A/D值。但有時(shí)用戶需要嵌入式系統(tǒng)提供人們?nèi)菀鬃R(shí)別的實(shí)際值，這時(shí)需要把A/D采樣得到的數(shù)字量轉(zhuǎn)化成實(shí)際值，如圖1中的②所示。這種將A/D值與實(shí)際值對(duì)應(yīng)起來的過程稱為物理量回歸。例如：利用MCU采集當(dāng)前室內(nèi)溫度，A/D值為138，這個(gè)數(shù)值代表的實(shí)際溫度是多少度；如果當(dāng)前室內(nèi)溫度是22.6 ℃，則138對(duì)應(yīng)22.6 ℃，物理量回歸就是要找到這種對(duì)應(yīng)關(guān)系。

圖1 A/D轉(zhuǎn)換過程示意圖1 物理量回歸常見算法

使用低端MCU進(jìn)行A/D采集時(shí)，要選擇一種高效的物理量回歸算法，使系統(tǒng)獲得更高的性能。本文以實(shí)際項(xiàng)目中溫度采集部分為背景，敘述低端嵌入式系統(tǒng)中物理量回歸算法的優(yōu)化。該項(xiàng)目中溫度采集部分主控芯片是Freescale公司的MC908GP32芯片，通過溫度傳感器采集3路溫度，溫度的范圍為0~100 ℃，精確到0.1 ℃。A/D采集部分示意圖如圖2所示，其中，固定電阻為62 kΩ。傳感器采用熱敏電阻，型號(hào)是MF58 10334，它具有體積小、穩(wěn)定性好、可靠性高、工作溫度寬等特點(diǎn)。

圖2 溫度采集示意圖A/D轉(zhuǎn)換芯片選用TCL2543，該轉(zhuǎn)換芯片為12位，輸出范圍是［0，4 095］。當(dāng)A/D采集點(diǎn)電壓為0時(shí)，輸出0，當(dāng)電壓為5 V時(shí)，輸出4 095。根據(jù)分壓原理，A/D采集點(diǎn)數(shù)字量的值=4 095*R/(62+R)，其中R為溫度傳感器阻值，單位 kΩ。

物理量回歸的算法比較多，常用的方法有：公式法、查表法。這些算法在一些數(shù)據(jù)精度要求不高的情況下可以使用，但是如果數(shù)據(jù)跨度大，精度高時(shí)，這些算法會(huì)占用大量的資源，嚴(yán)重影響系統(tǒng)的正常進(jìn)行，此時(shí)必須對(duì)算法進(jìn)行改進(jìn)，以得到比較好的運(yùn)行效果。

1.1 公式法

熱敏電阻測(cè)溫的原理是：阻值隨溫度變化而變化，兩者之間呈函數(shù)關(guān)系。公式法首先需要根據(jù)廠家提供的技術(shù)手冊(cè)找出阻值(R)和溫度(T)之間的關(guān)系。有些是線性關(guān)系，但多數(shù)情況下是非線性的^［2］，例如MF58 10334傳感器阻值R和溫度的關(guān)系：R=R1*eB*(1T2－1T1)(1)

說明：103表示25 ℃時(shí)標(biāo)準(zhǔn)阻值為10 kΩ，R1=10 kΩ，B=3 435，T2=25+273=298，T1為絕對(duì)溫度，T1=T+273（如：溫度為20 ℃，T1=20+273=293）。其阻值與溫度的關(guān)系如圖3所示。

圖3 MF58傳感器阻值與溫度的關(guān)系假設(shè)通過TCL2543采集的A/D值為AD_N，根據(jù)分壓原理得：AD_N=4 095×6262+R(2)綜合式(1)，(2)得：AD_N=4 095×6262+10×eB*(1T+273－1298)(3)

T=11298－13 435ln(4 095×62AD_N－62)－ln 103 435－273(4)

從式(4)可知由A/D值可以算出對(duì)應(yīng)溫度值。很多編譯器支持指數(shù)運(yùn)算，通過調(diào)用C庫(kù)函數(shù)實(shí)現(xiàn)對(duì)數(shù)運(yùn)算，但硬件上MCU不支持對(duì)數(shù)指令。首先將式(4)簡(jiǎn)化，得公式(5)：

T=1 023 6303 435－298ln(253 890AD_N－62)－686－273(5)

C語(yǔ)言實(shí)現(xiàn)對(duì)數(shù)函數(shù)的思想是用Taylor公式展開的方法。先將ln t轉(zhuǎn)化成ln(1+x)，在0

(－1)n1(n+1)(1+ξ)n+1xn+1

但該展開式只能解決t在(0，2)內(nèi)的自然對(duì)數(shù)，對(duì)于t>2，根據(jù)ln t=－ln1t將對(duì)數(shù)函數(shù)進(jìn)行轉(zhuǎn)換，通過以上理論分析，可以計(jì)算出自然對(duì)數(shù)的函數(shù)。n≥5 000時(shí)，這樣一個(gè)簡(jiǎn)單的對(duì)數(shù)如ln 2運(yùn)算要花費(fèi)至少50 000個(gè)周期。顯然在這種情況下，將一個(gè)復(fù)雜的公式直接用Ｃ語(yǔ)言實(shí)現(xiàn)對(duì)于MCU來說是不可取的。

公式法通常只適合于線性關(guān)系等簡(jiǎn)單運(yùn)算且測(cè)量范圍較小的場(chǎng)合，這種方法的優(yōu)點(diǎn)是程序設(shè)計(jì)簡(jiǎn)單。低端嵌入式的應(yīng)用開發(fā)中，MCU并不擅長(zhǎng)做那些復(fù)雜的高精度的數(shù)學(xué)運(yùn)算^［3］。對(duì)于這些消耗時(shí)間的運(yùn)算，可以采用空間換取時(shí)間的方法，預(yù)先將函數(shù)值計(jì)算出來，以表的形式置于程序存儲(chǔ)區(qū)中，程序運(yùn)行時(shí)直接查表即可，減少了程序執(zhí)行過程中計(jì)算的工作量^［4］，這就是查表法。

1.2 查表法

查表法一般使用線性表。一個(gè)具有n個(gè)數(shù)據(jù)元素(或稱數(shù)據(jù)項(xiàng))的線性表，其數(shù)據(jù)元素為a1，a2，a3，a4…，an。建立一張線性表格的思路是：首先定義一個(gè)自變量表格，并且按照一定的順序進(jìn)行排列，以此構(gòu)成一張數(shù)據(jù)表；然后以表頭地址為參照（基準(zhǔn)或基址），以被自變量為索引值（或表內(nèi)偏移值），到表中查找對(duì)應(yīng)的具體數(shù)據(jù)元素。

在上述的實(shí)際項(xiàng)目中，首先根據(jù)A/D值與溫度的關(guān)系，由式(3)，可以用Excel工具算出從0~100 ℃之間每0.1 ℃對(duì)應(yīng)的A/D值(四舍五入)。例：溫度20 ℃時(shí)，T2=298，T1=273+20=293，R₂=10*e3 435*(1/293－1/298)=12.2，數(shù)字量4 095*12.2/(62+12.2)=3 423。根據(jù)分析，可建立表格:

Table［1000］={2798，2842，2846…3157…3841…，

//|||||| ||||

//對(duì)應(yīng)溫度 {0 ℃ ，0.1 ℃，0.2 ℃…10 ℃…50 ℃

4030，4031， 4031， 4031}

//|| || ||||

//… ，99.7 ℃，99.8 ℃，99.9 ℃，100 ℃}

對(duì)應(yīng)的查表程序如下：

/*Convert:將采集到的A/D值轉(zhuǎn)化成對(duì)應(yīng)實(shí)際溫度

*功能：將采集到的A/D值轉(zhuǎn)化成對(duì)應(yīng)的實(shí)際溫度

*入口：*ZS整數(shù)部分，*XS小數(shù)部分

*出口：返回實(shí)際的溫度值(包括整數(shù)和小數(shù)部分)

* 成功查找返回0x00，沒有成功找到返回0xFF */

unsigned char Convert(unsigned int *ADValue，

unsigned char *ZS，unsigned char *XS)

{

unsigned int i=0，j=0;

//不在查找范圍內(nèi)，返回0xFF，查找

if(*ADValue TableAD［900］) return 0xFF;

//成功返回0X00 ，找到在表中的位置

while(*ADValue>=TableAD［i］) i++;

j= (i-1)/10;

*ZS=j; //整數(shù)部分

*XS=i-1-10*j;//小數(shù)部分

return 0x00;

}

算法分析：平均查找長(zhǎng)度為N/2，最大查找長(zhǎng)度為N。也就是說查找對(duì)應(yīng)的溫度要平均比較500個(gè)數(shù)字，最多要比較1 000個(gè)數(shù)字。

查看其List文件，僅對(duì)程序中1條比較語(yǔ)句while(*A/DValue>=TableA/D［i］){i++;}進(jìn)行分析：

8099 E6 17lda 23，X ;4個(gè)周期

809B AB 01add #1;2個(gè)周期

809D E7 17sta 23，X ;3個(gè)周期

809F E6 16lda 22，X ;4個(gè)周期

80A1 A9 00adc #0;2個(gè)周期

80A3 E7 16stA 22，X ;3個(gè)周期

可以看出進(jìn)行1次比較需要4+2+3+4+2+3=18個(gè)周期。N=1 000時(shí)，就需要18 000個(gè)周期，對(duì)于低端MCU而言，這也是不可取的。需要尋找一種高效算法或者對(duì)算法進(jìn)行優(yōu)化，使系統(tǒng)獲得更高的性能。

2 物理量回歸查表法優(yōu)化算法

2.1 優(yōu)化查表法

MCU采集的數(shù)字值隨溫度的增加而增加，在一維表中，數(shù)據(jù)若是順序的，稱為順序表。順序表的查找有很多方法，最常見的是建立一個(gè)二級(jí)索引，這樣查找時(shí)間會(huì)大大減少^［5］。因此可以參照操作系統(tǒng)中分頁(yè)的思想，建立2張表Table1和Table2。Table1是將每一度的A/D輸出值作為1個(gè)索引，為查詢Table2表服務(wù)。Table2是100行*10列的二維數(shù)組，每度為1行，每行分成10個(gè)，每2個(gè)數(shù)代表溫度間隔0.1 ℃。表如下所示。

Table1［100］ = {2798，2838…4029，4031};

// ||||||||

//對(duì)應(yīng)溫度 { 0 ℃ ， 1 ℃…99 ℃，100 ℃}

Table2［100］［10］ = {2798，2802，… 2800，2874

// ||||… ||||

//對(duì)應(yīng)溫度{0℃ ，0.1℃，… 0.8 ℃，0.9 ℃

//…

//對(duì)應(yīng)溫度…

//… 4031};

//…||

//對(duì)應(yīng)溫度… 99.9 ℃

其對(duì)應(yīng)的查找程序如下：

unsigned char Convert(unsigned int *A/DValue，

unsigned char *ZS，unsigned char *XS)

{ unsigned char i=0，j=0;

//不在查找范圍內(nèi)，返回0xFF，查找不成功 if(*A/DValue Table1［90］)

return 0xFF;

//尋找相對(duì)應(yīng)的值在表中的位置

while(*A/DValue>=Table1［i］)

{ i++;}

*ZS = i-1;//找到整數(shù)部分

//尋找相應(yīng)整數(shù)對(duì)應(yīng)的2級(jí)表

//查找不成功，返回0xFF

if（*A/DValue < Table2［*ZS］［0］ || *A/DValue > Table2［*ZS］［9］）

return 0xFF;

//成功返回0X00 ，找到在表中的位置

while(*A/DValue 1

{j++;}

*XS=j-1;//找到求小數(shù)部分

return 0; //查找成功

}

算法分析：平均查找長(zhǎng)度為50+5=55，最大查找長(zhǎng)度為100+10=110。比一級(jí)查表最大查找長(zhǎng)度1 000提高了一個(gè)數(shù)量級(jí)。因此使用二級(jí)查表的方式更進(jìn)一步地提高了A/D采集后物理量回歸效率，在系統(tǒng)的實(shí)際使用中也證明了這一點(diǎn)。

2.2 進(jìn)一步優(yōu)化

在嵌入式產(chǎn)品中，除了需要對(duì)算法的時(shí)間復(fù)雜度進(jìn)行優(yōu)化之外，還需要節(jié)省空間的使用，盡量用小的數(shù)據(jù)類型。在設(shè)計(jì)表的過程中，采集到的A/D值大于256，所以需要用int型數(shù)組來表示A/D值。經(jīng)過觀察發(fā)現(xiàn)采集到的數(shù)據(jù)值隨溫度上升而上升，每一度之間的差值不會(huì)超過256，每0.1 ℃的差值更加不可能超過256。因此如果用差值法來考慮，即每0.1 ℃記錄對(duì)應(yīng)A/D值與溫度取整對(duì)應(yīng)A/D值的差值。這樣Table2可用char類型數(shù)組來記錄差值：

Table2［100］［10］ = {0，4，8…，32 36

0，4，8…，32 36

…，

0，0，1… 3，3};

表中的數(shù)據(jù)是放在一段連續(xù)的FLASH空間中，一個(gè)8位數(shù)據(jù)占用1個(gè)字節(jié)，1個(gè)16位數(shù)據(jù)占用2個(gè)字節(jié)。采用差值技術(shù)可以節(jié)省100個(gè)字節(jié)的空間。可以用個(gè)變量將*ADValue-Tabl1［*ZS］得到的值再進(jìn)行二次查表。這樣建表不但節(jié)約了空間，時(shí)間上也有很大的改進(jìn)。特別是在一些８位系統(tǒng)中，對(duì)單字節(jié)的處理速度比雙字節(jié)要快，在進(jìn)行大量數(shù)據(jù)頻繁比較時(shí)，可以節(jié)省更多時(shí)間。

3 結(jié) 語(yǔ)

本文通過溫度采集實(shí)例分析2種常見的物理量回歸方法：公式法和查表法，對(duì)算法的復(fù)雜度做了具體分析，并在此基礎(chǔ)上對(duì)算法進(jìn)行優(yōu)化設(shè)計(jì)，大大提高系統(tǒng)的性能。該優(yōu)化方法在其他嵌入式系統(tǒng)的查表程序設(shè)計(jì)中同樣適用。

低端嵌入式編程不同于PC機(jī)編程，其最顯著的特點(diǎn)是要和程序存儲(chǔ)資源結(jié)合起來，要注意內(nèi)存空間使用和程序執(zhí)行效率^［6］。盡量選用存儲(chǔ)空間少的數(shù)據(jù)類型，可以大大減少所生成的代碼長(zhǎng)度。在程序中盡量避免復(fù)雜的數(shù)學(xué)公式，如采用查表代替復(fù)雜的計(jì)算，提高執(zhí)行速度，從而得到高質(zhì)量、高性能的嵌入式系統(tǒng)。

參 考 文 獻(xiàn)

［1］王百鳴.兩種A /D 轉(zhuǎn)換新方法——流水并行式和流水逐次逼近比較式［J］.數(shù)據(jù)采集與處理，2000(4):119123.

［2］壽慶余，黃春華，徐克奇.A/D轉(zhuǎn)換非線性補(bǔ)償實(shí)用算法［J］.計(jì)算機(jī)工程，2002，28(10):222223.

［3］劉峰，張曉林.淺談嵌入式程序設(shè)計(jì)中的優(yōu)化問題［J］.單片機(jī)與嵌入式應(yīng)用，2006(12):6668.

［4］葉凱，楊文淑，包啟亮.基于ARM的除法運(yùn)算優(yōu)化策略［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2006(3):7880.

［5］胡峰，王國(guó)胤.二維表快速排序的復(fù)雜度分析［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(6):963968.

［6］ 朱立新，王飛躍.特定應(yīng)用的嵌入式操作系統(tǒng)結(jié)構(gòu)方法研究［J］.計(jì)算機(jī)科學(xué)，2004(3):4243，161.

作者簡(jiǎn)介 劉 偉 女，1983年出生，碩士研究生。主要研究方向?yàn)榍度胧较到y(tǒng)應(yīng)用。

沈安東 男，高級(jí)工程師。主要研究方向?yàn)橹悄芸刂啤⑶度胧较到y(tǒng)應(yīng)用。

王宜懷 男，博士，教授，碩士生導(dǎo)師。主要研究方向?yàn)榍度胧较到y(tǒng)應(yīng)用、模式識(shí)別。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文