原码1位乘法
在定点计算机中,两个原码表示的数相乘的运算规则是:乘积的符号位由两数的符号按异或运算得到。而乘积的数值部分则是两个正数相乘之积。设n位被乘数和乘数用定点小数表示(定点整数也相同适用)
被乘数[x]原=xf.x0x1x2…xn
乘数[y]原=yf.y0y1y2…yn
则
乘积[z]原= (xf⊕yf)
. (0.x0x1x2…xn)(0 .y1y2…yn)
式中,xf为被乘数符号。yf为乘数符号。
乘积符号的运算法则是:同号相乘为正,异号相乘为负。因为被乘数和乘数和符号组合仅仅有四种情况(xfyf= 00,01,10,11),因此积的符号可按“异或”(按位加)运算得到。
数值部分的运算方法与普通的十进制小数乘法相类似。只是对于用二进制表达的数来说,其乘法规则更为简单一些:从乘法y的最低位開始。若这一位为“1”。则将被乘数x写下;若这一位为“0”,则写下全0。然后再对乘数y的高一位进行的乘法运算,其规则同上,只是这一位乘数的权与最低位乘数的权不一样。因此被乘数x要左移一位。依次类推。直到乘数各位乘完为止。最后将它们统统加起来。便得到最后乘积z。
设x= 0.1011。y= 0.1101,让我们先用习惯方法求其乘积。其步骤例如以下:
×
0.
1
1
0
1
(x)
0.
1
0
1
1
(y)
+
1
1
0
1
1
1
0
1
0
0
0
0
1
1
0
1
0.
1
0
0
0
1
1
1
1
(z)
假设被乘数和乘数用定点整数表示,我们也会得到相同的结果。可是。可是人们习惯的算法对机器并不全然适用。原因之中的一个,机器通常仅仅有n位长,两个n位数相乘,乘积可能为2n位。原因之二,仅仅有两个操作数相加的加法器,难以胜任将n个位积一次相加起来的运算。为了简化结构,机器通常仅仅有n位长。而且仅仅有两个操作数相加的加法器。为此,必须改动上述乘法的实现方法。将x·y改写成适于例如以下定点机的形式:
一般而言。设被乘数x、乘数y都是小于1的n位定点正数:
x= 0 .x1x2…xn。y= 0 .y1y2…yn
其乘积为
x·y=x·( 0.y1y2…yn)
=x·(y12-1+y22-2+…+yn2-n)
= 2-1(y1x+ 2-1(y2x+ 2-1(…+ 2-1(yn-1x+ )…))
令zi表示第i次部分积,则上式可写成例如以下递推公式:
z0= 0
z1= 2-1(ynx+z0)
…
zi= 2-1(yn-i+1x+zi-1)(2.3.2)
…
zn=x·y= 2-1(y1x+zn-1)
显然,欲求x·y,则需设置一个保存部分积的累加器。
乘法開始时,令部分积的初值z0= 0。然后求加上ynx。右移1位得第1个部分积,又将加上yn- 1x,再右移1位得第2个部分积。依此类推。直到求得y1x加上zn-1并右移1位得最后部分积,即得x·y。显然,两个n位数相乘。需反复进行n次“加”及“右移”操作。才干得到最后乘积。这就是实现原码一位乘法的规则。
【例 】x= 0.1101。y = 0.1011。用原码一位乘法计算x·y=?
[解:]求解步骤例如以下: Flash演示
部分积
乘数
说明
00.0000
yf
1
0
1
1
z0= 0
+
00.1101
y4= 1,+x
00.1101
→
00.0110
1
yf
1
0
1
右移。得z1
+
00.1101
Y3= 1。+x
01.0011
→
00.1001
1
1
yf
1
0
右移,得z2
+
00.0000
Y2= 0,+0
00.1001
→
00.0100
1
1
1
yf
1
右移,得z3
+
00.1101
Y1= 1,+x
01.0001
→
00.1000
1
1
1
1
yf
右移,得z3=xy
所以x·y=
0.10001111
图2-7为实现原码一位乘法的硬件逻辑原理图。这里有三个寄存器,当中R0存放部分积z,在乘法開始R0前应清“0”,
保证z0= 0,R1寄存器存放乘数y,R2寄存器存放被乘数x。因为乘法開始时先从乘数的最
低位yn開始,以后则使用yn- 1,yn- 2,…,y1,因此乘数寄存器R1应当是具有右移功能的移位寄存器。
假定加法器不具备右移功能,那么因为部分积须要右移,R0也应当是具有右移功能的移位寄存器。
图2-7 原码一位乘法逻辑结构原理图
除了三个寄存器R0,R1,R2外。还需一个加法器和一个计数器,前者完毕部分积与位积的累加,后者对移位的次数进行计数。以便推断乘法运算是否结束。
乘法開始时,“启动”信号使控制触发器Cx置“1”。于是开启时序脉冲T。当乘数寄存器R0最末位为“1”时,部分积z和被乘数x在加法器中相加。其结果输出至R0的输入端,一旦打入控制脉冲T。控制信号LDR0使部分积右移1位,与此同一时候,乘数寄存器R1也在控制信号LDR1作用下右移一位,且计数器i计数1次。
当计数器i
=n时。计数器i的溢出信号使控制触发器Cx置“0”。关闭时序脉冲T,乘法操作结束。假设将R0和R1连接起来,乘法结束时乘积的高n位部分在R0,低n位部分在R1。R1中原来的乘数y因为右移而所有丢失,乘积为2n+1位,当中包含1位符号位。
补码1位乘法
原码乘法的主要问题是符号位不能參加运算,单独用一个异或门产生乘积的符号位。
故自然提出是否能让符号数字化后也參加乘法运算,补码乘法就能够实现符号位直接參加运算。
为了得到补码一位乘法的规律。先从补码和真值的转换公式開始讨论。
1.补码与真值的转换公式
设[x]补=x0.x1x2…xn,有:
n
(2.3.3)
x= -x0+∑xi2-i
i=1
等式左边x为真值。此公式说明真值和补码之间的关系。
2.补码的右移
正数右移一位,相当于乘1/2(即除2)。
负数用补码表示时。右移一位也相当于乘1/2。因此。在补码运算的机器中,一个数不论其正负,连同符号位向右移一位。若符号位保持不变,就等于乘1/2。
3.补码乘法规则
设被乘数[x]补=x0.x1x2…xn和乘数[y]补=y0.y1y2…yn均为随意符号,则有补码乘法算式
n
(2.3.4)
[x·y]补= [x]补· ( -y0+ ∑yi2-i)
i=1
为了推出串行逻辑实现人分步算法,将上式展开加以变换:
[x·y]补= [x]补·[ -y0+y12-1+y22-2+…+yn2-n]
= [x]补·[ -y0+ (y1-y12-1) + (y22-1-y22-2) +…+ (yn2-(n-1)-yn2-n)]
= [x]补·[(y1-y0) + (y2-y1) 2-1+…+ (yn-yn-1) 2-(n-1)+
(0 -yn)2-n]
= [x]补·
(yn+1=0)
写成递推公式例如以下:
[z0]补= 0
[z1]补= 2-1{[z0]补+ (yn+1-yn)[x]补}(yn+1=0)
…
[zi]补= 2-1{[zi-1]补+ (yn-i+2-yn-i+1)[x]补}(2.3.5)
…
[zn]补= 2-1{[zn-1]补+ (y2-y1)[x]补}
[zn+1]补= [zn]补+ (y1-y0)[x]补=
[x·y]补
開始时。部分积为0。即[z0]补= 0。然后每一步都是在前次部分积的基础上,由(yi+1- yi)( i = 0。1,2。…,n)决定对[x]补的操作,再右移一位。得到新的部分积。如此反复n+ 1步,最后一步不移位,便得到[x·y]补。这就是有名的布斯公式。
实现这样的补码乘法规则时。在乘数最末位后面要添加一位补充位yn+1。開始时,由ynyn+1推断第一步该怎么操作。然后再由yn- 1yn推断第二步该怎么操作。由于每做一步要右移一位,故做完第一步后,yn-
1yn正好移到原来ynyn+1的位置上。依此类推,每步都要用ynyn+ 1位置进行推断。我们将这两位称为推断位。
假设推断位ynyn+1= 01,则yi+1 …yi= 1,做加[x]补操作。假设推断位ynyn+1= 10,则yi+1…yi=-
1,做加[ -x]补操作;假设推断位ynyn+1= 11或00。则yi+1…yi= 0。[zi]加0。即保持不变。
4. 补码一位乘法运算规则
(1)假设yn=yn+1,部分积[zi]加0。再右移一位;
(2)假设ynyn+1= 01。部分积加[x]补。再右移一位;
(3)假设ynyn+1= 10,部分积加[ -x]补,再右移一位;
这样反复进行n+1步,但最后一步不移位。包含一位符号位,所得乘积为2n+1位,当中n为尾数位数。
【例 】x= 0.1101。y = 0.1011,用补码一位乘法计算x·y=?
[解:]求解步骤例如以下: Flash演示
部分积
乘数
说明
00.0000
0.
1
0
1
1
0
yn+1=0
+
11.0011
ynyn+1= 10,加[-x]补
11.0011
→
11.1001
1
0
1
0
1
1
右移一位
+
00.0000
ynyn+1= 10,加0
11.1001
→
11.1100
1
1
0
1
0
1
右移一位
+
00.1101
ynyn+1= 01,加[x]补
00.1001
→
00.0100
1
1
1
0f
1
0
右移一位
+
11.0011
ynyn+1= 01,加[-x]补
11.0111
→
11.1011
1
1
1
1
0
1
右移一位
+
00.1101
ynyn+1= 01,加[x]补
00.1000
1
1
1
1
0
1
最后一步不移位
所以[x·y]补= 0.10001111
图2-8 补码一位乘法逻辑原理图
实现一位补码乘法的逻辑原理图如图2-8所看到的。它与一位原码乘法的逻辑结构很类似,所不同的有下面几点:
(1)被乘数的符号和乘数的符号都參加运算。
(2)乘数寄存器R1有附加位yn+1。其初始状态为“0”。
当乘数和部分积每次右移时。部分积最低位移至R1的首位位置,故R1必须是具有右移功能的寄存器。
(3)被乘数寄存器R2的每一位用原码(即触发器Q端)或反码(即触发器Q端)经多路开关传送到加法器相应位的一个输入端。而开关的控制位由和yn的yn+1输出译码器产生。当ynyn+1=
01时。送[x]补;当ynyn+1= 10时,送[-x]补,即送的反码且在加法器最末位上加“1”。
(4) R0保存部分积。它也是具有右移功能的移位寄存器。其符号位与加法器 ∑f符号位始终一致。
(5)当计数器i=n+1时,封锁LD R0和LD R1控制信号。使最后一位不移位。
运行补码一位乘法的总时间为
tm= (n +1 )ta+ntr
(2.3.6)
当中n为尾数位数,ta为运行一次加法操作的时间,tr为运行一次移位操作的时间。假设加法操作和移位操作同一时候进行,则tr项可省略。