1.人工算法与机器算法的同异性
在定点计算机中,两个原码表示的数相乘的运算规则是:乘积的符号位由两数的符号位按异或
运算得到,而乘积的数值部分则是两个正数相乘之积。
设n位被乘数和乘数用定点小数表示(定点整数也同样适用)
被乘数 [x]原=xf .xn-1…x1x0
乘数 [y]原=yf .yn-1…y1y0
式中,xf为被乘数符号,yf为乘数符号。
乘积符号的运算法则是:同号相乘为正,异号相乘为负。由于被乘数和乘数和符号组合只有
四种情况(xfyf=00,01,10,11),因此积的符号可按“异或”(按位加)运算得到。
数值部分的运算方法与普通的十进制小数乘法类似,不过对于用二进制表达式的数来说,其乘
设x=0.1101,y=0.1011.让我们先用习惯方法求其乘积,其过程如下:
运算的过程与十进制乘法相似:从乘数y的最低位开始,若这一位为“1”,则将被乘数x写
下;若这一位为“0”,则写下全0。然后在对乘数y的最高为进行乘法运算,其规则同上,不过这
一位乘数的权与最低位乘数的权不一样,因此被乘数x要左移一位。以此类推,直到乘数个位乘完
为止,最后将它们统统加起来,变得到最后乘积z。
如果被乘数和乘数用定点整数表示,我们也会得到同样的结果。
人们习惯的算法对机器并不完全适用。原因之一,机器通常只有n位长,两个n位数相乘,乘积可能为2n位。原因之二,只有两个操作数相加的加法器难以胜任将各n位积一次相加起来的运算。早期计算机中为了简化硬件结构,采用串行的1位乘法方案,即多次执行“加法—移位”操作来实现。这种方法并不需要很多器件。然而串行方法毕竟太慢,自从大规模集成电路问世以来,出现了各种形式的流水式阵列乘法器,它们属于并行乘法器。
图2.4 m×n位不带符号的阵列乘法器逻辑图
2.不带符号的阵列乘法器
设有两个不带符号的二进制整数:
它们的数值分别为a和b,即
m-1 n-1
i=0 j=0
在二进制乘法中,被乘数A与乘数B相乘,产生m+n位乘积P:
实现这个乘法过程所需要的操作和人们的习惯方法非常类似:
上述过程说明了在m位乘n位不带符号整数的阵列乘法中,“加法—移位”操作的被加数矩
阵。每一个部分乘积项(位积)aibj叫做一个被加数。
可以用m×n个“与”门并行地产生。显然,设计高速并行乘法器的基本问题,就在于缩短被加数
矩阵中每列所包含的1的加法时间。
5位×5位阵列乘法器的逻辑电路图演示
这种乘法器要实现n位×n位时,需要n(n-1)个全加器和n2个“与”门。该乘法器的总的乘法
令Ta为“与门”的传输延迟时间,Tf为全加器(FA)的进位传输延迟时间,假定用2级“与非”逻辑来实现FA的进位链功能,那么我们就有:
从演示中可知,最坏情况下延迟途径,即是沿着矩阵P4垂直线和最下面的一行。因而得
n位×n位不带符号的阵列乘法器总的乘法时间为:
=2T+(n-1)×6T+(n-1)×2T=(8n-6)T (2.27)
[例16] 参见上CAI演示,已知两个不带符号的二进制整数A = 11011,B = 10101,求每一部分乘
3.带符号的阵列乘法器
(1) 对2求补器电路
我们先来看看算术运算部件设计中经常用到的求补电路。一个具有使能控制的二进制对2求补
器电路图演示,其逻辑表达式如下:
在对2求补时,要采用按位扫描技术来执行所需要的求补操作。令A=an…a1a0是给定的(n+1)为
带符号的数,要求确定它的补码形式。进行求补的方法就是从数的最右端a0开始,,由右向左,直到
找出第一个“1”,例如ai=1, 0≤i≤n。这样,ai以左的每一个输入位都求反,即1变0,0变1。最右
端的起始链式输入C-1必须永远置成“0”。当控制信号线E为“1”时,启动对2求补的操作。当控
制信号线E为“0”时,输出将和输入相等。显然,我们可以利用符号位来作为控制信号。
例如,在一个4位的对2求补器中,,如果输入数为1010,那么输出数应是0110,其中从右算起的
第2位,就是所遇到的第一个“1”的位置。用这种对2求补器来转换一个(n+1)为带符号的数,所需
tTC=n·2T+5T=(2n+5)T (2.28)
其中每个扫描级需2T延迟,而5T则是由于“与”门和“异或”门引起的。
(2) 带符号的阵列乘法器
(n+1)×(n+1)位带求补器的阵列乘法器逻辑方框图演示
通常,把包括这些求补级的乘法器又称为符号求补的阵列乘法器。在这种逻辑结构中,共使
用三个求补器。其中两个算前求补器的作用是:将两个操作数A和B在被不带符号的乘法阵列(核心
部件)相乘以前,先变成正整数。而算后求补器的作用则是:当两个输入操作数的符号不一致时,把
运算结果变成带符号的数。
操作以后,A和B的码值输送给n×n位不带符号的阵列乘法器,并由此产生2n位真值乘积:
A·B=P=p2n-1…p1p0
p2n=an⊕bn
其中P2n为符号位。
上面CAI演示所示的带求补级的阵列乘法器既适用于原码乘法,也适用于间接的补码乘法。不
过在原码乘法中,算前求补和算后求补都不需要,因为输入数据都是立即可用的。而间接的补码阵
列乘法所需要增加的硬件较多。为了完成所必需的乘法操作,时间大约比原码阵列乘法增加1倍。