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

📚 文档目录
合集-数的二进制表示-定点运算-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$
  • 关系如下
    
    数据在传输的时候也正是这样穿插进行的
  • 数据位划分 $$\begin{aligned} C_{1}=D_{1} \oplus D_{2} \oplus D_{4} \oplus D_{5} \oplus D_{7} \\ C_{2}=D_{1} \oplus D_{3} \oplus D_{4} \oplus D_{6} \oplus D_{7} \\ C_{3}=D_{2} \oplus D_{3} \oplus D_{4} \oplus D_{8} \\ C_{4}=D_{5} \oplus D_{6} \oplus D_{7} \oplus D_{8} \end{aligned}$$

循环冗余校验 (CRC)

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