运算方法与运算器
预制知识: 数制转换
计算机中的常用进制
对于一种进制, 通俗讲“逢几进一即为几进制”：
- 十进制 Decimal: 逢十进一
- $ (559)_{10} $ 或 $ (559)_D $
- 二进制 Binary: 逢二进一
- $ (1000101111)_2 $ 或 $ (1000101111)_B $
- 八进制 Octal: 逢八进一
- $ (1057)_8 $ 或 $ (1057)_O $
- 十六进制 Hexadecimal: 逢十六进一
- $ (22F)_{16} $ 或 $ (22F)_H $
计算机中以二进制为基础，是因为二进制只包含两种状态，采用这样的二值表示较为简单，同时 0 1 也可以表好似真假，便于进行逻辑运算。
在计算机中常用的转换有以下几种：
- N进制转十进制
- 十进制转N进制
- 二进制转八进制、十六进制
- 八进制、十六进制转二进制
N进制转十进制
对于 二、八、十六进制转换为十进制，只需按权展开相加即可。
按权展开:
对于一个 $N$ 进制数, 其长度为 $len$ , 第 $i$ 位的数字为 $n_i$ , 其权重为 $N^{i-1}$ , 按权展开后表示为 $n_i\times N^{i-1}$.
对应的十进制为:
$$ \sum_{i=1}^{len}n_i\times N^{i-1}$$
以十进制为例，对于$(559)_{10}$, 我们可以表示为
$$5\times 10^2+5\times 10^1+9\times10^0=559$$
类似的, 二进制可以表示为:
$$1\times2^3+0\times2^2+1\times2^1+1\times2^0=1011$$
在计算机中可以使用如下算法:
string num;//待转换的数字
int N;//待转换数字的进制
cin>>num>>N;
int len=num.size();
int base=1;//进制基数
int Decimal=0;
for(int i=len-1;i>=0;i--)
{
Decimal+=(num[i]-'0')*base;//对于N大于10的进制需要特殊处理
base*=N;
}
cout<<Decimal<<endl;
十进制转N进制
对于十进制转N进制，我们可以采用短除法进行计算，将余数逆序写出即为转换后的进制表示。
这里以二进制为例：
<!– 补图，短除法 –>
在计算机中可以使用如下算法：
int num;//表示一个十进制数
int N;//表示要转化为N进制
cin>>num>>N;
stack<int> New_num;//存储当前的余数
while(num)
{
New_num.push(num%N);
num/=N;
}
while(New_num.size())
{
cout<<New_num.top();//对于N大于10的进制需要特殊处理
New_num.pop();
}
二进制转八进制、十六进制
根据八进制及十六进制的特点，每位可以表示的范围为：
$$ [(000)_2,(111)_2]=[0,7] \qquad [(0000)_2,(1111)_2]=[0,F]$$
因此可以采取分组求值的方式进行转换.
- 转八进制: 三位一组, 不足补 0
- 转十六进制: 四位一组, 不足补 0
例如将$(1011110)_2$转化为八进制及十六进制:
$$
\begin{matrix}
\underline{001}&\underline{011}&\underline{110} \\
1&3&6
\end{matrix}
$$ $$
\begin{matrix}
\underline{0101}&\underline{1110} \\
5&E
\end{matrix} $$
八进制、十六进制转二进制
八进制、十六进制转二进制与二进制转八进制、十六进制是相反的过程。
首先按位求二进制，不足一组的补 0 ，然后将其合并：
$$
\begin{matrix}
1&3&6&\\
\underline{001}&\underline{011}&\underline{110}&= 1011110
\end{matrix}
$$ $$
\begin{matrix}
5&E&\\
\underline{0101}&\underline{1110}&= 1011110
\end{matrix} $$
<!– 补链接，位运算 –>
数据与文字的表示
数据格式
定点数表示法
定点数：通常用来表示纯小数或者纯整数
$$ 纯小数: 0 <= |x| <= 1-2^{-n} $$
$$ 纯整数: 0 <= |x| <= 2^{n}-1 $$
目前计算机中多采用定点纯整数表示,因此将定点数表示的运算称作整数运算.
浮点数表示法
十进制的浮点数可以表示为：
$$ N=10^E\cdot M $$
二进制的浮点数则可以表示为：
$$ N=2^e\cdot M $$ $$其中 M 为尾数 $$ $$ e 为浮点数的指数,在计算机中使用阶码表示小数点位置 $$
在计算机中 2 作为一个常数.
一个浮点数由三部分组成: 数符, 尾数, 阶码
IEEE754标准
一个 754 标准的浮点数分为三部分：
- S 符号位 1 位，在最高位
- E 阶码 8 位，采用移码表示
- M 尾数 23位，在低位部分，纯小数表示
规格化：将浮点数表示成 $ (-1)^S \times (1.M) \times 2^{E-127} $ 的形式, 即底数部分的整数位为1.
将浮点数规格化的过程就是将整数位变为 1 的过程.
特殊情况:
| S | E | M | 意义 |
|---|---|---|---|
| 0/1 | 0 | 0 | +-0 |
| 0/1 | 0 | 非0 | 非规格化数 |
| 0/1 | 1~254 | 任意 | +-0 |
| 0/1 | 255 | 0 | +-无穷 |
| 0/1 | 255 | 非0 | NaN |
机器码表示
在机器中将符号数字化，通常将最高位作为符号为，0为正，1为负。
原码
将十进制转化为二进制数，并在最高位添加符号，例如 13 与 -13 在字长为八位的机器中使用原码表示为：
$$[13]_原=00001101$$$$[-13]_原=10001101$$
特别的, 0 的原码表示有两种,即 +0 与 -0
$$[0]_原=00000000$$ $$[-0]_原=10000000$$
原码特点:
- 表示简单,实现乘除运算规则简单,和真值之间的转换简单.
- 进行加减运算麻烦.
反码
整数与原码相同,负数时符号位为 1 不变,数值位按位取反就得到了反码.
对于反码的定义:
- 当X大于0时：$$[X]_反=X$$
- 当X小于0时,$$[X]_反=2^{n+1}+X-1$$
可以理解为将当前所有的位置置一，然后加上原来的数字。
在反码中同样有 +0 和 -0 之分。
$$[0]_反=00000000$$ $$[-0]_反=11111111$$
补码
我们定义补码为:
$$[X]_补=模+X (X<0)$$
通常模表示的是一个系统的量程(在这里为$2^{n+1},是系统的量程$)或系统表示的最大数.
根据定义,正数的补码等于正数的原码,对于负数,通常是通过先求反码再+1的形式取得.
补码由于其特殊性,在同样的字长下,根据定义可以表示的数字要比原码、反码多一位（$-2^n$）,但是这位数无法通过反码取得。
在补码中没有 +0 和 -0 之分.
补码的优点：可以将减法转化为加法.
小结
$$
[X]_原=\begin{cases}
&X & {0<=X<2^n}\\
&2^n-X & {-2^n<X<=0}
\end{cases}
$$
$$
[X]_反=
\begin{cases}
&X & {0<=X<2^n}\\
&2^{n+1}+X-1 & {-2^n<X<=0}
\end{cases}
$$
$$
[X]_原=
\begin{cases}
&X & {0<=X<2^n}\\
&2^{n+1}+X & {-2^n<=X<=0}
\end{cases}
$$
移码表示(用于阶码)
定点整数定义：
$$[X]_移=2^n+X (-2^n<=X<2^n)$$
在此定义中，移码和补码尾数相同，符号相反。
在浮点数中阶码使用移码表示。
设阶码为K，则偏移数值为$2^{K-1}-1$, 当 K=8 时，偏移值为127.
字符表示
符号数据：字符信息用数据表示，如ASCII码
ASCII：用一个字节表示，第七位用来编码(128个),最高位为校验位.
校验码
引入:防止信息传输和处理过程中受到干扰和故障.
解决方式:在有效信息中加入冗余信息(校验位)
奇偶校验:
奇校验位 $\overline C$ 定义为 二进制的按位加，只有当二进制中的1为奇数个时$\overline C$才为一
偶校验位$C$与奇校验位类似，但只有当1为偶数个时$C$才为1
定点加法减法
补码加法
补码加法公式:
$$ [X+Y]_补=[X]_补+[Y]_补 \quad (mod \quad 2^{n+1}) $$
在补码加法中,符号位要作为数的一部分一起参加运算,最终结果对$2^{n+1}$取模,超过范围的进位舍弃.
补码减法
补码减法通过把减数转化为相反数, 从而实现将减法转化为加法. 即:
$$
[X-Y]_补=[X]_补-[Y]_补=[X]_补-[-Y]_补
$$
求 $[-Y]_补$ 时同样按照取反+1的原则(包括符号位在内).
溢出检测
在运算过程中出现大于字长绝对值的现象称为溢出, 同时根据两种不同的溢出情况,分为:
- 上溢: 两正数相加变负数, 大于机器所能表示的最大数
- 下溢: 两负数相加变正数, 小于机器所能表示的最小数.
双符号检测
使用变形补码运算.
在变形补码中使用两位符号位表示正负。两个符号位通过一个异或门进行检测。
| Sf1 | Sf2 | ||
|---|---|---|---|
| 0 | 0 | 正确 | 正数 |
| 0 | 1 | 溢出 | 正溢 |
| 1 | 0 | 溢出 | 负溢 |
| 1 | 1 | 正确 | 负数 |
最终通过变形补码运算的结果如果符号位相异表示溢出。
单符号检测
通过符号位产生的进位和最高位产生的进位进行判断。
$Cf$ 表示符号位产生的进位，$C0$ 表示最高有效位产生的进位。
| Cf | C0 | ||
|---|---|---|---|
| 0 | 0 | 正确 | 正数 |
| 0 | 1 | 溢出 | 正溢 |
| 1 | 0 | 溢出 | 负溢 |
| 1 | 1 | 正确 | 负数 |
基本的二进制加法/减法器
基本运算器
- 半加器
半加器可以实现两个数相加即进位
真值表如下：A B Sum Carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 - 全加器
全加器可以在半加器的基础上实现进位相加。电路通过两个半加器实现。
真值表如下：A B Carry in Sum Carry out 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1
<!– 图片 –>
行波进位
二进制的加法器是通过多个全加器串联形成的，进行减法操作时先转化成加法在进行运算。
由于是串联计算，只有当上一位计算完成后下一位才会开始计算，因此在计算n位二进制加法时会产生延时：
$$
t_a=n \cdot 2T + 9T=(2n+9)T
$$
因此位数越多，时间越长。
同时加法器只能够做加减运算，不能进行逻辑运算。
定点运算器的组成
逻辑运算
暂略
算术逻辑单元 ALU
一片 74181 能够进行四位并行算数运算。
通过 74181 可以实现一级先行进位，通过多片 74181 串联可以实现组内先行进位，组间行波进位。
同时四片 74181 可以连接 74182 进行二级先行进位
浮点运算与浮点运算器
浮点数的运算
浮点数的运算大致分为六步：
- 0操作数检查: 简化运算($N+0=N$)
- 比较阶码完成对阶: 大阶向小阶看齐, 先计算阶差，尾数右移的次数等于阶差
- 尾数运算（补码运算）
- 结果规格化（单符号规格化与双符号规格化）
- 舍入处理(0舍1入)
- 溢出判断和处理
规格化与溢出处理
规格化有两种：
- 单符号位：$0.1…$ 的形式，要求尾数 $ 0.5<=|M|<1 $
- 双符号位：$11.0…$ 或者 $00.1…$
溢出分为两类共四种：
- 阶码上溢: 一般将其认为是 $ +\infty $ 或者 $ -\infty $
- 阶码下溢: 数值为0
- 尾数上溢: 尾数右移，阶码+1
- 尾数下溢: 尾数右移时最低位从最右端流出，进行舍入处理。
尾数的溢出处理在规格化时已经完成，最后第六步只需要判断阶码是否溢出。
浮点运算流水线
每一个子任务都有专门的部件实现。
流水线中各段时间应该尽量相等，避免出现“堵塞”和“断流”。
流水线有装入时间和排空时间，当流水线充满后才能充分发挥效率。
流水时钟周期
我们定义过程 $S_i$ 的时间为 $ \tau_i $ , 缓冲寄存器延时为 $ \tau_t $ ,则 流水时钟周期 的定义为：
$$
\tau=max(\tau_i)+\tau_t=\tau_m+\tau_t
$$
即最长时间+缓冲时间即为流水时钟周期
流水线处理的频率为：
$$
f=\frac{1}{\tau}
$$
线性流水线加速比计算
计算加速比需要计算:
- 流水线时钟周期数
- 非流水线时钟周期数
一个各段时间相等的k级过程的流水线处理n个任务所需要的时钟周期数为: $$ T_K=K+(n-1) $$
这是因为流水充满需要K个时钟周期,之后的每次任务都可以在一个时钟周期内完成。
非流水线时钟周期，每个任务都需要K个时钟周期才能处理完成，因此时钟周期数为：
$$ T_L=n \cdot K $$
加速比定义如下：
$$
加速比=\frac{非流水线所用时间}{流水线所用时间}
$$
计算出两种时钟周期数后我们只需要乘以 $ \tau_i $ (流水时钟周期)即可得到所用时间。
$$
\begin{aligned}
C_K&=\frac{n\cdot K\cdot \tau}{k+(n-1)\cdot \tau}\
&=\frac{n\cdot k}{k+(n-1)}
\end{aligned}
$$