利用重叠扫描方法改进单片机乘法运算

区别只是改加为减，因为部分积的减值在以后的扫描中可以修正回来，不用采用补码的运算也能完成，最常用的方法是设置辅助运算区，采用临时记录的方式保证其部分积在扫描任一周期保持正确结果，也称为临时扩展方法，这里就不重复。这样，在每次扫描仅剩下一个问题，即如何处理Pj，这里Pj与文［3］中处理的方法有类似之处。以2A为基础，将Pj形成一个加（减）法序列，也就是将Pj变为2qA的序列，如12A＝22A＋23A。这样就可以在一个扫描周期完成部分积的加法。这里建议读者去探索Pj更好的形成方法，因为形成2qA的序列，1≤q≤3，要占用时间（24A可以通过半字节操作做左端拼加处理，因为24A相当于A左移半字节，运算时直接依靠辅助运算区），同时在特殊处理上也额外占有一些运算时间，这一点在图7中也可以看出来。这样一来，在Pj的加法过程中，扫描算法在某些BMi值上并不都占优势，这一点在图5，6中也可以体现（BMi中Xi＋3，Xi＋2，Xi＋1，Xi为1的个数决定了在标准算法中的加法次数）；但重叠扫描毕竟节省了时间，其与标准算法在一个扫描周期内的加法次数情况如图8所示（其中系列1为重叠扫描算法，系列2为标准算法）。加之在移位中节省的时间，重叠扫描全过程的运算时间与标准右移算法的比较情况如图8所示（S1为重叠扫描算法，S2为标准算法）。在局部区域，由于采用上述的Pj处理方法，运算时间节省情况还不甚理想，但在总体上还是有很大的改进。

4 结 论

以上介绍的是重叠均匀移位扫描算法，前面谈到重叠非均匀移位扫描算法，有关这种算法的详细介绍请参见其他文献。

在以上过程中，是假定BMi中的Xi＋3，Xi＋2，Xi＋1，Xi值的1，0分布服从自然概率，然而在运算中由于Xi＋4的作用，在对某区间数据进行操作时存在差异，通过对一些运算区间的数据进行了统计，其Xi＋4与BMi值的分布概率如图9所示；以实际的一组分布来验证重叠算法运算时间的缩短情况，如图10所示（S1为重叠扫描算法，S2为标准算法；图中前面为S1，后面阴影为S2）。可以看到重叠扫描法对浮点多字节乘法运算有很大的改进，它打破了移位加法的传统乘法算法，有了算法的预测功能，提高了乘法运算的速度。本算法在某军工项目中得到应用，效果很好。

参考文献
1　黄　凯．计算机算术运算原理、结构与设计．北京：科学出版社，1980．106～110
2　陈　宇，王遵立．MC－51单片微型机上实现的快速扫描浮点乘法运算．数据采集与处理，1992，（9）：151～153
3　陈　宇，毕淑艳，王遵立，等．MCS－51单片机实现的快速浮点多字节BCD乘除运算．电子技术应用，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