分段插值實現(xiàn)多字節(jié)快速算法

高俊勇，王明明

（空軍航空大學(xué)基礎(chǔ)部，吉林長春 130022）

目前，多種多樣的測控系統(tǒng)廣泛應(yīng)用于各行各業(yè)中，尤其是時效性要求比較高的實時控制、通信、飛行、制導(dǎo)等系統(tǒng)，數(shù)據(jù)處理和運算的速度和時間對于系統(tǒng)的技術(shù)性能更加重要和關(guān)鍵。各種從簡單到復(fù)雜的數(shù)據(jù)處理和運算主要是使用傳統(tǒng)的基于多字節(jié)乘除法的計算方法，這種計算方法主要采用重復(fù)循環(huán)方式實現(xiàn)多字節(jié)運算，字節(jié)越多計算所需的時間就越長，具有效率低、速度慢的特點，嚴重制約了系統(tǒng)的性能[1]。本文探討一種針對特定要求的新的高速計算方法，可以大幅度提高特定運算的計算速度，從而提高實時測控系統(tǒng)的性能。

1 系統(tǒng)項目概況及數(shù)學(xué)模型

本文以MCS51-89C2051 CPU、LM331壓頻轉(zhuǎn)換和4位LED數(shù)碼管等器件構(gòu)成的能實現(xiàn)監(jiān)測壓力、溫度等模擬量的儀表為例，說明分段插值實現(xiàn)多字節(jié)快速運算的算法實現(xiàn)過程。

在儀表的模擬量輸入接口，需要將輸入的溫度（量程為10℃～50℃）通過溫度變送器轉(zhuǎn)變?yōu)殡娏餍盘柌⑤斔椭羶x表模擬接口，在儀表內(nèi)部通過LM331壓頻變換電路將對應(yīng)的模擬電流信號轉(zhuǎn)換成數(shù)字頻率信號以實現(xiàn)A/D變換。上述對應(yīng)關(guān)系如下：

圖1 計數(shù)值與溫度值的線性關(guān)系

設(shè)x為對應(yīng)溫度輸入電流和LM331計數(shù)值，y為計算出的實際溫度值，始點（x0，y0）表示10℃對應(yīng)的計數(shù)0664；終點（xe，ye）表示50℃對應(yīng)的計數(shù)6512。計數(shù)值與溫度值是線性關(guān)系如圖1所示。

所以實際的溫度數(shù)據(jù)為：

在該計算公式中，參與運算的數(shù)據(jù)都大于255，需用兩個字節(jié)來表示，也就是對于單字節(jié)的89C2051 CPU需要調(diào)用雙字節(jié)的運算子程序進行實時計算。

2 傳統(tǒng)算法

計算框圖及雙字節(jié)除法框圖如圖2和圖3所示：

圖2 計算框圖

圖3 雙字節(jié)除法框圖

傳統(tǒng)算法需調(diào)用雙字節(jié)乘除法子程序[3]。僅16位的雙字節(jié)除法子程序CPU就要執(zhí)行16次循環(huán)。每次計算需要機器周期998個，運行時間為988us。

3 分段插值查表算法

采用傳統(tǒng)算法工作效率低的主要原因是，計算時需要調(diào)用采用多次循環(huán)的乘除法子程序，字節(jié)數(shù)越多則計算速度越慢[3]。因此，分段插值法的設(shè)計思想是，在計算中回避直接對多字節(jié)進行乘除運算，預(yù)先將多字節(jié)的乘除運算處理形成數(shù)據(jù)表[4]。高字節(jié)數(shù)據(jù)通過查表得到計算結(jié)果和差值，低字節(jié)數(shù)據(jù)通過進行簡單的單字節(jié)乘除運算得到，最后將兩部分合成得出最終計算結(jié)果。其計算思路過程如圖4所示。

圖4 計算思路過程

圖5 線性關(guān)系圖

具體實現(xiàn)步驟如下：

步驟一：制作數(shù)據(jù)表

在計數(shù)的量值范圍內(nèi)預(yù)先進行多組典型抽樣，然后根據(jù)公式計算結(jié)果并形成數(shù)據(jù)表。

(1)選定插值節(jié)點（本系統(tǒng)以計數(shù)值256的倍數(shù)為各節(jié)點）；(2)對各節(jié)點的計數(shù)值xn按公式（1.1）計算出對應(yīng)的溫度值yn；(3)計算每兩個節(jié)點間對應(yīng)溫度值yn和yn+1的差值。

表1 插值數(shù)據(jù)表

步驟二：實際數(shù)據(jù)處理時，取實際計數(shù)凈值的高位字節(jié)，通過查表得出對應(yīng)的溫度值和差值（如：計數(shù)凈值2770，高位字節(jié)是10，查表計算結(jié)果為275，差值為18）；再取計數(shù)凈值的低位字節(jié)按下面公式計算（計數(shù)凈值2770的低位字節(jié)為2770-2560）。

步驟三：根據(jù)公式1.2進行計算

4 結(jié)論

實際編程運行，針對上述具體問題計算，兩種算法實例對比數(shù)據(jù)如表2所示。

表6 兩種算法實例對比數(shù)據(jù)

綜上可知，分段插值查表算法無論是指令條數(shù)，還是運算時間與傳統(tǒng)算法相比都減少很多，它較好地解決了計算機的多字節(jié)復(fù)雜運算計算速度慢的問題，可以大幅度提高計算機在實時測控系統(tǒng)中的運算速度，提高測控系統(tǒng)的性能。尤其是對特定的嵌入式專項測控系統(tǒng)效果更佳。本算法的不足之處主要是目前只適用對速度有特殊要求的固定運算。

[1]呂勇,謝長生,高三紅.實時測控計算機應(yīng)用系統(tǒng)的可靠性保障技術(shù)[J].計算機應(yīng)用,2003(6):101-103.

[2]J.M.奧特加.數(shù)值分析[M].北京:高等教育出版社,1984.

[3]張越.分段插值在嵌入式系統(tǒng)中的應(yīng)用[J].南京廣播電視大學(xué)期刊,2010.

[4]李慶揚,王能超,易大義.數(shù)值分析[M].4版.北京：清華大學(xué)出版社,2001.