运算方法和运算器

计算机组成原理——运算方法和运算器知识梳理

参考《计算机组成原理》第六版白中英、戴志涛主编，本文是对第二章运算方法和运算器的整理摘要。

1.1 数据与文字的表示

1.1.1 数据格式

一是定点格式，二是浮点格式。

定点数的表示方法
假设使用 $n+1$ 位字来表示，则 $x_n$ 表示符号，并用0表示正号，用1表示负号。
对于纯小数， $0\leq|x|\leq1-2^{-n}$
对于纯整数， $0\leq|x|\leq2^n-1$
浮点数的表示方法
计算时使数值部分的绝对值小于1，小数点的位置随比例因子的不同而在一定范围内可以自由浮动。
任意一个十进制数 $N$ 可以写成
$N=10^E.M$
任意一个二进制数 $N$ 可以写成
$N=2^e.M$
其中， $M$ 称为浮点数的尾数，是一个纯小数。e是比例因子的指数，称为浮点数的指数，是一个整数。指数也称为阶码
阶符阶码数符尾数
$E_s$ $E_{m-1}...E_1E_0$ $M_s$ $M_{n-1}...M_1M_0$
十进制数串的表示方法
（1）字符串形式，即1字节存放一个十进制的数位或符号位。
（2）压缩的十进制数串形式，即1字节存放两个十进制的数位。

阶符	阶码	数符	尾数
$E_s$	$E_{m-1}...E_1E_0$	$M_s$	$M_{n-1}...M_1M_0$

1.1.2 数的机器码表示

正整数的原码、补码、反码是一致的，符号位固定是0
负整数的原码、补码、反码是不同的，符号位固定是1

原码表示法
例如， $x=+1001$ ，则 $[x]_原=01001$
$x=-1001$ ，则 $[x]_原=11001$
实际上就是在真值的基础上增加了符号位
补码表示法
正整数的补码和原码一致。
负整数先把符号位以外的位取反变为反码，再在反码的基础上加1得到补码。
例如， $x=+1001$ ，则 $[x]_补=01001$
$x=-1001$ ，则 $[x]_补=10111$
通过补码计算真值
$x=-2^nx_n+\sum_{i=0}^{n-1}2^ix_i$
实际上就是将符号位以外的位按正常的二进制转十进制来计算累加，再计算符号位对应的十进制并取负号，相加得到结果。
因此，对于正整数来说，符号位为0，只需要正常计算即可。
对于负整数来说，符号位为1，需要将符号位以外部分的十进制结果减去符号位的十进制结果，得到真值。
通过补码求原码，除符号位和最后一个1以外，将这个符号位和1中间的部分全部取反。
移码表示法
移码通常用于表示浮点数的阶码。阶码( $k$ 位)的传统定义是
$[e]_移=2^k+e,2^k>e\geq-2^k$
式中， $[e]_移$ 为机器数， $e$ 为真值， $2^k$ 是一个固定的偏移值常数。
移码中符号位 $e_k$ 的表示的规律与原码、补码、反码相反，即正整数符号位移码表示为1，负整数符号位移码表示为0。
浮点数的机器表示
IEEE754标准
32位短浮点数
S(31，符号位占1位) E(30-23，阶码占8位) M(22-0，尾数占23位)
S是符号位，0表示正数，1表示负数。小数点位置在尾数域最左有效位的右边。
阶符采用隐含方式，即采用移码方法来表示正负指数。采用这种方式时，将浮点数的指数真值 $e$ 变成阶码 $E$ 时，应将指数 $e$ 加上一个固定的偏置常数127，即 $E=e+127$ 。
为了提高数据的表示精度，当尾数的值不为0时，尾数域的最高有效位应为1，这称为浮点数的规格化表示。对于非规格化浮点数，一般可以通过修改阶码同时右移动小数点位置的办法，使其变成规格化数的形式。
在IEEE754标准中，一个规格化的32位浮点数 $x$ 的真值表示为
$x=(-1)^S\times(1.M)\times2^{E-127},e=E-127$
其中，尾数域所表示的值是 $1.M$ 。由于规格化的浮点数的尾数域最左位(最高有效位)总是1，故这一位无需存储，而认为是隐藏在小数点的左边。因此，实际上可以将24位有效数用23位字段来存储。
对32位浮点数 $N$ ，IEEE754定义：
（1）若 $E=255$ 且 $M\neq0$ ，则 $N=NaN$ 。
（2）若 $E=255$ 且 $M=0$ ，则 $N=(-1)^S\infty$ 。
（3）若 $E=0$ 且 $M=0$ ，则 $N=(-1)^S0$ 。
（4）若 $0<E<255$ ，则 $N=(-1)^S\times(1.M)\times2^{E-127}$ (规格化数)。
（5）若 $E=0$ 且 $M\neq0$ ，则 $N=(-1)^S\times(0.M)\times2^-126$ (非规格化数)。这是无法进行规格化表示的数据，可以用非规格化形式表示。
对于64位长浮点数，64位浮点数中符号位1位，阶码域11位，尾数域52位，指数偏移值是1023。因此，规格化的64位浮点数 $x$ 的真值为
$x=(-1)^S\times(1.M)\times2^{E-1023},e=E-1023$

1.1.3 字符与字符串的表示方法

符号数据：将字符信息用数据表示。

1.1.4 汉字的表示方

汉字的输入编码
数字编码、拼音码、字形编码
汉字内码
汉字字模码

1.1.5 校验码

最简单且应用广泛的检错码是采用一位校验位的奇校验或偶校验。

设 $X=(x_0x_1...x_{n-1})$ 是一个n位字，则奇校验位 $\overline{C}$ 定义为

\overline{C}=x_0\oplus x_1\oplus...\oplus x_{n-1}

式中， $\oplus$ 代表按位相加，表明只有当 $X$ 中包含奇数个1时，才能使 $\overline{C}=1$ ，即 $C=0$ 。

同理，偶校验位 $C$ 定义为

C=x_0\oplus x_1\oplus...\oplus x_{n-1}

即 $X$ 中包含偶数个1时，才使 $C=0$ 。

奇偶校验只能检测奇数个错误，无法检测偶数个错误，更无法识别错误信息的位置。

在异或运算中，奇数个1计算出的结果为1，偶数个1计算出的结果为0。
从上面来看，当校验位结果为0时，表示信息正常，当校验位结果为1时，表示信息错误。
原始数据中有奇数个1，使用奇校验，当出现错误时，奇数个1变为偶数个1，检验位结果为0，由于奇校验位是 $\overline C$ 的形式，则最终校验结果 $C$ 为1，表示错误。
偶校验同理可得，当出现错误时，偶数个1变为奇数个，校验位结果直接为1，表示错误。

其他校验码如海明检验码，可参考海明码一篇文章彻底搞懂｜🔥秃桔子的博客

1.2 定点加法、减法运算

1.2.1 补码加法

基本公式

[x]_补+[y]_补=[x+y]_补\qquad(mod\ 2^{n+1})

考虑4种情况

（1） $x\geq0,y\geq0$ ，则 $x+y\geq0$ 。

[x]_补+[y]_补=[x+y]_补\qquad(mod\ 2^{n+1})

（2） $x\geq0,y<0$ ，则 $x+y\geq0$ 或 $x+y<0$ ，则由补码定义可得 $[x]_补=x,[y]_补=2^{n+1}+y$ 。

\begin{aligned} & \quad[x]_补+[y]_补\\ & =x+2^{n+1}+y\\ & = 2^{n+1}+(x+y)\\ &=[x+y]_补\qquad(mod\ 2^{n+1}) \\ \end{aligned}

（3） $x<0,y\geq0$ ，和情况（2）同理。

（4） $x<0,y<0$ ，则 $x+y<0$ ，则由补码定义可得 $[x]_补=2^{n+1}+x,[y]_补=2^{n+1}+y$ 。

\begin{aligned} &\quad[x]_补+[y]_补\\ &=2^{n+1}+x+2^{n+1}+y\\ &=2^{n+1}+2^{n+1}+(x+y)\\ &=[x+y]_补\qquad(mod\ 2^{n+1}) \end{aligned}

1.2.2 补码减法

基本公式

[x-y]_补=[x]_补-[y]_补=[x]_补+[-y]_补

从 $[y]_补$ 求 $[-y]_补$ 的法则是：对 $[y]_补$ 包括符号位“求反且最末位加1”，即可得到 $[-y]_补$ 。

1.2.3 溢出概念与检测方法

两个正数相加，结果过大导致符号位改变，结果为负数，正溢。

两个负数相加，结果过小导致符号位改变，结果为正数，负溢。

为了检测溢出，可采用两种检测方法。第一种方法就是双符号位法，也称为“变形补码”，使模 $2^{n+1}$ 补码所能表示的数的范围扩大一倍。

数的变形补码用同余式表示时

[x]_补=2^{n+2}+x \qquad(mod\ 2^{n+2})

采用变形补码，正数的符号位为00，负数的符号位为11。当发生溢出时，符号位会出现01和10的情况，但是最高符号位永远表示结果的正确符号。

01表示正溢，10表是负溢。

1.3 定点乘法运算

用原码阵列乘法器，输入数据用原码表示

用补码阵列乘法器，输入数据用补码表示

从实际计算过程来看，都是用真值绝对值的二进制形式计算得到结果。
如果给出的条件是十进制数，则直接取绝对值，如果是原码或补码，则经过一定的计算转换到真值的绝对值。

符号位都是单独计算，符号使用异或运算，最后结果加上符号位。

$0\oplus1=1$ ， $0\oplus0=0$ ， $1\oplus1=1$ 。

1.4 定点除法运算

由于机器计算无法提前判断结果，必须先计算出结果才能进行判断。那么关于除法运算中余数不够减的情况，提供了两种处理方法，恢复余数法和加减交替法。

恢复余数法，就是将当前的余数加上除数即可。但是由于恢复余数的步数不是固定的，难以控制，因此实际运算中更多使用不恢复的方法。

加减交替法，也就是不恢复余数法，能够在余数不够减的情况下，根据余数符号，继续往下运算，步数固定，控制简单。

当i-1次求商的余数为正时，上商为1，余数左移1位并减去除数得到下一个余数，即 $R_{i+1}=2R_i-Y$
当i-1次求商的余数为负时，上商为0，余数左移1位并加上除数得到下一个余数，即 $R_{i+1}=2(R_i+Y)-Y=2R_i+Y$

虽然加减交替法被称为不恢复余数法，但是如果最后一次得到的余数为负数，那仍需要进行恢复余数。恢复余数只需要直接加上除数即可，不需要进行任何的移位，即 $R=R_i+Y$ 。

另外，在计算过程中，通过左移计算的一般是手工实现版，通过右移计算的一般是算法实现版。

1.5 定点运算器的组成

1.5.1 逻辑运算

四种基本逻辑运算：逻辑非(求反)、逻辑加(或)、逻辑乘(与)、逻辑异(按位加)。

1.5.2 多功能算术/逻辑运算单元

半加器

$H_i=A_i\oplus B_i$ ，不考虑进位，很少使用。

全加器

考虑低位进位 $C_{i-1}$ 和向高位的进位 $C_i$ ，其逻辑表达式为

F_i=A_i\oplus B_i\oplus C_i \\ C_{i+1}=A_iB_i+B_iC_i+C_iA_i

式中， $F_i$ 是第 $i$ 位的和数， $A_i$ 、 $B_i$ 是第 $i$ 位的被加数和加数， $C_i$ 是第 $i$ 位的进位输入， $C_{i+1}$ 为第 $i$ 位的进位输出。

对全加器的功能进行拓展，将 $A_i$ 和 $B_i$ 先组合成由控制参数 $S_0$ 、 $S_1$ 、 $S_2$ 、 $S_3$ 控制的组合函数 $X_i$ 和 $Y_i$ ，然后再将 $X_i$ 和 $Y_i$ 和下一位进位数通过全加器进行全加。

其中
$X_i=\overline{S_3A_iB_i+S_2A_i\overline{B_i}}\\ Y_i=\overline{A_i+S_0B_i+S_1\overline{B_i}}\\ F_i=Y_i\oplus X_i \oplus C_{n+i}\\ C_{n+i+1}=Y_i+X_iC_{n+i}$
每一位的进位公式递推如下，
$C_{n+1}=Y_0+X_0C_n\\ C_{n+2}=Y_1+X_1C_{n+1}\\ C_{n+3}=Y_2+X_2C_{n+2}\\ C_{n+4}=Y_3+X_3C_{n+3}$
设
$G=Y_3+Y_2X_3+Y_1X_2X_3\\ +Y_0X_1X_2X_3\\ P=X_0X_1X_2X_3$
则
$C_{n+4}=G+PC_n$
其中， $G$ 称为进位发生输出， $P$ 称为进位传送输出。

并行进位

组内并行，组间串行

组内并行，组件并行

1.6 浮点运算与浮点运算器

移位操作

逻辑移位，不保留原符号位，直接补0。

循环移位，不保留原符号位，空位补位的值与原符号位的值相同。

原码算术移位，保留符号位，补0。

补码算术左移，单符号位保留不变，双符号位只保留第一位，空位补0

补码算术右移，单符号位保留不变，双符号位只保留第一位，空位补位的值与原符号位的值相同

浮点加法、减法运算

设有两个浮点数

x=2^{E_x}\cdot M_x\\ y=2^{E_y}\cdot M_y

其中， $E_x$ 和 $E_y$ 分别为数 $x$ 和 $y$ 的阶码， $M_x$ 和 $M_y$ 分别为数 $x$ 和 $y$ 的尾数。

两浮点数进行加法和减法的运算规则是

z=x\pm y=(M_x2^{E_x-E_y}\pm M_y)2^{E_y}\\E_x\leq E_y

运算步骤

0操作数检查
$x$ 和 $y$ 中有一个数为0，直接得出结果。
比较阶码大小并完成对阶
两浮点数加减，首先要看两数的阶码是否相同，即小数点的位置是否对齐。如果不同，则需要进行移位操作，使其阶码相同，这一过程就称为对阶。
要对阶，首先要求出阶差，即 $\Delta E=E_x-E_y$
一般使用尾数右移的方式来对阶，因为尾数右移造成的误差要远远小于尾数左移造成的误差。
因此，在对阶时，总是使小阶向大阶看齐，即小阶的尾数向右移位(相当于小数点左移)，每右移一位，其阶码加1，直到两数的阶码相等为止，右移的位数等于阶差 $\Delta E$ 。
这里的移位都是指补码算术移位。
尾数加减运算
注意浮点数都是用补码来计算的即可。
结果规格化
右规：尾数右移才能满足规格化条件。尾数右移1位，阶码加1。
左规：尾数左移才能满足规格化条件。尾数左移1位，阶码减1。
形如00.0…01…和11.1…10这种结果，可以将其左规为00.1…和11.0…的形式。
舍入处理
在尾数右移时需要对丢弃的低位部分进行舍入处理。
就近舍入：0舍1入，类似于4舍5入。丢弃的最高位为1则进1。
朝0舍入：就是简单的截尾。这种方法容易积累误差。
朝 $+\infty$ 舍入：对于正数，只要多余位不全为0则进1；对于负数，就是截尾。
朝 $-\infty$ 舍入：对于正数，就是截尾；对于负数，只要多余位不全为0则进1。
溢出判断和处理
分为对阶码的溢出处理和对尾数的溢出处理。
阶码上溢：一般将其认为是 $+\infty$ 和 $-\infty$ 。
阶码下溢：一般将其认为是0。
尾数上溢：由于最高位进位导致的溢出，进行尾数尾数右移，阶码加1，重新对齐。
尾数下溢：在尾数右移时，进行舍入处理。

树下集熵