引 言

1946年，第一臺電子計算機的誕生開創了計算機發展的新紀元。隨著計算機科學技術的迅速發展，計算機的應用領域越來越廣泛，并逐漸形成科學發展中的一個新的分支。在計算機的主要工作中，處理大量的數據是其一項基本功能；因而數據運算是必不可少的。于是人們設法在硬件設計與數據結構方面努力進行工作［1］，使計算機的速度不斷提高。

十幾年前，單片微型機脫穎而出，逐漸應用于微型計算機的各個領域，它不僅適用于一般的自動控　　制，而且還可以承擔高精度的數據處理工作。誠然，在許多系統中近來采用DSP來提高微機的數據處理能力，以便完成復雜的圖像處理、音頻處理、網絡通訊等功能，而且是一個趨勢；但在這些系統中仍不可忽視運算程序的執行速度，因為好的算法可以大大提高程序的執行效率［2］。同時，考慮到目前8BITMCU的主導地位及某些系統不適合配置DSP來進行數據處理［3］。因此，這里仍有必要對高精度高速度的浮點多字節運算進行進一步研究。

1　浮點多字節標準乘法

普通的計算機都采用標準的加法－移位技術來實現乘法，Mowle曾經對這些基本的乘法算法和問題作了詳細的描述［4］。對于二進制數A，B來說，設其數值為AV，BV

由此原始矩陣乘法產生了標準的移位加算法［5，6］。一般的標準浮點乘法運算分為階碼運算與尾數運算兩部分，其主要部分為尾數運算。標準尾數相乘是采用邊乘邊相加的辦法（即加法－移位）來實現的，即乘數向左移位，產生中間結果，中間結果被加至積區的方法；在整個過程中，積也與乘數一起移位。此過程如圖1所示。上述方法對于兩個n位二進制尾數的相乘結果，即乘積為2n位，也就是部分積要點n位，在運算過程中，這2n字節都有可能要有相加的操作，需2n個字節加法器。對于標準算法，相當于進行了8n次2n字節的移位，還有次2n字節的加法。其中Pj（bj）為其每個bit位的布爾取值，其為1則取1，反之則為0。

為了節省運算時間，標準乘法應用標準右移乘法方法以便減少加法器的數量，有關這方面的具體論述請參見文［2］。

2　掃描乘法的基本原理

在執行乘法指令時，如果每個周期所檢查的乘數位多于一位，乘法的速度便可以加快。例如，每次檢查二位，那么加法移位周期的總數就可以減半。這些逐次掃描的位組可以是分離的，也可以是重疊的。這里先簡述一下分離掃描的原理。對于乘數來講是以字節為單位的，其字長按二進制BIT來計是偶數，設被乘數A＝（AX），乘數B＝（MR）；則在掃描了最低一對乘數位（MR1，MR0）后，有四種可能的動作，如圖2所示。對于m＝（MR1，MR0）2來說，被乘數A的倍數m×A被加到當前的部分乘積上，用來生成下一個部分積。上述原理可以推廣到任意大小的掃描位組，其具體實現方法和分析結果請參見文［2］，這里不再敘述。

以上所描述的是分離掃描的情況，下面再介紹重疊多位掃描的情況。一般在乘數中bj為0的個數越多，則程序運行的時候對為0的情況僅僅是移位越過，而不用作加法的運算，在此種情況下的運算相對加快。因此希望對乘數的bj能否進行適當的操作，使這之在bj為1的區域也能使運算時間減少。

現考慮乘數中有一串k個連續的1，如下
　　列的位置…，i＋k，i＋k－1，i＋k－2，…，i，i－1，…
　　列的內容…，0，1，1，…，1，0，… （2）　

按常規，在移位加時，被乘數A與部分積要進行k次加法操作，但是存在
2i＋k－2i＝2i＋k－1＋2i＋k－2＋…＋2i＋1＋2i　 （3）

因此可以用下面的數符串來代替k個連續的1
　　列的位置…，i＋k，i＋k－1，i＋k－2，…，i，i－1，…
列的內容…，1，0，0，…，－1，0，… （4）

上面的－1表示執行一次減法。利用這種乘法再編碼的方法，只要在數字串開始時作一次加法，結束時作一次減法，使這能夠代替原來的k次連續加法。顯然，當k很大時，能節省大量的加法時間。

為了方便掃描，乘數位仍按二位一組分成許多組，但一次掃描三位，二位來自現在的組，第三位來自下一次高次組的低位，實際上每一組的低位被檢測了二次。為了與右移算法取得一致，假定掃描乘數從右端到左端，重疊和非重疊兩種掃描模式表示見圖3。

設掃描組XR＝［Xi＋1，Xi］2；下一掃描組XR′＝［Xi＋3，Xi＋2］2；每三位一組檢測后的動作說明見圖4。其指出了每個機器周期或執行一次單純的移位，或者執行一次加法，或者執行一次減法，這里只需要倍數2A或4A。當下一對的低次位xi＋2為0時，三位中最左邊的1經常指示一串1的左端（結束）。依式（3）所描述的特性，在具有非零的乘數位時應該執行加法。另一方面，當xi＋2＝1 時，即意味著是一串1的右端（開始）或中心，按照串特性需要作一次減法，在每個加法周期中，部分乘積每次要右移二位。這就使部分乘積比它應該具有的數值少了4倍被乘數（－4A）。這可以用在下一步掃描中加上所需被乘數的倍數與4倍數的差值來校正。倍數2A或4A進入加法器的地點是重要的。如果一對的尾數是 0，那么所得到的部分乘積是正確的，而且下一次的操作是一次加法。如果一對的結尾是1，則所得到的部分乘積太大，所以下一次操作將是一次減法。

3　單片機重疊掃描乘法運算的實現

從以上原理可知，針對二位一組的情況需要五個被乘數的倍數，其數值可取為0，±2A，±4A。由于其每移二位至多操作一次加減法，在多字節的運算中對提高執行效率有很大的益處；不過考慮到8BITMCU的移位操作并沒有二位一移的指令，對這種掃描算法有很大的障礙，必須重新考慮掃描運算如何在微型機上進行實施。

根據文［2］，MCU對字節與半字節操作的指令較強，因此可以在掃描算法的基礎上擴展其掃描位組，這樣在每個加法周期中的運算變得很復雜，因此首先必須研究清楚這種情況。

將乘數位按4BIT分成一組，一次掃描五位；設本組為BMi＝［Xi＋3，Xi＋2，Xi＋1，Xi］，下一次要掃描的BMi′的低位為Xi＋4；這樣在掃描過程中的情況與文［3］所介紹的情況有類似之處，但這里進行運算的次數不但與BMi有關，同時下一次掃描的低位對本算法也有重大的影響作用。假定在運算數中0，1的概率出現機會均等，對4位一組的掃描進行分析。　　根據重疊掃描算法的原理，BMi′低位為0時（如圖5所示），組中最左端的1指示一串1的左端（結束）。依據式（3），很容易得到每次掃描部分積所要加的被乘數倍數（見圖5），可以得到其倍數，即相加的倍數
Pj＝｛BMi－2G［BMi／2］｝A＋BMi．A　　＝2（BMi－G［BMi／2］）A （5）

其中G［］為取整函數。Pj實質上均與2A有關，這一點從圖中可以看到。如果一組的結尾是零，那么所得到部分乘積是正確的，按正常操作；如果一組的結尾是1，那么所得的部分積同上一次掃描有關；所以此時只是在掃描第一組時做一下記錄，在最后完成時針對它在最尾端減一次A即可。這一點對于BMi′低位為1時也成立。其部分積加的情況如圖6所示。