利用重叠扫描方法改进单片机乘法运算
设扫描组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值的分布概率
单片机 乘法 运算 改进 方法 重叠 扫描 利用 相关文章:
- FPGA的DSP性能揭秘(06-16)
- 基于单片机通用引脚的软件UART设计(10-16)
- 分时操作系统思想在单片机中的具体应用 (10-30)
- 基于AT89C51+DSP的双CPU伺服运动控制器的研究(05-26)
- 关于RTX51 TINY的分析与探讨(05-30)
- 基于MC9S12DGl28单片机的智能寻迹车设计(04-03)