1
0
0
【中软设】2.4 计算机组成与体系结构-算术逻辑运算、校验码
## 1. 算术逻辑运算
### 1.1 解题思路：抓住短路求值
这一类题考的核心是逻辑运算的**短路求值**：
- 逻辑与 `&&`：左边为假，整体必为假，右边不再计算；
- 逻辑或 `||`：左边为真，整体必为真，右边不再计算。
短路的真正“杀伤力”在于：**被短路的一侧根本不执行，赋值、自增这类副作用也随之消失**，命题人最爱把陷阱埋在这里。
```mermaid
flowchart TD
A["从左往右求值：先算左边"] --> B{"看运算符类型"}
B -->|"&& 且左边为假"| C["整体 = 假
右边被短路，不执行"] B -->|"|| 且左边为真"| D["整体 = 真
右边被短路，不执行"]xyz B -->|"未触发短路"| E["继续求值右边
再决定整体结果"] ``` ### 1.2 运算符优先级：先归组，再短路  短路是从左往右发生的，但“谁和谁一组”由优先级决定：**`!` > 算术运算 > 关系运算 > `&&` > `||`**。例如 `a || b && c` 应归组为 `a || (b && c)`，而不是 `(a || b) && c`——归组一错，短路的位置就错。**做题口诀：先按优先级归组，再从左往右短路。** ### 1.3 例题解析  答案为 B。`a` 为 `true` 时，`||` 左边为真即可锁定结果，右边的赋值、自增根本不会执行。做题先看短路能否提前“锁定”结果，别把每个变量老老实实全算一遍。 ## 2. 校验码 数据在传输、存储过程中可能因干扰出错。校验码的思路是：在有效信息位之外附加若干**冗余位**，发送方按规则编码，接收方按同一规则检验，从而**检错**，甚至定位并改正错误（**纠错**）。 三种常考校验码的能力是一条递进链： ```mermaid flowchart LR A["只报'对/错'
（奇偶校验）"] --> B["必能查出错
（CRC）"] --> C["能定位错在哪一位
（海明码）"] --> D["能把错改回来
（海明码纠错）"] ``` ### 2.1 奇偶校验码 无论数据多少位，都只附加 1 位校验位，使整个码字中 **1 的个数为奇数（奇校验）或偶数（偶校验）**。 它只回答“是/否”：不关心具体哪一位出错，因此无法纠错；且若同时有**偶数个位**出错，奇偶性不变，错误会漏检。所以严格地说，**奇偶校验只能检测出奇数个位的错误**。  答案为 C。奇偶校验开销最小（仅 1 位冗余），但能力也最弱：只能报“出错/没错”，不能定位，更不能纠错。 ### 2.2 CRC 循环冗余校验 CRC 检错能力极强：只要生成多项式选取得当，所有 1 位、2 位错误，所有奇数个位的错误，以及不超过一定长度的突发错误都能检出；但不可纠错，接收方发现错误后只能要求重传。可以把它理解为“指纹校验”：**生成多项式是收发双方事先约定的固定模子，余数就是数据的指纹**，指纹对得上（余数为 0）即判定无错。 **CRC 就是在原始数据后面追加一串校验码，用来检查传输后数据有没有出错；只能查出错，不能自动修复错误。** #### 2.2.1 计算流程：固定三步走 先记住关键知识点。 > 1. **模 2 除法**：本质就是**异或⊕**，没有借位、没有进位，`1⊕1=0`，`0⊕0=0`，`1⊕0=1`，异或其实就是只看个位数的加法。 > 2. **生成多项式\(G(X)\)** 若 G (X) 最高次是 r 次 → 除数一共`r+1`位，算出来的校验余数（校验位）是**r 位**。 ```mermaid flowchart TD A["k 位信息码"] -->|"① 末尾补 r 个 0"| B["待除序列"] B -->|"② 模 2 除法（按位异或）"| C["得到 r 位余数"] C -->|"③ 余数替换补的 0"| D["CRC 码字"] D --> E["接收方：用同一生成多项式再除一次"] E --> F{"余数是否为 0"} F -->|"是"| G["判定无错"] F -->|"否"| H["判定出错
要求重传"] ```   以上图为例，**题目：数据位 `10110011`，生成多项式 \(G(x)=x^4+x^3+1\)，求 CRC 余数（校验码）。** **第一步：把多项式变成二进制除数。** \(G(x)=x^4+x^3+1\) 展开：\(\boldsymbol{1\cdot x^4 +1\cdot x^3 +0\cdot x^2 +0\cdot x^1 +1\cdot x^0}\) - \(x^4\)系数 = 1 - \(x^3\)系数 = 1 - \(x^2\)系数 = 0 - \(x^1\)系数 = 0 - \(x^0\)系数 = 1 从高次到低次写系数：**1 1 0 0 1** → 除数 = `11001` 多项式最高次数是 4 次 → 要补 **4 个 0**，最后余数（校验位）一定是 4 位。 ** 第二步：原始数据后面补 4 个 0** 原始数据：`10110011` 后面追加 4 个 0：\(\boldsymbol{10110011\ 0000}\) > > 这就是竖式里面被除数。 ** 第三步：什么叫【模 2 除法】⭐重点** 普通十进制除法要借位、减法。 **模 2 除法没有减法！只用异或 ⊕：相同得 0，不同得 1** 模 2 除法 = 对齐最高位，做异或，**不借位、不进位**！ > 1⊕1=0 > 0⊕0=0 > 1⊕0=1 > 0⊕1=1 被除数：`10110011 0000` 除数：`11001` 规则：看当前被除数最高位，如果是`1`，就拿除数`11001`和它对齐做异或；最高位是`0`，就拿`00000`异或。 1. 取被除数前 5 位：`10110`，最高位是 1，异或除数`11001` `10110 ⊕ 11001 = 01111` 把下一位数字落下来 → `11110` 3. `11110`最高位 = 1，异或`11001` `11110 ⊕ 11001 = 00111` 落下下一位 → `11111` 5. `11111`最高位 = 1，异或`11001` `11111 ⊕ 11001 = 00110` 落下下一位 → `11000` 7. `11000`最高位 = 1，异或`11001` `11000 ⊕ 11001 = 00001` 继续把后面剩下的位往下挪，**算到最后剩下 4 位** ✅最后余数：\(\boldsymbol{0100}\)（4 位，正好等于多项式最高次数 4） > > 这个`0100`就是 CRC 校验码！ ** 第四步：真正要发送的完整数据** 原来我们补的是 4 个`0000`，现在把这 4 个 0 替换成余数`0100` 发送出去的帧 = **原始数据 + 余数** `10110011` + `0100` → \(\boldsymbol{101100110100}\) **接收方做什么？** 接收方收到完整串`101100110100`，拿同样除数`11001`再做一遍模 2 除法。 - 如果余数 = `0000` → 传输没问题 - 如果余数≠0 → 传输出错，要求重传 #### 2.2.2 例题解析  答案为 D。按“补 0 → 模 2 除 → 替换余数”三步走即可，细心别漏位。 ### 2.3 海明码  海明码是奇偶校验的升级版：插入**多位**校验位，不但能发现错误，还能定位到具体哪一位出错，把该位取反即完成纠错——“**检一位错、纠一位错**”。 #### 2.3.1 关键公式：先定校验位个数 设信息位 m 位、校验位 r 位，必须满足： **`2^r ≥ m + r + 1`** 即 r 位校验位要能表示“哪一位出错 + 全对”共 m + r + 1 种状态。 #### 2.3.2 校验位的位置与分工 校验位固定放在 `2^0`、`2^1`、`2^2`…（即第 1、2、4、8…）位置上，分别负责校验那些**二进制编号中对应位为 1** 的数据位（位置从 1 开始编号）： | 校验位 | 所在位置 | 负责校验的位置 | | --- | --- | --- | | P1 | 第 1 位（2^0） | 1、3、5、7、9…（编号二进制末位为 1） | | P2 | 第 2 位（2^1） | 2、3、6、7、10、11…（编号二进制倒数第 2 位为 1） | | P4 | 第 4 位（2^2） | 4、5、6、7、12…（编号二进制倒数第 3 位为 1） | 每个位置被覆盖的校验位组合恰好等于它的二进制编号，因此定位唯一。接收方对每组重新做奇（偶）校验，把各组“对/错”标志按 P1、P2、P4… 顺序拼成二进制数（**校验子**）：**全 0 表示无错，非 0 时其数值就是出错位置的编号**，取反即纠错。 #### 2.3.3 做题套路 ```mermaid flowchart TD A["信息位 m 位"] --> B["① 公式 2^r ≥ m + r + 1 定出 r"] B --> C["② 校验位放入第 1、2、4、8… 位
其余位置依序填信息位"] C --> D["③ 逐组做奇/偶校验
求出各校验位取值"] D --> E["接收方：各组重新校验
结果拼成校验子"] E --> F{"校验子为 0 ?"} F -->|"是"| G["无错"] F -->|"否"| H["校验子的值 = 出错位编号
该位取反即纠错"] ``` 注意易混点：**标准海明码（码距 3）只能纠一位错**；要“纠一位同时检两位”需码距为 4 的扩展海明码。（检 d 位错需码距 ≥ d + 1，纠 d 位错需码距 ≥ 2d + 1。）   后两题答案分别为 D、B。 # 海明码公式：\(\boldsymbol{2^r \ge m + r +1}\) - m：**数据位位数** - r：**校验位位数** ## 第一题：m=32，求最小 r 代入试算： - r=5：\(2^5=32\)，\(m+r+1=32+5+1=38\) \(32 \ge 38\) ❌不成立 - r=6：\(2^6=64\)，\(m+r+1=32+6+1=39\) \(64 \ge 39\) ✔成立 所以 r=6。 ## 第二题 位序号拆成 2 的幂之和： D₅位序 = 10，\(10 = 8+2\) \(8=2^3\)对应\(P_4\)，\(2=2^1\)对应\(P_2\)，即\(\boldsymbol{P_4P_2}\)。 ### 2.4 三种校验码对比 | 校验码 | 冗余开销 | 检错能力 | 纠错能力 | | --- | --- | --- | --- | | 奇偶校验 | 1 位 | 只能检奇数个位错 | 无 | | CRC | r 位（由生成多项式决定） | 极强，可检任意数的错误 | 无，出错重传 | | 海明码 | r 位（满足 `2^r ≥ m + r + 1`） | 可发现两位错 | 可纠一位错 | 一句话记忆：**奇偶校验“知错不知哪错”，CRC“知错不纠错”，海明码“知错还能纠一位错”**。
右边被短路，不执行"] B -->|"|| 且左边为真"| D["整体 = 真
右边被短路，不执行"]xyz B -->|"未触发短路"| E["继续求值右边
再决定整体结果"] ``` ### 1.2 运算符优先级：先归组，再短路  短路是从左往右发生的，但“谁和谁一组”由优先级决定：**`!` > 算术运算 > 关系运算 > `&&` > `||`**。例如 `a || b && c` 应归组为 `a || (b && c)`，而不是 `(a || b) && c`——归组一错，短路的位置就错。**做题口诀：先按优先级归组，再从左往右短路。** ### 1.3 例题解析  答案为 B。`a` 为 `true` 时，`||` 左边为真即可锁定结果，右边的赋值、自增根本不会执行。做题先看短路能否提前“锁定”结果，别把每个变量老老实实全算一遍。 ## 2. 校验码 数据在传输、存储过程中可能因干扰出错。校验码的思路是：在有效信息位之外附加若干**冗余位**，发送方按规则编码，接收方按同一规则检验，从而**检错**，甚至定位并改正错误（**纠错**）。 三种常考校验码的能力是一条递进链： ```mermaid flowchart LR A["只报'对/错'
（奇偶校验）"] --> B["必能查出错
（CRC）"] --> C["能定位错在哪一位
（海明码）"] --> D["能把错改回来
（海明码纠错）"] ``` ### 2.1 奇偶校验码 无论数据多少位，都只附加 1 位校验位，使整个码字中 **1 的个数为奇数（奇校验）或偶数（偶校验）**。 它只回答“是/否”：不关心具体哪一位出错，因此无法纠错；且若同时有**偶数个位**出错，奇偶性不变，错误会漏检。所以严格地说，**奇偶校验只能检测出奇数个位的错误**。  答案为 C。奇偶校验开销最小（仅 1 位冗余），但能力也最弱：只能报“出错/没错”，不能定位，更不能纠错。 ### 2.2 CRC 循环冗余校验 CRC 检错能力极强：只要生成多项式选取得当，所有 1 位、2 位错误，所有奇数个位的错误，以及不超过一定长度的突发错误都能检出；但不可纠错，接收方发现错误后只能要求重传。可以把它理解为“指纹校验”：**生成多项式是收发双方事先约定的固定模子，余数就是数据的指纹**，指纹对得上（余数为 0）即判定无错。 **CRC 就是在原始数据后面追加一串校验码，用来检查传输后数据有没有出错；只能查出错，不能自动修复错误。** #### 2.2.1 计算流程：固定三步走 先记住关键知识点。 > 1. **模 2 除法**：本质就是**异或⊕**，没有借位、没有进位，`1⊕1=0`，`0⊕0=0`，`1⊕0=1`，异或其实就是只看个位数的加法。 > 2. **生成多项式\(G(X)\)** 若 G (X) 最高次是 r 次 → 除数一共`r+1`位，算出来的校验余数（校验位）是**r 位**。 ```mermaid flowchart TD A["k 位信息码"] -->|"① 末尾补 r 个 0"| B["待除序列"] B -->|"② 模 2 除法（按位异或）"| C["得到 r 位余数"] C -->|"③ 余数替换补的 0"| D["CRC 码字"] D --> E["接收方：用同一生成多项式再除一次"] E --> F{"余数是否为 0"} F -->|"是"| G["判定无错"] F -->|"否"| H["判定出错
要求重传"] ```   以上图为例，**题目：数据位 `10110011`，生成多项式 \(G(x)=x^4+x^3+1\)，求 CRC 余数（校验码）。** **第一步：把多项式变成二进制除数。** \(G(x)=x^4+x^3+1\) 展开：\(\boldsymbol{1\cdot x^4 +1\cdot x^3 +0\cdot x^2 +0\cdot x^1 +1\cdot x^0}\) - \(x^4\)系数 = 1 - \(x^3\)系数 = 1 - \(x^2\)系数 = 0 - \(x^1\)系数 = 0 - \(x^0\)系数 = 1 从高次到低次写系数：**1 1 0 0 1** → 除数 = `11001` 多项式最高次数是 4 次 → 要补 **4 个 0**，最后余数（校验位）一定是 4 位。 ** 第二步：原始数据后面补 4 个 0** 原始数据：`10110011` 后面追加 4 个 0：\(\boldsymbol{10110011\ 0000}\) > > 这就是竖式里面被除数。 ** 第三步：什么叫【模 2 除法】⭐重点** 普通十进制除法要借位、减法。 **模 2 除法没有减法！只用异或 ⊕：相同得 0，不同得 1** 模 2 除法 = 对齐最高位，做异或，**不借位、不进位**！ > 1⊕1=0 > 0⊕0=0 > 1⊕0=1 > 0⊕1=1 被除数：`10110011 0000` 除数：`11001` 规则：看当前被除数最高位，如果是`1`，就拿除数`11001`和它对齐做异或；最高位是`0`，就拿`00000`异或。 1. 取被除数前 5 位：`10110`，最高位是 1，异或除数`11001` `10110 ⊕ 11001 = 01111` 把下一位数字落下来 → `11110` 3. `11110`最高位 = 1，异或`11001` `11110 ⊕ 11001 = 00111` 落下下一位 → `11111` 5. `11111`最高位 = 1，异或`11001` `11111 ⊕ 11001 = 00110` 落下下一位 → `11000` 7. `11000`最高位 = 1，异或`11001` `11000 ⊕ 11001 = 00001` 继续把后面剩下的位往下挪，**算到最后剩下 4 位** ✅最后余数：\(\boldsymbol{0100}\)（4 位，正好等于多项式最高次数 4） > > 这个`0100`就是 CRC 校验码！ ** 第四步：真正要发送的完整数据** 原来我们补的是 4 个`0000`，现在把这 4 个 0 替换成余数`0100` 发送出去的帧 = **原始数据 + 余数** `10110011` + `0100` → \(\boldsymbol{101100110100}\) **接收方做什么？** 接收方收到完整串`101100110100`，拿同样除数`11001`再做一遍模 2 除法。 - 如果余数 = `0000` → 传输没问题 - 如果余数≠0 → 传输出错，要求重传 #### 2.2.2 例题解析  答案为 D。按“补 0 → 模 2 除 → 替换余数”三步走即可，细心别漏位。 ### 2.3 海明码  海明码是奇偶校验的升级版：插入**多位**校验位，不但能发现错误，还能定位到具体哪一位出错，把该位取反即完成纠错——“**检一位错、纠一位错**”。 #### 2.3.1 关键公式：先定校验位个数 设信息位 m 位、校验位 r 位，必须满足： **`2^r ≥ m + r + 1`** 即 r 位校验位要能表示“哪一位出错 + 全对”共 m + r + 1 种状态。 #### 2.3.2 校验位的位置与分工 校验位固定放在 `2^0`、`2^1`、`2^2`…（即第 1、2、4、8…）位置上，分别负责校验那些**二进制编号中对应位为 1** 的数据位（位置从 1 开始编号）： | 校验位 | 所在位置 | 负责校验的位置 | | --- | --- | --- | | P1 | 第 1 位（2^0） | 1、3、5、7、9…（编号二进制末位为 1） | | P2 | 第 2 位（2^1） | 2、3、6、7、10、11…（编号二进制倒数第 2 位为 1） | | P4 | 第 4 位（2^2） | 4、5、6、7、12…（编号二进制倒数第 3 位为 1） | 每个位置被覆盖的校验位组合恰好等于它的二进制编号，因此定位唯一。接收方对每组重新做奇（偶）校验，把各组“对/错”标志按 P1、P2、P4… 顺序拼成二进制数（**校验子**）：**全 0 表示无错，非 0 时其数值就是出错位置的编号**，取反即纠错。 #### 2.3.3 做题套路 ```mermaid flowchart TD A["信息位 m 位"] --> B["① 公式 2^r ≥ m + r + 1 定出 r"] B --> C["② 校验位放入第 1、2、4、8… 位
其余位置依序填信息位"] C --> D["③ 逐组做奇/偶校验
求出各校验位取值"] D --> E["接收方：各组重新校验
结果拼成校验子"] E --> F{"校验子为 0 ?"} F -->|"是"| G["无错"] F -->|"否"| H["校验子的值 = 出错位编号
该位取反即纠错"] ``` 注意易混点：**标准海明码（码距 3）只能纠一位错**；要“纠一位同时检两位”需码距为 4 的扩展海明码。（检 d 位错需码距 ≥ d + 1，纠 d 位错需码距 ≥ 2d + 1。）   后两题答案分别为 D、B。 # 海明码公式：\(\boldsymbol{2^r \ge m + r +1}\) - m：**数据位位数** - r：**校验位位数** ## 第一题：m=32，求最小 r 代入试算： - r=5：\(2^5=32\)，\(m+r+1=32+5+1=38\) \(32 \ge 38\) ❌不成立 - r=6：\(2^6=64\)，\(m+r+1=32+6+1=39\) \(64 \ge 39\) ✔成立 所以 r=6。 ## 第二题 位序号拆成 2 的幂之和： D₅位序 = 10，\(10 = 8+2\) \(8=2^3\)对应\(P_4\)，\(2=2^1\)对应\(P_2\)，即\(\boldsymbol{P_4P_2}\)。 ### 2.4 三种校验码对比 | 校验码 | 冗余开销 | 检错能力 | 纠错能力 | | --- | --- | --- | --- | | 奇偶校验 | 1 位 | 只能检奇数个位错 | 无 | | CRC | r 位（由生成多项式决定） | 极强，可检任意数的错误 | 无，出错重传 | | 海明码 | r 位（满足 `2^r ≥ m + r + 1`） | 可发现两位错 | 可纠一位错 | 一句话记忆：**奇偶校验“知错不知哪错”，CRC“知错不纠错”，海明码“知错还能纠一位错”**。