【系统架构设计师】计算机组成与体系结构 ⑯ ( 奇偶校验码 | CRC 循环冗余码 | 海明码 | 模 2 除法 )

参考之前的博客 :

• 【计算机网络】数据链路层 : 差错控制 ( 检错编码 | 奇偶校验码 | CRC 循环冗余码 )★
• 【计算机网络】数据链路层 : 差错控制 ( 纠错编码 | 海明码 | “海明码“ 原理 | “海明码“ 工作流程 | 确定校验啊位数 | 确定校验码和数据位置 | 求校验码值 | 检错纠错 )★

一、校验码

---

1、校验码由来

计算机 数据 传输时 , 数据 可能会因为 电磁干扰、硬件故障等原因 出现 1 变 0 或 0 变 1 的错误 ;

校验码 可以 通过 增加冗余信息 来 检测和纠正 数据传输 过程中的 错误 , 可 提高数据传输的可靠性 , 确保数据的 完整性和准确性 ;

常用的校验码有 :

• 奇偶校验码
• CRC 循环冗余码
• 海明码

2、奇偶校验码

奇偶校验码 是在 数据的有效信息 之外 , 追加一位 , 组成校验码 ;

• 奇校验 : 1 的个数为 奇数 , 追加的 冗余校验码位为 1 ;
• 偶校验 : 1 的个数为 偶数 , 追加的 冗余校验码位为 0 ;

如果 正好有 2 位出现了错误 ,

• 两个 1 变成了 0 ,
• 两个 0 变成了 1 ,
• 一个 1 变成了 0 , 一个 0 变成了 1 ,

就无法检查出错误 ; 同理 , 如果有 4 位出现了错误 , 也无法检查出来 ;

奇偶校验码 只能检查 奇数个 比特错误 , 如果有 偶数个比特错误 , 无法检查出来 , 检错率是 50 % ;

奇偶校验码 只能检查错误 , 不能纠错 ;

• 纠错的前提是知道错误位置 , 将其取反即可 , 找不到错误位置 , 就无法进行纠错 ;

3、CRC 循环冗余码 ( 重点考点 )

CRC 循环冗余码 是 基于模 2 运算的校验码 , 通过将 数据 视为一个 多项式 并使用除法运算生成校验码 ;

CRC 循环冗余码 能够 检测错误 , 但是不能进行纠错 ;

CRC 循环冗余码 会在 信息位 之后 拼接 多位校验位 , 不是 奇偶校验码 的 一位 , 增加的冗余校验位增加 , 相对发现错误的几率也会更大 ;

CRC 循环冗余码 在 k 位信息后 , 拼接 r 位 校验码 , 这里涉及到两个问题 :

• 发送端 : 根据 k 位信息 , 计算出 r 位 校验码 ;
• 接收端 : 根据 k + r 位的信息 , 检验数据是否正确 ;

具体参考 【计算机网络】数据链路层 : 差错控制 ( 检错编码 | 奇偶校验码 | CRC 循环冗余码 )★ 博客中的内容 ;

4、海明码校验 ( 软考不经常考到 )

海明码校验 的 原理 是 通过 交叉校验的方式 , 形成了多组不同的 奇偶校验 ;

海明码 在 2 的幂次方的位置 插入校验位来工作 , 即位置1, 2, 4, 8, 16等 , 校验位的数量 取决于需要编码的数据位的数量 ;

校验位的数量 p 满足以下不等式 :

$$2^p\ge n+p+1$$

• p 是校验位数量 ;
• n 是原始数据的位数 ;

具体的案例 , 参考 【计算机网络】数据链路层 : 差错控制 ( 纠错编码 | 海明码 | “海明码“ 原理 | “海明码“ 工作流程 | 确定校验啊位数 | 确定校验码和数据位置 | 求校验码值 | 检错纠错 )★ 博客 ;

在架构师考试时 , 该知识点不经常考到 , 掌握校验位个数的公式即可 ;

二、CRC 循环冗余码 ( 重点考点 )

---

1、模 2 除法概念

" 模 2 除法 " , 又称为 " 二进制除法 " 或 " 模 2 运算中的除法 " ;

" 模 2 除法 " 是一种 在 二进制数 系统 中执行的除法运算 , 与普通的 十进制除法 不同 , 模 2 除法中的所有运算都是基于 二进制 进行 ;

" 模 2 除法 " 在 除法运算过程中 , 不进行 借位 , 直接得到 借位 后的结果 ;

" 模 2 除法 " 在 计算过程中 , 每一步的 结果 与 " 异或运算 " 的结果是一样的 , " 异或运算 " 是 二者相同 则为假 , 二者不同则为真 ;

2、模 2 除法步骤

" 模 2 除法 " 步骤 :

• 设置 被除数 和 除数 : 设置 两个 二进制数 , 一个作为 被除数 , 另一个作为除数 ;
• 模 2 除法过程 ( 异或运算 ) :
  • 从 被除数 的最高位开始 , 将其与 除数 进行比较 ;
    • 这里每一位都按照 " 异或运算 " , 进行计算 ;
  • 重复上述步骤 , 直到处理完被除数的所有位 ;
• 得到商和余数 : 完成上述步骤后 , 得到一个二进制数作为商 , 以及一个二进制数作为余数 , 余数就是 校验位 ;

3、模 2 除法示例

下面的运算就是一个 模 2 除法 :

第一步计算中 ,

• 红色矩形框 中 1 减去 0 , 得 1 是正常的 ,
• 蓝色矩形框 中 0 减去 1 , 按照普通除法来算的话 , 需要向前借一位 , 但是此时不进行借位 , 仍然得到结果 1 ;
• 绿色矩形框 中 , 1 减去 1 , 得到的结果是 0 ;

异或运算 规律 :

• 可以看到上述结果 不管是 1 和 0 还是 0 和 1 最终得到的结果都是 1 ;
• 但是 如果 上下两位 都是 1 或者 都是 0 , 最终得到的结果就是 0 ;
• 上述规律得到的结果与 异或运算 是相同的 ;

第二步中 ,

• 红色矩形框 中 1 与 0 进行 异或运算 , 得到的结果是 1 ;
• 蓝色矩形框 中 1 与 1 进行 异或运算 , 得到的结果是 0 ;

最终得到 011 , 小于 110 , 011 就是余数 , 商为 110 ;

4、CRC 循环冗余码示例 1

【计算机网络】数据链路层 : 差错控制 ( 检错编码 | 奇偶校验码 | CRC 循环冗余码 )★ 博客中也有一个 CRC 编码示例 , 可结合参考 ;

原始报文是 10111 , 生成多项式为 $G(x)=x^4+x+1$ , 计算编码后的发送数据 ;

生成多项式 是 发送方 和 接收方 约定好的 ;

计算 帧检验序列 FCS :

① 数据加 冗余码 位数个 $0$ : 首先确定 冗余码 位数 , 冗余码的位数是 生成多项式的 阶 加上 1 , 即 生成多项式 的 总位数 减去 $1$ , 相当于 离散数学 中的生成函数的 最高位次幂 ; FCS 的位数是 $4$ 位 ;

生成多项式 是 $N$ 位 , 那么阶 就是 $N-1$ 位 , FCS 帧检验序列就是 $N-1$ 位 ;

生成多项式为 $G(x)=x^4+x+1$ , 阶为 4 , FCS 帧检验序列是 4 位 , 其二进制形式有 5 位 ;

10111 数据加 $4$ 个 $0$ 后为 $101110000$ ;

② 生成多项式 转为二进制 :

$G(x)=x^4+x+1$

将空位补齐后为 :

$G(x)=1x^4+0x^3+0x^2+1x^1+1x^0$

将生成多项式转为二进制形式后为 : $10011$ ;

② 模 $2$ 除法 : 数据 加上 $0$ 后 , 除以 生成多项式 , 余数就是 FCS 帧检验序列 ;

二进制除法 , 与十进制除法不同的是 , 每个除法相除的计算是 异或操作 ;

异或运算 : 同 $0$ , 异 $1$ ;

模 $2$ 除法计算过程分析 : 被除数 9 位 ( 1 ~ 9 计数 ) , 除数 5 位 ( 1 ~ 5 计数 ) ;

• $10111$ 异或 $10011$ 计算得到 $100$ , 然后第六位 $0$ 落下来 , 得到 $1000$ ;
• $1000$ 位数不足 , 继续第七位 $0$ 落下来 , 得到 $10000$ ;
• $10000$ 异或 $10011$ 计算得到 $11$ , 然后下面第八位 落下来 , 得到 $110$ ;
• $110$ 位数不足 , 继续第九位 $0$ 落下来 , 得到 $1100$ ;

最终的余数是 1100 , 这也是 FSC 帧检验序列 ;

最终计算出来的 帧检验序列 是 $1100$ ;

最终发送的数据是 : $10111$ $1100$

接收端接收数据并校验 :

① 检验过程 : 接收端接收 上述 $10111$ $1100$ 数据 , 将上述数据 与 生成多项式 $10011$ 相除 , 如果余数为 $0$ 说明该数据帧没有差错 ;

② 结果判定 : 如果余数不为 $0$ , 说明数据帧错误 , 而且不知道哪里出现错误 , 丢弃该数据帧 , 重新发送 ;

5、CRC 循环冗余码示例 2

传输数据位 111000110 , 生成多项式为 $G(x)=x^5+x^3+x+1$ , 计算 CRC 循环冗余校验码 ;

生成多项式 是 发送方 和 接收方 约定好的 ;

生成多项式为 $G(x)=x^5+x^3+x+1$ , 补齐后为 :

$G(x)=1x^5+0x^4+1x^3+0x^2+1x^1+1x^0$

得到的二进制形式为 101011 ;

进行模 2 除法 : $111000110÷101011$ , 得到余数 $11001$ ;

余数 $11001$ 就是校验码 ;

最终的发送序列为 : $111000110$ $11001$

• 蓝色为原始数据 ;
• 红色为校验序列 ;