计算机乘法原理移位,原码乘法,原码乘法原理详解

原码乘法,原码乘法原理详解

1.人工算法与机器算法的同异性

在定点计算机中&＃xff0c;两个原码表示的数相乘的运算规则是:乘积的符号位由两数的符号位按异或运算得到&＃xff0c;而乘积的数值部分则是两个正数相乘之积。

设n位被乘数和乘数用定点小数表示(定点整数也同样适用)

被乘数 　　[&＃xff58;]原&＃61;&＃xff58;f .&＃xff58;n-1…&＃xff58;1&＃xff58;0

乘数 　  　[&＃xff59;]原&＃61;&＃xff59;f .&＃xff59;n-1…&＃xff59;1&＃xff59;0

则乘积

[z]原&＃61;(&＃xff58;f⊕&＃xff59;f)&＃xff0b;(0.&＃xff58;n-1…&＃xff58;1&＃xff58;0)(0.&＃xff59;n-1…&＃xff59;1&＃xff59;0)    (2.26)

式中&＃xff0c;&＃xff58;f为被乘数符号&＃xff0c;&＃xff59;f为乘数符号。

乘积符号的运算法则是&＃xff1a;同号相乘为正&＃xff0c;异号相乘为负。由于被乘数和乘数和符号组合只有四种情况(&＃xff58;f&＃xff59;f&＃61;00&＃xff0c;01&＃xff0c;10&＃xff0c;11)&＃xff0c;因此积的符号可按“异或”(按位加)运算得到。

数值部分的运算方法与普通的十进制小数乘法类似&＃xff0c;不过对于用二进制表达式的数来说&＃xff0c;其乘法规则更为简单一些。

设&＃xff58;&＃61;0.1101&＃xff0c;&＃xff59;&＃61;0.1011.让我们先用习惯方法求其乘积&＃xff0c;其过程如下:

运算的过程与十进制乘法相似:从乘数&＃xff59;的最低位开始&＃xff0c;若这一位为“1”&＃xff0c;则将被乘数&＃xff58;写下&＃xff1b;若这一位为“0”&＃xff0c;则写下全0。然后在对乘数&＃xff59;的最高为进行乘法运算&＃xff0c;其规则同上&＃xff0c;不过这一位乘数的权与最低位乘数的权不一样&＃xff0c;因此被乘数&＃xff58;要左移一位。以此类推&＃xff0c;直到乘数个位乘完为止&＃xff0c;最后将它们统统加起来&＃xff0c;变得到最后乘积&＃xff5a;。

如果被乘数和乘数用定点整数表示&＃xff0c;我们也会得到同样的结果。

人们习惯的算法对机器并不完全适用。原因之一&＃xff0c;机器通常只有n位长&＃xff0c;两个n位数相乘&＃xff0c;乘积可能为2n位。原因之二&＃xff0c;只有两个操作数相加的加法器难以胜任将各n位积一次相加起来的运算。早期计算机中为了简化硬件结构&＃xff0c;采用串行的1位乘法方案&＃xff0c;即多次执行“加法—移位”操作来实现。这种方法并不需要很多器件。然而串行方法毕竟太慢&＃xff0c;自从大规模集成电路问世以来&＃xff0c;出现了各种形式的流水式阵列乘法器&＃xff0c;它们属于并行乘法器。

图2.4 m×n位不带符号的阵列乘法器逻辑图

2.不带符号的阵列乘法器

设有两个不带符号的二进制整数&＃xff1a;

A&＃61;am-1…a1a0

B&＃61;bn-1…b1b0

它们的数值分别为a和b&＃xff0c;即

在二进制乘法中&＃xff0c;被乘数A与乘数B相乘&＃xff0c;产生m&＃xff0b;n位乘积P&＃xff1a;

P&＃61;pm&＃43;n-1…p1p0

乘积P 的数值为

　　实现这个乘法过程所需要的操作和人们的习惯方法非常类似&＃xff1a;

上述过程说明了在m位乘n位不带符号整数的阵列乘法中&＃xff0c;“加法—移位”操作的被加数矩阵。每一个部分乘积项(位积)aibj叫做一个被加数。

这m×n个被加数{aibj|0≤i≤m-1和0≤j≤n-1}

可以用m×n个“与”门并行地产生。显然&＃xff0c;设计高速并行乘法器的基本问题&＃xff0c;就在于缩短被加数矩阵中每列所包含的1的加法时间。

这种乘法器要实现n位×n位时&＃xff0c;需要n(n-1)个全加器和n2个“与”门。该乘法器的总的乘法时间可以估算如下&＃xff1a;

令Ta为“与门”的传输延迟时间&＃xff0c;Tf为全加器(FA)的进位传输延迟时间&＃xff0c;假定用2级“与非”逻辑来实现FA的进位链功能&＃xff0c;那么我们就有&＃xff1a;

Ta &＃61; Tf &＃61; 2T

从演示中可知&＃xff0c;最坏情况下延迟途径&＃xff0c;即是沿着矩阵P4垂直线和最下面的一行。因而得n位×n位不带符号的阵列乘法器总的乘法时间为&＃xff1a;

tm&＃61;Ta&＃43;(n-1)×6T&＃xff0b;(n-1)×Tf

&＃61;2T&＃xff0b;(n-1)×6T&＃xff0b;(n-1)×2T&＃61;(8n-6)T　　　　　(2.27)

[例16] 已知两个不带符号的二进制整数A&＃61;11011&＃xff0c;B&＃61;10101&＃xff0c;求每一部分乘积项aibj的值与p9p8……p0的值。

[解:]

a4b0&＃61;1 a3b0&＃61;1 a2b0&＃61;0 a1b0&＃61;1 a0b0&＃61;1　　

a4b1&＃61;0 a3b1&＃61;0 a2b1&＃61;0 a1b1&＃61;0 a0b1&＃61;0

a4b2&＃61;1 a3b2&＃61;1 a2b2&＃61;0 a1b2&＃61;1 a0b2&＃61;0

a4b3&＃61;0 a3b3&＃61;0 a2b3&＃61;0 a1b3&＃61;0 a0b3&＃61;0

a4b4&＃61;1 a3b4&＃61;1 a2b4&＃61;0 a1b4&＃61;1 a0b4&＃61;1

P&＃61;p9p8p7p6p5p4p3p2p1p0&＃61;1000110111(56710)

3.带符号的阵列乘法器

(1) 对2求补器电路

我们先来看看算术运算部件设计中经常用到的求补电路。一个具有使能控制的二进制对2求补器电路图&＃xff0c;其逻辑表达式如下&＃xff1a;

C-1&＃61;0&＃xff0c;　 Ci&＃61;ai&＃43;Ci-1

ai*&＃61;ai⊕ECi-1&＃xff0c;　　　0≤i≤n

在对2求补时&＃xff0c;要采用按位扫描技术来执行所需要的求补操作。令A&＃61;an…a1a0是给定的(n&＃xff0b;1)为带符号的数&＃xff0c;要求确定它的补码形式。进行求补的方法就是从数的最右端a0开始&＃xff0c;&＃xff0c;由右向左&＃xff0c;直到找出第一个“1”&＃xff0c;例如ai&＃61;1&＃xff0c; 0≤i≤n。这样&＃xff0c;ai以左的每一个输入位都求反&＃xff0c;即1变0&＃xff0c;0变1。最右端的起始链式输入C-1必须永远置成“0”。当控制信号线E为“1”时&＃xff0c;启动对2求补的操作。当控制信号线E为“0”时&＃xff0c;输出将和输入相等。显然&＃xff0c;我们可以利用符号位来作为控制信号。

例如&＃xff0c;在一个4位的对2求补器中&＃xff0c;&＃xff0c;如果输入数为1010&＃xff0c;那么输出数应是0110&＃xff0c;其中从右算起的第2位&＃xff0c;就是所遇到的第一个“1”的位置。用这种对2求补器来转换一个(n&＃xff0b;1)为带符号的数&＃xff0c;所需的总时间延迟为

tTC&＃61;n·2T&＃xff0b;5T&＃61;(2n&＃xff0b;5)T　　　　　　(2.28)

其中每个扫描级需2T延迟&＃xff0c;而5T则是由于“与”门和“异或”门引起的。

(2) 带符号的阵列乘法器

(n&＃xff0b;1)×(n&＃xff0b;1)位带求补器的阵列乘法器逻辑方框图

通常&＃xff0c;把包括这些求补级的乘法器又称为符号求补的阵列乘法器。在这种逻辑结构中&＃xff0c;共使用三个求补器。其中两个算前求补器的作用是&＃xff1a;将两个操作数A和B在被不带符号的乘法阵列(核心部件)相乘以前&＃xff0c;先变成正整数。而算后求补器的作用则是&＃xff1a;当两个输入操作数的符号不一致时&＃xff0c;把运算结果变成带符号的数。

设A&＃61;anan-1…a1a0和B&＃61;bnbn-1…b1b0均为用定点表示的(n&＃xff0b;1)位带符号整数。在必要的求补操作以后&＃xff0c;A和B的码值输送给n×n位不带符号的阵列乘法器&＃xff0c;并由此产生2n位真值乘积:

A·B&＃61;P&＃61;p2n-1…p1p0

p2n&＃61;an⊕bn

其中P2n为符号位。

上面所示的带求补级的阵列乘法器既适用于原码乘法&＃xff0c;也适用于间接的补码乘法。不过在原码乘法中&＃xff0c;算前求补和算后求补都不需要&＃xff0c;因为输入数据都是立即可用的。而间接的补码阵列乘法所需要增加的硬件较多。为了完成所必需的乘法操作&＃xff0c;时间大约比原码阵列乘法增加1倍。

[例17] 设&＃xff58;&＃61;&＃xff0b;15&＃xff0c;&＃xff59;&＃61;-13&＃xff0c;用带求补器的原码阵列乘法器求出乘积&＃xff58;·&＃xff59;&＃61;&＃xff1f;

[解:]

设最高位为符号位&＃xff0c;则输入数据为

[&＃xff58;]原&＃61;01111　　[&＃xff59;]原&＃61;11101

符号位单独考虑&＃xff0c;算前求补级后 |&＃xff58;|&＃61;1111&＃xff0c;|&＃xff59;|&＃61;1101

算后经求补级输出并加上乘积符号位1&＃xff0c;则原码乘积值为111000011。

换算成二进制数真值是

&＃xff58;·&＃xff59;&＃61;( -11000011)2&＃61;(-195)10

十进制数验证&＃xff1a;&＃xff58;×&＃xff59; &＃61; 15× (-13) &＃61; -195相等。

[例18] 设&＃xff58;&＃61;&＃xff0b;15&＃xff0c;&＃xff59;&＃61;-13&＃xff0c;用带求补器的补码阵列乘法器求出乘积&＃xff58;·&＃xff59;&＃61;&＃xff1f;

[解:]

设最高位为符号位&＃xff0c;则输入数据用补码表示为

[&＃xff58;]补&＃61;01111　　　 [&＃xff59;]补&＃61;10011

符号位单独运算&＃xff0c;x0⊕y0&＃61;0&＃43;1&＃61;1

尾数部分算前求补器输出为: |&＃xff58;|&＃61;1111&＃xff0c;|&＃xff59;|&＃61;1101

算后求补器输出为00111101&＃xff0c;加符号位1&＃xff0c;得

[&＃xff58;·&＃xff59;]补&＃61;100111101

补码二进制数真值是

&＃xff58;·&＃xff59;&＃61;-1×28&＃43;1×25&＃43;1×24&＃43;1×23&＃43;1×22&＃43;1×20&＃61;(-195)10

十进制数验证&＃xff1a;     &＃xff58;×&＃xff59;&＃61;(&＃43;15)×(-13)&＃61;-195相等。