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

引 言

1946年，第一台电子计算机的诞生开创了计算机发展的新纪元。随着计算机科学技术的迅速发展，计算机的应用领域越来越广泛，并逐渐形成科学发展中的一个新的分支。在计算机的主要工作中，处理大量的数据是其一项基本功能；因而数据运算是必不可少的。于是人们设法在硬件设计与数据结构方面努力进行工作［1］，使计算机的速度不断提高。

十几年前，单片微型机脱颖而出，逐渐应用于微型计算机的各个领域，它不仅适用于一般的自动控　　制，而且还可以承担高精度的数据处理工作。诚然，在许多系统中近来采用DSP来提高微机的数据处理能力，以便完成复杂的图像处理、音频处理、网络通讯等功能，而且是一个趋势；但在这些系统中仍不可忽视运算程序的执行速度，因为好的算法可以大大提高程序的执行效率［2］。同时，考虑到目前8BITMCU的主导地位及某些系统不适合配置DSP来进行数据处理［3］。因此，这里仍有必要对高精度高速度的浮点多字节运算进行进一步研究。

1　浮点多字节标准乘法

普通的计算机都采用标准的加法－移位技术来实现乘法，Mowle曾经对这些基本的乘法算法和问题作了详细的描述［4］。对于二进制数A，B来说，设其数值为AV，BV

由此原始矩阵乘法产生了标准的移位加算法［5，6］。一般的标准浮点乘法运算分为阶码运算与尾数运算两部分，其主要部分为尾数运算。标准尾数相乘是采用边乘边相加的办法（即加法－移位）来实现的，即乘数向左移位，产生中间结果，中间结果被加至积区的方法；在整个过程中，积也与乘数一起移位。此过程如图1所示。上述方法对于两个n位二进制尾数的相乘结果，即乘积为2n位，也就是部分积要点n位，在运算过程中，这2n字节都有可能要有相加的操作，需2n个字节加法器。对于标准算法，相当于进行了8n次2n字节的移位，还有次2n字节的加法。其中Pj（bj）为其每个bit位的布尔取值，其为1则取1，反之则为0。

为了节省运算时间，标准乘法应用标准右移乘法方法以便减少加法器的数量，有关这方面的具体论述请参见文［2］。

2　扫描乘法的基本原理

在执行乘法指令时，如果每个周期所检查的乘数位多于一位，乘法的速度便可以加快。例如，每次检查二位，那么加法移位周期的总数就可以减半。这些逐次扫描的位组可以是分离的，也可以是重叠的。这里先简述一下分离扫描的原理。对于乘数来讲是以字节为单位的，其字长按二进制BIT来计是偶数，设被乘数A＝（AX），乘数B＝（MR）；则在扫描了最低一对乘数位（MR1，MR0）后，有四种可能的动作，如图2所示。对于m＝（MR1，MR0）2来说，被乘数A的倍数m×A被加到当前的部分乘积上，用来生成下一个部分积。上述原理可以推广到任意大小的扫描位组，其具体实现方法和分析结果请参见文［2］，这里不再叙述。

以上所描述的是分离扫描的情况，下面再介绍重叠多位扫描的情况。一般在乘数中bj为0的个数越多，则程序运行的时候对为0的情况仅仅是移位越过，而不用作加法的运算，在此种情况下的运算相对加快。因此希望对乘数的bj能否进行适当的操作，使这之在bj为1的区域也能使运算时间减少。

现考虑乘数中有一串k个连续的1，如下
　　列的位置…，i＋k，i＋k－1，i＋k－2，…，i，i－1，…
　　列的内容…，0，1，1，…，1，0，… （2）　

按常规，在移位加时，被乘数A与部分积要进行k次加法操作，但是存在
2i＋k－2i＝2i＋k－1＋2i＋k－2＋…＋2i＋1＋2i　 （3）

因此可以用下面的数符串来代替k个连续的1
　　列的位置…，i＋k，i＋k－1，i＋k－2，…，i，i－1，…
列的内容…，1，0，0，…，－1，0，… （4）

上面的－1表示执行一次减法。利用这种乘法再编码的方法，只要在数字串开始时作一次加法，结束时作一次减法，使这能够代替原来的k次连续加法。显然，当k很大时，能节省大量的加法时间。

为了方便扫描，乘数位仍按二位一组分成许多组，但一次扫描三位，二位来自现在的组，第三位来自下一次高次组的低位，实际上每一组的低位被检测了二次。为了与右移算法取得一致，假定扫描乘数从右端到左端，重叠和非重叠两种扫描模式表示见图3。

设扫描组XR＝［Xi＋1，Xi］2；下一扫描组XR′＝［Xi＋3，Xi＋2］2；每三位一组检测后的动作说明见图4。其指出了每个机器周期或执行一次单纯的移位，或者执行一次加法，或者执行一次减法，这里只需要倍数2A或4A。当下一对的低次位xi＋2为0时，三位中最左边的1经常指示一串1的左端（结束）。依式（3）所描述的特性