计算机组织结构(八) 纠错

📚 文档目录 合集-数的二进制表示-定点运算-BCD 码-浮点数四则运算-内置存储器-Cache-外存-纠错-RAID-内存管理-总线-指令集: 特征- 指令集:寻址方式和指令格式

基本思想

• 方法： 添加一些位来存储附加信息以便校正
• 过程： 读入:M 位的数据 D 通过函数 f 产生 K 位的校验码 C 被读出:通过 f 由D’ 生成 C’’与 C’ 相比较 无错误: 发送 D’ 有错误并可以纠正,发送 D’’ 有错误且不能纠正, 报告

奇偶校验法

• 过程D=D_M…D_2D_1 奇校验: D_M \oplus …D_2 \oplus D_1 \oplus 1 偶校验: D_M \oplus …D_2 \oplus D_1 检查 S=C’ \oplus C’’ S=1 错误的位数为奇数 S=0 错误的位数为偶数或者无错误 注意: 此处是指C与D合在一起
• 优势:
  • 廉价
• 劣势:
  • 无法确定出错的位置
  • 无法纠正错误
• 适用于较短的 D

汉明码

• 基本思想:
  • 将数据的位分组, 每位都分到多个组且分到的组的情况不同, 每个组中奇偶校验产生一位校验码, 最后根据所有组的校验码可以定位到这位数据
  • 前提:仅有一位出错
• 具体过程: 将 M 位数据 D 分成 K 组 每个组中产生一位奇偶校验码, 最终产生一位K 位的校验码 C’ 由 D’ 产生 C’’ 检查: 故障字 SW=C’\oplus C’’, 长度为 K 位
• 校验码的长度 要确保故障字的情况能够包含所有的情况在内.即2^K\geq 1+ M+K其中 K 为校验码出错情况,M 为数据出错情况, 1 未出错情况
• 故障字分析: 如果是数据位出错,那么至少有两位校验码会出错, 即故障字至少有两位为1,可得下面规则 全为0 : 没有错误 只有一位为 1: 校验码 C’ 出错,无需纠正 多位为 1: 数据位出错,需要纠正(对相应位置的数据取反)
• 数据位划分 以 8 位的数据 D = D_8…D_2D_1为例子，校验码C_1C_2C_3C_4

关系如下

据在传输的时候也正是这样穿插进行的 数据位划分

循环冗余校验 (CRC)

• 奇偶校验问题:
  • 需要将数据 划分为字节级
  • 额外开销很大
• CRC 适用于以流形式存储和传输大型数据
• 用数学函数产生数据和校验码的关系
• 过程: 对于 n 位的数据 D, 次数为 K 的生成多项式(用二进制表示的话有 K+1 位),需要将 D 左移 K 位. 进行模二取余的除法运算
• 检查: 将 n+k 位的内容对生成多项式做上述操作,如果无误,所得结果为0