差错

  • 数据在计算机内部进行计算、存取和传送过程中, 由于元器件故障或噪音干扰等原因, 会出现差错

  • 以存储为例

    • 硬故障: 永久性的物理故障, 以至于受影响的存储单元不能可靠地存储数据, 成为固定的"1"或"0"故障, 或者在0和1之间不稳定地跳变
      • 由于恶劣的环境, 制造缺陷和旧损引起
    • 软故障: 随机非破坏性事件, 它改变了某个或某些存储单元的内容, 但没有损坏机器
      • 由电源问题或α粒子引起

  • 解决方案

    • 从计算机硬件可靠性入手, 在电路, 电源, 布线等方面采取必要的措施, 提高计算机的抗干扰能力

    • 采取数据检错和校正措施, 自动发现并纠正错误

      image-20250119221011640

纠错

  • 基本思想

    • 存储额外的信息以进行检错和校正

  • 处理过程

    image-20250119221018071

    image-20250119221023658

奇偶校验码

  • 基本思想

    • 增加1位校验码来表示数据中1的数量是奇数还是偶数
      • 奇校验: 使传输的数据(数据位+校验位)中有奇数个1
      • 偶校验: 使传输的数据(数据位+校验位)中有偶数个1

  • 处理过程

    image-20250119221028102

    image-20250119221034730

  • 优点

    • 代价低(只需要1位额外数据, 计算简单)

  • 缺点

    • 不能发现出错位数为偶数的情形
    • 发现错误后不能校正

  • 适用于对较短长度(如1字节)的数据进行检错

海明码

  • 基本思想

    • 将数据分成几组, 对每一组都使用奇偶校验码进行检错

  • 处理过程

    image-20250119221039071

  • 校验码长度

    • 假设最多1位发生错误
    • 可能的差错
      • 数据中有1位出现错误: M
      • 校验码中有1位出现错误: K
      • 没有出现错误: 1
    • 校验码的长度
      • 2K ≥ M + K + 1
      • 根据M求出最小的K

  • 故障字的作用

    • 每种取值都反映一种情形 (数据出错/校验码出错/未出错)
    • 规则
      • 全都是0: 没有检测到错误
      • 有且仅有1位是1: 错误发生在校验码中的某一位, 不需要纠正
      • 有多位为1: 错误发生在数据中的某一位, 将**D’**中对应数据位取反即可纠正

  • 数据位划分

    image-20250119221044726

  • 位安排

    • 将位设置在与其故障字值相同的位置

      image-20250119221049536

示例

image-20250119221054769

image-20250119221101969

码距和纠错位数

image-20250119221106325

补充: SEC-DED

image-20250119221111495

image-20250119221117214

循环冗余校验

  • 奇偶校验问题

    • 额外成本很大
    • 要求将数据分成字节

  • 循环冗余校验(Cyclic Redundancy Check, CRC)

    • 适用于以流格式存储和传输大量数据
    • 用数学函数生成数据和校验码之间的关系

  • 基本思想

    • 假设数据有M位, 左移数据K位(右侧补0), 并用K+1位生成多项式除它(模2运算)
    • 采用K位余数作为校验码
    • 把校验码放在数据(不含补的0)后面, 一同存储或传输

  • 校错

    • 如果M+K位内容可以被生成多项式除尽, 则没有检测到错误
    • 否则, 发生错误

示例

image-20250119221124842