次2n字節(jié)的加法。其中Pj（bj）為其每個bit位的布爾取值，其為1則取1，反之則為0。 
為了節(jié)省運算時間，標準乘法應(yīng)用標準右移乘法方法以便減少加法器的數(shù)量，有關(guān)這方面的具體論述請參見文［2］。
2 掃描乘法的基本原理
在執(zhí)行乘法指令時，如果每個周期所檢查的乘數(shù)位多于一位，乘法的速度便可以加快。例如，每次檢查二位，那么加法移位周期的總數(shù)就可以減半。這些逐次掃描的位組可以是分離的，也可以是重疊的。這里先簡述一下分離掃描的原理。對于乘數(shù)來講是以字節(jié)為單位的，其字長按二進制BIT來計是偶數(shù)，設(shè)被乘數(shù)A＝（AX），乘數(shù)B＝（MR）；則在掃描了最低一對乘數(shù)位（MR1，MR0）后，有四種可能的動作，如圖2所示。對于m＝（MR1，MR0）2來說，被乘數(shù)A的倍數(shù)m×A被加到當前的部分乘積上，用來生成下一個部分積。上述原理可以推廣到任意大小的掃描位組，其具體實現(xiàn)方法和分析結(jié)果請參見文［2］，這里不再敘述。
現(xiàn)考慮乘數(shù)中有一串k個連續(xù)的1，如下
列的位置…，i＋k，i＋k－1，i＋k－2，…，i，i－1，…
列的內(nèi)容…，0，1，1，…，1，0，… （2）
按常規(guī)，在移位加時，被乘數(shù)A與部分積要進行k次加法操作，但是存在
2i＋k－2i＝2i＋k－1＋2i＋k－2＋…＋2i＋1＋2i （3）
列的位置…，i＋k，i＋k－1，i＋k－2，…，i，i－1，…
列的內(nèi)容…，1，0，0，…，－1，0，… （4）
上面的－1表示執(zhí)行一次減法。利用這種乘法再編碼的方法，只要在數(shù)字串開始時作一次加法，結(jié)束時作一次減法，使這能夠代替原來的k次連續(xù)加法。顯然，當k很大時，能節(jié)省大量的加法時間。
為了方便掃描，乘數(shù)位仍按二位一組分成許多組，但一次掃描三位，二位來自現(xiàn)在的組，第三位來自下一次高次組的低位，實際上每一組的低位被檢測了二次。為了與右移算法取得一致，假定掃描乘數(shù)從右端到左端，重疊和非重疊兩種掃描模式表示見圖3。
設(shè)掃描組XR＝［Xi＋1，Xi］2；下一掃描組XR′＝［Xi＋3，Xi＋2］2；每三位一組檢測后的動作說明見圖4。其指出了每個機器周期或執(zhí)行一次單純的移位，或者執(zhí)行一次加法，或者執(zhí)行一次減法，這里只需要倍數(shù)2A或4A。當下一對的低次位xi＋2為0時，三位中最左邊的1經(jīng)常指示一串1的左端（結(jié)束）。依式（3）所描述的特性，在具有非零的乘數(shù)位時應(yīng)該執(zhí)行加法。另一方面，當xi＋2＝1 時，即意味著是一串1的右端（開始）或中心，按照串特性需要作一次減法，在每個加法周期中，部分乘積每次要右移二位。這就使部分乘積比它應(yīng)該具有的數(shù)值少了4倍被乘數(shù)（－4A）。這可以用在下一步掃描中加上所需被乘數(shù)的倍數(shù)與4倍數(shù)的差值來校正。倍數(shù)2A或4A進入加法器的地點是重要的。如果一對的尾數(shù)是 0，那么所得到的部分乘積是正確的，而且下一次的操作是一次加法。如果一對的結(jié)尾是1，則所得到的部分乘積太大，所以下一次操作將是一次減法。
3 單片機重疊掃描乘法運算的實現(xiàn)
從以上原理可知，針對二位一組的情況需要五個被乘數(shù)的倍數(shù)，其數(shù)值可取為0，±2A，±4A。由于其每移二位至多操作一次加減法，在多字節(jié)的運算中對提高執(zhí)行效率有很大的益處；不過考慮到8BITMCU的移位操作并沒有二位一移的指令，對這種掃描算法有很大的障礙，必須重新考慮掃描運算如何在微型機上進行實施。
根據(jù)文［2］，MCU對字節(jié)與半字節(jié)操作的指令較強，因此可以在掃描算法的基礎(chǔ)上擴展其掃描位組，這樣在每個加法周期中的運算變得很復(fù)雜，因此首先必須研究清楚這種情況。
將乘數(shù)位按4BIT分成一組，一次掃描五位；設(shè)本組為BMi＝［Xi＋3，Xi＋2，Xi＋1，Xi］，下一次要掃描的BMi′的低位為Xi＋4；這樣在掃描過程中的情況與文［3］所介紹的情況有類似之處，但這里進行運算的次數(shù)不但與BMi有關(guān)，同時下一次掃描的低位對本算法也有重大的影響作用。假定在運算數(shù)中0，1的概率出現(xiàn)機會均等，對4位一組的掃描進行分析�！ 「鶕�(jù)重疊掃描算法的原理，BMi′低位為0時（如圖5所示），組中最左端的1指示一串1的左端（結(jié)束）。依據(jù)式（3），很容易得到每次掃描部分積所要加的被乘數(shù)倍數(shù)（見圖5），可以得到其倍數(shù)，即相加的倍數(shù)
Pj＝｛BMi－2G［BMi／2］｝A＋BMi．A �。�2（BMi－G［BMi／2］）A （5）
其中G［］為取整函數(shù)。Pj實質(zhì)上均與2A有關(guān)，這一點從圖中可以看到。如果一組的結(jié)尾是零，那么所得到部分乘積是正確的，按正常操作；如果一組的結(jié)尾是1，那么所得的部分積同上一次掃描有關(guān)；所以此時只是在掃描第一組時做一下記錄，在最后完成時針對它在最尾端減一次A即可。這一點對于BMi′低位為1時也成立。其部分積加的情況如圖6所示。
不甚理想，但在總體上還是有很大的改進。
4 結(jié) 論
以上介紹的是重疊均勻移位掃描算法，前面談到重疊非均勻移位掃描算法，有關(guān)這種算法的詳細介紹請參見其他文獻。
在以上過程中，是假定BMi中的Xi＋3，Xi＋2，Xi＋1，Xi值的1，0分布服從自然概率，然而在運算中由于Xi＋4的作用，在對某區(qū)間數(shù)據(jù)進行操作時存在差異，通過對一些運算區(qū)間的數(shù)據(jù)進行了統(tǒng)計，其Xi＋4與BMi值的分布概率如圖9所示；以實際的一組分布來驗證重疊算法運算時間的縮短情況，如圖10所示（S1為重疊掃描算法，S2為標準算法；圖中前面為S1，后面陰影為S2）�？梢钥吹街丿B掃描法對浮點多字節(jié)乘法運算有很大的改進，它打破了移位加法的傳統(tǒng)乘法算法，有了算法的預(yù)測功能，提高了乘法運算的速度。本算法在某軍工項目中得到應(yīng)用，效果很好。
2 陳 宇，王遵立．MC－51單片微型機上實現(xiàn)的快速掃描浮點乘法運算．數(shù)據(jù)采集與處理，1992，（9）：151～153
3 陳 宇，畢淑艷，王遵立，等．MCS－51單片機實現(xiàn)的快速浮點多字節(jié)BCD乘除運算．電子技術(shù)應(yīng)用，1998，（2）：17～19
4 Chen T C．A binary multiplication scheme based onsquaring．IEEE Trans Comput，1971，C－20（6）：678～680
5 Booth A D．A signed binary multiplication technique．Quart Journ Mech and Appl，Math，1951，4（2）：236～240
6 Garner H L．A ring model for the study for a binarymultiplier using 2，3 or 4－bit at a time．IEEE Trans，1959，EC－80（1）：25～30
第一作者簡介 王遵立，男，研究員，1948年5月生。發(fā)表過“雙基色LED圖文顯示屏的可靠性分配”（《數(shù)據(jù)采集與 處理》，1999年第1期）等論文。
