利用重疊掃描方法改進(jìn)單片機乘法運算

區別只是改加為減，因為部分積的減值在以后的掃描中可以修正回來(lái)，不用采用補碼的運算也能完成，最常用的方法是設置輔助運算區，采用臨時(shí)記錄的方式保證其部分積在掃描任一周期保持正確結果，也稱(chēng)為臨時(shí)擴展方法，這里就不重復。這樣，在每次掃描僅剩下一個(gè)問(wèn)題，即如何處理Pj，這里Pj與文［3］中處理的方法有類(lèi)似之處。以2A為基礎，將Pj形成一個(gè)加（減）法序列，也就是將Pj變?yōu)?qA的序列，如12A＝22A＋23A。這樣就可以在一個(gè)掃描周期完成部分積的加法。這里建議讀者去探索Pj更好的形成方法，因為形成2qA的序列，1≤q≤3，要占用時(shí)間（24A可以通過(guò)半字節操作做左端拼加處理，因為24A相當于A(yíng)左移半字節，運算時(shí)直接依靠輔助運算區），同時(shí)在特殊處理上也額外占有一些運算時(shí)間，這一點(diǎn)在圖7中也可以看出來(lái)。這樣一來(lái)，在Pj的加法過(guò)程中，掃描算法在某些BMi值上并不都占優(yōu)勢，這一點(diǎn)在圖5，6中也可以體現（BMi中Xi＋3，Xi＋2，Xi＋1，Xi為1的個(gè)數決定了在標準算法中的加法次數）；但重疊掃描畢竟節省了時(shí)間，其與標準算法在一個(gè)掃描周期內的加法次數情況如圖8所示（其中系列1為重疊掃描算法，系列2為標準算法）。加之在移位中節省的時(shí)間，重疊掃描全過(guò)程的運算時(shí)間與標準右移算法的比較情況如圖8所示（S1為重疊掃描算法，S2為標準算法）。在局部區域，由于采用上述的Pj處理方法，運算時(shí)間節省情況還不甚理想，但在總體上還是有很大的改進(jìn)。

4 結 論

以上介紹的是重疊均勻移位掃描算法，前面談到重疊非均勻移位掃描算法，有關(guān)這種算法的詳細介紹請參見(jiàn)其他文獻。

在以上過(guò)程中，是假定BMi中的Xi＋3，Xi＋2，Xi＋1，Xi值的1，0分布服從自然概率，然而在運算中由于Xi＋4的作用，在對某區間數據進(jìn)行操作時(shí)存在差異，通過(guò)對一些運算區間的數據進(jìn)行了統計，其Xi＋4與BMi值的分布概率如圖9所示；以實(shí)際的一組分布來(lái)驗證重疊算法運算時(shí)間的縮短情況，如圖10所示（S1為重疊掃描算法，S2為標準算法；圖中前面為S1，后面陰影為S2）?？梢钥吹街丿B掃描法對浮點(diǎn)多字節乘法運算有很大的改進(jìn)，它打破了移位加法的傳統乘法算法，有了算法的預測功能，提高了乘法運算的速度。本算法在某軍工項目中得到應用，效果很好。

參考文獻
1　黃　凱．計算機算術(shù)運算原理、結構與設計．北京：科學(xué)出版社，1980．106～110
2　陳　宇，王遵立．MC－51單片微型機上實(shí)現的快速掃描浮點(diǎn)乘法運算．數據采集與處理，1992，（9）：151～153
3　陳　宇，畢淑艷，王遵立，等．MCS－51單片機實(shí)現的快速浮點(diǎn)多字節BCD乘除運算．電子技術(shù)應用，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