《逻辑与计算机系统设计》常用知识点#
逻辑函数#
逻辑函数的表达形式#
逻辑函数化简#
数据表示#
BCD编码#
8421码#
有权码，从高到低依次表示8、4、2、1
不允许出现：1010~1111
2421码#
有权码，从高到低依次表示2、4、2、1
无单值性：0101、1011都表示5
不允许出现：0101~1010
自补性：对9自补，按位取反后可得对9的补数的2421码
余3码#
8421码基础上，每位十进制数字加上0011得到。
不允许出现：00000010、11011111
自补性：按位取反后得到9的补数
可靠性编码#
格雷码#
二进制码为：
对应格雷码为：
两个相邻数仅有一位不同
汉明距离#
最小汉明距离：任意两个二进制合法编码之间不同位数的最小值
最小汉明距离越大，纠错能力越强，存储开销和计算开销越大
：检测到最多d个错误
：定位最多c个错误
奇偶校验#
偶校验：若前面出现1次数为偶数则校验位为0，校验通过
无错结论不可信，不能检测出同时发生偶数个错误
不能纠错
行列奇偶校验#
新增一行，对所有行的每一列进行奇偶校验，可定位1位错误，并纠正
海明校验#
需要校验位位数： ，因为校验位也可能出错
第i个校验位位置在汉明码的第位
校验位计算方法#
海明码通常采用偶校验。校验位放在编号为 2 的幂次的位置上，即第 1、2、4、8、16……位，其余位置放有效数据位。
以 7 位数据 b1 b2 b3 b4 b5 b6 b7 为例，需要 4 位校验位，位置安排为：
位置： 1 2 3 4 5 6 7 8 9 10 11
内容： P1 P2 b1 P3 b2 b3 b4 P4 b5 b6 b7每个校验位负责一组位置。判断规则是：如果某个位置编号的二进制表示中包含某个校验位对应的权值，那么该位置就由这个校验位负责。
采用偶校验时，各校验位计算公式为：
P1 = b1 ⊕ b2 ⊕ b4 ⊕ b5 ⊕ b7
P2 = b1 ⊕ b3 ⊕ b4 ⊕ b6 ⊕ b7
P3 = b2 ⊕ b3 ⊕ b4
P4 = b5 ⊕ b6 ⊕ b7其中 ⊕ 表示异或运算。异或结果为 0 表示参与运算的比特中 1 的个数为偶数，异或结果为 1 表示参与运算的比特中 1 的个数为奇数。
因此，计算校验位的本质就是：让每个校验位所负责的那一组比特满足偶校验，即该组中 1 的总个数为偶数。
校验方法#
接收端收到海明码后，重新对各组进行偶校验，得到错误定位字。
仍以 7 位数据、4 位校验位为例，设收到的数据位为：
P1 P2 b1 P3 b2 b3 b4 P4 b5 b6 b7则重新计算：
G1 = P1 ⊕ b1 ⊕ b2 ⊕ b4 ⊕ b5 ⊕ b7
G2 = P2 ⊕ b1 ⊕ b3 ⊕ b4 ⊕ b6 ⊕ b7
G3 = P3 ⊕ b2 ⊕ b3 ⊕ b4
G4 = P4 ⊕ b5 ⊕ b6 ⊕ b7将结果组合成错误定位字：
G4G3G2G1如果错误定位字为：
0000表示没有检测到错误。
如果错误定位字不为 0000，则它的二进制值就是出错位的位置编号。例如：
G4G3G2G1 = 01100110 的十进制值为 6，表示第 6 位出错。此时将第 6 位取反，即 0 变 1，或 1 变 0，即可完成纠错。
CRC 校验#
有效信息k位，校验信息r位，
适合检测连续多位出错
生成多项式#
CRC 校验需要选定一个生成多项式 G(x)，它是计算校验信息时使用的“除数”。如果校验信息为 r 位，则生成多项式对应的二进制串长度为 r + 1 位。
生成多项式通常要求最高位和最低位都为 1。例如，当 r = 3 时，可以选用 4 位生成多项式：
G(x) = 1011校验位计算方法#
设有效信息为 K，长度为 k 位；校验信息为 R，长度为 r 位。
计算 CRC 校验位的步骤如下：
1. 在有效信息 K 后面补 r 个 0，相当于将 K 逻辑左移 r 位。
2. 用补 0 后的数据除以生成多项式 G(x)，进行模 2 除法。
3. 得到 r 位余数 R。
4. 将余数 R 拼接到原始有效信息 K 后面，得到 CRC 编码结果。即：
发送码字 = K + R其中，模 2 除法中的减法不需要借位，本质上就是异或运算。
例如：
1 ⊕ 1 = 0
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1因此，CRC 校验位就是“补 0 后的数据”除以生成多项式后得到的余数。
校验方法#
接收端收到完整码字后，使用同一个生成多项式 G(x) 再做一次模 2 除法。
如果余数为全 0，说明没有检测到错误：
余数 = 000...0如果余数不为 0，说明数据在传输或存储过程中发生了错误：
余数 ≠ 000...0因此，CRC 校验的判断规则为：
收到的码字 ÷ G(x) 的余数为 0：未检测到错误
收到的码字 ÷ G(x) 的余数不为 0：检测到错误CRC 校验一般用于检错，尤其适合检测突发错误；它通常只能判断“是否出错”，不能像海明校验那样直接定位并纠正某一位错误。讲义中 CRC 的流程也是先根据 k+r ≤ 2^r-1 确定 r，再选 r+1 位生成多项式，并将待校验信息左移 r 位后进行模 2 除法。
模 2 除法#
模 2 除法是 CRC 校验中计算余数的方法，也可以理解为“二进制多项式除法”。它的除法形式与普通竖式除法相似，但运算规则不同：模 2 除法中的减法不需要借位，本质上就是异或运算。
其基本运算规则为：
0 ⊕ 0 = 0
1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1也就是说，在模 2 除法中：
相同为 0，不同为 1进行 CRC 计算时，通常不关心商是多少，只关心最后得到的余数。设生成多项式为 G(x)，其对应二进制串长度为 r + 1 位，则模 2 除法最终得到的余数长度为 r 位，这个余数就是 CRC 校验信息。
模 2 除法的具体过程如下：
1. 从被除数左侧开始，取出与除数等长的一段。
2. 如果当前段最高位为 1，就与除数进行异或。
3. 如果当前段最高位为 0，则不能除，直接继续向后取下一位。
4. 重复上述过程，直到所有位都处理完。
5. 最后剩下的 r 位就是余数。例如，设有效信息为：
K = 1011生成多项式为：
G(x) = 1101生成多项式长度为 4 位，所以 r = 3。先在有效信息后补 3 个 0：
1011 → 1011000然后用 1011000 对 1101 做模 2 除法：
1011 ⊕ 1101 = 0110去掉前导 0，并带下下一位，得到：
1100继续异或：
1100 ⊕ 1101 = 0001继续带下后面的位，最后得到余数：
100因此，CRC 校验位为：
R = 100最终发送的 CRC 编码结果为：
1011 100即：
1011100接收端校验时，将收到的完整码字再次除以同一个生成多项式 G(x)。如果余数为全 0，说明没有检测到错误；如果余数不为 0，说明数据出错。
因此，模 2 除法的关键是：用异或代替普通减法，不考虑借位和进位，最后得到的余数就是 CRC 校验信息。
纠错方法#
CRC 通常作为检错码使用，但在特定条件下也可以实现单比特纠错。其前提是：假设传输过程中有且只有 1 位发生错误，并且已经知道生成多项式 G(x) 对应的“余数—出错位”关系。
接收端收到完整码字后，使用同一个生成多项式 G(x) 进行模 2 除法，得到校验余数。
如果余数为全 0，表示没有检测到错误：
收到码字 ÷ G(x) 的余数 = 000...0如果余数不为 0，表示检测到错误。在有且只有 1 位出错的前提下，可以根据余数查表，确定出错的位置。
余数 ≠ 000...0 → 检测到错误
余数对应某一位 → 定位该位出错定位出错位后，将该位取反即可完成纠错：
0 变 1
1 变 0例如，如果根据余数查表得到出错位为第 6 位，则将第 6 位取反，就可以恢复原码字。
需要注意的是，CRC 的纠错能力依赖于前提条件。若有 2 位同时发生错误，CRC 可以判断出数据出错，但通常不能正确定位错误位置，因此不能可靠纠错。若有 3 位或更多位同时出错，CRC 甚至不能保证一定检测出来，可能出现余数为 0、误认为无错的情况。
因此可以总结为：
1 位出错：在已知余数—出错位对应关系时，可以定位并纠错。
2 位出错：可以检测到错误，但不能可靠定位，通常不能纠错。
3 位及以上出错：不能保证全部检测出来，也不能保证纠错。所以，CRC 的主要功能仍然是检错；讲义中提到的纠错，是在“有且只有 1 位出错”的特殊假设下，通过余数定位错误位并翻转该位来实现的。
IEEE754#
IEEE 754 的基本作用#
IEEE 754 是计算机中表示和处理浮点数的常用标准。它主要解决的问题是：如何用固定长度的二进制位串表示非常大或非常小的实数。
定点数的小数点位置固定，表示范围有限；而浮点数的小数点位置可以“浮动”，因此可以表示更大的数值范围。例如科学记数法可以把十进制数写成：
± 尾数 × 10^指数二进制浮点数也采用类似思想，把一个数表示成：
± 尾数 × 2^指数因此，IEEE 754 浮点数本质上由三部分组成：
符号位 S
阶码 E
尾数 M其中，符号位决定正负，阶码决定小数点移动的位置，尾数决定有效数字。
IEEE 754 单精度浮点数格式#
IEEE 754 单精度浮点数共有 32 位，格式如下：
S | EEEEEEEE | MMMMMMMMMMMMMMMMMMMMMMM
1位符号位 | 8位阶码 | 23位尾数也可以写成：
第31位：符号位 S
第30~23位：阶码 E
第22~0位：尾数 M其中：
S = 0 表示正数
S = 1 表示负数阶码 E 不是直接存储真实指数，而是采用移码表示。对于单精度浮点数：
E = e + 127
e = E - 127其中 e 是真实指数，127 是偏移量，也叫 bias。
规格化数的真值公式为：
N = (-1)^S × 1.M × 2^(E - 127)这里的 1.M 表示尾数前面默认有一个隐藏的 1。这个最高有效位称为隐藏位，不需要实际存储，因此可以多保存 1 位有效精度。
IEEE 754 双精度浮点数格式#
IEEE 754 双精度浮点数共有 64 位，格式如下：
S | EEEEEEEEEEE | MMMMM...MMMMM
1位符号位 | 11位阶码 | 52位尾数也就是：
第63位：符号位 S
第62~52位：阶码 E
第51~0位：尾数 M双精度浮点数的阶码偏移量为：
bias = 1023因此规格化数的真值公式为：
N = (-1)^S × 1.M × 2^(E - 1023)与单精度相比，双精度的阶码位数更多，能表示更大的指数范围；尾数位数更多，能保存更高的有效精度。
规格化数#
当阶码字段满足：
1 ≤ E ≤ 254时，单精度浮点数表示规格化数。
规格化数的形式为：
N = (-1)^S × 1.M × 2^(E - 127)其中 1.M 的整数部分 1 不存储，而是默认存在。
例如，一个正数可以规格化为：
101.101₂ = 1.01101₂ × 2^2此时：
S = 0
e = 2
E = 2 + 127 = 129 = 10000001₂
M = 01101000000000000000000规格化的好处是可以让浮点数表示唯一化，同时充分利用尾数字段保存有效数字。
非规格化数#
当阶码字段为：
E = 0且尾数字段为：
M ≠ 0时，IEEE 754 表示非规格化数。
非规格化数的形式不是：
1.M × 2^e而是：
0.M × 2^(-126)也就是说，非规格化数没有隐藏的最高位 1。
非规格化数的主要作用是表示非常接近 0 的数，使浮点数从最小规格化数逐渐过渡到 0，而不是突然断掉。这种设计可以减小下溢附近的误差。
零的表示#
当阶码字段为：
E = 0且尾数字段为：
M = 0时，IEEE 754 表示 0。
由于符号位仍然存在，所以 IEEE 754 中有两种 0：
S = 0, E = 0, M = 0 表示 +0
S = 1, E = 0, M = 0 表示 -0也就是说：
+0 和 -0 数值相等，但编码不同在一般数值比较中，+0 和 -0 通常被认为相等。
无穷大的表示#
当阶码字段为：
E = 255且尾数字段为：
M = 0时，IEEE 754 表示无穷大。
符号位决定是正无穷还是负无穷：
S = 0 表示 +∞
S = 1 表示 -∞例如：
正数 / +0 = +∞
负数 / +0 = -∞无穷大通常用于表示上溢结果，或者某些除零运算的结果。
NaN 的表示#
当阶码字段为：
E = 255且尾数字段为：
M ≠ 0时，IEEE 754 表示 NaN。
NaN 是 Not a Number 的缩写，表示“不是一个有效数值”。
常见产生 NaN 的运算包括：
0 / 0
∞ / ∞
0 × ∞
∞ - ∞
sqrt(负数)NaN 的意义是：该运算没有确定的实数结果，因此不能用普通浮点数表示。
为什么阶码要用移码表示#
IEEE 754 的阶码采用移码表示，而不是直接用补码表示指数。
对于单精度浮点数：
E = e + 127对于双精度浮点数：
E = e + 1023这样做有两个重要作用。
第一，阶码字段可以按无符号数存储，便于硬件比较大小。
第二，可以把阶码全 0 和全 1 预留出来表示特殊值：
E = 全0：表示 0 或非规格化数
E = 全1：表示 ∞ 或 NaN因此，规格化数不能使用全 0 或全 1 的阶码。
IEEE 754 单精度数值分类总结#
单精度浮点数可以根据 E 和 M 分成以下几类：
E = 0, M = 0：
表示 +0 或 -0
E = 0, M ≠ 0：
表示非规格化数
1 ≤ E ≤ 254：
表示规格化数
E = 255, M = 0：
表示 +∞ 或 -∞
E = 255, M ≠ 0：
表示 NaN所以分析 IEEE 754 位串时，不应直接套规格化数公式，而应先判断阶码 E 是否为全 0 或全 1。
IEEE 754 编码的一般步骤#
若要把一个十进制真值转换为 IEEE 754 单精度浮点数，可以按以下步骤进行：
1. 判断正负，确定符号位 S。
2. 将绝对值转换为二进制。
3. 将二进制数规格化为 1.M × 2^e。
4. 计算阶码 E = e + 127。
5. 取规格化后小数点后面的部分作为尾数 M。
6. 尾数不足 23 位补 0，超过 23 位则按规则舍入。
7. 拼接 S | E | M，得到 32 位浮点数编码。例如：
103.5₁₀ = 1100111.1₂规格化为：
1100111.1₂ = 1.1001111₂ × 2^6如果是 -103.5，则：
S = 1
e = 6
E = 6 + 127 = 133 = 10000101₂
M = 10011110000000000000000最终拼接为：
1 10000101 10011110000000000000000即：
11000010110011110000000000000000转成十六进制为：
C2CF0000HIEEE 754 解码的一般步骤#
若要把 IEEE 754 单精度浮点数转换为真值，可以按以下步骤进行：
1. 将 32 位二进制数拆成 S、E、M。
2. 判断 E 和 M 是否表示特殊值。
3. 若是规格化数，计算 e = E - 127。
4. 写出 1.M。
5. 根据公式 N = (-1)^S × 1.M × 2^e 计算真值。例如：
C2CF0000H写成二进制：
11000010110011110000000000000000拆分：
S = 1
E = 10000101₂ = 133
M = 10011110000000000000000所以：
e = 133 - 127 = 6真值为：
N = -1.1001111₂ × 2^6
= -1100111.1₂
= -103.5₁₀IEEE 754 的精度问题#
IEEE 754 浮点数虽然能表示很大的范围，但不能精确表示所有实数。
原因是浮点数的位宽有限，尾数字段只能保存有限位二进制有效数字。因此，很多十进制小数转换成二进制后会变成无限循环小数，只能被近似存储。
例如：
0.1
1.1
3.3这些十进制小数通常不能被二进制浮点数精确表示。
因此，浮点数运算可能出现如下现象：
3.3 / 1.1数学上结果是：
3.0但计算机中实际参与运算的 3.3 和 1.1 可能已经是近似值，所以结果可能不严格等于 3.0。
因此在程序中通常不应直接判断：
a == 3.0而应采用误差范围判断：
|a - 3.0| < εIEEE 754 的上溢和下溢#
IEEE 754 的指数范围有限，因此浮点运算可能发生上溢或下溢。
当运算结果的绝对值太大，超过浮点数能够表示的最大范围时，发生上溢：
overflow上溢结果通常变为：
+∞ 或 -∞当运算结果的绝对值太小，接近 0，小到无法用规格化数表示时，发生下溢：
underflow下溢结果可能变为：
非规格化数 或 +0 / -0可以简单理解为：
上溢：数太大，趋向无穷
下溢：数太小，趋向 0IEEE 754 异常运算结果#
IEEE 754 对一些特殊运算结果有规定。
非零数除以 0：
正数 / 0 = +∞
负数 / 0 = -∞无定义形式通常得到 NaN：
0 / 0 = NaN
∞ / ∞ = NaN
0 × ∞ = NaN
∞ - ∞ = NaN如果运算中已经有 NaN 参与，结果通常仍然是 NaN。
因此，分析浮点异常运算时，可以先判断是否涉及：
0
∞
NaN这三类特殊值。
IEEE 754 做题总结#
分析 IEEE 754 浮点数时，可以按以下模板：
1. 先拆位段：
S | E | M
2. 再判断类型：
E = 0, M = 0 → ±0
E = 0, M ≠ 0 → 非规格化数
1 ≤ E ≤ 254 → 规格化数
E = 255, M = 0 → ±∞
E = 255, M ≠ 0 → NaN
3. 若是规格化数：
e = E - 127
N = (-1)^S × 1.M × 2^e
4. 若是编码题：
先转二进制，再规格化，再求 E 和 M，最后拼接。核心记忆：
IEEE 754 = 符号位 S + 阶码 E + 尾数 M
单精度：1 + 8 + 23
双精度：1 + 11 + 52
规格化数：(-1)^S × 1.M × 2^(E - bias)
E 全 0：0 或非规格化数
E 全 1：∞ 或 NaNIEEE754与定点数的转换#
定点数与 IEEE 754 浮点数的基本区别#
定点数的特点是“小数点位置固定”。同一个二进制位串，如果小数点位置不同，表示的数值也不同。因此解释定点数时，必须先知道它的格式，例如有多少位整数部分、多少位小数部分，以及是否采用补码表示。
若一个定点数采用补码表示，并且有 F 位小数位，则可以先把整个二进制位串看作一个补码整数，再除以 2^F 得到真值：
真值 = 补码整数值 / 2^FIEEE 754 浮点数的小数点位置不固定，而是通过阶码控制数值范围。单精度 IEEE 754 浮点数共有 32 位，格式为：
S | EEEEEEEE | MMMMMMMMMMMMMMMMMMMMMMM
1位符号位 | 8位阶码 | 23位尾数规格化数的真值公式为：
其中，S 是符号位，E 是移码表示的阶码，M 是尾数字段。规格化数中的最高位 1 是隐藏位，不直接存储。
定点数转换为 IEEE 754 单精度浮点数#
定点数转换为 IEEE 754 的核心思路是：先求出定点数的真值，再按照 IEEE 754 的 S、E、M 三部分重新编码。
步骤如下：
1. 根据定点数格式求出真值。
2. 判断正负，确定符号位 S。
3. 将真值的绝对值转换为二进制。
4. 将二进制数规格化为 1.xxxxx × 2^e。
5. 计算阶码 E = e + 127。
6. 取规格化后小数点后面的部分作为尾数 M。
7. 尾数不足 23 位补 0，超过 23 位则需要舍入。
8. 按 S | E | M 拼接成 32 位 IEEE 754 单精度浮点数。例如，若真值为 -103.5，则：
103.5₁₀ = 1100111.1₂规格化为：
1100111.1₂ = 1.1001111₂ × 2^6所以：
S = 1
e = 6
E = 6 + 127 = 133 = 10000101₂
M = 10011110000000000000000拼接得到：
1 10000101 10011110000000000000000即：
11000010110011110000000000000000按 4 位分组转为十六进制：
1100 0010 1100 1111 0000 0000 0000 0000
C 2 C F 0 0 0 0所以：
(-103.5)₁₀ = C2CF0000HIEEE 754 单精度浮点数转换为定点数#
IEEE 754 转定点数的核心思路是：先拆出 S、E、M，求出浮点数真值，再根据目标定点格式重新编码。
步骤如下：
1. 将 32 位 IEEE 754 数拆成 S、E、M 三部分。
2. 判断 E 是否为特殊值。
3. 若 1 ≤ E ≤ 254，则说明它是规格化数。
4. 计算真实指数 e = E - 127。
5. 根据公式 N = (-1)^S × 1.M × 2^e 求出真值。
6. 若要转成定点数，设目标格式有 F 位小数位，则计算：
定点整数值 = N × 2^F
7. 再将该整数值按照目标定点格式存储，例如补码或无符号数。例如，IEEE 754 单精度数：
C2CF0000H先写成二进制：
11000010110011110000000000000000拆分：
S = 1
E = 10000101₂ = 133
M = 10011110000000000000000计算指数：
e = E - 127 = 133 - 127 = 6因此真值为：
N = -1.1001111₂ × 2^6
= -1100111.1₂
= -103.5₁₀如果目标定点格式是 Q8.8，即有 8 位小数位，则：
定点整数值 = -103.5 × 2^8 = -26496之后再把 -26496 按目标位宽写成补码即可。需要注意，若目标定点格式表示范围不足，则会发生溢出。
IEEE 754 特殊值的判断#
IEEE 754 单精度数中，最重要的是观察阶码 E 和尾数 M。
1. E = 0，M = 0：
表示 +0 或 -0。
2. E = 0，M ≠ 0：
表示非规格化数。
3. 1 ≤ E ≤ 254：
表示规格化数，真值为：
N = (-1)^S × 1.M × 2^(E - 127)
4. E = 255，M = 0：
表示 +∞ 或 -∞。
5. E = 255，M ≠ 0：
表示 NaN，即 Not a Number。因此，分析 IEEE 754 位串时，不能一上来就套规格化数公式。应当先判断 E 是否为全 0 或全 1。
浮点数异常运算结果分析#
IEEE 754 中有一些特殊运算结果，主要涉及 0、∞ 和 NaN。
非零数除以 0 时，结果通常为无穷大：
正数 / +0 = +∞
负数 / +0 = -∞例如：
1.0 / 0.0 = +∞
-1.0 / 0.0 = -∞无数学意义或无法确定唯一结果的运算，通常得到 NaN：
0 / 0 = NaN
∞ / ∞ = NaN
0 × ∞ = NaN
∞ - ∞ = NaN
sqrt(负数) = NaN如果运算结果太大，超过浮点数能够表示的范围，则可能发生上溢，结果变为：
+∞ 或 -∞如果运算结果太小，接近 0，可能发生下溢，结果变为：
非规格化数 或 +0 / -0因此，分析异常运算时可以按以下顺序判断：
1. 是否有 NaN 参与。
如果有 NaN 参与，结果一般仍为 NaN。
2. 是否出现无定义形式。
例如 0/0、∞/∞、0×∞、∞-∞，结果为 NaN。
3. 是否是非零数除以 0。
若是，则结果为 +∞ 或 -∞，符号由运算符号决定。
4. 是否发生上溢。
若结果超过可表示范围，则得到 +∞ 或 -∞。
5. 是否发生下溢。
若结果太接近 0，则得到非规格化数或 0。为什么浮点数运算可能不精确#
很多十进制小数在二进制中不能被有限位精确表示。例如：
3.3
1.1
0.1这些数转换为二进制后通常是无限循环小数，而 IEEE 754 的尾数字段长度有限，因此只能存储近似值。
因此，类似下面的运算：
3.3 / 1.1数学结果应为：
3.0但在计算机中，3.3 和 1.1 可能都不是精确值，而是近似值，所以实际计算结果可能不是严格等于 3.0。
所以程序中不应直接用：
a == 3.0来判断浮点计算结果是否等于 3，而应使用误差范围判断：
|a - 3.0| < ε做题总结模板#
遇到定点数与 IEEE 754 互换题，可以按如下模板书写：
若由定点数转 IEEE 754：
1. 根据定点格式求出真值。
2. 判断符号，得到 S。
3. 将绝对值转为二进制。
4. 规格化为 1.M × 2^e。
5. 计算 E = e + 127。
6. 得到尾数 M。
7. 拼接 S | E | M。
若由 IEEE 754 转定点数：
1. 拆分 S、E、M。
2. 先判断是否为特殊值。
3. 若为规格化数，计算 e = E - 127。
4. 根据 N = (-1)^S × 1.M × 2^e 求真值。
5. 根据目标定点格式重新编码。遇到异常运算结果分析题，可以按如下模板书写：
1. NaN 参与运算，结果通常为 NaN。
2. 0/0、∞/∞、0×∞、∞-∞ 等无定义形式，结果为 NaN。
3. 非零数除以 0，结果为 +∞ 或 -∞。
4. 结果过大，发生上溢，可能得到 +∞ 或 -∞。
5. 结果过小，发生下溢，可能得到非规格化数或 0。核心记忆：
定点数看小数点位置；
IEEE 754 看 S、E、M；
异常运算重点看 0、∞、NaN。组合逻辑电路设计#
险象#
竞争与险象#
竞争：同一个输入变量经过不同路径到达同一逻辑门，因路径延迟不同，到达时间不同。
竞争是原因；
险象是结果。有竞争不一定有险象，但险象通常由竞争引起。
0 型险象#
0 型险象：输出本应保持为 1，却短暂变为 0。
波形：1 → 0 → 1
典型形式：F = A + A' = 1记忆：
正常为 1，中间掉到 0 → 0 型险象1 型险象#
1 型险象：输出本应保持为 0，却短暂变为 1。
波形：0 → 1 → 0
典型形式：F = A · A' = 0记忆：
正常为 0，中间冒出 1 → 1 型险象险象判断条件#
![[4 逻辑与计算机系统设计基础-第四章 组合逻辑电路设计(一) 4.1-4.4-cnwang-rev.pdf#page=35]]
判断是否可能有险象，看三点：
1. 某变量同时以原变量和反变量出现，如 A 和 A'。
2. 固定其他变量后，表达式可化为：
X + X' 或 X · X'
3. 输入到同一门的两条路径传播延迟不同。对应关系：
X + X' → 可能产生 0 型险象
X · X' → 可能产生 1 型险象为什么只看一个变量变化#
分析险象时，通常只改变一个变量，固定其他变量。
固定 n-1 个变量；
只看 1 个变量变化。因为多个变量同时变化会使分析复杂，也可能抵消某个变量的险象。
险象消除方法#
常用方法：
1. 增加冗余项
2. 卡诺图中补圈，使相邻项被同一个圈覆盖
3. 平衡路径延迟
4. 加滤波或惯性延时，滤掉短脉冲同步时序电路设计#
Moore型&Mealy型
运算方法与运算器#
运算溢出#
![[9 逻辑与计算机系统设计基础 第五章 运算方法与算术逻辑单元(一）-cnwang-rev.pdf#page=19]]
溢出的基本概念#
在定点补码运算中，计算机只能用固定的位数表示数值。如果真实运算结果超出了该位数补码所能表示的范围，就会发生溢出。
设一个补码数共有 n+1 位，其中最高位为符号位，后面 n 位为数值位，则它能表示的范围是：
-2^n ~ 2^n - 1如果运算结果小于 -2^n，称为负溢出；如果运算结果大于 2^n - 1，称为正溢出。
溢出只针对“按有符号补码解释”的结果而言。补码加法器本身只是做二进制加法，硬件得到的结果仍然是一个固定位宽的二进制串；但这个二进制串可能已经不能表示真实数学结果。
补码加法与溢出的关系#
补码加法的基本公式是：
[X + Y]补 = [X]补 + [Y]补也就是说，在补码表示下，两个有符号数相加，可以直接把它们的补码送入加法器相加。
但是，加法器的位数是固定的。如果最高位产生了进位，超出固定位宽的进位会被舍去。需要注意：
最高位进位被舍去，不等于一定发生溢出；
没有最高位进位，也不等于一定没有溢出。因此，不能只看最后的进位输出 Carryout 来判断补码有符号数是否溢出。
方法一：根据操作数符号和结果符号判断溢出#
补码加法中，溢出只可能发生在两个同号数相加时。
正数 + 正数：结果应该为正
负数 + 负数：结果应该为负
正数 + 负数：不会溢出
负数 + 正数：不会溢出因此，方法一的判断规则是：
1. 先判断两个操作数的符号是否相同。
2. 如果两个操作数异号，则不会发生溢出。
3. 如果两个操作数同号，再看结果符号。
4. 若结果符号与操作数符号不同，则发生溢出。
5. 若结果符号与操作数符号相同，则没有溢出。可以写成：
同号相加，结果变号 → 溢出
同号相加，结果不变号 → 不溢出
异号相加 → 不溢出例如：
负数 + 负数 = 正数两个负数相加，真实结果应当更小，仍然应该是负数；如果机器结果变成正数，就说明发生了负溢出。
又如：
正数 + 正数 = 负数两个正数相加，真实结果应当仍为正数；如果机器结果变成负数，就说明发生了正溢出。
方法一的逻辑表达式#
设两个操作数的符号位分别为：
X_s
Y_s结果的符号位为：
S_s则发生溢出的条件为：
X_s = Y_s 且 S_s ≠ X_s也可以分成正溢出和负溢出：
正溢出：X_s = 0，Y_s = 0，S_s = 1
负溢出：X_s = 1，Y_s = 1，S_s = 0所以：
V = (~X_s & ~Y_s & S_s) | (X_s & Y_s & ~S_s)其中 V 是溢出标志位：
V = 1 表示溢出
V = 0 表示没有溢出方法二：根据符号位进位判断溢出#
方法二从加法器的进位角度判断溢出。
设：
Cn：最高数据位向符号位产生的进位
Cf：符号位向更高位产生的进位则溢出判断规则为：
如果 Cn = Cf，则没有溢出；
如果 Cn ≠ Cf，则发生溢出。也就是：
V = Cn ⊕ Cf其中 ⊕ 表示异或。
方法二的理解#
最高数据位的进位 Cn 表示数值部分对符号位产生了影响；符号位的进位 Cf 表示符号位运算后又向更高位产生了影响。
如果这两个进位相同，说明符号位的变化是正常的，结果仍在补码可表示范围内。
如果这两个进位不同，说明符号位被异常改变，结果超出了补码表示范围，因此发生溢出。
可以记成：
进位进符号位 和 进位出符号位 不同 → 溢出
进位进符号位 和 进位出符号位 相同 → 不溢出这种方法适合硬件实现，因为只需要对两个进位信号做异或运算即可。
方法三：使用变型补码双符号位判断溢出#
方法三使用变型补码，也就是使用两个符号位。
设双符号位为：
f1 f2其中 f1 是最高符号位，f2 是第二符号位。
判断规则为：
f1f2 = 00：结果为正数，没有溢出
f1f2 = 11：结果为负数，没有溢出
f1f2 = 01：正溢出
f1f2 = 10：负溢出因此，双符号位法的溢出标志为：
V = f1 ⊕ f2如果两个符号位相同，说明没有溢出；如果两个符号位不同，说明发生溢出。
双符号位法的理解#
双符号位可以理解为给符号位多留了一位“观察空间”。
正常情况下，一个正数的符号位应为：
00一个负数的符号位应为：
11如果两个正数相加后结果超过最大正数，第二符号位会表现出异常，出现：
01这表示正溢出。
如果两个负数相加后结果小于最小负数，会出现：
10这表示负溢出。
所以可以记成：
00、11：正常
01、10：溢出加法溢出判断总结#
补码加法的溢出判断可以总结为三种方法。
第一种是符号法：
同号相加，结果变号，则溢出。第二种是进位法：
V = Cn ⊕ Cf其中：
Cn：进入符号位的进位
Cf：符号位产生的进位输出第三种是双符号位法：
V = f1 ⊕ f2其中：
f1f2 = 00：无溢出，正数
f1f2 = 11：无溢出，负数
f1f2 = 01：正溢出
f1f2 = 10：负溢出考试中最常用的是符号法，硬件实现中常用进位异或法。
减法溢出判断#
补码减法通常转化为加法实现：
X - Y = X + (-Y)因此：
[X - Y]补 = [X]补 + [-Y]补所以判断减法是否溢出时，不要直接把它当成普通减法看，而应先改写成加法：
X - Y → X + (-Y)然后按照补码加法溢出规则判断。
也就是说，判断 X - Y 是否溢出时，应该比较：
X 的符号
-Y 的符号
结果的符号规则仍然是：
X 与 -Y 同号，而结果变号 → 溢出
X 与 -Y 异号 → 不溢出减法中的常见溢出情况#
减法中容易发生溢出的情况包括：
正数 - 负数 = 正数 + 正数如果结果超过最大正数，则发生正溢出。
例如：
较大正数 - 较大负数真实结果会非常大，可能超过补码最大正数。
另一种情况是：
负数 - 正数 = 负数 + 负数如果结果小于最小负数，则发生负溢出。
例如：
较小负数 - 较大正数真实结果会非常小，可能超过补码最小负数的下界。
判断溢出时的注意点#
判断补码有符号运算溢出时，不能只看最高位是否产生进位。
例如，两个负数相加时，最高位可能产生进位并被舍去，但这不一定表示溢出；两个正数相加时，即使没有最终进位，也可能因为结果变成负数而溢出。
因此，判断补码溢出时应优先使用以下规则：
1. 有符号数看符号变化。
2. 加法只在同号相加时可能溢出。
3. 减法先转化为加法，再按加法规则判断。
4. 硬件中可用 V = Cn ⊕ Cf 判断。
5. 双符号位中可用 V = f1 ⊕ f2 判断。溢出判断做题模板#
遇到补码加法溢出判断题，可以这样写：
1. 写出两个操作数的补码。
2. 进行补码加法。
3. 观察两个操作数符号是否相同。
4. 若两个操作数异号，则不溢出。
5. 若两个操作数同号，再观察结果符号。
6. 若结果符号与操作数符号不同，则溢出。
7. 若结果符号与操作数符号相同，则不溢出。遇到补码减法溢出判断题，可以这样写：
1. 将 X - Y 改写为 X + (-Y)。
2. 求 [-Y]补。
3. 进行补码加法 [X]补 + [-Y]补。
4. 比较 X、-Y 和结果的符号。
5. 若 X 与 -Y 同号而结果变号，则溢出。
6. 否则不溢出。如果题目要求从硬件信号判断，可以写：
V = Cn ⊕ Cf如果题目使用双符号位，可以写：
V = f1 ⊕ f2核心记忆：
同号相加才可能溢出；
结果变号就是溢出；
进位判断看进入符号位和离开符号位是否不同；
双符号位判断看两个符号位是否不同。定点乘除法运算#
原码一位乘法#
原码一位乘法采用“符号单独处理，数值部分相乘”的方法。
设：
则结果符号位为：
数值部分只计算：
核心操作是：
每轮只判断乘数的一位；
若当前乘数判断位为 1，则部分积加 |X|；
若当前乘数判断位为 0，则部分积加 0；
然后 {部分积Σ, 乘数Y} 整体逻辑右移一位。可写成：
其中 /2 表示逻辑右移一位。
做题步骤：
1. 写出 [X]原 和 [Y]原。
2. 符号位单独异或，得到结果符号 Pf。
3. 取 |X| 和 |Y| 做无符号一位乘法。
4. Σ 初值为 0，Y 存放乘数数值位。
5. 每轮看乘数最低位：
- 为 1：Σ = Σ + |X|
- 为 0：Σ = Σ + 0
6. 将 {Σ,Y} 整体逻辑右移一位。
7. 重复 n 次。
8. 最终结果为 Pf.{Σ,Y}。注意：
1. 原码乘法中符号位不参与数值运算。
2. 右移是逻辑右移，因为参与运算的是绝对值。
3. 若加法产生最高进位，该进位也要参与整体右移，不能丢。
4. 结果数值部分通常为 2n 位，最终结果为 1 位符号位 + 2n 位数值位。记忆：
原码一位乘法 = 符号异或 + 数值部分循环执行“判断乘数位、加或不加、整体右移”。补码 Booth 一位乘法#
补码 Booth 一位乘法直接对补码进行乘法，符号位参与运算。
它不再单独处理符号位，而是利用乘数相邻两位的变化决定加法操作。
需要增加一个附加位：
每轮检查：
其中 (Y_n) 是当前乘数最低位，(Y_{n+1}) 是附加位。
Booth 判断规则：
Yn Yn+1 = 00：Σ = Σ + 0
Yn Yn+1 = 11：Σ = Σ + 0
Yn Yn+1 = 01：Σ = Σ + [X]补
Yn Yn+1 = 10：Σ = Σ + [-X]补然后对：
整体算术右移一位。
做题步骤：
1. 写出 [X]补、[-X]补、[Y]补。
2. 设置 Σ = 0，附加位 Yn+1 = 0。
3. 检查 YnYn+1：
- 00 或 11：加 0
- 01：加 [X]补
- 10：加 [-X]补
4. 将 {Σ,Y,Yn+1} 整体算术右移一位。
5. 重复规定次数。
6. 最后 {Σ,Y} 即为补码乘积。注意：
1. Booth 乘法中符号位参与运算。
2. 右移必须是算术右移，负数左边补 1，正数左边补 0。
3. 通常使用双符号位，保证中间部分积的符号不会丢失。
4. 双符号位中：
00 表示正数正常；
11 表示负数正常；
01 或 10 表示溢出或中间位宽不够。Booth 算法的本质是识别乘数中连续的 1：
00：仍在 0 区间，不操作
11：仍在 1 区间，不操作
01：连续 1 的结束边界，加 X
10：连续 1 的开始边界，减 X记忆：
Booth 乘法 = 看乘数相邻两位；
01 加 X，10 减 X，00/11 不动；
然后整体算术右移。原码一位除法：恢复余数法与加减交替法#
原码除法采用“符号单独处理，数值部分相除”的方法。
设：
商的符号位为：
数值部分只计算：
原码恢复余数法#
恢复余数法的核心是：
每轮先减除数试商；
如果结果非负，说明够减，商上 1；
如果结果为负，说明不够减，商上 0，并加回除数恢复余数。每轮操作：
判断：
若 R ≥ 0：商上 1，余数保持不变。
若 R < 0：商上 0，执行 R = R + |Y| 恢复余数。做题步骤：
1. 写出 [X]原 和 [Y]原。
2. 商符号 Qf = Xf ⊕ Yf。
3. 只取 |X| 和 |Y| 做除法。
4. 通常先做一次 X - Y，得到 Q0，用于判断整数位或溢出。
5. 之后每轮：
- 余数左移一位；
- 减除数试商；
- 结果非负，商上 1；
- 结果为负，商上 0，并加除数恢复余数。
6. 做满 n 位小数商。
7. 最终商写成 Qf.Q1Q2...Qn。
8. 由于余数左移了 n 次，最后余数要乘 2^(-n)。注意：
1. Q0 通常是整数位或溢出判断位，不一定写入最终定点小数商。
2. 若要求 n 位小数商，通常需要 n+1 次试商，其中第 1 次用于得到 Q0。
3. 左移次数为 n 次，所以最终余数要右移 n 位，即乘 2^(-n)。记忆：
恢复余数法 = 先减除数试商；
够减商 1；
不够减商 0，并把减掉的除数加回来。原码加减交替法#
原码加减交替法也叫不恢复余数法。
它对恢复余数法进行改进： 如果试商失败，不立刻恢复余数，而是在下一轮通过相反操作修正。
基本规则：
若当前余数 R ≥ 0：
左移一位后减除数。
若当前余数 R < 0：
左移一位后加除数。也就是：
每次加减完成后判断结果：
若 R ≥ 0：商上 1。
若 R < 0：商上 0。做题步骤：
1. 商符号仍然为 Qf = Xf ⊕ Yf。
2. 数值部分使用 |X| 和 |Y|。
3. 先试 X - Y，得到 Q0。
4. 如果余数为正，下一轮左移后减除数。
5. 如果余数为负，下一轮左移后加除数。
6. 每轮根据新余数的符号上商：
- R ≥ 0：商上 1
- R < 0：商上 0
7. 若最后余数为负，通常需要加除数校正。
8. 最终余数仍需乘 2^(-n)。和恢复余数法的区别：
恢复余数法：
试商失败后立刻加除数恢复余数。
加减交替法：
试商失败后不恢复，下一轮改为加除数。记忆：
原码加减交替法 = 余数正，左移减除数；
余数负，左移加除数；
结果正商 1，结果负商 0。补码加减交替法除法#
补码加减交替法除法直接使用补码进行除法，符号位参与运算。
与原码除法不同，它不单独用异或求商符号，而是让被除数、除数、余数和商都按补码规则参与运算。
通常采用双符号位，以防止中间运算溢出。
设：
第一步根据被除数和除数的符号决定操作：
被除数与除数同号：
做 x - y，即加 [-y]补。
被除数与除数异号：
做 x + y，即加 [y]补。后续每轮根据余数和除数的符号决定操作。
判断规则：
余数与除数同号：
商上 1，余数左移一位，下一步减除数。
余数与除数异号：
商上 0，余数左移一位，下一步加除数。即：
做题步骤：
1. 写出 [x]补、[y]补、[-y]补。
2. 扩展成双符号位。
3. 判断 x 与 y 是否同号：
- 同号：先做 x - y
- 异号：先做 x + y
4. 得到余数 R 后，比较 R 与 y 的符号：
- 同号：商上 1，左移后减 y
- 异号：商上 0，左移后加 y
5. 重复直到得到规定商位。
6. 最后一步通常只移商，不再继续试商。
7. 根据情况校正商和余数。商的校正#
补码一位除法中，商可能需要校正。
常见规则：
能除尽时：
若除数 > 0，商不校正；
若除数 < 0，商加 2^(-n) 校正。
不能除尽时：
若商 > 0，商不校正；
若商 < 0，商加 2^(-n) 校正。其中 (n) 是保留的小数位数。
例如保留 4 位小数：
若未校正商为：
则校正后：
余数的校正#
补码不恢复余数法是先比较、后上商，因此最后余数也可能需要校正。
校正规则：
若商 > 0：
当余数与被除数异号时，余数加除数校正。
若商 < 0：
当余数与被除数同号时，余数减除数校正。也就是：
商正：余数和被除数异号 → 余数加除数。
商负：余数和被除数同号 → 余数减除数。注意：
1. 补码除法中符号位参与运算。
2. 判断上商不是看余数正负，而是看余数与除数是否同号。
3. 同号商 1，异号商 0。
4. 最终商可能需要校正，尤其是商为负且不能除尽时。
5. 最终余数也可能需要校正。记忆：
补码加减交替除法 =
符号位参与运算；
余数与除数同号商 1，下一步减除数；
余数与除数异号商 0，下一步加除数；
最后检查商和余数是否需要校正。存储系统#
![[22 逻辑与计算机系统设计基础-第九章 存储器层次结构（一）v5.3-cnwang-rev.pdf#page=112]]
字长扩展&字数扩展#
字长扩展：数据总线扩展#
字长扩展也叫位扩展，解决的是：单片存储器的数据位宽不够。
例如 CPU 一次要读写 8 bit，但单片芯片只有 256K × 1，每次只能输出 1 bit，就需要 8 片并联，组成：
8片 256K × 1 → 1组 256K × 8讲义中给出的规则是：若存储系统位宽为 N 位，使用位宽为 k 位的芯片，且 k < N，则需要：
芯片数 = N / k字长扩展的连接方法#
字长扩展时，所有芯片的地址线、控制线、片选信号共用，但每片芯片接到数据总线的不同位上。
例如用 8 片 256K × 1 组成 256K × 8：
所有芯片共用地址线 A17~A0
所有芯片共用读写控制线 WE / OE / CS
第0片接 D0
第1片接 D1
……
第7片接 D7也就是说，CPU 给出一个地址时，8 片芯片同时工作，每片贡献 1 bit，合起来得到 8 bit。
考试关键词：
字长扩展：各芯片并行工作字长扩展的特点#
字长扩展只扩大数据位宽，不扩大可寻址单元个数。
例如：
256K × 1 扩展成 256K × 8变化是：
字数：仍然是 256K
字长：从 1 bit 变成 8 bit所以地址线数量不变，数据线数量增加。
字数扩展：地址总线扩展#
字数扩展也叫容量扩展，解决的是：单片存储器的存储单元个数不够。
例如需要 256K × 8 的存储系统，但单片只有 64K × 8，则需要 4 片：
4片 64K × 8 → 1组 256K × 8讲义中给出的规则是：若存储系统容量为 M，使用容量为 l 的芯片，且 l < M，则需要：
芯片数 = M / l字数扩展的连接方法#
字数扩展时，每片芯片的数据位宽已经够用，所以每片芯片都接完整的数据总线。
低位地址线接入每片芯片内部，用来选择芯片内部的某个单元；高位地址线送入译码器，用来产生片选信号，决定当前访问哪一片。
例如用 4 片 64K × 8 组成 256K × 8：
64K = 2^16，所以每片内部需要 A15~A0
256K = 2^18，所以系统总共需要 A17~A0
高位 A17~A16 经过 2-4 译码器产生片选信号地址分配可以理解为：
A17 A16 = 00 → 选第0片
A17 A16 = 01 → 选第1片
A17 A16 = 10 → 选第2片
A17 A16 = 11 → 选第3片考试关键词：
字数扩展：同一时刻仅一片芯片工作字数扩展的特点#
字数扩展只扩大存储单元个数，不扩大每个单元的数据位宽。
例如：
64K × 8 扩展成 256K × 8变化是：
字数：从 64K 变成 256K
字长：仍然是 8 bit所以数据线数量不变，地址线数量增加。
综合扩展#
![[22 逻辑与计算机系统设计基础-第九章 存储器层次结构（一）v5.3-cnwang-rev.pdf#page=119]]
如果单片芯片的字数不够，同时字长也不够，就要同时进行字数扩展和字长扩展。
讲义中给出的总公式是：若目标存储系统为 M × N 位，使用芯片为 l × k 位，且 l < M, k < N，则需要：
总芯片数 = (M / l) × (N / k)理解方法：
先用 N/k 片做一组，完成字长扩展；
再用 M/l 组，完成字数扩展。例如用 64K × 1 芯片组成 256K × 8：
字长扩展：8片 64K×1 → 64K×8
字数扩展：4组 64K×8 → 256K×8
总芯片数 = 8 × 4 = 32片映射关系#
直接映射 Cache#
直接映射（direct-mapped cache）是最简单的 Cache 映射方式。它规定：每个主存块只能放到 Cache 中唯一确定的一个位置。
映射关系为：
Cache块号 i = 主存块号 j mod Cache块数也就是说，主存块的位置不是自由选择的，而是由地址直接决定。
主存地址通常分为：
Tag | Index | Offset其中：
Offset：块内偏移，选择块内的哪个字节/字
Index：Cache 行号/组号，确定访问哪一行
Tag：标记，判断该行中放的是不是目标主存块直接映射可以看作：
1路组相联因为每个组中只有 1 个 Cache 块。讲义中也明确说明：直接映射 = 1 路组相联，一个组里面只有一个 Cache 块。
查找过程：
1. 用 Index 找到唯一的 Cache 行
2. 判断该行 valid 位是否为 1
3. 比较该行 Tag 是否等于地址中的 Tag
4. 相等则命中，不相等则缺失特点：
优点：结构简单，查找速度快，只需要一路比较
缺点：冲突缺失多，多个主存块可能争抢同一个 Cache 行直接映射发生冲突时，被替换的位置是确定的，所以：
不需要替换算法N 路组相联 Cache#
N 路组相联（N-way set-associative cache）是直接映射和全相联之间的折中。
它把 Cache 分成若干个组，每组有 N 个 Cache 块，也叫 N 个 way。
N路组相联 = 每组有 N 个 Cache line主存块进入 Cache 时：
先由组索引确定它属于哪一组；
再在该组的 N 个位置中任选一个位置存放。所以它不是“任意放”，而是：
组固定，组内位置可选主存地址仍然分为：
Tag | Set Index | Offset其中：
Offset：块内偏移
Set Index：确定访问哪一组
Tag：和该组内所有路的 Tag 并行比较查找过程：
1. 用 Set Index 找到对应组
2. 读出该组内 N 个 Tag 和 Valid 位
3. N 路并行比较 Tag
4. 若某一路 valid=1 且 Tag 相等，则命中
5. 若都不相等，则缺失讲义中说，N 路组相联的标签阵列采用“普通 SRAM 单元阵列读出 + 并行比较”的机制；由于每组路数通常较少，如 2 路、4 路、8 路或 16 路，所以比较器数量仍可接受。
缺失时：
若该组还有空路，则放入空路；
若该组已满，则需要替换算法选择一个牺牲块。常见替换算法：
LRU：替换最近最少使用的块
FIFO：替换最早进入的块
Random：随机替换特点：
优点：比直接映射冲突少，命中率更高
缺点：硬件更复杂，需要多个比较器和多路选择器讲义中也指出，组相联 Cache 通常比直接映射慢一些，因为需要额外比较器和输出多路选择器。
全相联 Cache#
全相联（fully-associative cache）是最灵活的 Cache 映射方式。它规定：主存中的任意块可以放入 Cache 的任意位置。
可以理解为：
整个 Cache 只有一个组
该组中包含所有 Cache 块讲义中明确说明：全相联 Cache 只有一个组，主存的一个给定块可以放置在 Cache 中任意块的位置。
全相联地址通常只分为：
Tag | Offset它没有普通意义上的组索引 Index，因为只有一个组，不需要用 Index 选择组。
查找过程：
1. 将地址中的 Tag 与 Cache 中所有块的 Tag 并行比较
2. 若某一项 valid=1 且 Tag 相等，则命中
3. 若所有 Tag 都不相等，则缺失全相联的特点：
优点：映射最灵活，冲突缺失最少，命中率高
缺点：需要和所有 Cache 块的 Tag 并行比较，硬件开销最大讲义中指出：对于给定 Cache 容量，全相联 Cache 的冲突缺失率最少，但只适合非常小容量的 Cache。
缺失时：
如果 Cache 还有空块，放入任意空块；
如果 Cache 已满，必须使用替换算法选择牺牲块。全相联一定需要替换算法，因为目标块可以放在任意位置，满了以后必须决定淘汰谁。
替换策略#
先进先出替换（FIFO）#
维护：距离进来已经经过的时间
替换时，替换经过时间最长的内容
最不经常使用算法（LFU）#
维护：使用次数
替换时，替换使用次数最少的内容
最近最少使用（LRU）#
维护：距离进来已经经过的时间，命中后重置为0
替换时，替换经过时间最长的内容
写策略#
写穿#
写入 cache 块的数据同时写入主存，不需要脏位，但需要更多主存写入
写回#
需要脏位，脏块移除时才会写回主存
cache优化#
读优化#
时间局部性：利用驱逐算法将最不经常使用的数据逐出 cache。
空间局部性：大块预取。
写优化#
写回
命中率#
表示 cache 完成存取访问的总次数
表示主存完成存取访问的总次数
平均访问时间#
表示命中 cache 存储器时的访问时间
表示命中主存储器时的访问时间
存储访问时间#
虚拟内存#
指令系统#
指令数量计算#
![[17 逻辑与计算机系统设计基础-第七章 指令集架构(一)-cnwang-rev.pdf#page=21]]
寻址模式#
![[17 逻辑与计算机系统设计基础-第七章 指令集架构(一)-cnwang-rev.pdf#page=24]]
操作数寻址#
- 立即数寻址 ：变量赋初值
MOV AX, 200H- 寄存器寻址
MOV AX, BX- 内存直接寻址：直接访问内存
MOV AX, [200H]-
内存间接寻址
-
寄存器间接寻址
-
基址寻址
-
变址寻址 ：数组访问
MIPS寻址模式#
寄存器寻址
变址寻址
立即数寻址
PC相对寻址