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

设扫描组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所示。

区别只是改加为减，因为部分积的减值在以后的扫描中可以修正回来，不用采用补码的运算也能完成，最常用的方法是设置辅助运算区，采用临时记录的方式保证其部分积在扫描任一周期保持正确结果，也称为临时扩展方法，这里就不重复。这样，在每次扫描仅剩下一个问题，即如何处理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值的分布概率