资源描述：
《乘法和高速乘法算法及电路.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、乘法和高速乘法算法及电路1.普通乘法与电路一位二进制的乘法运算规则如下:0*0=0,0*1=0,1*0=0,1*1=1.实际和”与”操作相同.多位二进制乘法与十进制乘法类似:如A*B=CAnAn-1---A0ΧBnBn-1---B0AnB0An-1B0---A0B0------------AnBn-1An-1Bn-1---A0Bn-1AnBnAn-1Bn---A0BnCn+nCn+n-1Cn+n-2---CnCn-1---C0多位二进制乘法运算可以用一个加法器多次迭代完成,迭代次数与乘数位数相同,而加法器位数与被乘数位数相
2、同.硬件电路如上图.设被乘数A与乘数B都为四位.被乘数放在寄存器A中,乘数放在寄存器B中,经过四次加法迭代运算,8位结果保存在寄存器P(高四位)和B(低四位)中.先算出的低位部分积向右移,并ꉩ每次部分积累加,最后得到结果.上述电路简剕,综合后所用的面积较小,但电路却有很大的延迟.每次迭代时间由3部分组成:与门的延迟时间,n位全加器的延迟时间和移位寄存器的延迟时间.运算通过右移操作一位一位的进行,不适合高速运算.若设想位移操作直接用硬件连接而成,则运算速度可大大加快.将上面电路加以改进,如下图.上述结构的电路图运算速度显然将
3、和加法器产生进位信号延迟时间有关,我们可将全加器做成超前进位加法器,上面的四位加法器可做成三级门延时的超前进位加法器,设一级门延时2.0ns,则上面电路的关键路径延时为2.0*3*4=24ns,运算速度可达到30Mhz-40Mhz.这种电路还是受位数限制,但位数太多,提高速度已不太现实.1.高速乘法与电路一.Booth算法以上讨论的乘法算法只是检查乘数是一位二进制位.为了加快运算速度,我们可以检查k位二进制,即乘数是k位与被乘数相乘,这就是高基乘法,也叫”Booth”算法.算法原理为:设被乘数为A,乘数为B,如果以k=2为
4、例,即乘数每次移动两位与被乘数相乘.这两位二进制数为00,则加0;如果这两位二进制数为01,则加A;如果这两位二进制数为10,则加2A(A左移一位).但是,如果这两位数为11,应加3A,而3A=A+2A,引入了一次加法运算,这是我们所不希望的.我们可将3A理解成4A-A.这意味着:如果两位二进制数为11,则减A,但4A还没有加上,要打上标号,在下次部分积右移两位是补上,右移两位使原来的加4A变成加A.如何打上标号使下次移动时能补上.我们可这样做:在检查当前两位的同时也检查与这两位相邻的低位,即前一次的高位.如果它为1,则要
5、加A(相当前一次的加4A).由于10的高位也为1,也就是说要把2A变成4A-2A.编码见下表:Boothradix-4encodingB的低两位前次移出的位运算结果注释2i+12i-12i0000+0+0001+A+0+A010+A+A+0011+2A+A+A100-2A+4A-2A+0101-A+4A-2A+A110-A+4A-A+01110+4A-A+A由于有+2A和-2A的操作,部分积P要比实际位数多一位.下面举一下例子:A=011011(27),B=101001(-23)C=A*BP为部分积PB前次移出的位码表注释
6、00000001010010010+A+00110110011011101001算术根右移两位0000110111010(01)0100-2A-01101101010000111010(01)算术根右移两位1110100*001110(1001)1101-A-00110111011001001110(1001)算术根右移两位1110110*010011(101001)C=110110_010011(-621)*:无论是乘数拚接成乘积P还是算术根向右移位，填补位的值是原来乘数或乘积P的最高位，而不总是0。该算法的电路图如下:
7、用Verilog描述上面电路,综合得到下表参数:A*B位数FPGA(speedgrade)Area(gates)Delay(MHz)注释12*4-4(0.75ns)52641.7程序为一级流水(即暂不用流水结构).综合工具为Mentor-Leonardospectrum.所选用的FPGA为Xinlix的XC9500系列(9536x1pc44).-7(1.0ns)52631.38*4-435655.6-735641.74*4-418688.9-718666.712*8-4121529.3-7121523.18*8-48493
8、4.3-784926.1Booth算法适合于补码表示的成运算.更高基的Booth的编码(Boothendoding).例如8基(即检查乘数为三位)也是可以实现.不过电路更复杂,而且需要使用3A.改动方法为在计算之前首先算出3A.用Booth算法实现乘法运算优点在于把常规乘法(乘数为k位)k步移位运算至小
