利用重疊掃描方法改進單片機乘法運算

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

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)用，效果很好。

參考文獻
1　黃　凱．計算機算術(shù)運算原理、結(jié)構(gòu)與設(shè)計．北京：科學(xué)出版社，1980．106～110
2　陳　宇，王遵立．MC－51單片微型機上實現(xiàn)的快速掃描浮點乘法運算．?dāng)?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