计算机组成原理-运算方法
乘法
原码一位乘法
运算规则
原码的乘法运算规则类似于手动计算,即列竖式计算乘法,在计算机中可以使用移位运算和加法进行计算
运算推导如下:
推导后,得出原码一位乘法的计算方法:
- y 的第 n 位乘以 x 加上 部分积
- 进行移位运算
- 符号位的计算
上述公式最里面的括号 +0 是为了表示最开始时部分积为0
例题
特点
- 绝对值计算
- 逻辑移位
- 使用移位的次数判断乘法是否结束
补码一位乘法
运算规则
根据公式,前面一部分的计算和原码一位乘法是类似的,但是右移操作改为算数右移,并且符号位需要参与运算,最后还要根据符号位减去x的补码(如果符号位是1,即Y是负数,需要加上-X的补码)。
在此种运算中,使用双符号位来进行计算,
例题
设 X = -0.1101,Y = -0.1011,求 [X * Y] 的补码
即X的补码为 11.0011 ,Y的补码为 11.0101
运算操作 | 部分积 | 乘数 | 说明 |
---|---|---|---|
00.0000 | 0101 | ||
+ | 11.0011 | ||
= | 11.0011 | ||
>> | 11.1001 | 1 | 010 | 算数移位 |
+ | 00.0000 | ||
= | 11.1001 | 1 | 010 | |
>> | 11.1100 | 11 | 01 | |
+ | 11.0011 | ||
= | 10.1111 | 11 | 01 | 符号位参与运算 |
>> | 11.0111 | 111 | 0 | |
+ | 00.0000 | ||
= | 11.0111 | 111 | 0 | |
>> | 11.1011 | 1111 | |
+ | 00.1101 | 因为Y的符号位是1,加上[-X]的补码 | |
= | 00.1000 | 1111 | 结果 |
特点
- 采用算数移位(高位符号位向右移动)
- 符号位参与运算
- 需要根据符号位减去X的补码
布斯公式
根据补码一位乘法进行变化,由布斯提出了布斯公式加快乘法运算速度
运算规则
计算规则使用一个辅助位,根据辅助位和乘数的最后一位的差值来加上不同的值,在实际应用时,辅助位往往位于寄存器的末尾,其中辅助位初始为0。运算规则如下表所示:
辅助位-乘数最后一位 | 操作 |
---|---|
-1 | 部分积加-X的补码,右移一位 |
0 | 部分积加0,右移一位 |
1 | 部分积加X的补码,右移一位 |
例题
设 X = -0.1101,Y = 0.1011
即 X 的补码为:11.0011 ,Y的补码为:00.1011
操作 | 部分积 | 乘数 | 说明 |
---|---|---|---|
00.0000 | 010110 | 辅助位初始为0,符号位参与运算 | |
+ | 00.1101 | 辅助位-乘数最后一位为-1,部分积加-X的补码 | |
= | 00.1101 | 010110 | |
>> | 00.0110 | 1 | 01011 | |
+ | 00.0000 | 辅助位-乘数最后一位为0,部分积加0 | |
= | 00.0110 | 1 | 01011 | |
>> | 00.0011 | 01 | 0101 | |
+ | 11.0011 | 辅助位-乘数最后一位为1,部分积加X的补码 | |
= | 11.0110 | 01 | 0101 | |
>> | 11.1011 | 001 | 010 | |
+ | 00.1101 | 辅助位-乘数最后一位为-1,部分积加-X的补码 | |
= | 00.1000 | 001 | 010 | |
>> | 00.0100 | 0001 | 01 | |
+ | 11.0011 | 辅助位-乘数最后一位为1,部分积加X的补码 | |
= | 11.0111 | 0001 | 结果 |
特点
- 乘数的符号位参与运算
- 硬件配置上乘数寄存器的位数比原来多了两位,和部分积寄存器的位数相同
原码二位乘法
运算规则
两位乘数有四种可能的组合,分别代表0~3这四个数
组合 | 操作 |
---|---|
00 | 部分积右移两位 |
01 | 部分积加 X ,右移两位 |
10 | 部分积加 2X,右移两位 |
11 | 部分积加 3X,右移两位 |
在实际计算中,2X的实现较为简单,即把X左移一位实现,3X则转化为 4X-X 实现,4X即把X左移两位,改+4X为-X,将4X留到下一轮计算,经过移位后-X已经变成了+X,使用一个触发器C来记忆是否有+X,C的意义为记下是否有X没有被加上,乘法规则表如下:
最后两位 | C | 操作 |
---|---|---|
00 | 0 | 部分积加0,C=0 |
00 | 1 | 部分积加X,C=0 |
01 | 0 | 部分积加X,C=0 |
01 | 1 | 部分积加2X,C=0 |
10 | 0 | 部分积加2X,C=0 |
10 | 1 | 部分积加-X,C=1 |
11 | 0 | 部分积加-X,C=1 |
11 | 1 | 部分积加0,C=1 |
如果最后一次移位后,C中还为1,还要进行一次+X操作,但不进行移位
在二位乘法中,符号位为3位
例题
设X=0.100111,Y=0.100111
即X的补码为:00.100111,Y的补码为:00.100111,-X的补码为:11.011001
操作 | 部分积 | 乘数 | C | 说明 |
---|---|---|---|---|
000.000000 | 100111 | 0 | ||
+ | 111.011001 | 部分积加-X,C=1 | ||
= | 111.011001 | 100111 | 1 | |
>> | 111.110110 | 01 | 1001 | 1 | 右移两位 |
+ | 001.001110 | 部分积加2X,C=0 | ||
= | 001.000100 | 0 | ||
>> | 000.010001 | 0001 | 10 | 0 | 右移两位 |
+ | 001.001110 | 部分积加2X,C=0 | ||
= | 001.011111 | 0001|10 | 0 | |
>> | 000.010111 | 110001 | 0 | 结果 |
特点
- 使用三符号位
- 如果最后移位后C为1,需要再执行+X操作
- 移位为两位一起移动
除法
除法运算的思想
手算二进制除法
规律:
-
忽略小数点
-
比较余数和除数,如果余数较大则商1,余数较小则商0
恢复余数法
运算规则
恢复余数使用三个寄存器
- 被除数/余数
- 商
- 除数
恢复余数计算的步骤:
- 计算余数减去除数,即新余数
- 判断新余数是否为负
- 如果为负上商0,则需要恢复余数
- 如果为正上商1
- 余数逻辑左移
特点
当差值,即新余数为负值时,需要多一步恢复余数
加减交替法
运算规则
因为加减交替法中的恢复余数操作和下一步减去除数操作可以写成 2(R+Y)-Y即2R+Y,那么就有了加减交替法
加减交替法的描述如下:
- 被除数-除数=新余数
- 判断新余数是否为负
- 如果新余数为负,左移并加上除数
- 如果新余数为正,左移并减去除数
例题
设 X=0.1011,Y=0.1101,使用加减交替法求X/Y
即-Y的补码为1.0011
操作 | 余数 | 商 | 说明 |
---|---|---|---|
00.1011 | 00000 | ||
+ | 11.0011 | ||
= | 11.1110 | 0000 | 0 | 余数为负数,商0 |
<< | 11.1100 | 000 | 00 | |
+ | 00.1101 | ||
= | 00.1001 | 000 | 01 | 余数为正数,商1 |
<< | 01.0010 | 00 | 010 | |
+ | 11.0011 | ||
= | 00.0101 | 00 | 011 | 余数为正数,商1 |
<< | 00.1010 | 0 | 0110 | |
+ | 11.0011 | ||
= | 11.1101 | 0 | 0110 | 余数为负数,商0 |
<< | 11.1010 | 01100 | |
+ | 00.1101 | ||
00.0111 | 01101 | 余数为正数,商1 |
其中符号位和乘法一样,通过除数和被除数的符号位异或来获取
注意:如果最后一次上商0,而又需要获取正确的余数,需要进行恢复余数操作来获取正确的余数
特点
- 使用逻辑左移
- 根据当前余数的正负性,来判断商0还是商1
浮点数
浮点数的表示
浮点数和科学计数法
十进制科学计数法
$$
+302657264526 = +3.026 * 10^{11}
$$
二进制计数法
$$
0.01001*2^2
$$
计算机中浮点数的表示和科学计数法有着一定的相似之处
定点数和浮点数
定点数:小数点位置固定的数
定点数分为定点小数和定点整数:
- 定点小数:小数点固定在数值部分的左边
- 定点整数:小数点固定在数值部分的右边
浮点数:小数点位置不固定的数
表示形式:
$$
N = M · R^E
$$
说明:
- N:浮点数
- M:尾数
- R:基数,是一个常数
- E:阶码,常用移码表示
浮点数的规格化表示
规格化的目的是为了使尾数部分的绝对值尽可能以最大值的形式出现
规格化数的规则:
- 右归:将尾数的结果右移N位,阶码E+N
- 左归:将尾数的结果左移N位,阶码相对应减去N
其中补码表示的尾数进行规格化时,尾数的符号位和尾数的数值部分最高位必须是不同的
左归
通过算数左移将浮点数规格化
当二进制浮点数如:
$$
b=0.01001*2^2
$$
此时符号位后有一位无效位0,那么我们可以通过阶码的变换,将b变为:
$$
b=0.10010*2^1
$$
右归
当尾数发生溢出(双符号位表示),如:
$$
b=01.10010*2^2
$$
那么我们可以让尾数右移一位,并且阶码加一的方式规格化这个数:
$$
b=0.11001*2^3
$$
浮点数的下溢与上溢
浮点数的表示都具有一个范围,超出这个范围就会发横溢出
上溢
要表示的数的绝对值超出了我们能表示的最大的范围
如果发生上溢,会抛出中断
下溢
要表示的数的绝对值超出了我们能够表示的最小的范围
如果发生下溢,我们会把这个数当作机器数的0
浮点数的加减法运算
浮点数加减运算的步骤有五个:对阶,尾数加减,规格化,舍入,判溢出
对阶
运算的两个数的阶数需要相同才能进行运算,我们一般使阶数更小的向阶数更大的对齐
如果阶数更大的向阶数更低的对齐,那么小数点之前会产生更多有效位,不方便实现
尾数加减
执行对阶后,对尾数进行加/减运算
规格化
使尾数以最大的形式表示出来
舍入
如果新得到的尾数会长度过长,我们需要进行舍入
常用舍0入1法。当移除的最高位为1时,尾数末尾+1,如果加1后又发生了尾数的溢出,则又需要进行一次右归
判溢出
如果阶码超出范围,则溢出
例题
两浮点数相加,求X+Y
已知:
$$
X=2^{010}·0.11011011
$$
$$
Y=2^{100}·(-0.10101100)
$$
-
对阶操作
-
求出阶差(双符号位):[Ex]+[-Ey]=00010+11100=11110
-
根据阶差的正负,X需要进行对阶
[Mx]=00 00100100 | 11
(对阶后超出范围的两位不要舍去)
-
-
尾数相加
[Mx]+[My]=00 00100100 | 11 + 11 01010100 = 11 10001010 | 11
-
规格化操作
根据补码的规格化要求,进行左归
[M] = 11 00010101 | 10 ,[E]= 00 011
-
舍入
附加位最高位为1,所以舍入时需要将阶码+1,[M]=11 00010110
-
判定溢出
阶码的符号位时 00 ,故不存在溢出
-
得出结果
本题的最终结果为
$$
X+Y = 2^{011}·(-0.11101010)
$$
浮点数的乘除法运算
浮点数的乘除法运算也由五个步骤构成:阶码相加,尾数相乘,规格化,舍入,判断阶码是否溢出
阶码相加/减
此步骤中,对阶码进行加减运算,同时需要判定运算的结果是否溢出
这一步的溢出可以使用双符号位进行判断
尾数相乘/除
尾数相乘后会有很长的辅助位,需要保留下来
规格化
和浮点数的加减法规则相同
舍入
0舍1入
判断阶码是否溢出
和浮点数的加减法规则相同
例题
已知:
$$
X = 2^{-5}·0.1110011
$$
$$
Y = 2^3·(-0.1110010)
$$
求X·Y,阶码用移码计算,尾数用补码计算
-
阶码相加
[Ex+Ey]=00 011 + 00 011 = 00 110\
此步骤没有溢出
-
尾数相乘
[Mx * My] = 1.0011001 1001010
-
规格化
不需要规格化
-
舍入
[Mx * My] = 1.0011010
-
判断溢出
不存在溢出
-
结果
$$
X · Y=2^{110}·(-0.1100110)
$$
校验码
数据校验码:能够发现错误或自动纠正错误的数据编码方法
实现原理:增加一些冗余码
奇偶校验码
实现方法,给一个字节加一个校验位
奇校验
一个字节加上校验码一共有奇数个1
偶校验
一个字节加上校验码一共有偶数个1
优缺点
- 优点:开销小
- 缺点:只能发现一位或奇数位出错,并不能发现哪一位出错
海明码
实现方法:在数据中加N个校验位,并把二进制位分配在几个奇偶校验组中,某一位出现错误会导致多个校验组出错
校验码为r位,数据为k位,两者之间满足以下关系:
$$
2^ \geq k+r
$$
此时海明码能纠正一位错,并发现两位错
要检验8位数据,需要5位校验位,海明码的排列方式如下:
$$
H_{13}H_{12}H_{11}...H_{2}H_{1}
$$
其中海明码的5个校验位和参与校验的数据位具有一定的对应关系,五个校验位只与本身有关,数据位参与校验的位号是校验位号之和,13位海明码中校验位和数据位之间的对应关系如下表所示:
海明码位号 | 数据位/校验位 | 参与校验的校验位位号 | 校验位位号之和 |
---|---|---|---|
H1 | P1 | 1 | |
H2 | P2 | 2 | |
H3 | D1 | 1,2 | 1+2 |
H4 | P3 | 4 | |
H5 | D2 | 1,4 | 1+4 |
H6 | D3 | 2,4 | 2+4 |
H7 | D4 | 1,2, 4 | 1+2+4 |
H8 | P4 | 8 | |
H9 | D5 | 1,8 | 8+1 |
H10 | D6 | 2,8 | 8+2 |
H11 | D7 | 1,2,8 | 8+2+1 |
H12 | D8 | 4,8 | 8+4 |
H13 | P5 | 13 |
每一个校验位参与对应数据位的偶校验,海明码的求取方法入下:
$$
P_1 = D_1 \bigoplus D_2 \bigoplus D_4 \bigoplus D_5 \bigoplus D_7
$$
其他位以此类推,其中,总校验位P5为前N位异或
海明码的校验方法如下:
$$
S_1 = P_1 \bigoplus D_1 \bigoplus D_2 \bigoplus D_4 \bigoplus D_5 \bigoplus D_7
$$
其他以此类推,最后S5能反映是奇数位出错还是偶数位出错,任何偶数个数出错,S5一定为0,S1~S4如果为0则无错,如果出错则反之
同时,通过S4~S1,能够将错误的编码进行纠正,将这四位编码进行顺序排列,便能得出错的位