计组期中复习笔记

计算机基础

发展史

• 第一代：电子管；机器语言。
• 第二代：晶体管；监控语言、高级语言。
• 第三代：中小规模集成电路、磁芯存储器；高级语言、分时操作系统。
• 第四代：大规模与超大规模集成电路、半导体存储器、微处理器；DOS / Windows，Unix / Linux，Mac OS。
• 第五代：巨大规模集成电路，超大规模、超高速集成电路，多处理器、多核处理器；软件与算法。

基本组成

• 硬件系统
• 软件系统
• 指令体系结构（ISA）

分类

Flynn 分类法。

• SISD（单指令流单数据流）
• SIMD
• MISD
• MIMD（多指令流多数据流）

加速比

阿姆达尔定律

改进后系统执行时间：$T_n=T_0(1-f_e+\frac{f_e}{r_e})$

加速比：$S_p=\frac{1}{1-f_e+\frac{f_e}{r_e}}$

​ 多个部件的加速比：$S_p=\frac{1}{1-\sum f_e+\sum \frac{f_e}{r_e}}$

例题

若计算机系统有 3 个部件 a、b、c 是可改进的，它们的部件加速比分别为 30、30、20，部件 a 和 b 在总执行时间中所占的比例分别是 30％、30％。 若要使整个系统的加速比达到 10，则部件 c 在总执行时间中所占的比例应为 ？%

$S_p=10$

$\sum f_e=0.3+0.3+x=0.6+x$

$\sum \frac{f_e}{r_e}=\frac{0.3}{30}+\frac{0.3}{30}+\frac{x}{20}=0.02+\frac{x}{20}$

带入公式得：$10=\frac{1}{1-(0.6+x)+(0.02+\frac{x}{20})}$

解得：$x=\frac{95}{32} \approx 0.3368$

进制转换

例：97.625 转换为二进制和十六进制。

转换结果：1100001.101

转换结果：61.A

定点数

下述的 $n$ 均表示编码的位数（含符号位）。

原码

• 符号位：0 为正，1 为负。
• 数值位：$|X|$

• 可表示范围

  • 纯整数：$-(2^{n-1}-1)\sim +(2^{n-1}-1)$
  • 纯小数：$-(1-2^{-(n-1)})\sim +(1-2^{-(n-1)})$

补码

• 符号位：0 为正，1 为负。

• 数值位

  • $X\ge 0$：$X$
  • $X\lt 0$：$2^n+X$

• 可表示范围

  • 纯整数：$-2^{n-1}\sim +(2^{n-1}-1)$
  • 纯小数：$-1\sim +(1-2^{-(n-1)})$
• 负数补码求法：先将 $|X|$ 用原码表示。从右往左找到第一个 1，将这一位左边的位全部取反，这一位及其右边的位保持不变。
• 补码减法：$\begin{align} [X-Y]_\text{补}&=[X]_\text{补}+[-Y]_\text{补} \\ &=[X]_\text{补}+[[Y]_\text{补}]_\text{求补} \end{align}$

反码

• 符号位：0 为正，1 为负。

• 数值位

  • $X\ge 0$：$X$
  • $X\lt 0$：$|X|$ 按位取反
• 可表示范围：与原码相同。
• 负数补码与反码的关系：$[X]_\text{补}=[X]_\text{反}$的最低位加 1。

移码

• 符号位：1 为正，0 为负。
• 数值：$[X]_\text{移}=2^{n-1}+X$
• 与补码的关系：补码的符号位取反就是移码。
• 可表示范围：与补码相同。

编码与真值的关系

由此可见，移码可以直接比较大小。

浮点数

二进制的科学计数法。

规格化浮点数

尾数 $M$ 形式

• $M\ge 0$：$[M]_\text{补}=0.1\times\times\cdots\times$
• $M\lt 0$：$[M]_\text{补}=1.0\times\times\cdots\times$

规格化

• 左归：每算数左移 1 位，阶码减 1。
• 右规：每算数右移 1 位，阶码加 1。

IEEE 754 标准

IEEE 754 规格化尾数：1.f，即 $1.\times\times\cdots\times$（包含符号位）

$\text{尾数}\times 2^\text{阶数}$

阶码应为阶数的补码符号位取反再减去 1（比标准移码少 1）。

图片勘误：f 为原码。

BCD 码

把十进制数拆成一位位数字来表示，每位使用四位二进制数来表示。

以常用的 8421 码为例，如 49，可拆成 4 和 9，即 0100 和 1001，故 49 的 8421 BCD 码为 01001001。

BCD 码也可以参与运算。

检错与纠错码

海明码距

• 定义：将两个码字按位异或后 1 的个数。
• 检错 $r$ 位：$d_\text{min}$ 至少为 $r+1$。
• 纠错 $r$ 位：$d_\text{min}$ 至少为 $2r+1$。

确保具有一位纠错能力

$2^k\ge n+k+1$，其中：$n$ 为数据长度，$k$ 为校验位位数。

奇偶校验

• 奇校验：数据中 1 的个数为奇数时，校验位为 0。
• 偶校验：数据中 1 的个数为偶数时，校验位为 0。

海明校验码

编码

例：编码 10101110。

校验与纠错

例：给定如下码字：010111010110，判断出错位置，以及纠错后的原始数据。

若无出错，则校验码均通过，此时 $H_0H_1H_2H_3=0$。

如果只有校验位出错，则只有一个校验码不通过，此时原数据无需修正。

循环冗余校验码（CRC）

编码

信息：1010110

生成多项式：$G(x)=x^3+x+1$

校验与纠错

若有出错，根据余数值查询出错定位表即可得到出错的位。

定点数的运算

加减运算

补码运算。

溢出及其判断

由于补码表示范围有限，如果计算结果不在范围内，则发生了溢出。

双符号位（变形码）判决

00 表示正，11 表示负。如果运算结果中，两个符号位不一致，则说明发生了溢出。

乘法运算

Booth 法。

$$X\times Y$$

例：$X=-0.1101$，$Y=+0.0110$，求乘积。

$[X]_\text{补}=11.0011$，$[-X]_\text{补}=00.1101$（双符号补码）；$[Y]_\text{补}=0.0110$（单符号补码）。

得 $[X\cdot Y]_\text{补}=1.10110010$。

除法运算

原码加减交替法。

$$|X|\div|Y|$$

• 余数 $R\ge 0$，商为 1，余数左移，减 $|Y|$（加 $[-|Y|]_\text{补}$）。
• 余数 $R<0$，商为 0，余数右移，加 $|Y|$。

表格数值位扩展到 $|Y|$ 数值位的 2 倍。

例：$X=+0.1001110001$，$Y=-0.10101$。求 $X\div Y$。

$|X|=0.1001110001$，$|Y|=0.10101$，$[-|Y|]_\text{补}=1.01011$。

得 $[X\div Y]_\text{原}=1.11101$，$\text{余数}=0.10000\times 2^{-5}$。

需要恢复余数的情况

R 符号为负（11），则余数需要加 $|Y|$，该操作称为恢复余数。

例：$X=-0.1010100000$，$Y=+0.11011$，求 $X\div Y$。

过程如下（已省略加减交替过程）。

得 $\text{余数}=1.11000\times 2^{-5}$（符号位与被除数一致）。

浮点数的运算

加减运算

1. 对阶：尾数右移阶码加。
2. 尾数求和/差。
3. 运算结果规格化、舍入。

例：$X=\frac{11}{16}\times 2^{-4}$，$Y=\frac{35}{64}\times 2^{-3}$，计算 $X\pm Y$。

$X=0.101100\times 2^{-4}$，$Y=0.100011\times 2^{-3}$

$[X]_\text{浮}=01100;0.101100$，$[Y]_\text{浮}=01101;0.100011$

对阶：$[X]'_\text{浮}=01101;0.010110$，$[Y]_\text{浮}=01101;0.100011$

尾数求和/差

• 求和
  $\begin{array}{ccc} &00.010110 \\ +&00.100011 \\ \hline &00.111001 \end{array}$
• 求差
  $\begin{array}{ccc} &00.010110 \\ -&11.011101 \\ \hline &11.110011 \end{array}$

规格化：

• $0.111001$ 已经是规格化尾数。$[X+Y]_\text{浮}=01101;0.111001$。
• $1.110011$ 需要左归，左移 2 位，阶码减 2。$[X-Y]_\text{浮}=01011;1.001100$。

无需进行舍入处理。

乘除运算

1. 阶码加/减。
2. 尾数乘/除。
3. 运算结果规格化、舍入。