低端嵌入式系統中物理量回歸算法的優化

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

關鍵詞：低端嵌入式系統;A/D;物理量回歸;查表法

中圖分類號：TP311 文獻標識碼：B 文章編號：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

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

A/D轉換即數/模轉換，其目的是把模擬信號轉換為數字信號。圖1表示A/D轉換的過程，其中，①表示A/D采樣的過程，采集實際物理量經過傳感器和相應的變換電路轉化成MCU能夠處理的數字量，也稱A/D采樣值或A/D值。但有時用戶需要嵌入式系統提供人們容易識別的實際值，這時需要把A/D采樣得到的數字量轉化成實際值，如圖1中的②所示。這種將A/D值與實際值對應起來的過程稱為物理量回歸。例如：利用MCU采集當前室內溫度，A/D值為138，這個數值代表的實際溫度是多少度；如果當前室內溫度是22.6 ℃，則138對應22.6 ℃，物理量回歸就是要找到這種對應關系。

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

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

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

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

1.1 公式法

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

說明：103表示25 ℃時標準阻值為10 kΩ，R1=10 kΩ，B=3 435，T2=25+273=298，T1為絕對溫度，T1=T+273（如：溫度為20 ℃，T1=20+273=293）。其阻值與溫度的關系如圖3所示。

圖3 MF58傳感器阻值與溫度的關系假設通過TCL2543采集的A/D值為AD_N，根據分壓原理得：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值可以算出對應溫度值。很多編譯器支持指數運算，通過調用C庫函數實現對數運算，但硬件上MCU不支持對數指令。首先將式(4)簡化，得公式(5)：

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

C語言實現對數函數的思想是用Taylor公式展開的方法。先將ln t轉化成ln(1+x)，在0

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

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

公式法通常只適合于線性關系等簡單運算且測量范圍較小的場合，這種方法的優點是程序設計簡單。低端嵌入式的應用開發中，MCU并不擅長做那些復雜的高精度的數學運算^［3］。對于這些消耗時間的運算，可以采用空間換取時間的方法，預先將函數值計算出來，以表的形式置于程序存儲區中，程序運行時直接查表即可，減少了程序執行過程中計算的工作量^［4］，這就是查表法。

1.2 查表法

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

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

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

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

//對應溫度 {0 ℃ ，0.1 ℃，0.2 ℃…10 ℃…50 ℃

4030，4031， 4031， 4031}

//|| || ||||

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

對應的查表程序如下：

/*Convert:將采集到的A/D值轉化成對應實際溫度

*功能：將采集到的A/D值轉化成對應的實際溫度

*入口：*ZS整數部分，*XS小數部分

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

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

unsigned char Convert(unsigned int *ADValue，

unsigned char *ZS，unsigned char *XS)

{

unsigned int i=0，j=0;

//不在查找范圍內，返回0xFF，查找

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

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

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

j= (i-1)/10;

*ZS=j; //整數部分

*XS=i-1-10*j;//小數部分

return 0x00;

}

算法分析：平均查找長度為N/2，最大查找長度為N。也就是說查找對應的溫度要平均比較500個數字，最多要比較1 000個數字。

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

8099 E6 17lda 23，X ;4個周期

809B AB 01add #1;2個周期

809D E7 17sta 23，X ;3個周期

809F E6 16lda 22，X ;4個周期

80A1 A9 00adc #0;2個周期

80A3 E7 16stA 22，X ;3個周期

可以看出進行1次比較需要4+2+3+4+2+3=18個周期。N=1 000時，就需要18 000個周期，對于低端MCU而言，這也是不可取的。需要尋找一種高效算法或者對算法進行優化，使系統獲得更高的性能。

2 物理量回歸查表法優化算法

2.1 優化查表法

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

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

// ||||||||

//對應溫度 { 0 ℃ ， 1 ℃…99 ℃，100 ℃}

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

// ||||… ||||

//對應溫度{0℃ ，0.1℃，… 0.8 ℃，0.9 ℃

//…

//對應溫度…

//… 4031};

//…||

//對應溫度… 99.9 ℃

其對應的查找程序如下：

unsigned char Convert(unsigned int *A/DValue，

unsigned char *ZS，unsigned char *XS)

{ unsigned char i=0，j=0;

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

return 0xFF;

//尋找相對應的值在表中的位置

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

{ i++;}

*ZS = i-1;//找到整數部分

//尋找相應整數對應的2級表

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

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

return 0xFF;

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

while(*A/DValue 1

{j++;}

*XS=j-1;//找到求小數部分

return 0; //查找成功

}

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

2.2 進一步優化

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

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

0，4，8…，32 36

…，

0，0，1… 3，3};

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

3 結 語

本文通過溫度采集實例分析2種常見的物理量回歸方法：公式法和查表法，對算法的復雜度做了具體分析，并在此基礎上對算法進行優化設計，大大提高系統的性能。該優化方法在其他嵌入式系統的查表程序設計中同樣適用。

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

參 考 文 獻

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

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

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

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

［5］胡峰，王國胤.二維表快速排序的復雜度分析［J］.計算機學報，2007，30(6):963968.

［6］ 朱立新，王飛躍.特定應用的嵌入式操作系統結構方法研究［J］.計算機科學，2004(3):4243，161.

作者簡介 劉 偉 女，1983年出生，碩士研究生。主要研究方向為嵌入式系統應用。

沈安東 男，高級工程師。主要研究方向為智能控制、嵌入式系統應用。

王宜懷 男，博士，教授，碩士生導師。主要研究方向為嵌入式系統應用、模式識別。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文