定點(diǎn)DSP中高精度除法的實(shí)現方案

引言

各種集成化單片數字信號處理器(DSP)以其功能強、集成度高、應用靈活、性?xún)r(jià)比高等優(yōu)點(diǎn)，在信號處理和系統控制中的主導性地位日益明顯。許多信號處理和控制需要運用除法運算。一般的數字信號處理器中沒(méi)有現成的除法指令。十多年前誕生的浮點(diǎn)DSP，由于其用硬件完成浮點(diǎn)數的運算，在數據處理和運算能力上大大超出定點(diǎn)DSP，處理除法運算也比定點(diǎn)DSP更為簡(jiǎn)單。但是定點(diǎn)DSP每器件產(chǎn)品的價(jià)格更低，這對大規模的大眾市場(chǎng)應用而言是相當重要的優(yōu)勢，也是定點(diǎn)器件至今仍是業(yè)界主流的主要原因。所以，討論定點(diǎn)DSP中除法的實(shí)現仍不失其意義。在定點(diǎn)DSP中雖然已經(jīng)有人給出除法的算法，但是由于其運算的復雜和精度難以如愿，致使一些帶有除法的好的算法在信號處理中難以得到應用。

為了提高運算結果的精度，本文在已有除法算法的基礎上進(jìn)行了一些改進(jìn)，最大限度地保證了結果的精度。最后在TI公司的TMS320C5416芯片里具體實(shí)現并驗證了這一高精度除法。

1 經(jīng)典算法

DSP中沒(méi)有現成的除法指令，除法是靠被除數與除數之間的移位相減來(lái)實(shí)現的。在C54X系列里利用減法指令SUBC和循環(huán)指令RPT實(shí)現2個(gè)16位數的相除。下面以C54X為例來(lái)具體實(shí)現經(jīng)典的除法：

C54X提供的SuBC指令僅對無(wú)符號數進(jìn)行操作，所以在移位相減開(kāi)始之前必須先將被除數和除數取絕對值，僅考慮2個(gè)正數的除法。此時(shí)除法運算有兩種情況：

當|被除數||除數|時(shí)，將|被除數|存放在累加器的高16位，然后用SUBC完成15次移位相減，相減之后在累加器A的低16位中存放商的絕對值。根據運算前被除數和除數的符號是否相同來(lái)決定是否要改變所得結果的符號。

當|被除數|≥|除數|時(shí)，將|被除數|存放在累加器的低16位，然后用SUBC完成16次移位相減，相減之后在累加器A的低16位中存放商的絕對值。根據運算前被除數和除數的符號是否相同來(lái)決定是否要改變所得結果的符號。

從實(shí)現的過(guò)程分析，當|被除數||除數|時(shí)，移位相減開(kāi)始時(shí)|被除數|和|除數|的小數點(diǎn)位置正好相差一位。第一次相減后在累加器A的O位最低位存進(jìn)的數值正是商的最高位，該位為商的小數點(diǎn)后第一位。在15次移位相減之后，累加器A低16位所得的結果為Q值為15的小數。當|被除數|≥|除數|時(shí)，在第l6次相減時(shí)，|被除數|位于A(yíng)的高16位(30～15位)上，小數點(diǎn)位在A(yíng)的15位后，和|除數|的小數點(diǎn)位正好對齊，則此次相減后在A(yíng)的 0位加上的值正好是商的最低有效整數位，相當于十進(jìn)制數中的個(gè)位。所以在16次移位相減之后，累加器A低16位所得的結果為Q值為0的整數。以此分析，當商的精確值不是整數，或者超出Q值15所表示的范圍時(shí)，此算法所得結果就達不到16位數據所能表達的精確度。

表1中任取幾組數據來(lái)說(shuō)明。

2 高精度算法

由于經(jīng)典算法在結果上存在精度不高的問(wèn)題，所以應考慮精度盡可能高的除法算法。和經(jīng)典算法一致，本算法也采用移位相減實(shí)現除法。但不同的是，在進(jìn)行移位相減之前算法對除數與被除數進(jìn)行了一些處理，并且在移位相減時(shí)不再分兩種情況。下面具體介紹算法的流程。

首先給出被除數y和除數x。由于定點(diǎn)DSP中所有的數據都以整數的形式存在，所以在這里就把y和x看成是整數，不考慮它們本身的Q值。在圖1所示的流程圖中，A和B是C5416的2個(gè)累加器。算法第一步是將x和y相乘，結果存放在B中，以便在最后從B中提取商的符號(商的符號與B的符號相同)。第二步分別對x和y取絕對值以進(jìn)行無(wú)符號數相除。第三步，分別判斷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(yíng)的高位，即AH=y，利用SUBC指令進(jìn)行1 5次移位相減。在所得的結果當中，A的低位即為商的絕對值，B的符號即為商的符號，兩者結合得到quot值。由于在移位相減之前分別對除數和被除數有一個(gè)左移放大的操作，所以在結果中就必須考慮商的Q值。

假設給定的除數和被除數是x0和y0，則進(jìn)行移位相減的兩數分別為x=x0·2n-1，y=y0·2m-2。根據計算的過(guò)程可以得到商的Q值為 (14+m-n)，所以最后的結果應該包括quot值和Q值(14+m—n)兩部分。即商=quot·2-Q。

3 實(shí)驗結果及討論

前一節中詳細介紹了高精度算法的具體流程，可以發(fā)現其與經(jīng)典算法相比，不同之處在于進(jìn)行移位相減之前把除數和被除數進(jìn)行了不同位數的左移，保證進(jìn)行移位相減的除數的數據位最高位是l，即14位為1，而被除數的第13位為1。正是這個(gè)左移使結果的精度得到了提高。

在所引用的經(jīng)典算法中，當1被除數ll除數I時(shí)所得的商為小數，而當|被除數|≥|除數|時(shí)所得的商為整數。實(shí)際上商為小數時(shí)其Q值為 15，商為整數時(shí)其Q值為O。根據后面給出的算法，結果的Q值為(14+m一n)。當|被除數||除數|時(shí)，可以得到n≤m，則商的Q值≥14；當|被除數|≥|除數|時(shí)，可以得到n≥m，則商的Q值≤14。從對比中可以發(fā)現，當|被除數|≥|除數|時(shí)結果的Q值提高了(14+m—n)。

利用高精度算法在TMS320C5416中計算上面的4組數據，所得結果如表2所列。

上面的實(shí)驗說(shuō)明，該算法使計算結果的精度有了很大的提高。取表中第三組數據進(jìn)行詳細分析，y=479、x=240，利用經(jīng)典算法結果為整數1。利用改進(jìn)后的算法，得到的結果有兩部分：quot值=3FDDH，Q值=13。由這兩部分可以算得精確的商值1．995 727 539 062 5，而479／240=1．995 83，計算結果與實(shí)際值之間的誤差為O．000105 794 270 83。當Q值=13時(shí)，定點(diǎn)數據表示形式允許的誤差為2-13=O．000 122 070 312 5，可見(jiàn)計算結果誤差在允許的誤差范圍之內，也就是說(shuō)計算結果滿(mǎn)足所推導出的精度的范圍。對比前后兩種算法，可以發(fā)現這里的計算結果精度由原來(lái)的1提高到了2-13。

通過(guò)分析可知，該算法使計算結果在精度上有了非常大的提高，但是在效率上則有所降低。如表3所列：

表3中的時(shí)鐘周期指的是DSP的機器時(shí)鐘周期。由表3可以發(fā)現高精度算法對于不同的數據所需的周期數是不一樣的，而且算法中計算被除數和除數的高位無(wú)效位數占用了大部分的周期數。

經(jīng)典算法在效率上比高精度算法高，主要是因為在高精度算法中高位無(wú)效位數的計算效率過(guò)低。用C5416計算|被除數|和|除數|的高位無(wú)效位數，效率低是由于在C5416中沒(méi)有現成的指令來(lái)探測數據中哪一位為最高有效位。表3給出的時(shí)鐘周期數是在筆者的程序中所得到的結果，由于時(shí)間匆忙和優(yōu)化方面能力的局限性，所以并不能保證在程序優(yōu)化方面做得很好，所以在C5416中對該部分程序再進(jìn)行更好的優(yōu)化以減少執行的時(shí)間是很可能的。

在TI公司C6000系列的定點(diǎn)DSP中，有專(zhuān)門(mén)的指令LMBD來(lái)快速得到累加器中從符號位開(kāi)始無(wú)效0位的個(gè)數，只需幾個(gè)周期就能完成C5416里高位無(wú)效位數的計算，所以在C6000中完成整個(gè)算法的效率與經(jīng)典算法相比肯定能夠提高。并且在C6000系列中對不同的數據進(jìn)行計算所需的時(shí)鐘周期數是一樣的，因此在C6O0O系列定點(diǎn)DSP中該算法有著(zhù)更好的實(shí)用性。

結語(yǔ)

本文介紹了高精度除法在定點(diǎn)DSP中的實(shí)現，通過(guò)與經(jīng)典除法算法的對比，顯示了其高精度的優(yōu)點(diǎn)。定點(diǎn)TMS320C5416實(shí)驗表明該算法使商的精度得到了很大的提高，但是在計算的效率上有待進(jìn)一步提高。