孫瑞一，張 巖

(哈爾濱工業(yè)大學(xué)深圳研究生院網(wǎng)絡(luò)環(huán)境智能計(jì)算重點(diǎn)實(shí)驗(yàn)室，518055 廣東深圳)

位寬優(yōu)化中乘法運(yùn)算的一種自動(dòng)范圍分析方法

孫瑞一，張 巖

(哈爾濱工業(yè)大學(xué)深圳研究生院網(wǎng)絡(luò)環(huán)境智能計(jì)算重點(diǎn)實(shí)驗(yàn)室，518055 廣東深圳)

乘法是硬件平臺(tái)中最基本的非線性運(yùn)算，而且在自動(dòng)位寬優(yōu)化過(guò)程中，目前的范圍分析方法沒(méi)有在精確的范圍分析結(jié)果和計(jì)算復(fù)雜度之間做很好折衷.為了在較低的計(jì)算復(fù)雜度前提下更準(zhǔn)確地分析乘法運(yùn)算結(jié)果的范圍，提出了改進(jìn)的仿射近似法(NAA).在改進(jìn)的仿射近似法中，利用額外噪聲項(xiàng)來(lái)表示近似產(chǎn)生的誤差，并根據(jù)誤差的特點(diǎn)把誤差分成兩部分，在不增加計(jì)算復(fù)雜度的前提下更準(zhǔn)確地估計(jì)誤差的范圍.新方法的計(jì)算復(fù)雜度是O(M1)，其中M1是乘法的兩個(gè)操作數(shù)中非零噪聲個(gè)數(shù)的和.實(shí)例分析表明，利用該方法得到的乘法結(jié)果范圍的準(zhǔn)確程度是用簡(jiǎn)單估計(jì)法得到的準(zhǔn)確程度的1.47倍，和切比雪夫近似法的準(zhǔn)確度接近.

位寬優(yōu)化;范圍分析;乘法;仿射算術(shù);仿射近似法

在硬件系統(tǒng)的設(shè)計(jì)中，為了得到較高的數(shù)據(jù)精度及動(dòng)態(tài)范圍，算法模型都用浮點(diǎn)數(shù)表示.但是在硬件上實(shí)現(xiàn)浮點(diǎn)運(yùn)算的代價(jià)很大，為了提高運(yùn)行速度、降低功耗、節(jié)省面積，在硬件實(shí)現(xiàn)階段數(shù)據(jù)一般都采用定點(diǎn)數(shù)表示.將浮點(diǎn)數(shù)轉(zhuǎn)化為定點(diǎn)數(shù)的過(guò)程被稱為位寬優(yōu)化，也叫做定點(diǎn)化.位寬優(yōu)化的目的是在滿足系統(tǒng)規(guī)格要求的前提下尋找最佳的定點(diǎn)數(shù)位寬組合使系統(tǒng)的代價(jià)(面積、功耗、速度等)最小.位寬優(yōu)化包括范圍分析(對(duì)整數(shù)部分的優(yōu)化)和精度分析(對(duì)小數(shù)部分的優(yōu)化)兩個(gè)步驟.

位寬優(yōu)化是NP－h(huán)ard問(wèn)題［1］，常用的分類方法有動(dòng)態(tài)法［2－6］和靜態(tài)法［7－10］.動(dòng)態(tài)法通過(guò)對(duì)大量的測(cè)試向量進(jìn)行反復(fù)的蒙特卡洛仿真來(lái)確定信號(hào)的位寬.它的結(jié)果質(zhì)量較高，但優(yōu)化時(shí)間長(zhǎng)，甚至占到整個(gè)設(shè)計(jì)周期的50%以上［11］.而且，動(dòng)態(tài)法不能保證測(cè)試向量沒(méi)有覆蓋到的情況也滿足系統(tǒng)規(guī)格要求.靜態(tài)法使用代碼分析手段來(lái)推導(dǎo)出信號(hào)的位寬，它不需要測(cè)試向量，所以它的執(zhí)行速度快、人為干擾因素小，而且簡(jiǎn)便易行，適于大規(guī)模系統(tǒng)的自動(dòng)優(yōu)化分析.

在硬件平臺(tái)，如Xilinx公司的FPGA或全定制的ASIC芯片中，乘法運(yùn)算是最基本也是最常用的非線性運(yùn)算.其他的非線性運(yùn)算，如除法、余弦、對(duì)數(shù)等超越函數(shù)一般都是通過(guò)加、減、乘這些基本運(yùn)算計(jì)算的.但是目前乘法運(yùn)算的范圍分析的靜態(tài)法得不到范圍的精確解，所以對(duì)乘法運(yùn)算結(jié)果的位寬優(yōu)化的準(zhǔn)確程度就關(guān)系到整個(gè)電路的位寬優(yōu)化的準(zhǔn)確程度.本文討論基于靜態(tài)法的對(duì)乘法結(jié)果的范圍分析方法.

區(qū)間算術(shù)(interval arithmetic，IA)是1960年由Moore［12］提出的解決范圍分析的方法.Cmar等［13］首次采用IA對(duì)信號(hào)的變化范圍進(jìn)行分析.但是IA在估計(jì)信號(hào)范圍時(shí)過(guò)于保守，甚至不切實(shí)際.

仿射算術(shù)(affine arithmetic，AA)保留了區(qū)間之間的相關(guān)性，這使得它比IA更精確.AA非常適于對(duì)線性操作結(jié)果的范圍分析.但是AA不能為乘法等非線性操作提供準(zhǔn)確的仿射形式.為解決該問(wèn)題，Stolfi等［14］提出了乘法的仿射近似法，包括簡(jiǎn)單估計(jì)法和切比雪夫近似法.簡(jiǎn)單估計(jì)法計(jì)算效率高，但誤差較大，分析范圍最多可達(dá)到真實(shí)范圍的4倍.這種誤差沿著數(shù)據(jù)流累積到輸出，會(huì)導(dǎo)致誤差爆炸，這限制了它在大系統(tǒng)中的應(yīng)用;切比雪夫近似法利用比簡(jiǎn)單估計(jì)法更精確的仿射形式，實(shí)現(xiàn)較好的范圍分析結(jié)果，但是它的計(jì)算過(guò)程太復(fù)雜所以不適合在大系統(tǒng)中應(yīng)用.

為了解決計(jì)算效率和計(jì)算復(fù)雜度之間的問(wèn)題，Zhang等［15］提出了一種叫N-級(jí)近似的，在分析精度和復(fù)雜度之間作折中的方法.其分析結(jié)果比用簡(jiǎn)單估計(jì)法得到的準(zhǔn)確，比切比雪夫近似法簡(jiǎn)單.但是仍不能滿足大系統(tǒng)對(duì)分析范圍的精度和復(fù)雜度的要求.Pang等［16］提出了一種新的范圍分析方法，它混合了傳統(tǒng)的IA、AA和算術(shù)變換(arithmetic transform，AT)，能得到比 AA更精確的范圍結(jié)果，但是執(zhí)行時(shí)間比AA長(zhǎng)很多.所有這些對(duì)AA的改進(jìn)方法，都以犧牲計(jì)算復(fù)雜度為代價(jià)來(lái)?yè)Q取分析的精度.它們都是把自變量的仿射形式看成是一個(gè)整體，沒(méi)有考慮仿射形式中的每一個(gè)噪聲，這樣就忽略了不同噪聲之間的獨(dú)立性和相同噪聲在不同變量中的相關(guān)性.

為了更簡(jiǎn)便、更精確的實(shí)現(xiàn)對(duì)乘法運(yùn)算結(jié)果的范圍分析，本文提出一種名為改進(jìn)的仿射近似法(novel affine arithmetic approximation，NAA)的新的仿射近似法.NAA利用一個(gè)仿射形式近似的表示乘法運(yùn)算的結(jié)果，并利用增加的額外噪聲項(xiàng)來(lái)表示近似產(chǎn)生的誤差.為了利用現(xiàn)有方法忽略的獨(dú)立性和相關(guān)性，這個(gè)誤差用各個(gè)噪聲來(lái)表示，并且在不增加計(jì)算復(fù)雜度的前提下更準(zhǔn)確的估計(jì)誤差的范圍，從而減少了新增噪聲的系數(shù).這種方法能比簡(jiǎn)單估計(jì)法得到更準(zhǔn)確的分析范圍，而且計(jì)算復(fù)雜度和簡(jiǎn)單估計(jì)法一樣，比切比雪夫近似法更簡(jiǎn)單.

1 仿射算術(shù)

為了更清楚的分析仿射近似的過(guò)程和更方便的推導(dǎo)NAA，首先介紹仿射算術(shù)的基礎(chǔ)知識(shí).

仿射算術(shù)用一次多項(xiàng)式的仿射形式^x表示一個(gè)未知的信號(hào)x為

式中:εi=［-1，1］.對(duì)于未知信號(hào) x，x0表示它的中心值;εi為第i個(gè)噪聲，代表信號(hào)x的一個(gè)獨(dú)立的、未知的噪聲源;xi為這個(gè)噪聲的系數(shù);xiεi、x0+xiεi分別為噪聲項(xiàng).

令x0=(xmax+xmin)/2，x1=(xmax-xmin)/2，信號(hào)的范圍區(qū)間ˉx=［xmin，xmax］可以轉(zhuǎn)化為等價(jià)的仿射形式為

AA通過(guò)與計(jì)算鏈中的其他信號(hào)共享噪聲εi來(lái)保留信號(hào)之間的相關(guān)性.

乘法的簡(jiǎn)單估計(jì)法的仿射形式為

這種方法的分析結(jié)果誤差很大，但是其計(jì)算復(fù)雜度是O(M1)，其中M1=max(n1，n2)，n1、n2分別為信號(hào)x、y中非零噪聲的個(gè)數(shù).

式中:m、n分別為(x-x0)(y-y0)的最大值和最小值.

計(jì)算最值m和n的計(jì)算復(fù)雜度是O(M2log M2)，其中 M2=n1+n2.

2 乘法的改進(jìn)的仿射近似法

2.1 算法分析

自變量為仿射形式的乘法，可以表示為

因?yàn)閦不是仿射形式，選擇一個(gè)仿射形式fz來(lái)近似的表示它.式(1)的前3項(xiàng)組成了一個(gè)仿射形式，為了簡(jiǎn)單，把這個(gè)仿射形式作為近似的仿射形式，即

式中:fz為z的近似表示，所以fz與z之間存在誤差，引入一個(gè)新的獨(dú)立噪聲項(xiàng)來(lái)表示這個(gè)誤差df，即

計(jì)算df的真實(shí)最大值和最小值的計(jì)算量難以承受，所以dfmax、dfmin分別為df的近似最大值和近似最小值.dfmax、dfmin與真實(shí)的最大值和最小值越接近，^z的形式越準(zhǔn)確.

綜上所述，z的仿射形式可以記為

2.2 仿射形式

df可以表示為

式中:εi，εj=［-1，1］.估計(jì)df的近似的最大值和最小值的最簡(jiǎn)單的方法就是把εi，εj的最大值和最小值代入.根據(jù)式(2)，當(dāng) i=j時(shí)，有 xiyjεiεj=.把εi，εj=［-1，1］代入，xiyi估計(jì)的近似的最大值和最小值比xiyjεiεj更精確，而且沒(méi)有增加計(jì)算復(fù)雜度.因此把df分成兩部分，即

距離df可以記為

d1的最大值和最小值分別為

和它等價(jià)的仿射形式為

d2的最大值和最小值分別為

和它等價(jià)的仿射形式為

計(jì)算一次乘法要引入兩個(gè)獨(dú)立噪聲會(huì)使接下來(lái)的計(jì)算噪聲越來(lái)越多.所以需要化簡(jiǎn)根據(jù)式(4)，的范圍為

和它等價(jià)的仿射形式為

式(4)中的εn+1和εn+2之間有相關(guān)性，但是將df分為d1和d2并沒(méi)有考慮它們之間的相關(guān)性，所以df的真實(shí)范圍一定比的范圍小，這是過(guò)估計(jì).因此，NAA的準(zhǔn)確程度比切比雪夫近似法的準(zhǔn)確程度稍低.

2.3 乘法的改進(jìn)的仿射近似法的表達(dá)式及計(jì)算復(fù)雜度分析

有了式(2)和新引入的式(5)，乘法的改進(jìn)的仿射近似法的表達(dá)式為

設(shè)n1、n2分別為^x、^y中非零噪聲的個(gè)數(shù)，M1=max(n1，n2)為n1和n2的最大值，M2=n1+n2，則切比雪夫近似法的計(jì)算復(fù)雜度為 O(M2log M2)［14］.簡(jiǎn)單估計(jì)法的計(jì)算復(fù)雜度為O(M1).

為了計(jì)算NAA的計(jì)算復(fù)雜度，把式(6)改寫為

式(7)的計(jì)算復(fù)雜度為

可以看出，NAA的計(jì)算復(fù)雜度和簡(jiǎn)單估計(jì)法的一樣，都是O(M1).很明顯M1＜M2，所以有O(M1)＜O(M2log M2).根據(jù)計(jì)算復(fù)雜度的分析，NAA比切比雪夫近似法要簡(jiǎn)單.

3 實(shí)例分析

為了比較NAA的性能，本文以包含乘法的計(jì)算為例.第1個(gè)實(shí)例是多項(xiàng)式近似.第2個(gè)實(shí)例是B-splines.這兩個(gè)實(shí)例均來(lái)自于文獻(xiàn)［8］.第3個(gè)實(shí)例是多變量多項(xiàng)式，來(lái)自于文獻(xiàn)［17－19］.將仿射算術(shù)用C++實(shí)現(xiàn)，乘法分別采用簡(jiǎn)單估計(jì)法、切比雪夫近似法和改進(jìn)的仿射近似法.這些實(shí)例的計(jì)算平臺(tái)是內(nèi)存為2.99 G的Intel(R)Pentium(R)CPU G630@2.7 GHz的32位雙核PC.

3.1 實(shí)例

實(shí)例1 多項(xiàng)式近似

對(duì) y=ln(1+x)，x=［0，1］的多項(xiàng)式近似進(jìn)行信號(hào)范圍分析，采用文獻(xiàn)［20］的4級(jí)多項(xiàng)式表達(dá)為

其中，5個(gè)四舍五入到小數(shù)點(diǎn)后第4位的系數(shù)由多項(xiàng)式曲線擬合的方法獲得.

實(shí)例2 B-splines

B-splines常用于圖像卷繞，它的基本函數(shù)B0、B1、B2、B3分別定義如下，其中，輸入 u= ［0，1］.

實(shí)例3 變量多項(xiàng)式

考察表1中的8個(gè)多變量多項(xiàng)式.

表1 多變量多項(xiàng)式函數(shù)及輸入范圍

3.2 3種方法分析范圍的比較

利用仿射近似法計(jì)算得到的變量范圍用分析范圍來(lái)表示.用分析范圍比率來(lái)表示分析范圍的準(zhǔn)確程度.分析范圍比率是用3種方法得到的分析范圍的區(qū)間間隔(ymax-ymin)與真實(shí)范圍的區(qū)間間隔的比值，表示了分析范圍的區(qū)間間隔是真實(shí)范圍的區(qū)間間隔的倍數(shù).其中，ymax、ymin分別為變量的最大值和最小值.分析范圍比率越接近1說(shuō)明分析范圍越接近真實(shí)范圍.

表2給出了用3種方法計(jì)算得到的3個(gè)例子的分析范圍和范圍比率.它顯示了利用NAA計(jì)算得到的分析范圍全部覆蓋了真實(shí)的輸出范圍.對(duì)于這些例子，利用簡(jiǎn)單估計(jì)法計(jì)算得到的范圍比率從1.04～281.19;利用切比雪夫近似法計(jì)算得到的范圍比率從1.03～233.66;利用NAA計(jì)算得到的范圍比率從1.03～221.78.利用NAA得到的范圍比率是利用簡(jiǎn)單估計(jì)法得到的范圍比率的0.18～0.99倍，范圍比率倍數(shù)的平均是0.68倍;利用NAA計(jì)算得到的范圍的比率是利用切比雪夫近似法計(jì)算得到的范圍比率的0.33～1.39倍，范圍比率倍數(shù)的平均是0.99倍.這說(shuō)明，平均來(lái)看，利用NAA計(jì)算得到的分析范圍的準(zhǔn)確程度是用簡(jiǎn)單估計(jì)法計(jì)算得到的分析范圍的準(zhǔn)確程度的1.47倍，和切比雪夫近似法的分析范圍的準(zhǔn)確度接近.

表2 3種方法分析范圍和范圍比率的比較

對(duì)于實(shí)例3中的第7個(gè)函數(shù)，利用3種靜態(tài)法得到的范圍比率都在200以上.這是因?yàn)檫@個(gè)函數(shù)最終的乘法中的兩個(gè)乘數(shù)都包含很多乘法，每一次乘法運(yùn)算都會(huì)產(chǎn)生誤差，而且這兩個(gè)乘數(shù)都是相同自變量的函數(shù)，它們的相關(guān)性很強(qiáng)，這種情況下兩個(gè)乘數(shù)的誤差會(huì)相互放大，使最終得到的范圍結(jié)果比真實(shí)范圍大很多.所以靜態(tài)法不適用于對(duì)這種情況的范圍分析，動(dòng)態(tài)法會(huì)得到更準(zhǔn)確的分析范圍.

從表2可以看出，這3種方法有一個(gè)共同的不足之處，即分析范圍的下限誤差較大.這是因?yàn)楫?dāng)變量x用仿射形式表示時(shí)，x的范圍是相對(duì)于x0中心對(duì)稱的.在計(jì)算過(guò)程中，x0是由計(jì)算鏈中變量決定的，很難保證它是在x范圍的中心.當(dāng)^x要滿足變量范圍的上限或下限時(shí)，由于x0不在x范圍的中心，^x表示的x范圍的下限或上限就有了較大的誤差.在本文所舉的例子中，都是上限大于下限的，所以表現(xiàn)為分析范圍下限誤差較大.

3.3 3種方法整數(shù)位寬和執(zhí)行時(shí)間的比較

變量的整數(shù)位寬可以由變量范圍推導(dǎo).表3列出了3種方法得到的輸出變量位寬和CPU運(yùn)行時(shí)間.B-splines的4個(gè)基本函數(shù)是在同一個(gè)程序中完成的，所以只有一個(gè)CPU時(shí)間.NAA最多比簡(jiǎn)單估計(jì)法節(jié)省2個(gè)bit位寬，比切比雪夫近似法最多節(jié)省1個(gè)bit位寬.與簡(jiǎn)單估計(jì)法相比，NAA需要0.95～1.39倍的CPU時(shí)間，而切比雪夫近似法需要54.01～57.97倍的 CPU時(shí)間.NAA和簡(jiǎn)單估計(jì)法有著近似的執(zhí)行時(shí)間，不到切比雪夫近似法執(zhí)行時(shí)間的1/50.

表3 3種方法得到的整數(shù)位寬和CPU時(shí)間的比較

4 結(jié)論

1)利用一個(gè)仿射形式近似的表示乘法運(yùn)算的結(jié)果，并利用額外噪聲項(xiàng)來(lái)表示近似產(chǎn)生的誤差.

2)把近似產(chǎn)生的誤差分成兩部分，分別用兩個(gè)噪聲來(lái)表示，能得到更精確的近似誤差的范圍.

3)與以往的范圍分析的改進(jìn)方法相比，新方法在不增加計(jì)算復(fù)雜度的前提下的，更準(zhǔn)確的估計(jì)變量的范圍.實(shí)例分析顯示NAA的分析范圍的準(zhǔn)確程度和切比雪夫近似法的準(zhǔn)確程度接近，比簡(jiǎn)單估計(jì)法更準(zhǔn)確.而且，它的計(jì)算復(fù)雜度和簡(jiǎn)單估計(jì)法的一樣，都是O(M1)，比切比雪夫近似法的小.

［1］CONSTANTINIDES G，WOEGINGER G.The complxity ofmultiple wordlength assignment［J］. Applied Mathematics Letters，2002，15(2):137－140.

［2］KUM K I，SUNG W.Combined word-length optimization and highlevel synthesis of digital signal processing systems［J］.IEEE Trans on Computer-Aided Design Integrated Circuits，and Systems，2001，20(8):921－930.

［3］CAFFARENA G，CARRERAS C，LOPEZ J A，et al.SQNR estimation of fixed-point DSP algorithms［J］.Eurasip Journal on Advances in Signal Processing，2010，2010(21):1－12.

［4］朱珂，華林，周曉方，等.JPEG2000中小波濾波器的定點(diǎn)分析及其VLSI實(shí)現(xiàn)［J］.固體電子學(xué)研究與進(jìn)展，2004，24(4):466－471，504.

［5］馬志強(qiáng)，季振洲，胡銘曾.基于超窄數(shù)據(jù)的低功耗數(shù)據(jù)Cache方案［J］.計(jì)算機(jī)研究與發(fā)展，2007，44(5):775－781.

［6］BANCIU A，CASSEAU E，MENARD D，et al.Stochastic modelingforfloating-pointto fixed-point conversion［C］//Proceedings of IEEE Workshop on Signal Processing Systems(SiPS).Beirut，Lebanon:IEEE Computer Society Press，2011:180－185.

［7］SARBISHEI O，RADECKA K，ZILIC Z.Analytical optimization of bit-widths in fixed-point LTI systems［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2012，31(3):343－355.

［8］LEE D－U，GAFFAR A A，CHEUNG R C，et al.Accuracy guaranteed bit-width optimisation［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2006，25(10):1990－2000.

［9］ROCHER R，MENARD D，SCALART P.Analytical approach for numerical accuracy estimation of fixed-point systems based on smooth operations［J］.IEEE Trans on Circuits and Systems I-Regular Papers，2012，59(10):2326－2339.

［10］KINSMAN A B，NICOLICI N.Computational vectormagnitude-based range determination for scientific abstract data types［J］.IEEE Trans on Computers，2011，60(11):1652－1663.

［11］KEDING H，WILLEMS M， COORS M， et al.FRIDGE:a fixed-point design and simulation environment［C］//Proceedings of Design，Automation and Test in Europe.Paris:DATE，1998:429－435.

［12］MOORE R E.Interval Arithmetic and Automatic Error Analysis in Digital Computing［D］.California:Stanford University，1962.

［13］CMAR R，RIJNDERS L，SCHAUMONT P，et al.A methodology and design environment for DSP ASIC fixed point refinement［C］//Proceedings of Design，Automation and Test in Europe.Munich:ACM，1999:271－276.

［14］STOLFI J，de FIGUEIREDO L H.Self-validated Numerical Methods and Applications［M］.Rio De Janeiro:Brazilian Mathematics Colloquium monograph，IMPA，1997.

［15］ZHANG Linsheng，ZHANG Yan，ZHOU Wenbiao.Tradeoff between Approximation accuracy and complexity for range analysis using affine arithmetic［J］.Journal of Signal Processing Systems，2010，61(3):279－291.

［16］PANG Y，RADECKA K.An efficient algorithm of performing range analysisforfixed-pointarithmetic circuits based on SAT checking［C］//Proceedings of IEEE International Symposium on Circuits and Systems(ISCAS).Rio de Janeiro，BRAZIL:IEEE Computer Society Press，2011:1736－1739.

［17］SHEKHAR N，KALLA P，ENESCU F.Equivalence verification of arithmetic datapaths with multiple wordlength operands ［C］//Proceedings of Design，Automation and Test in Europe.Munich:DATE，2006:824－829.

［18］GOPALAKRISHNAN S，KALLA P，MEREDITH M B，et al.Finding linear building-blocks for RTL synthesis of polynomial datapaths with fixed-size bit-vectors［C］//Proceedings of International Conference on Computer-Aided Design.San Jose:IEEE Computer Society Press，2007:143－148.

［19］SHOU Huahao，SONG Wenhao，SHEN Jie，et al.A recursive taylor method for ray casting algebraic surfaces［C］//Proceedings ofInternationalConference on Computer Graphics and Virtual Reality，Las Vegas:CGVR，2006:196－204.

［20］HORNER W G.A new method of solving numerical equations of all orders，by continuous approximation［J］.Philosophical Transactions of the Royal Society of London，1819，109:308－335.

A range analysis in automatic word length optimization for multiplication

SUN Ruiyi，ZHANG Yan
(Key Laboratory of Network Oriented Intelligent Computation，Shenzhen Graduate School，Harbin Institute of Technology，518055 Shenzhen，Guangdong，China)

To achieve more accurate result and lower computational complexity of range analysis for multiplication in automatic word length optimization，this paper presents a novel refined affine approximation method of multiplication for range analysis in automatic word length optimization，which is named novel affine arithmetic approximation(NAA).In NAA，a new noise term represents the error which is caused by approximation.This error is estimated more accurately without increasing the computational complexity.The computational complexity of NAA is O(M1)，where M1denotes the total of the nonzero noise of the two multipliers.In experiments，the accuracy of the range using NAA is 1.47 times of that using trivial range estimation，and the same as that using Chebyshev approximation.

word-length optimization;range analysis;multiplication;affine arithmetic;affine approximation method

TP391.72

A

0367－6234(2014)03－0043－06

2013－02－27.

深圳市科技研發(fā)基礎(chǔ)研究計(jì)劃資助項(xiàng)目(JC201005260168A).

孫瑞一(1980—)，女，博士研究生;

張 巖(1969—)，男，教授，博士生導(dǎo)師.

張 巖，ianzh@foxmail.com.

(編輯 張 紅)