04_数据校验码

1.差错和纠错

1.1故障的分类

• 硬故障（hard failure）：永久性的物理故障
• 软故障（soft error）：随机非破坏性事件

1.2纠错

• 基本思想
  • 大多数数据校验方式都基于冗余校验，，即除了原数据的信息外还增加额外若干位的编码校验位
• 处理过程
  • 数据输入：使用函数在位数据上生成位校验码
  • 数据输出：使用函数在位数据上生成新的位代码，并与取出的位码进行比较
    • 没有检测到差错：使用数据
    • 检测到差错且可以校正：校正数据来生成数据，并用数据
    • 检测到差错但无法纠正：报告

2.奇偶校验码

• 基本思想
  • 利用了异或运算的性质（消除，相同异或为0，不同异或为1）
  • 增加1位校验码来表示数据中1的数量是奇数还是偶数
  • 偶校验直接对数据按位做异或，奇校验的最后多异或一个1
• 运算过程
  • 在源部件计算出奇（偶）校验位
  • 在目标部件计算出奇（偶）校验位
  • 计算最终校验位，结果为1则奇数个位置出错，结果为0则正确或偶数个位置错
• 优点
  • 代价低，只要1位额外数据
  • 计算简单
• 缺点
  • 不能发现出错位数为偶数的情形
  • 无法纠错
• 应用
  • 存储器读写检查或按字节传输过程中的数据校验，因为一字节长的数据中一位出错的概率远大于两位以上出错。

3.海明码

• 基本思想
  • 将数据分组，对每一组都使用奇偶校验码进行检错
  • 数据位和校验位按某种排列方式一起存储成位的码字
• 处理过程
• 校验码长度确定
  • 假设最多1位发生错误
  • 可能的差错
    • 数据中有1位出现错误：M
    • 校验码中有1位出现错误：K
    • 没有出现错误：1
  • 校验码长度
• 故障字的规则
• 码字排列方式/分组方式
  • 数据，校验位
  • 位设置在与其故障字值相同的位置()
  • 每个数据位至少要参与两组奇偶校验
    紫书排列方式从左往右，PPT排列方式从右往左，但不影响
    
    
• 校验位计算
  

4.循环冗余校验

模2除法->异或
模2除法它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可

在网络通信中，数据的位数较大，通常只用循环冗余校验检查错误直接要求对方重发，不用循环冗余校验码来纠错。