定點(diǎn)DSP中高精度除法的實(shí)現(xiàn)方法
引 言
各種集成化單片數(shù)字信號(hào)處理器(DSP)以其功能強(qiáng)、集成度高、應(yīng)用靈活、性價(jià)比高等優(yōu)點(diǎn),在信號(hào)處理和系統(tǒng)控制中的主導(dǎo)性地位日益明顯。許多信號(hào)處理和控制需要運(yùn)用除法運(yùn)算。一般的數(shù)字信號(hào)處理器中沒(méi)有現(xiàn)成的除法指令。十多年前誕生的浮點(diǎn)DSP,由于其用硬件完成浮點(diǎn)數(shù)的運(yùn)算,在數(shù)據(jù)處理和運(yùn)算能力上大大超出定點(diǎn)DSP,處理除法運(yùn)算也比定點(diǎn)DSP更為簡(jiǎn)單。但是定點(diǎn)DSP每器件產(chǎn)品的價(jià)格更低,這對(duì)大規(guī)模的大眾市場(chǎng)應(yīng)用而言是相當(dāng)重要的優(yōu)勢(shì),也是定點(diǎn)器件至今仍是業(yè)界主流的主要原因。所以,討論定點(diǎn)DSP中除法的實(shí)現(xiàn)仍不失其意義。在定點(diǎn)DSP中雖然已經(jīng)有人給出除法的算法,但是由于其運(yùn)算的復(fù)雜和精度難以如愿,致使一些帶有除法的好的算法在信號(hào)處理中難以得到應(yīng)用。
為了提高運(yùn)算結(jié)果的精度,本文在已有除法算法的基礎(chǔ)上進(jìn)行了一些改進(jìn),最大限度地保證了結(jié)果的精度。最后在TI公司的TMS320C5416芯片里具體實(shí)現(xiàn)并驗(yàn)證了這一高精度除法。
1 經(jīng)典算法
DSP中沒(méi)有現(xiàn)成的除法指令,除法是靠被除數(shù)與除數(shù)之間的移位相減來(lái)實(shí)現(xiàn)的。在C54X系列里利用減法指令SUBC和循環(huán)指令RPT實(shí)現(xiàn)2個(gè)16位數(shù)的相除。下面以C54X為例來(lái)具體實(shí)現(xiàn)經(jīng)典的除法:
C54X提供的SuBC指令僅對(duì)無(wú)符號(hào)數(shù)進(jìn)行操作,所以在移位相減開(kāi)始之前必須先將被除數(shù)和除數(shù)取絕對(duì)值,僅考慮2個(gè)正數(shù)的除法。此時(shí)除法運(yùn)算有兩種情況:
當(dāng)|被除數(shù)|<|除數(shù)|時(shí),將|被除數(shù)|存放在累加器的高16位,然后用SUBC完成15次移位相減,相減之后在累加器A的低16位中存放商的絕對(duì)值。根據(jù)運(yùn)算前被除數(shù)和除數(shù)的符號(hào)是否相同來(lái)決定是否要改變所得結(jié)果的符號(hào)。
當(dāng)|被除數(shù)|≥|除數(shù)|時(shí),將|被除數(shù)|存放在累加器的低16位,然后用SUBC完成16次移位相減,相減之后在累加器A的低16位中存放商的絕對(duì)值。根據(jù)運(yùn)算前被除數(shù)和除數(shù)的符號(hào)是否相同來(lái)決定是否要改變所得結(jié)果的符號(hào)。
從實(shí)現(xiàn)的過(guò)程分析,當(dāng)|被除數(shù)|<|除數(shù)|時(shí),移位相減開(kāi)始時(shí)|被除數(shù)|和|除數(shù)|的小數(shù)點(diǎn)位置正好相差一位。第一次相減后在累加器A的O位最低位存進(jìn)的數(shù)值正是商的最高位,該位為商的小數(shù)點(diǎn)后第一位。在15次移位相減之后,累加器A低16位所得的結(jié)果為Q值為15的小數(shù)。當(dāng)|被除數(shù)|≥|除數(shù)|時(shí),在第l6次相減時(shí),|被除數(shù)|位于A的高16位(30~15位)上,小數(shù)點(diǎn)位在A的15位后,和|除數(shù)|的小數(shù)點(diǎn)位正好對(duì)齊,則此次相減后在A的0位加上的值正好是商的最低有效整數(shù)位,相當(dāng)于十進(jìn)制數(shù)中的個(gè)位。所以在16次移位相減之后,累加器A低16位所得的結(jié)果為Q值為0的整數(shù)。以此分析,當(dāng)商的精確值不是整數(shù),或者超出Q值15所表示的范圍時(shí),此算法所得結(jié)果就達(dá)不到16位數(shù)據(jù)所能表達(dá)的精確度。
表1中任取幾組數(shù)據(jù)來(lái)說(shuō)明。
2 高精度算法
由于經(jīng)典算法在結(jié)果上存在精度不高的問(wèn)題,所以應(yīng)考慮精度盡可能高的除法算法。
和經(jīng)典算法一致,本算法也采用移位相減實(shí)現(xiàn)除法。但不同的是,在進(jìn)行移位相減之前算法對(duì)除數(shù)與被除數(shù)進(jìn)行了一些處理,并且在移位相減時(shí)不再分兩種情況。下面具體介紹算法的流程。
首先給出被除數(shù)y和除數(shù)x。由于定點(diǎn)DSP中所有的數(shù)據(jù)都以整數(shù)的形式存在,所以在這里就把y和x看成是整數(shù),不考慮它們本身的Q值。在圖1所示的流程圖中,A和B是C5416的2個(gè)累加器。算法第一步是將x和y相乘,結(jié)果存放在B中,以便在最后從B中提取商的符號(hào)(商的符號(hào)與B的符號(hào)相同)。第二步分別對(duì)x和y取絕對(duì)值以進(jìn)行無(wú)符號(hào)數(shù)相除。第三步,分別判斷x和y在最高有效位之前共有多少個(gè)O,分別記為n和m,即在x和y的分別有(16一n)和(16一m)個(gè)有效位。然后將x和y分別左移(n一1)位和(m一2)位,即x=x·2n-1,y=y·2m-2。第四步,將前面所得x和y再進(jìn)行移位相減,把y存放在A的高位,即AH=y,利用SUBC指令進(jìn)行1 5次移位相減。在所得的結(jié)果當(dāng)中,A的低位即為商的絕對(duì)值,B的符號(hào)即為商的符號(hào),兩者結(jié)合得到quot值。由于在移位相減之前分別對(duì)除數(shù)和被除數(shù)有一個(gè)左移放大的操作,所以在結(jié)果中就必須考慮商的Q值。
假設(shè)給定的除數(shù)和被除數(shù)是x0和y0,則進(jìn)行移位相減的兩數(shù)分別為x=x0·2n-1,y=y0·2m-2。根據(jù)計(jì)算的過(guò)程可以得到商的Q值為(14+m-n),所以最后的結(jié)果應(yīng)該包括quot值和Q值(14+m—n)兩部分。即商=quot·2-Q。
3 實(shí)驗(yàn)結(jié)果及討論
前一節(jié)中詳細(xì)介紹了高精度算法的具體流程,可以發(fā)現(xiàn)其與經(jīng)典算法相比,不同之處在于進(jìn)行移位相減之前把除數(shù)和被除數(shù)進(jìn)行了不同位數(shù)的左移,保證進(jìn)行移位相減的除數(shù)的數(shù)據(jù)位最高位是l,即14位為1,而被除數(shù)的第13位為1。正是這個(gè)左移使結(jié)果的精度得到了提高。
在所引用的經(jīng)典算法中,當(dāng)1被除數(shù)l
利用高精度算法在TMS320C5416中計(jì)算上面的4組數(shù)據(jù),所得結(jié)果如表2所列。
上面的實(shí)驗(yàn)說(shuō)明,該算法使計(jì)算結(jié)果的精度有了很大的提高。取表中第三組數(shù)據(jù)進(jìn)行詳細(xì)分析,y=479、x=240,利用經(jīng)典算法結(jié)果為整數(shù)1。利用改進(jìn)后的算法,得到的結(jié)果有兩部分:quot值=3FDDH,Q值=13。由這兩部分可以算得精確的商值1.995 727 539 062 5,而479/240=1.995 83,計(jì)算結(jié)果與實(shí)際值之間的誤差為O.000105 794 270 83。當(dāng)Q值=13時(shí),定點(diǎn)數(shù)據(jù)表示形式允許的誤差為2-13=O.000 122 070 312 5,可見(jiàn)計(jì)算結(jié)果誤差在允許的誤差范圍之內(nèi),也就是說(shuō)計(jì)算結(jié)果滿足所推導(dǎo)出的精度的范圍。對(duì)比前后兩種算法,可以發(fā)現(xiàn)這里的計(jì)算結(jié)果精度由原來(lái)的1提高到了2-13。
通過(guò)分析可知,該算法使計(jì)算結(jié)果在精度上有了非常大的提高,但是在效率上則有所降低。如表3所列:
表3中的時(shí)鐘周期指的是DSP的機(jī)器時(shí)鐘周期。由表3可以發(fā)現(xiàn)高精度算法對(duì)于不同的數(shù)據(jù)所需的周期數(shù)是不一樣的,而且算法中計(jì)算被除數(shù)和除數(shù)的高位無(wú)效位數(shù)占用了大部分的周期數(shù)。
經(jīng)典算法在效率上比高精度算法高,主要是因?yàn)樵诟呔人惴ㄖ懈呶粺o(wú)效位數(shù)的計(jì)算效率過(guò)低。用C5416計(jì)算|被除數(shù)|和|除數(shù)|的高位無(wú)效位數(shù),效率低是由于在C5416中沒(méi)有現(xiàn)成的指令來(lái)探測(cè)數(shù)據(jù)中哪一位為最高有效位。表3給出的時(shí)鐘周期數(shù)是在筆者的程序中所得到的結(jié)果,由于時(shí)間匆忙和優(yōu)化方面能力的局限性,所以并不能保證在程序優(yōu)化方面做得很好,所以在C5416中對(duì)該部分程序再進(jìn)行更好的優(yōu)化以減少執(zhí)行的時(shí)間是很可能的。
在TI公司C6000系列的定點(diǎn)DSP中,有專門的指令LMBD來(lái)快速得到累加器中從符號(hào)位開(kāi)始無(wú)效0位的個(gè)數(shù),只需幾個(gè)周期就能完成C5416里高位無(wú)效位數(shù)的計(jì)算,所以在C6000中完成整個(gè)算法的效率與經(jīng)典算法相比肯定能夠提高。并且在C6000系列中對(duì)不同的數(shù)據(jù)進(jìn)行計(jì)算所需的時(shí)鐘周期數(shù)是一樣的,因此在C6O0O系列定點(diǎn)DSP中該算法有著更好的實(shí)用性。
結(jié) 語(yǔ)
本文介紹了高精度除法在定點(diǎn)DSP中的實(shí)現(xiàn),通過(guò)與經(jīng)典除法算法的對(duì)比,顯示了其高精度的優(yōu)點(diǎn)。定點(diǎn)TMS320C5416實(shí)驗(yàn)表明該算法使商的精度得到了很大的提高,但是在計(jì)算的效率上有待進(jìn)一步提高。